文脈自由言語より広い言語に対する構文解析アルゴリズムとシステム開発

本研究では,文脈自由言語より広いクラスの言語に対する新しい構文解析法を考案した.大きく分けて,構文解析法に確率を導入しないで解析できる言語のクラス解析する方式(1.)と,確率を導入して構文解析木の生起確率や情報の抽出をおこなう方式(2.)の二つ手法を提案している.1.文脈自由言語より広い言語の構文解析アルゴリズムの展開文脈自由言語の部分クラスを構文解析する方法としてLR構文解析法が知られているが,そのLR構文解析の拡張として,文法規則の導出のとき,先読み文字列を非終端記号とし,導出する文法規則より右側の非終端記号列を部分木の親とする構文解析法(unrestricted LR(k)構文解析)を提案した.加えて,この構文解析法は,先読み文字列数k>1となるような複数個必要な文法でも,先読み文字をk=1に削減する文法規則の変換法ついて明らかにした.2.確率構文解析アルゴリズムの展開これまで構文解析木の生成確率には,文法規則の生起確率を利用していたが,構文解析木の高さ方向の情報を考慮していない.そのため,必ずしも精密な構文解析木の生起確率が求められてはいなかった.それに対し,本研究では,入力文字のLC親と1つ前の入力時に生成される生成規則の組み合わせを数え上げることによって,入力文字列や部分文字列から得られる構文解析木の生起確率をこれまでよりも精密に求めることができることを示した.日本電子化辞書研究所(EDR)の日本語コーパスを用いて,非文(構文解析木の存在しない入力)の構文解析の生起確率はすべての文で正しい生起確率を求めることができた.また,毎日新聞94年度版を利用して数値情報を抽出して,適合率83.2%,再現率74.8%を得た.

本研究では,文脈自由言語より広いクラスの言語に対する新しい構文解析法を考案した.大きく分けて,構文解析法に確率を導入しないで解析できる言語のクラス解析する方式(1.)と,確率を導入して構文解析木の生起確率や情報の抽出をおこなう方式(2.)の二つ手法を提案している.1.文脈自由言語より広い言語の構文解析アルゴリズムの展開文脈自由言語の部分クラスを構文解析する方法としてLR構文解析法が知られているが,そのLR構文解析の拡張として,文法規則の導出のとき,先読み文字列を非終端記号とし,導出する文法規則より右側の非終端記号列を部分木の親とする構文解析法(unrestricted LR(k)構文解析)を提案した.加えて,この構文解析法は,先読み文字列数k>1となるような複数個必要な文法でも,先読み文字をk=1に削減する文法規則の変換法ついて明らかにした.2.確率構文解析アルゴリズムの展開これまで構文解析木の生成確率には,文法規則の生起確率を利用していたが,構文解析木の高さ方向の情報を考慮していない.そのため,必ずしも精密な構文解析木の生起確率が求められてはいなかった.それに対し,本研究では,入力文字のLC親と1つ前の入力時に生成される生成規則の組み合わせを数え上げることによって,入力文字列や部分文字列から得られる構文解析木の生起確率をこれまでよりも精密に求めることができることを示した.日本電子化辞書研究所(EDR)の日本語コーパスを用いて,非文(構文解析木の存在しない入力)の構文解析の生起確率はすべての文で正しい生起確率を求めることができた.また,毎日新聞94年度版を利用して数値情報を抽出して,適合率83.2%,再現率74.8%を得た.