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

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

基本信息

批准号：
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法に基づく文脈自由文法の並列構文解析アルゴリズムを構成し,その正当性を証明した.また,このアルゴリズムの解析能率として,入力長に対する処理時間,記憶領域,および必要なプロセッサ数との関係を明らかにした.さらにこの並列構文解析アルゴリズムを計算機上に実現し,いくつかの文脈自由文法に対して構文解析実験を行うことなよつて,解析能率の検証を行った.

随着计算机硬件的进步，大量平行的机器正变得越来越实用，但是在自然语言处理，使用语法知识，含义和上下文信息的复杂分析中，需要大量的处理时间。有效利用这些并行机器的并行处理算法的开发对于实现需要实际处理速度的自然语言自然系统是必不可少的。对于自然语言语法的基础的无上下文语法，到目前为止提出的并行分析算法包括基于CYK方法的方法以及基于LR分析方法的算法，但是Earley方法的并行化，但基于桌子的分析算法是顺序类型分析方法最出色的分析算法，这是困难的。该研究主题是进行以下研究的目的，目的是建立基于法律的无上下文语法的平行分析算法，并探索其应用于包含语义约束的自然语言语法的可能性。首先，通过介绍“ GAP”的概念，该概念代表了Earley方法中使用的分析表中注册的项目中不完整的分析状态，我们构建了基于Earley方法的无上下文语法的平行分析算法，并证明了其有效性。此外，我们阐明了处理时间，存储区域与输入长度所需的处理器数量之间的关系，作为该算法的分析效率。此外，我们在计算机上实施了这种并行分析算法，并通过对几种无上下文语法进行句法分析实验来验证分析效率。