文脈自由文法の並列構文解析アルゴリズムと自然言語解析への応用

点击翻译按钮获取中文摘要

計算機ハードウェアの進歩により超並列マシンが実用化されつつあるが,自然言語処理においては,構文,意味,文脈情報などの知識を用いた複雑な解析により膨大な処理時間が必要となるため,これらの並列マシンを有効に利用する並列処理アルゴリズムの開発は,実用的な処理速度が要求される自然言語自然システムの実現にとって必要不可欠なものとなっている.自然言語文法の基礎となっている文脈自由文法に対して,これまで提案されてきた並列構文解析アルゴリズムには,CYK法に基づくものやLR解析法に基づくものなどがあるが,つい逐次型構文解析法として最も優れた表方式の解析アルゴリズムであるEarley法の並列化は困難であった.本研究課題は,Earley法に基づく文脈自由文法の並列構文解析アルゴリズムの確立と,意味的制約を含んだ自然言語文法に対するその応用の可能性を探ることを目的とし,以下の研究を行った.まず,Earley法で用いる解析表に登録する項目中に解析が未完の状態を表わす“gap"という概念を導入することにより,Earley法に基づく文脈自由文法の並列構文解析アルゴリズムを構成し,その正当性を証明した.また,このアルゴリズムの解析能率として,入力長に対する処理時間,記憶領域,および必要なプロセッサ数との関係を明らかにした.さらにこの並列構文解析アルゴリズムを計算機上に実現し,いくつかの文脈自由文法に対して構文解析実験を行うことなよつて,解析能率の検証を行った.