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

上下文无关语法并行解析算法及其在自然语言分析中的应用

• 批准号: 05780301
• 负责人: 中村 貞吾
• 金额: $ 0.51万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1993
• 资助国家: 日本
• 起止时间: 1993 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-05780301/
• 关键词: 構文解析; 文脈自由文法; Earley法; 並列

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

The progress of computer science and natural language processing is necessary for the development of parallel processing, such as parallel processing, parallel processing and parallel processing. The actual processing speed is required, so it is necessary and indispensable for the realization of natural speech systems. Natural Speech Grammar (NSG) is based on Context-Free Grammar (CCF), which makes it difficult to paraphrase the Earley method. The purpose of this study is to establish the meaning constraints of the Earley method, and to explore the possibility of using the Earley method in the context free grammar. The Earley method is used to analyze the incomplete state of the entry in the analysis table. The concept of "gap" is introduced. The Earley method is based on the analysis of the parallel structure of the free grammar. For example, the resolution rate of the data is higher than the processing time, the memory area is higher than the necessary number, and the processing time is higher than the input length. The parallel structure analysis is implemented on the computer, and the context-free grammar is implemented on the parallel structure analysis.

项目成果

中村貞吾: "Earleyアルゴリズムの並列化手法" 情報処理学会研究報告NL. 94-NL-101. (1994)

Teigo Nakamura：“Earley 算法的并行化方法”日本信息处理学会研究报告 NL 94-NL-101 (1994)。