(57)【要約】【課題】係り受け解析における探索量を削減する。【解決手段】本方法は、（Ａ）文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、第１の文節より文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、（Ｂ）第１の文節について、第１の係り受けに含まれる係り受けを辿って第１の文節から末尾の文節へ到達するまでに経由する係り受けの数を計数し、（Ｃ）第１の係り受けに対して、係り受けの数を含む評価項目に応じた評価値を算出し、（Ｄ）算出された評価値に基づき、第１の係り受けにさらに係り受けを追加して設定するか否かを判断する処理を含む。【選択図】図４
2016004472.tif 000002
【特許請求の範囲】
【請求項１】
文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、前記第１の文節より前記文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、
前記第１の文節について、前記第１の係り受けに含まれる係り受けを辿って前記第１の文節から前記末尾の文節へ到達するまでに経由する係り受けの数を計数し、
前記第１の係り受けに対して、前記係り受けの数を含む評価項目に応じた評価値を算出し、
算出された前記評価値に基づき、前記第１の係り受けにさらに係り受けを追加して設定するか否かを判断する
処理を、コンピュータに実行させるための係り受け解析プログラム。
【請求項２】
前記判断する処理が、
評価値が大きな値の方が良い値の場合には、算出された前記評価値が、前記文において先頭の文節からの係り受けが設定された場合に算出された最大評価値より大きいという条件、
評価値が小さい値の方が良い値の場合には、算出された前記評価値が、前記文において先頭の文節からの係り受けが設定された場合に算出された最小評価値より小さいという条件
を満たすか否かを判断する
処理を含み、
前記条件を満たさないと判断された場合には、前記第１の係り受けに追加される係り受けの設定処理が省略される、
請求項１記載の係り受け解析プログラム。
【請求項３】
前記条件を満たすと判断された場合には、前記文において前記ある位置より前に位置する第３の文節からの係り受けを含む第２の係り受けを設定し、
前記計数する処理以降の処理を、前記第２の係り受けに対して実行する
処理をさらに前記コンピュータに実行させるための請求項２記載の係り受け解析プログラム。
【請求項４】
前記条件を満たさないと判断された場合には、
前記第１の文節から前記第２の文節への係り受けを解除し、
前記第１の文節から前記文において前記第１及び第２の文節とは異なる第４の文節への係り受けを含む第３の係り受けを設定し、
前記計数する処理以降の処理を、前記第３の係り受けに対して実行する
処理をさらに前記コンピュータに実行させるための請求項２又は３記載の係り受け解析プログラム。
【請求項５】
前記条件を満たすと判断され、且つ前記第１の文節が前記文における先頭の文節であれば、算出された前記評価値を、前記最大評価値又は前記最小評価値に設定し、前記第１の係り受けをデータ格納部に格納する
処理をさらに前記コンピュータに実行させるための請求項２乃至４のいずれか１つ記載の係り受け解析プログラム。
【請求項６】
文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、前記第１の文節より前記文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、
前記第１の文節について、前記第１の係り受けに含まれる係り受けを辿って前記第１の文節から前記末尾の文節へ到達するまでに経由する係り受けの数を計数し、
前記第１の係り受けに対して、前記係り受けの数を含む評価項目に応じた評価値を算出し、
算出された前記評価値に基づき、前記第１の係り受けにさらに係り受けを追加して設定するか否かを判断する
処理を含み、コンピュータが実行する係り受け解析方法。
【請求項７】
文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、前記第１の文節より前記文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、前記第１の文節について、前記第１の係り受けに含まれる係り受けを辿って前記第１の文節から前記末尾の文節へ到達するまでに経由する係り受けの数を計数する係り受け解析部と、
前記第１の係り受けに対して、前記係り受けの数を含む評価項目に応じた評価値を算出する評価値算出部と、
を有し、
前記係り受け解析部が、
算出された前記評価値に基づき、前記第１の係り受けにさらに係り受けを追加して設定するか否かを判断する
係り受け解析装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自然言語処理における係り受け解析技術に関する。
【背景技術】
【０００２】
自然言語処理においては、入力として平文が与えられた後、通常まず形態素解析が行われて、当該平文は形態素に分割される。また同時に形態素には品詞が付与される。次に、文節分割が実行される。係り受け解析はその次に行われる処理であり、各文節がどの文節に係るかを決定する。図１に係り受けの例を示す。ここでは「太郎は花子が読んでいる本を次郎に渡した」を、文節Ａ「太郎は」、文節Ｂ「花子が」、文節Ｃ「読んでいる」、文節Ｄ「本を」、文節Ｅ「次郎に」、文節Ｆ「渡した」に分割する。ここで、係り受け解析を行えば、図１に示すように、文節Ａは文節Ｆに係り、文節Ｂは文節Ｃに係り、文節Ｃは文節Ｄに係り、文節Ｄ及び文節Ｅは文節Ｆに係る。
【０００３】
日本語においては、文節は常に文の前から後ろに係る。このため、例えば文節が４の場合であって平文「ＡがＢをＣにＤする」という文の場合、図２に示すような探索木を構築し、各係り受けに対して評価値を与えることになる。図２では、第０の階層として、文節Ａから文節Ｂ、文節Ｃ又は文節Ｄへの係り受けが設けられ、第１の階層として、上記の３つの係り受けの各々について、文節Ｂから、文節Ｃ又は文節Ｄへの係り受けが設けられる。第３の階層として、文節Ｃからの係り受けを設定するが、文節数が４の場合には、文節Ｃから文節Ｄへの係り受けしか存在しないので、この例では第２の階層が末端の階層となる。
【０００４】
そして、点数が高いほど好ましい係り受けであるとすると、図２の例では、文節Ａから文節Ｄへの係り受け、文節Ｂから文節Ｄへの係り受け、文節Ｃから文節Ｄへの係り受けが最も好ましい係り受けと判断される。
【０００５】
従来広く使われてきた係り受け解析ツールにおいては、この探索木の全域を残さず探索するのは計算量的に困難なため、何らかの基準を用いて探索木における枝刈りを行うものが多い。
【０００６】
良く用いられている係り受け解析ツールには、チャンキングの段階的適用という手法を用いているものがあるが、このような手法では探索木における探索量を削減できても、本来探索すべきところを一部のノードしか見ないため、正解ノードを探索対象から外すことがある。すなわち、正解を見落とすリスクを抱えている。このため解析精度がある程度以上は上がらないという欠点がある。
【０００７】
解析精度を上げるには探索木の全域探索を行う方が好ましいが、そのためには探索量の問題を解決することが求められる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００９−２７１８２６号公報
【特許文献２】特開２０１２−２２５９９号公報
【特許文献３】特開２００４−２４０５７６号公報
【非特許文献】
【０００９】
【非特許文献１】工藤、松本, 「チャンキングの段階適用による係り受け解析」, 情報処理学会研究報告, 情報学基礎研究会報告, 2001(20), p.97-104, 2001-03-05
【非特許文献２】平川秀樹, 「最適解探索に基づく日本語意味係り受け解析」, 情報処理学会論文誌, 43(3), p.696-707, 2002-03-15
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従って、本発明の目的は、一側面として、係り受け解析における探索量を削減するための技術を提供することである。
【課題を解決するための手段】
【００１１】
本係り受け解析方法は、（Ａ）文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、第１の文節より文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、（Ｂ）第１の文節について、第１の係り受けに含まれる係り受けを辿って第１の文節から末尾の文節へ到達するまでに経由する係り受けの数を計数し、（Ｃ）第１の係り受けに対して、係り受けの数を含む評価項目に応じた評価値を算出し、（Ｄ）算出された評価値に基づき、第１の係り受けにさらに係り受けを追加して設定するか否かを判断する処理を含む。
【発明の効果】
【００１２】
一側面として、係り受け解析における探索量を削減できるようになる。
【図面の簡単な説明】
【００１３】
【図１】図１は、日本語の係り受けの例を示す図である。
【図２】図２は、探索木の一例を示す図である。
【図３】図３は、係り段数を説明するための図である。
【図４】図４は、本実施の形態に係る情報処理装置の機能ブロック図である。
【図５】図５は、本実施の形態に係るメインの処理フローを示す図である。
【図６】図６は、本実施の形態に係る探索処理の処理フローを示す図である。
【図７】図７は、本実施の形態に係る探索処理の処理フローを示す図である。
【図８】図８は、探索処理を説明するための図である。
【図９】図９は、探索処理を説明するための図である。
【図１０】図１０は、探索処理を説明するための図である。
【図１１】図１１は、探索処理を説明するための図である。
【図１２】図１２は、探索処理を説明するための図である。
【図１３】図１３は、探索処理を説明するための図である。
【図１４】図１４は、効果を説明するための図である。
【図１５】図１５は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１４】
評価関数にある種の属性があるとき、安全な枝刈りが可能になるケースがある。例えば、評価値が「係り受け関係が増えると値が悪化する」ときである。この条件を満たす場合には、一部のみ係り受けが設定されている状態（探索木における中間ノードまで探索した状態）における評価値が、係り受けの設定が完了したもの（探索木の末端ノードまで探索した状態）についてこれまでに算出された最良の評価値より悪いとき、一部のみの係り受けが設定された状態に対して残りの係り受けを設定しても現在の評価値より悪い評価値しか算出されない。従って、探索木における中間ノードについて評価値を算出すれば、その下の階層のノードについては探索をスキップできる。これによって探索量を削減できる。
【００１５】
このような手法は、広い意味で分岐限定法と呼ばれるが、分岐限定法を採用する際には、評価関数の設計が鍵となる。そこで、本実施の形態では、「その文節からルート（末尾の文節）への係り段数」を評価項目として新たに採用することとする。この評価項目は、上で述べたような条件を満たし、日本語の係り受けの評価項目としては有効である。すなわち、あるノード（ある文節に対応するノード）から数多くの係り段を経てルート（末尾の文節に対応するノード）に係るような文は、多くの場合日本語として不自然である。従って、ルートへの係り段が増えるほど評価値が悪くなる（例えば小さくなる）ように評価関数を設定する。これによって、探索木の探索量を削減できるようになる。
【００１６】
なお、「ようやく先日、書いた解析のコードが役立った」という文が、文節Ａ「ようやく」、文節Ｂ「先日、」、文節Ｃ「書いた」、文節Ｄ「解析の」、文節Ｅ「コードが」、文節Ｆ「役立った」という文節に分割されるものとする。この時、図３に示すような係り受けを検討するものとする。そうすると、文節Ａについての「ルートへの係り段数」は「１」であり、文節Ｂについての「ルートへの係り段数」は「１」、文節Ｃについての「ルートへの係り段数」は「２」、文節Ｄについての「ルートへの係り段数」は「２」、文節Ｅについての「ルートへの係り段数」は「１」と計数される。なお、「ようやく」は副詞であり、「先日」は副詞可能名詞、「書いた」及び「役立った」が述語、「コードが」が格補語、「コード」及び「解析」は名詞である。
【００１７】
このように探索木の探索量を削減するための情報処理装置の構成を図４に示す。情報処理装置１００は、入力データ格納部１０１と、形態素解析部１０２と、辞書データ格納部１０３と、第１データ格納部１０４と、文節分割部１０５と、第２データ格納部１０６と、係り受け解析部１０７と、評価値算出部１０８と、出力データ格納部１０９と、出力部１１０とを有する。
【００１８】
入力データ格納部１０１は、係り受け解析の対象となる文のデータを格納する。形態素解析部１０２は、辞書データ格納部１０３に格納されている辞書を用いて、解析対象の文に対して、よく知られた形態素解析を実行し、処理結果を第１データ格納部１０４に格納する。処理結果には、形態素への分割結果と、形態素の品詞情報を含む。
【００１９】
文節分割部１０５は、第１データ格納部１０４に格納されているデータから、よく知られた文節分割を行って、処理結果を第２データ格納部１０６に格納する。なお、処理結果には、形態素への分割結果と、形態素の品詞情報と、文節への分割結果とを含む。なお、本実施の形態では、処理結果には、評価値算出のために、文節毎に、名詞＋助詞「の」であるか否かを表すフラグと、名詞で始まるか否かを表すフラグと、副詞可能名詞であるか否かを表すフラグと、副詞か否かを表すフラグと、格補語か否かを表すフラグと、述語か否かを表すフラグと、活用語連体形か否かを表すフラグとが含まれる。
【００２０】
係り受け解析部１０７は、第２データ格納部１０６に格納されているデータを用いて係り受け解析を実行し、処理結果を出力データ格納部１０９に格納する。この際、ルートへの係り段数に基づく評価値の計算処理を行う評価値算出部１０８と連携して処理を行う。係り受け解析部１０７は、各文節について、係り先文節の識別子（ＩＤ）と、ルートへの係り段数とを管理する。出力部１１０は、出力データ格納部１０９に格納されたデータを、出力する。
【００２１】
次に、図５乃至図１４を用いて、情報処理装置１００の処理内容を説明する。なお、以下では、処理を分かりやすくするために、上で述べた「ようやく先日、書いた解析のコードが役立った」という例文を処理する例を共に説明する。
【００２２】
まず、形態素解析部１０２は、辞書データ格納部１０３に格納されている辞書データを用いて、入力データ格納部１０１に格納されている解析対象の文について形態素解析を行って、処理結果を第１データ格納部１０４に格納する（図５：ステップＳ１）。
【００２３】
また、文節分割部１０５は、第１データ格納部１０４に格納されているデータを用いて、文節分割処理を実行し、処理結果を第２データ格納部１０６に格納する（ステップＳ３）。ここまでの処理は、上で述べたように従来から知られた処理であるので、これ以上詳細には述べない。
【００２４】
なお、上で述べた例文については、上で述べたように文節Ａ乃至Ｆに分割される。そして、文節Ａ「ようやく」については、副詞か否かを表すフラグがオンに設定されている。文節Ｂ「先日、」については、副詞可能名詞であるか否かを表すフラグがオンに設定されている。文節Ｃ「書いた」については、述語か否かを表すフラグがオンに設定されている。文節Ｄ「解析の」については、名詞＋助詞「の」であるか否かを表すフラグがオンに設定されている。文節Ｅ「コードが」については、格補語か否かを表すフラグがオンに設定されている。文節Ｆ「役立った」については、述語か否かを表すフラグがオンに設定されている。
【００２５】
その後、係り受け解析部１０７は、後の処理で用いられる変数を初期化する（ステップＳ５）。例えば、これまでの評価値最大値を保持するための変数αには、非常に小さい値（例えば−１００００）を設定し、各文節ｉについてルートへの係り段数を保持するための変数chunk[i].stepに対して、０を設定する。各文節ｉについての係り先文節を保持するための変数chunk[i].dstに対しても、−１（係り受けが無効であることを表す）を設定する。また、文の文節数をｎに設定する。さらに、本実施の形態では、評価値は大きいほど良い値であるものとするが、評価値については小さいほど良い値とする場合もある。
【００２６】
その後、係り受け解析部１０７は、探索木の階層番号ｄｅｐ＝１として、探索処理Ｓｅａｒｃｈ（１）を実行する（ステップＳ７）。探索処理Ｓｅａｒｃｈ（ｄｅｐ）については、図６乃至図１４を用いて説明する。なお、この処理を実行することで、最終的に、最大評価値αと、当該最大評価値αが算出された係り受けｂｅｓｔｓｅｑが、出力データ格納部１０９に格納される。
【００２７】
そうすると、出力部１１０は、最大評価値αと、当該最大評価値αが算出された係り受けｂｅｓｔｓｅｑとを、出力装置（表示装置、印刷装置又は他のコンピュータ）に出力する（ステップＳ９）。
【００２８】
次に、探索処理Ｓｅａｒｃｈ（ｄｅｐ）について図６乃至図１４を用いて説明する。
【００２９】
まず、係り受け解析部１０７は、現在の係り受けに対して評価値算出部１０８に評価値を算出させ、得られた評価値を変数ｖに設定する（図６：ステップＳ１１）。
【００３０】
ｄｅｐ＝１の場合には、まだ係り受けが設定されていないので、例えばｖに対してαより大きい値（例えば−１０００）を設定する。
【００３１】
それ以外の場合には、何らかの係り受けが設定されているので、その係り受けについてのデータを係り受け解析部１０７から評価値算出部１０８に出力して、評価値を算出させる。
【００３２】
本実施の形態では、説明を簡略化するために以下のような評価項目について評価値を算出して総和を計算する。
評価項目１）
格補語、副詞及び副詞可能名詞についての文節は、述語文節に係る。述語文節に係る場合には０点、それ以外の場合には−１０点を加算する。
評価項目２）
活用語連体形、及び名詞＋助詞「の」についての文節は、名詞に係る。名詞に係る場合には０点、それ以外の場合には−１０点を加算する。
評価項目３）
「ルートへの係り段数」が多くなると不自然な日本語となる。これは上でも述べたように本実施の形態で新たに追加された評価項目である。例えば、以下で述べる簡単な例では、ルートへの係り段数が「２」以下であれば０点、「３」以下であれば−２点を加算する。
【００３３】
ここで述べた値については一例であって、異なる評価値を設定するようにしても良い。実際的には、ルートへの係り段数が１０程度の場合に、ペナルティを与えるようにする。また、評価項目１及び２についても一例であって、他の評価項目を採用するようにしても良い。
【００３４】
そして、係り受け解析部１０７は、階層番号ｄｅｐが文節数ｎであるか否かを判断する（ステップＳ１３）。すなわち、探索木のリーフまで探索が達したのか否かを判断するものである。
【００３５】
従って、階層番号ｄｅｐが文節数ｎと一致すれば、係り受け解析部１０７は、ｖを返して（ステップＳ１５）、端子Ｂを介して呼び出し元の処理に戻る。なお、ステップＳ１５に遷移するのは、再帰的に探索処理Ｓｅａｒｃｈ（ｄｅｐ）を呼び出した場合だけであり、最初からステップＳ１５へ遷移することはない。
【００３６】
一方、階層番号ｄｅｐが文節数ｎではない場合には、係り受け解析部１０７は、ｖ≦αであるか判断する（ステップＳ１７）。本実施の形態では、αは、これまでにリーフまで係り受けを設定した場合における評価値の最大値であるので、ステップＳ１１で算出された現在の係り受けの評価値ｖが、α以下であれば、これ以降の階層について係り受け設定の処理を行っても、評価値ｖがαを上回ることはない。そこで、ｖ≦αであれば、係り受け解析部１０７は、αを返して（ステップＳ１９）、端子Ｂを介して呼び出し元の処理に戻る。すなわち、枝刈りが行われたことになる。これにより探索量の削減が行われている。
【００３７】
一方、ｖがαより大きい場合には、係り受け解析部１０７は、係り先ノードの文節番号である変数ｊを０に設定する（ステップＳ２１）。本実施の形態では、後に述べるように、最後の文節Ｆがｊ＝０番目の文節であり、最後から２番目の文節Ｅが第１階層に相当し、最後から３番目の文節Ｄが第２階層に相当し、最後から４番目の文節Ｃが第３階層に相当し、最後から５番目の文節Ａが第５階層に相当するといった形で探索木が形成される。処理としては、初期的には、こちらの経路で処理される。以下、係り受けを新たに設定する。処理は端子Ａを介して図７の処理に移行する。
【００３８】
図７の処理の説明に移行して、係り受け解析部１０７は、変数ｊがｄｅｐと一致しているか否かを判断する（ステップＳ２３）。ｊ番目の文節について係り受けの設定試行が完了したか否かを判断している。ｊがｄｅｐと一致する場合には、係り受け解析部１０７は、αを返して（ステップＳ２５）、呼び出し元の処理に戻る。階層番号ｄｅｐについての係り受けの設定試行が行われたということで、１つ上の階層の処理に戻る。
【００３９】
一方、ｊとｄｅｐが一致しない場合には、係り受け解析部１０７は、ｄｅｐ番目の文節からｊ番目の文節への係り受けを設定する（ステップＳ２７）。すなわち、変数chunk[dep].dst＝ｊを設定する。
【００４０】
最初の場合には、１番目の文節Ｅから０番目の文節Ｆへの係り受けが設定される。図８に模式的に示すように、第１階層目の文節Ｅから０番目の文節Ｆへの係り受け（探索木のリンク）が設定された状態である。
【００４１】
そして、係り受け解析部１０７は、ｄｅｐ番目の文節についての「ルートへの係り段数」を計数して設定する（ステップＳ２９）。上で述べた変数ではchunk[dep].step＝chunk[j].step＋１と設定する。ここでは、文節Ｅについての「ルートへの係り段数」が１になる。
【００４２】
その後、係り受け解析部１０７は、次の階層についての探索処理Ｓｅａｒｃｈ（ｄｅｐ＋１）の再帰呼び出しを行う（ステップＳ３１）。返り値は評価値ｖである。
【００４３】
そうすると、Ｓｅａｒｃｈ（ｄｅｐ＝２）を実行することになって、図６のステップＳ１１で文節Ｅから文節Ｆへの係り受けに対する評価値ｖは、いずれの評価項目にも該当しないので「０」となる。ステップＳ１３ではＮｏルートに遷移し、ステップＳ１７でもＮｏルートに遷移し、ステップＳ２１でｊは「０」に設定される。
【００４４】
そして、図７のステップＳ２３ではＮｏルートに遷移し、ステップＳ２７では、文節Ｄから文節Ｆへの係り受けが設定される。さらにステップＳ２９では、文節Ｄについての「ルートへの係り段数」は「１」に設定される。そして、再度ステップＳ３１で、さらに下位の階層についての探索処理Ｓｅａｒｃｈ（ｄｅｐ＋１）が再帰呼び出しされる。ここまでで、図９の状態になる。
【００４５】
そうすると、ｄｅｐ＝３ということで、ステップＳ１１で、文節Ｅから文節Ｆへの係り受けの評価値（「０」）＋文節Ｄから文節Ｆへの係り受けの評価値（評価項目２から「−１０」）で、ｖ＝−１０が得られる。ステップＳ１３ではＮｏルートに遷移し、ステップＳ１７でもＮｏルートに遷移し、ステップＳ２１でｊは「０」に設定される。
【００４６】
そして、ステップＳ２３ではＮｏルートに遷移し、ステップＳ２７では、文節Ｃから文節Ｆへの係り受けが設定される。さらにステップＳ２９では、文節Ｃについての「ルートへの係り段数」は「１」に設定される。そして、再度ステップＳ３１で、さらに下位の階層についての探索処理Ｓｅａｒｃｈ（ｄｅｐ＋１）が再帰呼び出しされる。ここまでで、図１０の状態になる。
【００４７】
そうすると、ｄｅｐ＝４ということで、ステップＳ１１で、文節Ｅから文節Ｆへの係り受けの評価値（「０」）＋文節Ｄから文節Ｆへの係り受けの評価値（「−１０」）＋文節Ｃから文節Ｆへの係り受けの評価値（評価項目２から「−１０」）で、ｖ＝−２０が得られる。ステップＳ１３ではＮｏルートに遷移し、ステップＳ１７でもＮｏルートに遷移し、ステップＳ２１でｊは「０」に設定される。
【００４８】
そして、ステップＳ２３ではＮｏルートに遷移し、ステップＳ２７では、文節Ｂから文節Ｆへの係り受けが設定される。さらにステップＳ２９では、文節Ｂについての「ルートへの係り段数」は「１」に設定される。そして、再度ステップＳ３１で、さらに下位の階層についての探索処理Ｓｅａｒｃｈ（ｄｅｐ＋１）が再帰呼び出しされる。ここまでで、図１１の状態になる。
【００４９】
そうすると、ｄｅｐ＝５ということで、ステップＳ１１で、文節Ｅから文節Ｆへの係り受けの評価値（「０」）＋文節Ｄから文節Ｆへの係り受けの評価値（「−１０」）＋文節Ｃから文節Ｆへの係り受けの評価値（「−１０」）＋文節Ｂから文節Ｆへの係り受けの評価値（「０」）で、ｖ＝−２０が得られる。ステップＳ１３ではＮｏルートに遷移し、ステップＳ１７でもＮｏルートに遷移し、ステップＳ２１でｊは「０」に設定される。
【００５０】
そして、ステップＳ２３ではＮｏルートに遷移し、ステップＳ２７では、文節Ａから文節Ｆへの係り受けが設定される。さらにステップＳ２９では、文節Ａについての「ルートへの係り段数」は「１」に設定される。そして、再度ステップＳ３１で、さらに下位の階層についての探索処理Ｓｅａｒｃｈ（ｄｅｐ＋１）が再帰呼び出しされる。ここまでで、図１２の状態になる。
【００５１】
そうすると、ｄｅｐ＝６ということで、ステップＳ１１で、文節Ｅから文節Ｆへの係り受けの評価値（「０」）＋文節Ｄから文節Ｆへの係り受けの評価値（「−１０」）＋文節Ｃから文節Ｆへの係り受けの評価値（「−１０」）＋文節Ｂから文節Ｆへの係り受けの評価値（「０」）＋文節Ａから文節Ｆへの係り受けの評価値（「０」）で、ｖ＝−２０が得られる。ステップＳ１３では、ｄｅｐ＝ｎ＝６であるから、Ｙｅｓルートに遷移し、ステップＳ１５でｖ＝−２０が返される。そうすると、ｄｅｐ＝５の状態で、ステップＳ３１に戻ってくることになる。
【００５２】
図６の処理の説明に戻って、係り受け解析部１０７は、ｄｅｐ＝ｎ−１であり且つｖがαより大きいか判断する（ステップＳ３３）。ｄｅｐ＝５でステップＳ３１に戻ってきた場合には、ｄｅｐ＝ｎ−１＝５である。また、ｖ＝−２０であれば、αの初期値（＝−１００００）よりも大きい。従って、条件を満たしていると判断される。
【００５３】
ステップＳ３３の条件を満たしている場合には、係り受け解析部１０７は、ｖをαに代入し、現在の係り受けを変数ｂｅｓｔｓｅｑに設定する（ステップＳ３５）。そして処理はステップＳ３９に移行する。上の例では、α＝−２０となり、ｂｅｓｔｓｅｑに対して、Ａ，Ｂ，Ｃ，Ｄ，Ｅ−＞Ｆという係り受けが設定される。一方、ステップＳ３３の条件を満たしていない場合には、処理はステップＳ３９に移行する。
【００５４】
そして、係り受け解析部１０７は、ｄｅｐ番目の文節からｊ番目の文節への係り受けを外す（ステップＳ３９）。すなわち、文節Ａから文節Ｆへの係り受けを外して、変数chunk[dep].dst＝−１（無効を表す値）をセットする。そうすると、探索木は図１２の状態から、図１１の状態に戻る。
【００５５】
さらに、係り受け解析部１０７は、ｊを１インクリメントする（ステップＳ４１）。上で述べた例では、ｊ＝１となる。そして処理はステップＳ２３に戻る。
【００５６】
上で述べた例では、ステップＳ２３ではＹｅｓルートに遷移し、ステップＳ２７では、文節Ａから文節Ｅへの係り受けが設定される。さらにステップＳ２９では、ｄｅｐ＝５であるから文節Ａについての「ルートへの係り段数」を計数することになり、Ａ−＞Ｅ−＞Ｆとなるので、「２」が得られる。そして、再度ステップＳ３１で、下位の階層についての探索処理Ｓｅａｒｃｈ（ｄｅｐ＋１）が再帰呼び出しされる。ここまでで、図１３の状態になる。
【００５７】
そうすると、ｄｅｐ＝６ということで、ステップＳ１１で、文節Ｅから文節Ｆへの係り受けの評価値（「０」）＋文節Ｄから文節Ｆへの係り受けの評価値（「−１０」）＋文節Ｃから文節Ｆへの係り受けの評価値（「−１０」）＋文節Ｂから文節Ｆへの係り受けの評価値（「０」）＋文節Ａから文節Ｅへの係り受けの評価値（評価項目１に該当するので「−１０」）で、ｖ＝−３０が得られる。ここで、ｄｅｐ＝６であるから、ｎ＝６と一致する。従って、ステップＳ１３ではＹｅｓルートに遷移し、ステップＳ１５でｖ＝−３０が返される。そうすると、ｄｅｐ＝５の状態で、ステップＳ３１に戻ってくることになる。
【００５８】
しかしながら、ｖ＜αであるからステップＳ３３ではＮｏルートに遷移し、文節Ａから文節Ｅへの係り受けを外すことになる。そして、ｊを１インクリメントすると、ｊ＝２となり、ステップＳ２３でＮｏルートに遷移する。以下、文節Ａから文節Ｄへの係り受けを設定する処理、ｊ＝３で文節Ａから文節Ｃへの係り受けを設定する処理、ｊ＝４で文節Ａから文節Ｂへの係り受けを設定する処理が行われる。そうすると、ｊ＝５になったところで、ｄｅｐ＝５と一致することになるので、ステップＳ２５で、αを返して呼び出し元の処理に戻る。
【００５９】
そうすると、ｄｅｐ＝４の状態でステップＳ３１に戻るが、ステップＳ３３の条件を満たさないので、ステップＳ３９で文節Ｂから文節Ｆ（ｊ＝０）への係り受けを外すことになる。そうすると、図１０の状態に戻ることになる。
【００６０】
その後、ｊ＝１となって、文節Ｂから文節Ｅへの係り受けを設定し、さらに、文節Ａから文節Ｆへの係り受けを設定する（図１３）。このような処理が繰り返される。
【００６１】
その後、リーフ「Ａ，Ｂ，Ｅ−＞Ｆ及びＣ，Ｄ−＞Ｅ」というような係り受けについて評価値を算出する順番がやってくる。この場合、いずれの評価項目についての０点となるので、合計で０点となる。この値は、これまでの最大評価値αよりも大きいので、α＝０が設定され、ｂｅｓｔｓｅｑに「Ａ，Ｂ，Ｅ−＞Ｆ及びＣ，Ｄ−＞Ｅ」という係り受けが設定される。
【００６２】
図１４に探索木の全体像（概略）を示しているが、太線で示される上記のような係り受けがｂｅｓｔｓｅｑに設定され、α＝０となる。なお、「Ｅ−＞Ｆ，Ｄ，Ｃ−＞Ｅ」という係り受けに対応するノードにおいてｖ＝０となっているので、α＝０が得られた後でも、文節Ｂからの係り受け設定は行われる。
【００６３】
その後、ｄｅｐ＝３において「Ｃ−＞Ｄ−＞Ｅ−＞Ｆ」という係り受けに対応するノードについて評価値を算出することになる。そうすると、評価項目３において「ルートへの係り段数」が「３」となるので、ｖ＝「−２」点となる。これは、α≧ｖとなるので、ステップＳ１７でステップＳ１９に遷移する。すなわち、図１４において、矩形Ｘに含まれるノードについての処理は省略される。
【００６４】
以上のように探索量が削減されて、高速に係り受けを決定できるようになる。
【００６５】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。上でも述べたように、評価値は小さい方が良いように設定することもできる。さらに、実施の形態で述べたアルゴリズムは一例であって、ルートへの係り段数によって探索木に対する探索の枝刈りができるようなものであればよい。
【００６６】
さらに、図３に示した情報処理装置１００の機能ブロック構成は一例であり、プログラムモジュール構成と一致しない場合もある。また、データ格納部の構成についても、ファイル構成とは一致しない場合もある。
【００６７】
処理フローについても、処理結果が変わらなければ、処理順番を入れ替えたり、複数ステップを並列実行できる場合もある。
【００６８】
なお、上で述べた情報処理装置１００は、コンピュータ装置であって、図１５に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００６９】
以上述べた本実施の形態をまとめると、以下のようになる。
【００７０】
本実施の形態に係る係り受け解析方法は、（Ａ）文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、第１の文節より文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、（Ｂ）第１の文節について、第１の係り受けに含まれる係り受けを辿って第１の文節から末尾の文節へ到達するまでに経由する係り受けの数を計数し、（Ｃ）第１の係り受けに対して、係り受けの数を含む評価項目に応じた評価値を算出し、（Ｄ）算出された評価値に基づき、第１の係り受けにさらに係り受けを追加して設定するか否かを判断する処理を含む。
【００７１】
このように末尾の文節へ到達するまでに経由する係り受けの数（実施の形態におけるルートへの係り段数）という新規な評価項目を採用することで、効果的に探索量を削減できるようになる。
【００７２】
なお、上で述べた判断する処理が、（ｄ１）評価値が大きな値の方が良い値の場合には、算出された評価値が、文において先頭の文節からの係り受けが設定された場合に算出された最大評価値より大きいという条件、（ｄ２）評価値が小さい値の方が良い値の場合には、算出された評価値が、文において先頭の文節からの係り受けが設定された場合に算出された最小評価値より小さいという条件を満たすか否かを判断する処理を含むようにしても良い。この場合、上記条件を満たさないと判断された場合には、第１の係り受けに追加される係り受けの設定処理が省略される。より良い評価値が得られない場合には、探索の枝刈りを行って、探索量を削減するものである。
【００７３】
また、本係り受け解析方法は、（Ｅ）上で述べた条件を満たすと判断された場合には、文において上記ある位置より前に位置する第３の文節からの係り受けを含む第２の係り受けを設定し、（Ｆ）上記計数する処理以降の処理を、第２の係り受けに対して実行する処理をさらに含むようにしても良い。このように、さらに好ましい係り受けが見つかる可能性があれば、探索を継続するものである。
【００７４】
さらに、本係り受け解析方法は、（Ｇ）上で述べた条件を満たさないと判断された場合には、第１の文節から第２の文節への係り受けを解除し、（Ｈ）第１の文節から文において第１及び第２の文節とは異なる第４の文節への係り受けを含む第３の係り受けを設定し、（Ｉ）上記計数する処理以降の処理を、第３の係り受けに対して実行する処理をさらに含むようにしても良い。条件を満たさない場合には、下位の階層についての探索を省略して、別の枝に切り替えて探索するものである。
【００７５】
また、本係り受け解析方法は、（Ｊ）上記条件を満たすと判断され、且つ第１の文節が文における先頭の文節であれば、算出された評価値を、最大評価値又は最小評価値に設定し、第１の係り受けをデータ格納部に格納する処理をさらに含むようにしても良い。このように探索木のリーフまで探索して、最善の評価値が得られた場合には、これまでに算出された最善の評価値を更新し、現在の係り受けのデータを保持しておくものである。
【００７６】
なお、上で述べたような処理をコンピュータに実行させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【００７７】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７８】
（付記１）
文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、前記第１の文節より前記文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、
前記第１の文節について、前記第１の係り受けに含まれる係り受けを辿って前記第１の文節から前記末尾の文節へ到達するまでに経由する係り受けの数を計数し、
前記第１の係り受けに対して、前記係り受けの数を含む評価項目に応じた評価値を算出し、
算出された前記評価値に基づき、前記第１の係り受けにさらに係り受けを追加して設定するか否かを判断する
処理を、コンピュータに実行させるための係り受け解析プログラム。
【００７９】
（付記２）
前記判断する処理が、
評価値が大きな値の方が良い値の場合には、算出された前記評価値が、前記文において先頭の文節からの係り受けが設定された場合に算出された最大評価値より大きいという条件、
評価値が小さい値の方が良い値の場合には、算出された前記評価値が、前記文において先頭の文節からの係り受けが設定された場合に算出された最小評価値より小さいという条件
を満たすか否かを判断する
処理を含み、
前記条件を満たさないと判断された場合には、前記第１の係り受けに追加される係り受けの設定処理が省略される、
付記１記載の係り受け解析プログラム。
【００８０】
（付記３）
前記条件を満たすと判断された場合には、前記文において前記ある位置より前に位置する第３の文節からの係り受けを含む第２の係り受けを設定し、
前記計数する処理以降の処理を、前記第２の係り受けに対して実行する
処理をさらに前記コンピュータに実行させるための付記２記載の係り受け解析プログラム。
【００８１】
（付記４）
前記条件を満たさないと判断された場合には、
前記第１の文節から前記第２の文節への係り受けを解除し、
前記第１の文節から前記文において前記第１及び第２の文節とは異なる第４の文節への係り受けを含む第３の係り受けを設定し、
前記計数する処理以降の処理を、前記第３の係り受けに対して実行する
処理をさらに前記コンピュータに実行させるための付記２又は３記載の係り受け解析プログラム。
【００８２】
（付記５）
前記条件を満たすと判断され、且つ前記第１の文節が前記文における先頭の文節であれば、算出された前記評価値を、前記最大評価値又は前記最小評価値に設定し、前記第１の係り受けをデータ格納部に格納する
処理をさらに前記コンピュータに実行させるための付記２乃至４のいずれか１つ記載の係り受け解析プログラム。
【００８３】
（付記６）
文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、前記第１の文節より前記文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、
前記第１の文節について、前記第１の係り受けに含まれる係り受けを辿って前記第１の文節から前記末尾の文節へ到達するまでに経由する係り受けの数を計数し、
前記第１の係り受けに対して、前記係り受けの数を含む評価項目に応じた評価値を算出し、
算出された前記評価値に基づき、前記第１の係り受けにさらに係り受けを追加して設定するか否かを判断する
処理を含み、コンピュータが実行する係り受け解析方法。
【００８４】
（付記７）
文に含まれる複数の文節のうちある位置における第１の文節から第２の文節への係り受けと、前記第１の文節より前記文において後ろに位置する、末尾の文節を除く各文節からの係り受けとを含む第１の係り受けを設定し、前記第１の文節について、前記第１の係り受けに含まれる係り受けを辿って前記第１の文節から前記末尾の文節へ到達するまでに経由する係り受けの数を計数する係り受け解析部と、
前記第１の係り受けに対して、前記係り受けの数を含む評価項目に応じた評価値を算出する評価値算出部と、
を有し、
前記係り受け解析部が、
算出された前記評価値に基づき、前記第１の係り受けにさらに係り受けを追加して設定するか否かを判断する
係り受け解析装置。
【符号の説明】
【００８５】
１００  情報処理装置
１０１  入力データ格納部
１０２  形態素解析部
１０３  辞書データ格納部
１０４  第１データ格納部
１０５  文節分割部
１０６  第２データ格納部
１０７  係り受け解析部
１０８  評価値算出部
１０９  出力データ格納部
１１０  出力部
【図１】
2016004472.tif 000003
【図２】
2016004472.tif 000004
【図３】
2016004472.tif 000005
【図４】
2016004472.tif 000006
【図５】
2016004472.tif 000007
【図６】
2016004472.tif 000008
【図７】
2016004472.tif 000009
【図８】
2016004472.tif 000010
【図９】
2016004472.tif 000011
【図１０】
2016004472.tif 000012
【図１１】
2016004472.tif 000013
【図１２】
2016004472.tif 000014
【図１３】
2016004472.tif 000015
【図１４】
2016004472.tif 000016
【図１５】
2016004472.tif 000017