(57)【要約】【課題】内包する構文木を個々に評価することなく一括して係り受け解析を施すことが可能な構造を有した統語森を生成する自然言語解析装置及び同装置による係り受け解析方法を提供すること。【解決手段】入力形態素列を構文解析することにより、複数の構文木を内包する統語森を生成する自然言語解析装置であって、文法規則を記憶する第１のメモリを具備し、前記文法規則に基づいて、前記入力形態素列から主辞及び前記主辞が支配する部分構造に相当する主辞支配域を検出する検出手段を具備する。また、検出手段により検出された主辞支配域を有する主辞構造付統語森を生成する構文解析手段を具備する。【選択図】      図１
2006053679.tif 000002
【特許請求の範囲】
【請求項１】
入力形態素列を構文解析することにより、複数の構文木を内包する統語森を生成する自然言語解析装置において、
文法規則を記憶する第１のメモリと、
前記文法規則に基づいて、前記入力形態素列から主辞及び前記主辞が支配する部分構造に相当する主辞支配域を検出する検出手段と、
前記検出手段により検出された主辞支配域を有する主辞構造付統語森を生成する構文解析手段を具備する自然言語解析装置。
【請求項２】
係り側形態素と受け側形態素との間の依存関係の尤もらしさを表す依存知識を記憶する第２のメモリと、
前記構文解析手段により生成された主辞構造付統語森に対し、前記依存知識に基づいて係り受け解析を行うことにより、前記主辞支配域の間の係り受け関係の得点を計算して節点に付与する係り受け解析手段と、をさらに具備する請求項１記載の自然言語解析装置。
【請求項３】
前記係り受け解析手段により前記節点に付与された得点に基づいて、構文木の解釈の尤もらしさに相当する優先順序を付与する優先順序付与手段をさらに具備する請求項２記載の自然言語解析装置。
【請求項４】
入力形態素列を構文解析器が構文解析することにより、複数の構文木を内包する統語森を生成する自然言語解析方法において、
第１のメモリから文法規則を読み出し、該文法規則に基づいて、前記入力形態素列から主辞及び前記主辞が支配する部分構造に相当する主辞支配域を検出する検出し、
前記主辞支配域を有する主辞構造付統語森を生成する自然言語解析方法。
【請求項５】
係り側形態素と受け側形態素との間の依存関係の尤もらしさを表す依存知識を第２のメモリに記憶するステップと、
前記主辞構造付統語森に対し、前記依存知識に基づいて係り受け解析を行うことにより、前記主辞支配域の間の係り受け関係の得点を計算して節点に付与する係り受け解析ステップと、をさらに含む請求項４記載の自然言語解析方法。
【請求項６】
前記係り受け解析ステップにより前記節点に付与された得点に基づいて、構文木の解釈の尤もらしさに相当する優先順序を付与する優先順序付与ステップをさらに含む請求項５記載の自然言語解析方法。
【請求項７】
入力形態素列を構文解析することにより、複数の構文木を内包する統語森を生成する自然言語解析プログラムにおいて、
文法規則を第１のメモリに記憶する手順と、
前記文法規則に基づいて、前記入力形態素列から主辞及び前記主辞が支配する部分構造に相当する主辞支配域を検出する検出手順と、
前記検出手順により検出された主辞支配域を有する主辞構造付統語森を生成する構文解析手順をコンピュータに実行させるための自然言語解析プログラム。
【請求項８】
係り側形態素と受け側形態素との間の依存関係の尤もらしさを表す依存知識を第２のメモリに記憶する手順と、
前記構文解析手順により生成された主辞構造付統語森に対し、前記依存知識に基づいて係り受け解析を行うことにより、前記主辞支配域の間の係り受け関係の得点を計算して節点に付与する係り受け解析手順と、をさらに含む請求項７記載の自然言語解析プログラム。
【請求項９】
前記係り受け解析手順により前記節点に付与された得点に基づいて、構文木の解釈の尤もらしさに相当する優先順序を付与する優先順序付与手順をさらに含む請求項８記載の自然言語解析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は機械翻訳、対話システムなどに好適であって、自然言語をコンピュータ等を用いて解析する自然言語解析、具体的には自然言語の係り受け解析に関する。
【背景技術】
【０００２】
機械翻訳システム、音声対話システムなど、コンピュータにより自然言語文を解析するシステムが広く知られてきている。これらシステムでは、文法に基づく構文解析や、文節間の修飾・被修飾関係に基づく係り受け解析などの文解析アルゴリズムが文の解析に利用されている。
【０００３】
例えば、下記非特許文献１では、曖昧性のある文脈自由文法による構文解析が可能な一般化ＬＲ解析（ＧＬＲ解析）アルゴリズムが示されている。また同文献では、その構文解析結果である構文木を圧縮共有統語森(Shared Packed Forest)構造を用いて効率的に保持する方式が提案されている。
【０００４】
また例えば、下記非特許文献２では、格文法に従って、入力文中の依存関係や意味的整合性を評価し、意味的な曖昧性を解消する手法について示されている。
【非特許文献１】M.Tomita,“Generalized LR Parsing,”Kluwer Academic Publishers, Norwell, Massachusetts,(1991).
【非特許文献２】長尾真編, “自然言語処理”,岩波講座ソフトウェア科学１５,岩波書店,(1996).
【発明の開示】
【発明が解決しようとする課題】
【０００５】
自然言語には、語彙的な曖昧性、構文的な曖昧性、可能な解釈が複数あることが多く、構文解析結果である構文木が複数存在することが多く、また時に膨大な数に上ることがある。このため、文法規則を満たす全ての構造の内、意味的な整合性を有するものを優先させることが自然言語解析の精度を向上させる上で必要である。
【０００６】
しかしながら、従来の係り受け解析は、曖昧性を含まない一つの構文木を解析対象とすることから、複数の構文木を圧縮した構造である圧縮共有統語森構造を直接評価できない。したがって、圧縮共有された複数の構文木の中から、意味的に尤もらしい解釈の構文木を優先させるには、全ての構文木を個々に評価しなければならず、係り受け解析を効率的に行えないという問題点がある。
【０００７】
そこで本発明は、内包する構文木を個々に評価することなく一括して係り受け解析を施すことが可能な構造を有した統語森を生成する自然言語解析装置及び方法、自然言語解析プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一観点に係る自然言語解析装置は、入力形態素列を構文解析することにより、複数の構文木を内包する統語森を生成する自然言語解析装置である。該装置は、文法規則を記憶する第１のメモリを具備し、前記文法規則に基づいて、前記入力形態素列から主辞及び前記主辞が支配する部分構造に相当する主辞支配域を検出する検出手段を具備する。また、検出手段により検出された主辞支配域を有する主辞構造付統語森を生成する構文解析手段を具備する。
【０００９】
本発明によれば、内包する構文木を個々に評価することなく一括して係り受け解析を施すことが可能な主辞構造付統語森を生成できる。
【発明の効果】
【００１０】
本発明によれば、内包する構文木を個々に評価することなく一括して係り受け解析を施すことが可能な構造を有した統語森を生成する自然言語解析装置及び方法、自然言語解析プログラムを提供できる。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照しながら本発明の実施形態を説明する。図１は、本発明の一実施形態に係る自然言語解析装置を示すブロック図である。
【００１２】
入力文１０１は文字列からなり、形態素解析部１０３は、辞書１０２を参照しながら入力文を構成する形態素を認識し、形態素列１０４を出力する。形態素解析については、日本語や英語などの各種言語に対して確立された技術が広く知られており、これを利用することにより実現可能である。
【００１３】
構文解析部１０６が文法規則記憶部１０５から参照する文法規則は、文脈自由文法をベースに記述される。以下では、文法規則を「Y→X1/R1 … Xn/Rn」という書式で記述する。Ｙを左辺、X1/R1 … Xn/Rnを右辺と呼ぶ。Xiは構成素の文法記号（カテゴリ）を表している。Riは構文役割と呼び、右辺に高々一つ存在する主辞を表す“HEAD”、もしくは、他の役割の名称を表す。主辞とは、文法規則において意味的に中心的な役割を果たす構成素であり、入力形態素に対応付けられる。Riが“HEAD”ではない構成素は、Riが“HEAD”である構成素、すなわち主辞に、構文役割Riによって依存する。
【００１４】
例えば、図２は、文法規則“W→X/role1 Y/role2 Z/HEAD”に対応する解析木を示している。２０１は、文法規則の左辺に相当する節点(vertex)である。括弧外が前記文法規則の左辺の文法記号にあたり、括弧内は主辞であり、前記文法からこの構文木の主辞として“ｚ”が導かれたことを示している。２０２、２０３は右辺の構成素に相当する節点である。２０１と同様に文法カテゴリと主辞のペアからなる。２０４や２０５は節点間の依存関係を表し、アーク(arc)と呼ばれる。特に、アーク２０４は主辞との間を結ぶ特別なアークであり、以降の図では太線で表現する。２０６は前記文法規則の構文役割に相当する。これにより、節点２０２が、アーク２０５で特定される構文役割(role1)２０６により、主辞２０３との依存関係を持ち、文法規則に従って文法記号２０１に書き換えられることが表現されている。２０７は、ある一つの主辞が支配する領域を表す。節点２０１と節点２０３は主辞が同じであるので、同じ領域に属している。
【００１５】
主辞構造付統語森１０７は、次の条件を満たす複数の構文木構造を圧縮共有するデータ構造を有する。すなわち、
(a)句の非終端記号が同じ、
(b)句が被覆する入力文の範囲が同じ、
(c)句の主辞となる主構成素が同じ、
であるような複数の構文木構造を圧縮共有する。
【００１６】
主辞構造付統語森１０７は、このようなデータ構造において、任意の入力形態素に対応付けられる主辞が支配する部分構造を「主辞支配域」として統語森上に保持する。
【００１７】
主辞支配域は、構文解析時に構築できる。注目節点が表す範疇が同じであり、かつ、注目節点が被覆する入力形態素列の範囲も同じであり、さらに、根の主辞となる主構成素が同じである場合に、この注目節点は同じ主辞支配域に併合される。ある節点について、このような併合条件を満たす主辞支配域が存在しない場合には、その節点の主辞に対する新たに主辞支配域が生成される。
【００１８】
例えば図３に示す文法規則に基づいて、入力文「２つ目のケーキを焼いてみる」を構文解析して生成された主辞構造付統語森の一例を図４に示す。図４の主辞構造付統語森における節点４０１は、局所曖昧性を併合した構造を有しており、これは一つの節点として扱われる。図４の主辞構造付統語森は、図５の(a)から(d)に示す４つの構文解析木を内包している。これら４つの構文解析木は、それぞれ、
(a)「I try to bake the 2nd cake.」，
(b)「I baked the 2nd cake, and watch it.」，
(c)「I try to bake a cake with two eyes.」，
(d)「I bake a cake with two eyes, and watch it.」
という意味解釈に対応付けられる解析木にあたる。
【００１９】
構文解析部１０６は、形態素列１０４を入力し、文法規則記憶部１０５に記憶されている文法規則を適用して構文解析を行うことにより主辞構造付統語森１０７を生成する。文法規則に照らし、可能な構文的解釈は、全て主辞構造付統語森１０７に含まれる。
【００２０】
依存関係評価部１０９は、主辞構造付統語森１０７を入力し、統語森構造に従って係り受け解析を行い、依存知識記憶部１０８を参照しながら節点に対して得点を付与し、依存得点付統語森１１０を生成する。
【００２１】
依存知識記憶部１０８は、係り側形態素と受け側形態素を指定することで計算される依存関係の尤もらしさを表す数値を依存知識として記憶する。この数値は、表層における受け側・係り側の形態素間距離、あるいは、依存関係の種類、あるいは、他の条件によって変化させてもよい。本実施形態では、例えば図６に示すような依存知識を用いることとする。図６の依存知識は、係り側形態素と受け側形態素、及び、受け側・係り側形態素の解析木構造における構造的距離をもとに、依存関係の尤もらしさを得点として表現したものである。例えば、係り側形態素「２つ」と受け側形態素「目の」、及び、構造的距離１が与えられると、図６の依存知識から得点１を計算できる。
【００２２】
優先順序付与部１１１は、依存得点付統語森１１０を入力として、統語森上に付与された得点を集計し、内包する構文木に尤もらしさの順位を付け、優先順序付統語森１１２を生成する。
【００２３】
本発明の実施形態は、係り受け解析を直接行うことが可能な統語森構造を有する主辞構造付統語森を生成する点に特徴を有する。また、このような統語森構造上で計算した係り受け得点に基づく優先順序が付与された優先順序付統語森を生成する点にも特徴を有する。
【００２４】
なお、本実施形態に従い生成される主辞構造付統語森ならびに優先順序付統語森は、必ずしも自然言語解析装置としてのコンピュータから外部に出力する必要はなく、自然言語処理に係る応用的なコンピュータ処理において内部的に利用され得る。
【００２５】
構文解析部１０６は、構文解析アルゴリズムを実行し、構文解析の結果として、主辞構造付統語森１０７を生成する。構文解析は、形態素列を入力とし、文脈自由文法パーザによって文法規則を参照することにより実施される。主辞構造付き統語森は、既に述べた、圧縮共有統語森における共有条件を追加することで構築可能である。このため、圧縮共有統語森を構築するアルゴリズムにおいて、節点の共有判定に前記条件を追加するだけで、そのまま主辞構造付き統語森を構築可能である。本実施例では、一般化ＬＲ解析法（ＧＬＲ解析法）のアルゴリズムをベースに説明するが、アルゴリズムの構築方法は、チャート法などの種々の構文解析手法が適用可能である。
【００２６】
ＧＬＲ解析アルゴリズムの基礎となるＬＲ解析アルゴリズムは、決定性プッシュダウンオートマトン（Deterministic Push down Automaton）である。同オートマトンが備えるスタックには、ＬＲパーザの状態sと文法記号cの組が格納される。ＬＲパーザは入力形態素列から形態素を一つずつ読み出し、ＬＲ解析表を参照しながら解析を進める。
【００２７】
図７に図３の文法規則から作られるＬＲ解析表を示す。ＬＲ解析表は、動作(ACTION)表と行き先(GOTO)表からなる。
【００２８】
ACTION表は、パーザの状態と入力記号からパーザが次に取るべき動作を決定する。ACCTION表の要素は、“s#”、“r#”、“acc”のいずれかである。“s#”は、状態番号#への遷移（shift）を表し、“r#”は#番の文法規則による還元(reduce)を表し、“acc”は受理(accept)を表す。また、空欄は解析の失敗(reject)を表す。
【００２９】
GOTO表は、パーザの現在の状態と、スタックの先頭にある記号から還元操作後に遷移すべき状態（GotoState）を決定する。ＬＲパーザは、１単語先読みすれば適応可能な動作を一意に決定できる文脈自由文法のクラスを対象としており、ＬＲ解析表の各項は単一の動作を規定している。 
ＧＬＲ解析アルゴリズムは、ＬＲ解析表に複数の動作を記述した項を許し、スタックを分岐及び併合するなど各動作を同時並行的に行うことによって解析を進めるアルゴリズムである。ＧＬＲ解析アルゴリズムにおいて、パーザの状態と統語森上の対応する節点との２項組をスタックノードと呼び、スタックノードとＬＲ解析表から得られる動作との２項組を保持するリストをフロンティア(FRONTIER)と呼び、フロンティアが持っているノードをアクティブなノードと呼ぶ。
【００３０】
以下では、まず従来のＧＬＲ解析アルゴリズムについて説明し、次に、主辞構造付統語森１０７を生成する拡張ＧＬＲ解析アルゴリズムについて説明する。図８は、従来のＧＬＲ解析の処理手順を示すフローチャート、図９は、前記従来のＧＬＲ解析におけるリデュース・フェイズの処理手順を示すフローチャート、図１０は、前記従来のＧＬＲ解析におけるシフト・フェイズの処理手順を示すフローチャートである。
【００３１】
＜処理手順：ＧＬＲ解析＞  
801：START
802：入力形態素列の末尾に入力終端を表す記号“＄”を追加する。
【００３２】
803：状態０のスタックノードη0を作り、スタックにプッシュする。η0はスタックの底を表し、節点を表すフィールドは空である。
【００３３】
804：入力形態素列の先頭形態素uを読む。
【００３４】
805：ＬＲ解析表を参照し、全てのエラーではない動作 a ∈ ACTION[s0,u] に対して、２項組(η0,a)を作り、FRONTIERに追加する。
【００３５】
806：サブルーチン、リデュース・フェイズを呼び出す。
【００３６】
807：サブルーチン、シフト・フェイズを呼び出す。
【００３７】
808：FRONTERが(η,accept)のみかを判定し、真ならば809へ、偽ならば810へ行く。
【００３８】
809：受理状態とし、ステップ808のスタックノードηが持つvertexを返す。
【００３９】
810：FRONTIERが空か判定し、空であるならば811へ行き、空でないならば処理を繰り返すために806へ行く。
【００４０】
811：棄却状態とする。
【００４１】
812：END
＜処理手順：リデュース・フェイズ＞  
901：START
902：reduce動作を持つアクティブなスタックノードが存在するか確認し、存在するならば処理を繰り返すために903へ、存在しないなら914へ行く。
【００４２】
903：FRONTIERから（η,reduce Ａ→α）の形をした要素を一つ取り出す。
【００４３】
904：ηで終わる長さ|α|のグラフ構造化スタック上の経路集合Pを作る。
【００４４】
905：全てのp∈Pに対して、pに接続するスタックノード（ベースノードと呼ぶ）の集合Bpを作る。
【００４５】
906：Bpを文法記号Ａで参照した次GOTO状態に基づき分割し、各状態に対してbs⊆Bpを作る。
【００４６】
907：再利用可能な以下の条件を満たすスタックノードを探す。
【００４７】
1.現在の入力形態素について作られたスタックノードである
2.該スタックノードの子の集合がbsと等しい
3.vertexが非終端記号Ａを表している
908：907でスタックノードη´が見つかったかを判定し、見つかっているなら909へ、見つかっていないならば911へ行く。
【００４８】
909：この還元操作により局所曖昧性が発生したので、スタックノードη´を再利用なスタックノードに設定する。
【００４９】
910：スタックノードη´の持つvertexの子集合に、対応する経路p中のvertexを追加することで、構造を圧縮(Pack)する。914へ行く。
【００５０】
911：経路p中のvertexを子として持つvertex νpを作る。
【００５１】
912：状態s、vertex νp を持つスタックノードη″を作り、bsのスタックにプッシュする。
【００５２】
913：ＬＲ解析表を参照し、全てのエラーではない動作 a ∈ ACTION[s,u] に対して、２項組(η″,a)を作り、FRONTIERに追加する。
【００５３】
914：END
＜処理手順：シフト・フェイズ＞  
1001：START
1002：FRONTIERから（η,shift）の形をした要素を全て取り出す。
【００５４】
1003：読込形態素uに対するvertex ν を作る。
【００５５】
1004：次入力形態素wを読み込む。
【００５６】
1005：1002で取り出したηの集合の次GotoStateに基づく分割Πを作る。
【００５７】
1006：各分割πs∈Πに対して状態s,vertex νを持つスタックノードηsを作り、πsのスタックにプッシュする。
【００５８】
1007：ＬＲ解析表を参照し、全てのエラーではない動作 a ∈ ACTION[s,w] に対して、２項組(ηs,a)を作り、FRONTIERに追加する。
【００５９】
1006：END
次に、本実施形態の特徴に係わる拡張ＧＬＲ解析アルゴリズムについて説明する。この拡張ＧＬＲ解析アルゴリズムには、上述した従来のＧＬＲ解析アルゴリズムを基本としており、解析過程における主辞支配域構築のために、従来の処理手順に３点の変更がなされている。
【００６０】
第一の変更点として、グラフ構造化スタックには、パーザの状態と対応する統語森の節点に加えて、該節点を支配する主辞の３項組としたスタックノードを格納する。これに伴い、図８におけるステップ906の再利用可能ノード条件に以下を加える。
【００６１】
4.主辞が同じである。
【００６２】
４つ目の条件を加えたことにより、従来のＧＬＲ解析アルゴリズムの受理・停止条件では、従来受理されていた文であっても受理されないことがある。そこで、第二の変更点として、本実施形態では受理・停止条件を、「FRONTIERの持つ２項組が、全て(η,accept)の形をしている」とする。
【００６３】
第三の変更点として、主辞支配域を解析の進行と並行して行うために、主辞支配域の生成・併合操作を統語森におけるvertexの生成と操作に追加する。
【００６４】
図１１は、以上の変更が加えられた拡張ＧＬＲ解析の処理手順を示すフローチャート、図１２は、同拡張ＧＬＲ解析におけるデュース・フェイズの処理手順を示すフローチャート、図１３は、同拡張ＧＬＲ解析におけるシフト・フェイズの処理手順を示すフローチャートである。
【００６５】
＜処理手順：拡張ＧＬＲ解析＞  
1101：START
1102：入力形態素列の末尾に入力終端を表す記号“＄”を追加する。
【００６６】
1103：状態０のスタックノードη0を作り、スタックにプッシュするη0はスタックの底を表し、節点及び主辞を表すフィールドは空である。
【００６７】
1104：入力形態素列の先頭形態素uを読む。
【００６８】
1105：ＬＲ解析表を参照し、全てのエラーではない動作 a ∈ ACTION[s0,u] に対して、２項組(η0,a)を作り、FRONTIERに追加する。
【００６９】
1106：サブルーチン、リデュース・フェイズを呼び出す。
【００７０】
1107：サブルーチン、シフト・フェイズを呼び出す。
【００７１】
1108：FRONTIERの持つ２項組が全て、(η,accept)の形をしているか判定し、真ならば1109へ、偽ならば1110へ行く。
【００７２】
1109：受理状態とし、ステップ1108のスタックノードηが持つvertexの集合を返す。
【００７３】
1110：FRONTIERが空か判定し、空であるならば1111へ行き、空でないならば処理を繰り返すために1106へ行く。
【００７４】
1111：棄却状態とする。
【００７５】
1112：END
＜処理手順：拡張リデュース・フェイズ＞  
1201：START
1202：reduce動作を持つアクティブなスタックノードが存在するか確認し、存在するなら処理を繰り返すために1203へ、存在しないなら1216へ行く。
【００７６】
1203：FRONTIERから（η,reduce，Ａ→α）の形をした要素を一つ取り出す。
【００７７】
1204：文法を満たす、ηで終わる長さ|α|のグラフ構造化スタック上の経路集合Pを作る。
【００７８】
1205：全てのp∈Pに対して、pに接続するスタックノード（ベースノードと呼ぶ）の集合Bpを作る。
【００７９】
1206：Bpを文法記号Ａで参照した次GotoStateに基づき分割し、各状態に対してbs⊆Bpを作る。
【００８０】
1207：再利用可能な以下の条件を満たすスタックノードを探す。
【００８１】
1.現在の入力形態素について作られたスタックノードである
2.該スタックノードの子の集合がbsと等しい
3.vertexが非終端記号Aを表している
4.主辞が同じである
1208：1206でスタックノードη´が見つかったかを判定し、見つかっているなら1209へ見つかっていないならば1212へ行く
1209：この還元操作により局所曖昧性が発生したので、スタックノードη´を再利用なスタックノードに設定する
1210：スタックノードη´の持つvertexの子集合に、対応する経路p中のvertexを追加することで、構造を圧縮(Pack)する。
【００８２】
1211：スタックノードη´と同じ主辞である経路p中のvertexを、スタックノードη´が持つvertexの主辞支配域へ併合する。
【００８３】
1212：経路p中のvertexを子として持つvertex νpを作る。
【００８４】
1213：文法規則を参照してνpの主辞θを得、該νpの子の主辞支配域のなかから、同じ主辞である主辞支配域を併合する。
【００８５】
1214：状態s、vertex νp 、主辞θを持つスタックノードη″を作り、bsのスタックにプッシュする。
【００８６】
1215：ＬＲ解析表を参照し、全てのエラーではない動作 a ∈ ACTION[s,u] に対して、２項組(η″,a)を作り、FRONTIERに追加する。
【００８７】
1216：END
＜処理手順：拡張シフト・フェイズ＞  
1301：START
1302：FRONTIERから（η,shift）の形をした要素を全て取り出す。
【００８８】
1303：読込形態素uに対するvertex ν を作る。
【００８９】
1304：入力形態素uを主辞θとした主辞支配域を作り、1303で作ったvertex νを、これに加える。
【００９０】
1305：次入力形態素wを読み込む。
【００９１】
1306：1302で取り出したηの集合の次GotoStateに基づく分割Πを作る。各分割πs∈Πに対して状態s,vertex ν，主辞θを持つスタックノードηsを作り、πsのスタックにプッシュする。
【００９２】
1307：ＬＲ解析表を参照し、全てのエラーではない動作 a ∈ ACTION[s,w] に対して、２項組(ηs,a)を作り、FRONTIERに追加する。
【００９３】
1308：END
これらの変更は、基本的には、共有・圧縮するvertexを選定するための条件の変更と、統語森の構築に併せて主辞支配域を作る操作の追加であるため、主たる解析操作に変更はない。よって、ＧＬＲ（ｋ）アルゴリズム、ボトムアップチャートアルゴリズムなど、種々の構文解析アルゴリズムに対して適応可能である。
【００９４】
次に、依存関係評価部１０９の動作について説明する。図１４は依存関係評価の処理手順を示すフローチャート、図１５は係り受け解析の処理手順を示すフローチャート、図１６は得点計算の処理手順を示すフローチャートである。
【００９５】
＜処理手順：依存関係評価＞  
1401：START
1402：構文解析結果である主辞構造付統語森の葉節点リストを得る。
【００９６】
1403：リストが空ならば、全ての葉節点について処理が済んでいるので、ループを抜けて1408へ行く。空でないならば処理対象が残っているので、1404へ行く。
【００９７】
1404：リストから葉節点を一つ取り出し、注目節点とする。また、該葉節点の主辞を、係り側主辞とする。
【００９８】
1405：係り受け得点の計算に用いられ、係り側主辞と受け側主辞との構造的な距離を規定する主辞間距離を０で初期化する。
【００９９】
1406：係り受け解析サブルーチンを呼び出す。
【０１００】
1407：得点計算がなされた節点に関して、各節点における総計点に、一つの葉節点に注目して計算した得点を加算する。
【０１０１】
1408：END
＜処理手順：係り受け解析＞  
1501：START
1502：注目節点の親節点のリストを得る。
【０１０２】
1503：リストが空ならば、全ての親節点について処理が済んでいるので、ループを抜けて1512へ行く。空でないならば処理対象が残っているので、1504へ行く。
【０１０３】
1504：リストから親節点を一つ取り出し、注目親節点とする。
【０１０４】
1505：注目節点の属する主辞支配域と注目親節点の属する主辞支配域が違うならば、得点計算の対象となる係り受け関係が発生しているので、1506へ行く。主辞支配域が同じならば、係り受け関係は発生しないので、1509へ行く。
【０１０５】
1506：受け側主辞を親節点の主辞とする。
【０１０６】
1507：主辞支配域を移動したので、主辞間距離に１を加算する。
【０１０７】
1508：得点計算サブルーチンを呼び出す。
【０１０８】
1509：注目節点を注目親節点で更新する。
【０１０９】
1510：係り受け解析サブルーチンを呼び出す。
【０１１０】
1511：END
＜処理手順：得点計算＞  
1601：START
1602：主辞間距離、受け側主辞、係り側主辞を基に係り受け得点を計算する。
【０１１１】
1603：現在注目している係り側主辞について、既に注目親節点における得点計算がなされているかを評価し、なされている場合には1604へ行く。そうでなければ1605へ行く。
【０１１２】
1604：計算済み得点が、1602で新たに計算された得点より高ければ1605へ、低ければ1606へ移動する。
【０１１３】
1605：1602で計算した得点で、節点の得点を更新する。
【０１１４】
1606：END
優先順序付与部１１１は、依存得点付統語森１１０を入力として、統語森上に付与された得点を集計し、内包する構文木に尤もらしさの順位を付け、優先順序付統語森１１２を生成する。依存得点付統語森１１０は、局所曖昧性圧縮のなされたvertexをOR構造、他のvertexをAND構造としてみれば、AND-ORグラフであると考えることができる。よって、AND構造をとるvertexでは、自身の得点と子どもの得点とを足し合わせた得点を、OR構造をとるvertexでは、子どもが持つ最大得点を選択し、ボトムアップに得点を集計していくことが可能である。
【０１１５】
以上が、本発明の実施形態に係る自然言語解析装置の構成および動作である。上述した本発明の実施形態によれば、複数の構文木を圧縮共有した構造を有する主辞構造付統語森を生成し、該主辞構造付統語森に対し一括して係り受け解析を施すことのできる自然言語解析装置及び同装置による係り受け解析方法を提供できる。さらに、上述した実施形態によれば、内包する構文木に対して解釈に対して尤もらしさに関する優先順位を付与することが容易に可能になり、時間的・空間的に効率が良く、精度が高い自然言語処理を実現できる。
【０１１６】
次に、上述した拡張ＧＬＲ解析アルゴリズムを用いた実際の解析の様子を実例に沿って説明する。図３の文法規則及び、これを基に作られた図６のＬＲ解析表を用いて「２つ目のケーキを焼いてみる」を構文解析する過程を図１８〜図２５に示す。図１８〜図２５において、左側はグラフ構造化スタックを表し、右側はグラフ構造化スタックに対応する主辞構造付統語森を表している。
【０１１７】
グラフ構造化スタックは、図１７に示す構成素からなる。1701，1702は状態であり、中の数字が状態番号にあたる。1703は1702と共にスタックに積まれた文法記号及び主辞を表し、[]外が文法記号、[]内が主辞を表す。1704は、“／”の前部が次入力形態素を表し、後部がＬＲ解析表を参照して得られた動作であり、この例では、“r2”すなわち２番の文法規則に従ったreduceと、“s3”状態３にshiftを意味している。
【０１１８】
つづいて、実際の動作を「２つ目のケーキを焼いてみる」を入力文として、図１１、図１２、及び図１３のフローチャートに従って説明する。
【０１１９】
1101：START
1102：入力形態素列の末尾に入力終端を表す記号“＄”を追加し、「２つ目のケーキを焼いてみる＄」とする。
【０１２０】
1103：状態０のスタックノードη0を作り、スタックにプッシュする。η0はスタックの底を表し、節点及び主辞を表すフィールドは空である。
【０１２１】
1104：入力形態素列の先頭形態素“２つ”を読む。
【０１２２】
1105：ＬＲ解析表を参照し、（η0，s6）をFRONTIERに追加する。
【０１２３】
ここまでの処理を施した時のグラフ構造化スタックと主辞構造付統語森の様子を図１８に示す。この段階では、統語森にvertexは存在しないため、φとなっている。
【０１２４】
1106：サブルーチン、リデュース・フェイズを呼び出す。
【０１２５】
1202：FRONTIER={（η0，s6）}より、reduceを持つスタックノードはないので、1216へ行く。
【０１２６】
1107：サブルーチン、シフト・フェイズを呼び出す。
【０１２７】
1302：FRONTIER = {（η0，s6）}であるから、shift動作を持つアクティブなスタックノードが存在するので1303へ行く。
【０１２８】
1303：FRONTIERから（η0，s6）を取り出す。
【０１２９】
1304：読込形態素“２つ”に対するvertex ν1 を作る。
【０１３０】
1305：入力形態素“２つ”を主辞とし、“２つ”の主辞支配域を作り、1304で作ったvertex ν1を、これに加える。
【０１３１】
1306：次入力形態素“目の”を読み込む。
【０１３２】
1307：1302で取り出したηの集合の次GotoStateに基づく分割Πを作る。取り出した要素は（η0，s6）であるから、次GotoStateは6のみであり、π6＝{(η0，s6)}という分割ができる。
【０１３３】
1308：分割π6に対して、状態６,vertex ν1，主辞“２つ”を持つスタックノードη1を作り、π6のスタックにプッシュする。
【０１３４】
1309：ＬＲ解析表を参照し、 (η1,r8)をFRONTIERに追加する。
【０１３５】
ここまでの処理を施した時のグラフ構造化スタックと主辞構造付統語森の様子を図１９に示す。
【０１３６】
1108：FRONTIER={(η1,r8)}であるから、1110へ行く。
【０１３７】
1110：FRONTIERは空でないので1106へ行く。
【０１３８】
1106：サブルーチン、リデュース・フェイズを呼び出す。
【０１３９】
1202：FRONTIER = {(η1,r8)}より、reduce動作を持つアクティブなスタックノードが存在するので1203へ行く。
【０１４０】
1203：FRONTIERから(η1,r8)を取り出す。
【０１４１】
1204：8番の文法規則は“NUM→２つ/HEAD”であるので、η1で終わる長さ１のグラフ構造化スタック上の経路集合Pを作り、P={{η1}}を得る。
【０１４２】
1205：p={η1}に対して、n2に接続するスタックノードの集合Bp={η0}を得る。
【０１４３】
1206：Bp={η0}について、文法記号NUM，状態番号0で参照した次GotoStateは4であるので、b4={η0}とする。
【０１４４】
1207：再利用可能なノードを探すが、現在の入力形態素に対して作られたノードはないので、見つからない。
【０１４５】
1208：スタックノードη´が見つからなかったので1212へ行く。
【０１４６】
1212：経路p中のvertex集合{ν1}を子として持つvertex ν2を作る。
【０１４７】
1213：8番の文法規則より、ν2の主辞が“２つ”になるので、対応する主辞支配域を併合する。
【０１４８】
1214：状態4、vertex ν2、主辞“２つ”を持つ、スタックノードη2を作り、b4のスタックにプッシュする。
【０１４９】
1215：ＬＲ解析表を参照し、 (η2,s13)をFRONTIERに追加する。
【０１５０】
1202：FRONTIER = {(η2,s13)}より、reduce動作を持つアクティブなスタックノードが存在しないので1216へ行く。
【０１５１】
1107：サブルーチン、シフト・フェイズを呼び出す。
【０１５２】
1302：FRONTIER = {(η2,s13)} であるから、shift動作を持つアクティブなスタックノードが存在するので1303へ行く。
【０１５３】
1303：FRONTIERから(η2,s13)を取り出す。
【０１５４】
1304：読込形態素“目の”に対するvertex ν3 を作る。
【０１５５】
1305：入力形態素“目の”を主辞として、“目の”の主辞支配域を作り、1303で作ったvertex ν3を、これに加える。
【０１５６】
1306：次入力形態素“ケーキを”を読み込む。
【０１５７】
1307：1302で取り出したηの集合の次GotoStateに基づく分割Πを作る。取り出した要素は(η2,s13)であるから、次GotoStateは13のみであり、π13＝{(η2，s13)}という分割ができる。
【０１５８】
1308：分割π13に対して、状態13,vertex ν3，主辞“目の”を持つスタックノードη3を作り、π13のスタックにプッシュする。
【０１５９】
1309：ＬＲ解析表を参照し、{(η3,r9)}をFRONTIERに追加する。
【０１６０】
ここまでの処理を施した時のグラフ構造化スタックと主辞構造付統語森の様子を図２０に示す。
【０１６１】
1108：FRONTIER={(η3,r9)} であるから、1110へ行く。
【０１６２】
1110：FRONTIERは空ではないので1106へ行く。
【０１６３】
1106：サブルーチン、リデュース・フェイズを呼び出す。
【０１６４】
1202：FRONTIER = {(η3,r9)}より、reduce動作を持つアクティブなスタックノードが存在するので1203へ行く。
【０１６５】
1203：FRONTIERから(η3,r9)を取り出す。
【０１６６】
1204：9番の文法規則は“N→目の/HEAD”であるので、η3で終わる長さ１のグラフ構造化スタック上の経路集合Pを作り、P={{η3}}を得る。
【０１６７】
1205：p={η3}に対して、η3に接続するスタックノードの集合Bp={η2}を得る。
【０１６８】
1206：Bp={η2}について、文法記号N、状態番号4で参照した次GotoStateは16であるので、b16={η2}とする。
【０１６９】
1207：再利用可能なノードを探すが、現在の入力形態素に対して作られたノードはないので、見つからない。
【０１７０】
1208：スタックノードη´が見つからなかったので1212へ行く。
【０１７１】
1212：経路p中のvertex集合{ν3}を子として持つvertex ν4を作る。
【０１７２】
1213：9番の文法規則より、ν4の主辞が“目の”になるので、対応する主辞支配域を併合する。
【０１７３】
1214：状態16、vertex ν4、主辞“目の”を持つ、スタックノードη4を作り、b4のスタックにプッシュする。
【０１７４】
1215：ＬＲ解析表を参照し、 {(η4,r4), (η4,r3)}をFRONTIERに追加する。
【０１７５】
ここまでの処理を施した時のグラフ構造化スタックと主辞構造付統語森の様子を図２１に示す。
【０１７６】
1202：FRONTIER={(η4,r4), (η4,r3)}より、reduce動作を持つアクティブなスタックノードが存在するので1103へ行く。
【０１７７】
1203：FRONTIERから(η4,r4)を取り出す。
【０１７８】
1204：4番の文法規則は“NP→NUM/num  N/HEAD”であるので、η4で終わる長さ2のグラフ構造化スタック上の経路集合Pを作り、P={{η4,η2}}を得る。
【０１７９】
1205：p={η4,η2}に対して、η2に接続するスタックノードの集合Bp={η0}を得る。
【０１８０】
1206：Bp={η0}について、文法記号NP、状態番号0で参照した次GotoStateは2であるので、b2={η0}とする。
【０１８１】
1207：再利用可能なノードを探すが、現在の入力形態素に対して作られたノードはないので、見つからない。
【０１８２】
1208：スタックノードη´が見つからなかったので1212へ行く。
【０１８３】
1212：経路p中のvertex集合{ν4,ν2}を子として持つvertex ν5を作る。
【０１８４】
1213：4番の文法規則より、ν5の主辞が“目の”になるので、対応する主辞支配域を併合する。
【０１８５】
1214：状態2、vertex ν5、主辞“目の”を持つ、スタックノードη5を作り、b2のスタックにプッシュする。
【０１８６】
1215：ＬＲ解析表を参照し、 {(η5,s14)}をFRONTIERに追加する。
【０１８７】
1202：FRONTIER={(η4,r3) ,(η5,s14)}より、reduce動作を持つアクティブなスタックノードが存在するので1203へ行く。
【０１８８】
1203：FRONTIERから=(η4,r3)を取り出す。
【０１８９】
1204：3番の文法規則は“NP→NUM/HEAD  N/tani”であるので、η4で終わる長さ2のグラフ構造化スタック上の経路集合Pを作り、P={{η4,η2}}を得る。
【０１９０】
1205：p={η4,η2}に対して、η2に接続するスタックノードの集合Bp={η0}を得る。
【０１９１】
1206：Bp={η0}について、文法記号NP、状態番号0で参照した次GotoStateは2であるので、b2={η0}とする。
【０１９２】
1207：再利用可能なノードを探すが、現在の入力形態素に対して作られたη5は、条件すなわち４．「主辞が同じである」を満たさないので、再利用できない。
【０１９３】
1208：スタックノードη´が見つからなかったので1212へ行く。
【０１９４】
1212：経路p中のvertex集合{ν4,ν2}を子として持つvertex ν6を作る。
【０１９５】
1213：4番の文法規則より、ν6の主辞が“２つ”になるので、対応する主辞支配域を併合する。
【０１９６】
1214：状態2、vertex ν6、主辞“２つ”を持つ、スタックノードη6を作り、b2のスタックにプッシュする。
【０１９７】
1215：ＬＲ解析表を参照し、 {(η6,s14)}をFRONTIERに追加する。
【０１９８】
ここまでの処理を施した時のグラフ構造化スタックと主辞構造付統語森の様子を図２２に示す。従来のＧＬＲ解析アルゴリズムでは、1207の再利用条件は１〜３までであるので、このようなスタックの分岐はしないことに注意したい。次ステップから、従来のＧＬＲ解析アルゴリズムでは想定していなかった、このようなスタックの状態であっても、解析アルゴリズムを修正することなく正しく動作し、また、本実施形態により主辞構造付統語森が正しく作られることを確認する。
【０１９９】
1202：FRONTIER={(η5,s14), (η6,s14)}より、reduce動作を持つアクティブなスタックノードが存在しないので、1216へ行く。
【０２００】
1107：サブルーチン、シフト・フェイズを呼び出す。
【０２０１】
1302：FRONTIER = {(η5,s14), (η6,s14)} であるから、shift動作を持つアクティブなスタックノードが存在するのでZ03へ行く。
【０２０２】
1303：FRONTIERから(η5,s14), (η6,s14)を取り出す。
【０２０３】
1304：読込形態素“ケーキを”に対するvertex ν7 を作る。
【０２０４】
1305：入力形態素“ケーキを”を主辞として、“ケーキを”の主辞支配域を作り、1303で作ったvertex ν7を、これに加える。
【０２０５】
1306：次入力形態素“焼いて”を読み込む。
【０２０６】
1307：1302で取り出したηの集合の次GotoStateに基づく分割Πを作る。取り出した要素、(η5,s14), (η6,s14)共、次GotoStateは14であるので、π14＝{(η5,s14), (η6,s14)}という分割ができる。
【０２０７】
1308：分割π14に対して、状態14,vertex ν7,主辞“ケーキを”を持つスタックノードη7を作り、π14のスタックにプッシュする。
【０２０８】
1309：ＬＲ解析表を参照し、{(η7,r10)}をFRONTIERに追加する。
【０２０９】
ここまでの処理を施した時のグラフ構造化スタックと主辞構造付統語森の様子を図２３に示す。
【０２１０】
1108：FRONTIER={(η7,r10)} であるから、1110へ行く。
【０２１１】
1110：FRONTIERは空ではないので1106へ行く。
【０２１２】
1106：サブルーチン、リデュース・フェイズを呼び出す。
【０２１３】
1202：FRONTIER ={(η7,r10)}より、reduce動作を持つアクティブなスタックノードが存在するので1203へ行く。
【０２１４】
1203：FRONTIERから(η7,r10)を取り出す。
【０２１５】
1204：10番の文法規則は“N→ケーキを/HEAD”であるので、η7で終わる長さ１のグラフ構造化スタック上の経路集合Pを作り、P={{η7}}を得る。
【０２１６】
1205：p={η7}に対して、η3に接続するスタックノードの集合Bp={η5, η6}を得る。
【０２１７】
1206：Bpの要素η5, η6とも、文法記号N、状態番号2で参照した次GotoStateは10であるので、b10={η5, η6}とする。
【０２１８】
1207：再利用可能なノードを探すが、現在の入力形態素に対して作られたノードはないので、見つからない。
【０２１９】
1208：スタックノードη´が見つからなかったので1212へ行く。
【０２２０】
1212：経路p中のvertex集合{ν7}を子として持つvertex ν8を作る。
【０２２１】
1213：10番の文法規則より、ν7の主辞が“ケーキを”になるので、対応する主辞支配域を併合する。
【０２２２】
1214：状態10、vertex ν7、主辞“ケーキを”を持つ、スタックノードη8を作り、b10のスタックにプッシュする。
【０２２３】
1215：ＬＲ解析表を参照し、 (η8,r5)をFRONTIERに追加する。
【０２２４】
ここまでの処理を施した時のグラフ構造化スタックと主辞構造付統語森の様子を図２４に示す。
【０２２５】
1202：FRONTIER={(η8,r5)}より、reduce動作を持つアクティブなスタックノードが存在するので1203へ行く。
【０２２６】
1203：FRONTIERから(η8,r5)を取り出す。
【０２２７】
1204：5番の文法規則は“NP→NP/rentai  N/HEAD”であるので、η4で終わる長さ2のグラフ構造化スタック上の経路集合Pを作り、P={{η8,η5},{η8,η6}}を得る。
【０２２８】
1205：{η8,η5},{η8,η6}∈Pにおいて、η5,η6共に接続するスタックノードはη0であるので、Bp={η0}を得る。
【０２２９】
1206：Bp={η0}について、文法記号NP、状態番号0で参照した次GotoStateは2であるので、b2={η0}とする。
【０２３０】
1207：再利用可能なノードを探すが、現在の入力形態素に対して作られたノードはないので、見つからない。
【０２３１】
1208：スタックノードη´が見つからなかったので1212へ行く。
【０２３２】
1212：経路p中のvertex集合{ν5,ν8}及び、{ν6,ν8}を子として持つvertex ν9を作る。
【０２３３】
1213：4番の文法規則より、ν9の主辞が“ケーキを”になるので、対応する主辞支配域を併合する。
【０２３４】
1214：状態2、vertex ν9、主辞“ケーキを”を持つ、スタックノードη9を作り、b2のスタックにプッシュする。
【０２３５】
1215：ＬＲ解析表を参照し、 {(η9,s7)}をFRONTIERに追加する。
【０２３６】
ここまでの処理を施した時のグラフ構造化スタックと主辞構造付統語森の様子を図２５に示す。以下同様にして構文解析、統語森及び主辞支配域の構築を進める。
【０２３７】
以上により、入力文「２つ目のケーキを焼いてみる」の解析結果である、図２６の主辞構造付統語森が生成される。
【０２３８】
図２６では、次処理である依存関係評価部１０９の動作説明のために、ν9を該ν9の子どもによって、ν91、ν92と分けて表現しているが、実際には一つのvertexである。また、この主辞構造付統語森は図５に示す４つの構文木を内包していることも確認できる。
【０２３９】
つづいて、図２６の主辞構造付統語森を入力例として、依存関係評価部１０９の実際の動作を説明する。
【０２４０】
1401：START
1402：主辞構造付統語森の葉節点リスト{ν1, ν3, ν7, ν10, ν13}を得る。
【０２４１】
1403：葉節点リスト{ν1, ν3, ν7, ν10, ν13}は、空でないので、1404へ行く。
【０２４２】
1404：リストから葉節点をν1を取り出して注目節点とし、係り側主辞を葉節点の主辞“２つ”とする。
【０２４３】
1405：係り受け得点の計算に用いる、係り側主辞と受け側主辞との構造的な距離を規定する主辞間距離を０で初期化する。
【０２４４】
1406：係り受け解析サブルーチンを呼び出す。
【０２４５】
1502：注目節点ν1の親節点のリスト{ν2}を得る。
【０２４６】
1503：親節点のリスト{ν2}は空でないので、1504へ行く。
【０２４７】
1504：リストから親節点ν２を取り出し、注目親節点とする。
【０２４８】
1505：注目節点の属する主辞支配域と注目親節点の属する主辞支配域は同じであるので、1509へ行く。
【０２４９】
1509：注目節点を注目親節点ν２で更新する。
【０２５０】
1510：係り受け解析サブルーチンを呼び出す。
【０２５１】
1502：注目節点ν2の親節点のリスト{ν5,ν6}を得る。
【０２５２】
1503：親節点のリスト{ν5,ν6}は空でないので、1504へ行く。
【０２５３】
1504：リストから親節点ν5を取り出し、注目親節点とする。
【０２５４】
1505：注目節点の属する主辞支配域と注目親節点の属する主辞支配域が異なるので、1506へ行く。
【０２５５】
1506：受け側主辞を親節点の主辞“目の”とする。
【０２５６】
1507：主辞支配域を移動したので、主辞間距離に１を加算して１とする。
【０２５７】
1508：得点計算サブルーチンを呼び出す。
【０２５８】
1602：主辞間距離１、受け側主辞“目の”、係り側主辞“２つ”を基に、係り受け得点を計算し、１点を得る。
【０２５９】
1603：現在注目している係り側主辞“２つ”について、未だ注目親節点において得点がなされていないので1605へ移動する。
【０２６０】
1605：1602で計算した1点で、節点の得点を更新する。
【０２６１】
1509：注目節点を注目親節点ν5で更新する。
【０２６２】
1510：係り受け解析サブルーチンを呼び出す。
【０２６３】
以下同様にして、ν92→ν12→ν16→ν17→ν91の順で得点計算アルゴリズムに沿って処理が進む。ここまでの処理を施した時の様子を図２７に示す。図において、丸で囲まれた数値が、当該vertexにおける係り受け得点を表している。
【０２６４】
つづいて、係り側主辞“２つ”、ν91を注目節点、主辞間距離１の状態で、図１５のステップ1502からの動作を説明する。
【０２６５】
1502：注目節点ν91の親節点のリスト{ν12,ν17}を得る。
【０２６６】
1503：親節点のリスト{ν12,ν17}は空でないので、1504へ行く。
【０２６７】
1504：リストから親節点ν12を取り出し、注目親節点とする。
【０２６８】
1505：注目節点の属する主辞支配域と注目親節点の属する主辞支配域が異なるので、1506へ行く。
【０２６９】
1506：受け側主辞を親節点の主辞“焼いて”とする。
【０２７０】
1507：主辞支配域を移動したので、主辞間距離に１を加算して２とする。
【０２７１】
1508：得点計算サブルーチンを呼び出す。
【０２７２】
1602：主辞間距離２、受け側主辞“焼いて”、係り側主辞“２つ”を基に、係り受け得点を計算し、0.2点を得る。
【０２７３】
1603：現在注目している係り側主辞“２つ”について、既に注目親節点において得点がなされているので、1604へ行く。
【０２７４】
1604：計算済み得点は0.1点であり、新たに計算された0.2点よりも低いので1505へ移動する。
【０２７５】
1605：1602で計算した0.2点で、節点の得点を更新する。
【０２７６】
1509：注目節点を注目親節点ν12で更新する。
【０２７７】
1510：係り受け解析サブルーチンを呼び出す。
【０２７８】
以下同様にして、ν12→ν16→ν17の順で得点計算アルゴリズムに沿って処理が進む。以上により、葉節点ν1に注目した場合の係り受け解析が終了し、図１４のステップ1403へ処理が戻る。ここまでの処理を施した時の様子を図２８に示す。ついで、次葉節点であるν3について処理を始め、以下同様に全ての葉節点について処理がなされる。
【０２７９】
以上により、入力である図２６の主辞構造付統語森に対して、係り受け解析に基づく得点が付与された、図２９に示すような依存得点付統語森を生成できる。
【０２８０】
また、図２９の依存得点付統語森について、統語森上に付与された得点を集計し、内包する構文木に尤もらしさの順位を付けることにより、図３０の優先順序付統語森を生成することができる。
【０２８１】
図３０の優先順序付統語森は、図３１の構文木を内包しており、優先順位の一位が(a)「I try to bake the 2nd cake.」の木、優先順位の二位が(b)「I bake the 2nd cake, and watch it.」の木、優先順位の三位が(c)「I try to bake a cake with two eyes.」の木、優先順位の四位が(d)の「I bake a cake with two eyes, and watch it.」の木を表しており、自然な解釈である(a)「I try to bake the 2nd cake.」が優先されていることが分かる。
【０２８２】
以上説明した実施形態による文解析及び係り受け解析によれば、複数の構文木を圧縮して保持する統語森構造に対し一括して係り受け解析を施すことができる。また、内包する構文木に対して得点を付与することで、構文木間に優先順位を付与することができる。したがって、係り受け解析を効率的に行うことが可能になる。また、全ての解釈を考慮した優先順位を付与することができることにより、全ての解析候補を評価した中から尤もらしい構造を選び出すことも可能となる。
【０２８３】
係り受けに基づく得点の付与、内包する構文木間の優先順位の付与は、全て構文解析によって構築される主辞構造付統語森上でなされることから、係り受け関係を評価するために別の構造を用意する必要がない。さらに、同じく統語森内の構造的な尤もらしさを評価する確率一般化ＬＲ解析などと組み合わせて用いることが可能になるなどの副次的な効果も得られる。
【０２８４】
以上述べた本発明に係る処理手順は、コンピュータで実行可能なプログラムとして実現してもよい。また、このプログラムをコンピュータで読み取り可能な記憶媒体として本発明を実現することも可能である。なお、記憶媒体としては、磁気ディスク、フレキシブルディスク、ハードディスク、光ディスク（ＣＤ−ＲＯＭ，ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリなど、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、記憶形式はいずれの形態であっても良い。
【０２８５】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼動しているＯＳ（オペレーションシステム）や、データベース管理ソフト、ネットワーク等のミドルウェア等が本実施形態を実現するための各処理の一部を実行してもよい。
【０２８６】
さらに、記憶媒体としては、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行されてもよく、記録媒体の構成は何れの構成であってもよい。
【０２８７】
なお、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本願発明の機能を実現することが可能な機器、装置を総称している。
【０２８８】
本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０２８９】
【図１】本発明の一実施形態に係る自然言語解析装置を示すブロック図
【図２】ある文法規則に対応する解析木の一例を示す図
【図３】文法規則の一例を示す図
【図４】主辞構造付統語森の一例を示す図
【図５】図４の主辞構造付統語森が内包する構文木の一例を示す図
【図６】依存知識の一例を示す図
【図７】図３の文法規則から導かれるＬＲ解析表の一例を示す図
【図８】従来のＧＬＲ解析の処理手順を示すフローチャート
【図９】上記従来のＧＬＲ解析におけるリデュース・フェイズの処理手順を示すフローチャート
【図１０】上記従来のＧＬＲ解析におけるシフト・フェイズの処理手順を示すフローチャート
【図１１】拡張ＧＬＲ解析の処理手順を示すフローチャート
【図１２】上記拡張ＧＬＲ解析におけるデュース・フェイズの処理手順を示すフローチャート
【図１３】上記拡張ＧＬＲ解析におけるシフト・フェイズの処理手順を示すフローチャート
【図１４】依存関係評価の処理手順を示すフローチャート
【図１５】係り受け解析の処理手順を示すフローチャート
【図１６】得点計算の処理手順を示すフローチャート
【図１７】ＧＬＲ解析アルゴリズムで用いられるグラフ構造化スタックの一例を示す図
【図１８】構文解析部による解析過程の一部を示す図
【図１９】構文解析部による解析過程の一部を示す図
【図２０】構文解析部による解析過程の一部を示す図
【図２１】構文解析部による解析過程の一部を示す図
【図２２】構文解析部による解析過程の一部を示す図
【図２３】構文解析部による解析過程の一部を示す図
【図２４】構文解析部による解析過程の一部を示す図
【図２５】構文解析部による解析過程の一部を示す図
【図２６】構文解析部による解析の結果として得られる主辞構造付統語森の一例を示す図
【図２７】依存関係評価部による評価過程の一部を示す図
【図２８】依存関係評価部による評価過程の一部を示す図
【図２９】本発明の実施形態において得られた依存得点付与森の一例を示す図
【図３０】本発明の実施形態において得られた優先順序付統語森の一例を示す図
【図３１】図３０の優先順序付統語森が内包する構文木を示す図
【符号の説明】
【０２９０】
１０１…入力文、１０２…辞書、１０３…形態素解析部、１０４…形態素列、１０５…文法規則記憶部、１０６…構文解析部、１０７…主辞構造付統語森、１０８…依存知識記憶部、１０９…依存関係評価部、１１０…依存得点付統語森、１１１…優先順序付与部、１１２…優先順序付統語森、２０１…文法規則における左辺の文法記号及び主辞、２０２…文法規則における右辺の文法記号及び主辞、２０３…文法規則における右辺の文法記号及び主辞、２０４…主辞を表すアーク、２０５…節点間の依存関係を表すアーク、２０６…構文役割、２０７…主辞領域、４０１…局所曖昧性圧縮構造、１７０１…パーザの初期状態番号、１７０２…パーザの状態番号、１７０３…スタックノードが持つ文法記号および主辞、１７０４…次入力形態素とＬＲ解析表から得られた動作
【図１】
2006053679.tif 000003
【図２】
2006053679.tif 000004
【図３】
2006053679.tif 000005
【図４】
2006053679.tif 000006
【図５】
2006053679.tif 000007
【図６】
2006053679.tif 000008
【図７】
2006053679.tif 000009
【図８】
2006053679.tif 000010
【図９】
2006053679.tif 000011
【図１０】
2006053679.tif 000012
【図１１】
2006053679.tif 000013
【図１２】
2006053679.tif 000014
【図１３】
2006053679.tif 000015
【図１４】
2006053679.tif 000016
【図１５】
2006053679.tif 000017
【図１６】
2006053679.tif 000018
【図１７】
2006053679.tif 000019
【図１８】
2006053679.tif 000020
【図１９】
2006053679.tif 000021
【図２０】
2006053679.tif 000022
【図２１】
2006053679.tif 000023
【図２２】
2006053679.tif 000024
【図２３】
2006053679.tif 000025
【図２４】
2006053679.tif 000026
【図２５】
2006053679.tif 000027
【図２６】
2006053679.tif 000028
【図２７】
2006053679.tif 000029
【図２８】
2006053679.tif 000030
【図２９】
2006053679.tif 000031
【図３０】
2006053679.tif 000032
【図３１】
2006053679.tif 000033