本研究の成果は、一般化 LR 法に基づく頑健な構文解析法の提案および、逐次環 境と並列環境に動作する頑健な構文解析システムの実装である。ここで、逐次環 境で動作するシステムは SICSTUS Prolog 言語により記述され、Prologインタプ リタのある計算機環境で動かせる。特に想定している環境は UNIXである。一方、 並列環境で動作するシステムは KL1 (KLIC) 言語で記述され、PIMOS上で利用す ることができる。本研究が提案した構文解析法は与えられた文法や辞書に基づき、 適格文および不適格文を解析できる。対象にする不適格文中の誤りの種類は、単 語の置換誤り、挿入誤り、脱落誤りおよび、句構造の挿入誤り、脱落誤りである。 また、構文的な曖昧性および計算量を抑えるために次のヒューリスティックを用 いた。「通常の解析において途中で解析に失敗した場合、1 箇所の誤り修正処理 を行ない、修正に成功した場合には再び解析を開始し、その後も解析に失敗する ごとに 1 箇所の誤り修正処理を行ないながら、文末に到達するまで解析を行な う。」
一般化 LR 構文解析法は入力文に対して左から右へと解析を行なう性質を持っ ているので、誤り箇所としては、解析に失敗した位置より左の方に存在してい るはずである。その誤り箇所を推定する順序は (1) 解析に失敗した箇所、(2) まだ部分解析木が生成されていない箇所、(3) 二つの部分解析木が隣接して いる箇所、(4) 部分解析木内の箇所、である。また、本手法には以下の特徴が ある。(1) 正しい文に対しては通常の解析を行い、無駄な処理はしない。(2) 誤り発生までに解析した情報を利用可能である。(3)出力結果は修正回数が 必ず最も少ないものだけが得られる。(4) 1 回の誤り修正処理に対して 1 箇 所の誤りの出現を仮定しているヒューリスティックを用いる。
一般的に、不適格文解析では、文法自身の持つ曖昧性に加え、修正した誤りの 種類による曖昧性も組み合わされることになり、不適格文の可能な解釈(構文 木)の数は適格文に比べ非常に多い。これは実用的なシステムを構築する際に は大きな問題となってくる。この問題を対処するために本研究は二つの対策を 行なった。一つは何らかの尺度で解の候補の尤もらしさを計算し、それによっ て解の候補の数を絞り込むことである。もう一つはアルゴリズムを並列化し、 並列環境で不適格文の解析を実用的な時間で行なうことである。
前者に対して、本研究では、誤りの箇所および誤りの種類、誤り箇所の大きさ に基づいたスコアを計算することで、解の候補の尤もらしさとしているが、ユー ザに応じて誤りスコアの尺度を変更することができる。後者に対しては、本研 究は並列環境における構文解析システムを開発した。並列化を行なう際に、ラ ンダム型動的負荷分散および要求駆動型動的負荷分散という二つの負荷分散方 式を提案し実装した。一般化 LR 法において、文を解析する時に曖昧性が生じ た場合、スタックの分岐が行なわれる。各々のスタックを並列に処理すること によって実現した。
また、本システムは、既存の形態素解析器(Tagger)と連結して動作する。入力 文中の各単語に対して、Brill により開発された Tagger を用いて決定的に品 詞を付与した結果、得られる品詞列を入力とし、構文解析結果を出力するプロ グラムとして、頑健な構文解析ツールは動作する。また、本システムの有効性 を評価するために、ATRの英語対話コーパスを用いて予備実験を行なった。そ の結果は後記「予備実験」に示す。
誤り推定およびスコアリング
不適格文を解析する時、通常の解析において途中で解析に失敗した場合、1 箇 所の誤り修正処理を行ない、修正に成功した場合には再び解析を開始し、その 後も解析に失敗するごとに 1 箇所の誤り修正処理を行ないながら、文末に到 達するまで解析を行なう。図 --1 は本研究が提案した誤り推 定の例である。
この例では、9 番目の単語を解析する時に誤りが生じた。その時、4 種類の位置 に誤りが存在していると仮定し、可能なすべての解釈を探索する。解析木のスコ アリングによる順位付けは、誤りの出現位置・誤りの種類によりそれぞれスコア を加算し、その和が最も小さいものから順に選び出す。
誤りの出現位置によるスコア
誤りの出現位置によるスコア 
を以下のように定義する。
ここで、
は、修正された位置 x がその修正範囲
において何番目に選ばれたかを表す。図
--2 に例を示す。
誤りの種類によるスコア
誤りの種類によるスコア 
の計算方法を示す。 は、誤りの種
類と修正した記号の種類にそれぞれ基本値を設け、それらをかけあわせること
で計算する。
・挿入 
・脱落 
のいずれか。
これらの値はあらかじめ与えておく。
Snonterm=(nonterm が覆っている終端記号の数)×
(nonterm から到達できる終端記号で最短の深さ)
非終端記号を挿入する場合は入力から計算できないので、 あらかじめ各非終端記号に対して文法からこれらの値を計算しておき、それを 利用する(図 --3)。
これらを用いて、
ＳT＝Σfor errors S type・S sym
とする。
解析木のスコア
と を足し合わせ、解析木全体のスコア S とする。
Ｓ＝αＳP＋(1-α)ＳT(α は重みで 0-1 に値を持つ。)重み α はあらかじめ設定しておく。
システムの並列化
提案した一般化 LR 頑健な構文解析システムを並列計算機 PIM 上で動作する ように開発した。一般化 LR 構文解析法では、文法の曖昧性により文の解析に 対して複数解釈が得られる場合、スタックの分岐が生じる。それぞれのスタッ クを異るプロセッサ上で処理することによって、並列処理が行なわれる(図 --4)。具体的に最初プロセッサを資源として管理する「プロセッ サマネジャー」を起動しておき、必要に応じてプロセッサを生成されたタスク (各々の分岐したスタック)に割り当てる。
そこで、本研究はプロセッサマネジャーのタスク割当て手法としてランダム型 動的負荷分散および要求駆動型動的負荷分散の 2 負荷分散方式を提案してい る。それぞれは以下の特徴を持つ。
分岐したスタック(タスク)を順番にプロセッサに割り当てる。また、タスク の数がプロセッサの数より多くなった場合は、Round-robin でプロセッサを割 り当てる。
暇になったプロセッサだけにプロセッサマネジャーがタスクを 割り当てる。この方式では、暇になったプロセッサがプロセッサマネジャーに その状況を知らせる必要があるが、プロセッサマネジャーはどのプロセッサが 暇になったかを把握することが可能である。
