枝刈り式構文解析法の効率化と自然言語解析への応用

概要

論文の詳細を見る
本論文では,文脈自由文法に対する構文解析アルゴリズムである枝刈り式グラフ構造スタック方式(以下では枝刈り法と呼ぶ)を自然言語解析に適用した場合の課題と対応および枝刈り法の効率化について述べる.枝刈り法は強いあいまい性を持つ文脈自由文法の多くに適用でき,時間計算量はO(n^2)であるがすべての解析木を求めることはできない.文脈自由文法の応用では強いあいまい性に対応するために可能な解析木の一部のみを対象とする場合がある.そのような応用の例として自然言語の解析を取り上げ,枝刈り法の適用を検討する.さらに枝刈り法の時間計算量がO(n)となる文法の十分条件を述べる.本論文ではまず枝刈り法の定義を述べる.次に枝刈り法の自然言語解析への応用について述べる.まず自然言語解析において対象とする解析木を選択する既存の手法を示し,枝刈り法と既存の手法を比較し枝刈り法を適用する場合の課題を述べる.最後にこの課題に対応する枝刈り法の変更を示す.続いて枝刈り法によりO(n)で解析できる文法の十分条件を述べる.さらに自然言語解析で用いられる文法がこの条件を満たすことを示す.
2008-01-15