(57)【特許請求の範囲】
【請求項１】
照会パターンに対する文のマッチングのスコアを算出する情報処理装置であって、
解析対象の前記文と、該文内の言語単位間の係り易さを指標する指標値と、前記照会パターンとを入力として取得する入力部と、
前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を含む関数で表して、演算するスコア演算部と
を含み、
前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記マッチングのスコアを表す関数の部分演算結果を、再利用するため記憶領域に格納しながら、前記部分構造および前記範囲の内部に関して再帰的に演算することによって、前記スコアを算出し、前記部分演算結果は、前記マッチングのスコアを表す関数の一部を構成する関数であって、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値を含む関数で表されて演算される、部分スコアである、情報処理装置。
【請求項２】
前記指標値は、前記文の統計的構文解析で与えられ、
前記マッチングのスコアを表す関数は、前記対応付けられる各指標値の積を含む関数であり、
前記部分スコアを表す関数は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数であり、
前記スコア演算部は、前記再帰的な演算によって前記照会パターンの構造を辿る、請求項１に記載の情報処理装置。
【請求項３】
前記指標値は、前記文内の各言語単位間の係り受け周辺確率であり、
前記マッチングのスコアは、前記文に対する解析候補中の前記照会パターンを部分木として有する候補が生成されるパターン周辺確率であり、
前記マッチングのスコアを表す関数は、前記対応付けられる各係り受け周辺確率の積であり、前記パターン周辺確率を近似し、
前記部分スコアは、前記部分構造内の各係り受け関係に対応付けられる各係り受け周辺確率の積の局所最大値であり、
前記スコア演算部は、前記再帰的な演算によって、前記照会パターンの構造を辿りながら、前記パターン周辺確率を大域的に最大化することを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記指標値は、前記文内の各言語単位ペア間の係り易さを指標する重みであり、
前記マッチングのスコアは、前記文に対する解析候補中の前記照会パターンが部分木として出現する見込みを意味するパターン出現回数期待値であり、
前記照会パターンが出現する解析候補に含まれる各係り受け関係の各重みの積を規格化したものが該解析候補の確率を表すとして、前記マッチングのスコアを表す関数は、前記照会パターンが出現する解析候補にわたる該解析候補の確率と出現回数との積の総和であり、
前記部分スコアは、前記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和であり、
前記スコア演算部は、前記再帰的な演算によって、前記照会パターンの構造および前記文の構造を辿りながら、前記照会パターンが出現する事象を数え上げ、前記照会パターンが出現した解析候補の確率を加算して、前記パターン出現回数期待値を算出することを特徴とする、請求項２に記載の情報処理装置。
【請求項５】
前記照会パターンは、言語単位にマッチさせるノードと係り受け関係を表すエッジとからなる木構造を構成し、前記スコア演算部は、前記再帰的な演算により前記マッチングのスコアを表す関数の演算結果を得るために呼び出され、前記照会パターンの部分構造と前記文の範囲との対応付けを試行する関数群として、
前記照会パターン内の第１注目ノードの子孫親反対側末端と親ノードと間の部分構造を文の第１範囲に対応付けて、前記第１注目ノードをマッチさせ得る各試行位置に関して、該試行位置から前記親ノードの位置への係り受け関係に対応付けられる前記指標値を与えるとともに、前記第１範囲内の該試行位置を境界とした親反対側範囲について順方向の第１型関数を再帰的に呼び出し、全試行位置にわたる前記部分スコアを出力するとともに、再利用するため記憶領域に格納する前記第１型関数を含む、請求項２に記載の情報処理装置。
【請求項６】
前記スコア演算部は、前記再帰的な演算により前記マッチングのスコアを表す関数の演算結果を得るために呼び出され、前記照会パターンの部分構造と前記文の範囲との対応付けを試行する関数群として、さらに、
前記照会パターン内の第２注目ノードと親ノードとの間の部分構造を文の第２範囲に対応付けて、前記第２注目ノードの親側末端の子ノードと兄弟ノードとの子孫間を境界させる各試行位置に関して、前記第２範囲内の該試行位置を境界とした親反対側範囲について逆方向の前記第１型関数を再帰的に呼び出し、前記第２範囲内の該試行位置を境界とした親側範囲について順方向の前記第１型関数を再帰的に呼び出し、全試行位置にわたる部分スコアを出力するとともに、再利用するため記憶領域に格納する第２型関数を含み、
前記第１型関数は、前記順方向の第１型関数の呼び出しとともに、前記第１範囲の前記試行位置を境界とした親側範囲について順方向の前記第２型関数を再帰的に呼び出すことを特徴とする、請求項５に記載の情報処理装置。
【請求項７】
前記第１型関数は、前記順方向の第１型関数の呼び出しの際に前記第１注目ノードの親反対側末端の子ノードを与え、前記順方向の第２型関数の呼び出しの際に当該第１注目ノードを与え、
前記第２型関数は、前記逆方向の第１型関数の呼び出しの際に前記第２注目ノードの親側末端の子ノードを与え、前記順方向の第１型関数の呼び出しの際に前記第２注目ノードの兄弟ノードを与えることを特徴とする、請求項６に記載の情報処理装置。
【請求項８】
前記スコア演算部は、前記再帰的な演算により前記マッチングのスコアを表す関数の演算結果を得るために呼び出され、前記照会パターンの部分構造と前記文の範囲との対応付けを試行する関数群として、さらに、
前記照会パターン内の第３注目ノードの親ノード子孫末端と該親ノードとの間の部分構造を文の第３範囲に対応付けて、前記第３注目ノードの子孫の親反対側末端を境界させる各試行位置に関して、前記第３範囲の試行位置を境界とした親側範囲について順方向の前記第１型関数を再帰的に呼び出し、全試行位置にわたる部分スコアを出力するとともに、再利用するため記憶領域に格納する第３型関数を含み、
前記第１型関数は、前記第１注目ノードがマッチしない場合の各試行位置に関して、前記第１範囲内の該試行位置を境界とした親側範囲について順方向の前記第３型関数を再帰的に呼び出すことを特徴とする、請求項６に記載の情報処理装置。
【請求項９】
前記第１型関数は、前記順方向の第１型関数の呼び出しの際に前記第１注目ノードの親反対側末端の子ノードを与え、前記順方向の第２型関数の呼び出しの際に当該第１注目ノードを与え、
前記第２型関数は、前記照会パターンの部分構造の内側に処理を進めて、前記逆方向の第１型関数の呼び出しの際に前記第２注目ノードの親側末端の子ノードを与え、前記順方向の第１型関数の呼び出しの際に前記第２注目ノードの兄弟ノードを与え、
前記第３型関数は、前記照会パターンの部分構造の内側に処理を進めず、前記順方向の第１型関数の呼び出しの際に前記第３注目ノードを与えることを特徴とする、請求項８に記載の情報処理装置。
【請求項１０】
前記関数群は、それぞれ、前記照会パターンの部分構造の右端に注目ノードの親ノードが位置する左方向関数と、前記照会パターンの部分構造の左端に注目ノードの親ノードが位置する右方向関数とを含む、請求項５に記載の情報処理装置。
【請求項１１】
前記解析対象の文は、複数の文からなる文集合の各要素として与えられ、
前記照会パターンの検索依頼に応答して、前記文集合の要素のうち、該照会パターンを用いて該要素である解析対象の文に対して演算された前記マッチングのスコアが閾値以上のものを検索結果として出力する情報検索インタフェースをさらに含むことを特徴とする、請求項１に記載の情報処理装置。
【請求項１２】
前記情報検索インタフェースは、前記閾値を受け付けることを特徴とする、請求項１１に記載の情報処理装置。
【請求項１３】
前記解析対象の文は、複数の文からなる文集合の各要素として与えられ、
前記文集合の各要素に対して演算された前記マッチングのスコアの総和を求めて出力する機能部をさらに含むことを特徴とする、請求項１に記載の情報処理装置。
【請求項１４】
前記解析対象の文は、非交差であり、双方向または単方向であり、前記照会パターンは、非交差係り受け木の部分木である、請求項１に記載の情報処理装置。
【請求項１５】
照会パターンに対する文のマッチングのスコアを算出する情報処理装置であって、
解析対象の前記文と、該文内の各言語単位間の係り受け周辺確率と、前記照会パターンとを入力として取得する入力部と、
前記文に対する解析候補中の前記照会パターンを部分木として有する候補が生成されるパターン周辺確率を、前記照会パターンに規定される各係り受け関係が対応付けられる各係り受け周辺確率の関数で表して、前記スコアとして演算するスコア演算部と
を含み、
前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用のため記憶領域に格納しながら前記部分構造および前記範囲の内側に関して再帰的に演算することによって、前記パターン周辺確率を算出する、情報処理装置。
【請求項１６】
前記パターン周辺確率を表す関数は、前記各係り受け周辺確率の積であり、前記パターン周辺確率を近似し、
前記関数の部分演算結果は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係が対応付けられる各係り受け周辺確率の積の局所最大値であり、
前記スコア演算部は、前記再帰的な演算によって前記パターン周辺確率を大域的に最大化することを特徴とする、請求項１５に記載の情報処理装置。
【請求項１７】
照会パターンに対する文のマッチングのスコアを算出する情報処理装置であって、
解析対象の前記文と、該文内の各言語単位間の係り易さを指標する重みと、前記照会パターンとを入力として取得する入力部と、
前記文に対する解析候補中の前記照会パターンが部分木として出現するパターン出現回数期待値を、前記照会パターンが出現する候補に含まれる各係り受け関係の各重みを変数とする関数で表して、前記スコアとして演算するスコア演算部と
を含み、
前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら前記部分構造および前記範囲の内部に関して再帰的に算出することによって、前記パターン出現回数期待値の演算する、情報処理装置。
【請求項１８】
前記照会パターンが出現する解析候補に含まれる各係り受け関係の各重みの積を規格化したものが該解析候補の確率を表すとして、前記パターン出現回数期待値を表す関数は、前記照会パターンが出現する解析候補にわたる該解析候補の確率と出現回数との積の総和であり、
前記関数の部分演算結果は、前記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和であり、
前記スコア演算部は、前記再帰的な演算によって前記照会パターンが出現する事象を数え上げながら、前記照会パターンが出現した解析候補の確率を加算して、前記パターン出現回数期待値を算出することを特徴とする、請求項１７に記載の情報処理装置。
【請求項１９】
コンピュータ・システムが実行する、係り受け構造を有する照会パターンに対する自然言語で記述された文のマッチングのスコアを算出する自然言語解析方法であって、
コンピュータ・システムが、解析対象の前記文と、該文内の言語単位間の係り易さを指標する指標値と、前記照会パターンとを入力として取得し、記憶領域に記憶するステップと、
コンピュータ・システムが、前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を含む関数で表して、プロセッサにより演算するステップと
を含み、
前記演算するステップは、
前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記マッチングのスコアを表す関数の部分演算結果を、再利用するため記憶領域に格納しながら演算するサブステップを前記部分構造および前記範囲の内部に関して再帰的に呼び出すステップを含み、前記部分演算結果は、前記マッチングのスコアを表す関数の一部を構成する関数であって、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値を含む関数で表されて演算される、部分スコアである、自然言語解析方法。
【請求項２０】
前記指標値は、前記文の統計的構文解析で与えられ、
前記マッチングのスコアを表す関数は、前記対応付けられる各指標値の積を含む関数であり、
前記部分スコアを表す関数は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数であり、
前記再帰的に呼び出すステップにより、前記照会パターンの構造が辿られることを特徴とする、請求項１９に記載の自然言語解析方法。
【請求項２１】
コンピュータ・システム上に、照会パターンに対する文のマッチングのスコアを算出する情報処理装置を実現するためのコンピュータ実行可能なプログラムであって、前記コンピュータ・システムを、
解析対象の前記文と、該文内の言語単位間の係り易さを指標する指標値と、前記照会パターンとを入力として取得する入力部、および
前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を含む関数で表して、演算するスコア演算部であって、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記マッチングのスコアを表す関数の部分演算結果を、再利用するため記憶領域に格納しながら前記部分構造および前記範囲の内部に関して再帰的に演算することによって、前記スコアを算出する、当該スコア演算部
として機能させるためのプログラムであり、
前記部分演算結果は、前記マッチングのスコアを表す関数の一部を構成する関数であって、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値を含む関数で表されて演算される、部分スコアである、プログラム。
【請求項２２】
請求項２１に記載のコンピュータ実行可能なプログラムをコンピュータ読取可能に格納する記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自然言語解析技術に関し、より詳細には、係り受け構造を有する照会パターンに対する文のマッチング・スコアを演算するための情報処理装置、自然言語解析方法、プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
近年、コンピュータおよびインターネットなどの情報処理技術の発展に伴い、非定型なテキスト情報が膨大に生成されるようになり、テキスト情報を活用する重要性が高まっている。日本語や英語など自然言語による文は、形態素解析によって単語に分割し、係り受け構文解析することによって、それら単語間の意味的な係り受け構造を推定することができる。近年は、製品の評判情報等から特定の評判表現を抽出したり、技術に関する特徴表現を抽出したりすることに対する要望は高く、特定の単語の有無だけではなく、より上位の意味表現である係り受け構造を考慮した情報検索および情報抽出を高精度に行うことができる技術の開発が望まれている。
【０００３】
しかし、簡易な単語の有無だけでなく、係り受け構造を考慮した情報検索および情報抽出では、係り受け構文解析自体の誤りによる抽出漏れを引き起こす可能性がある。自然言語で記述された文は、自然言語固有の曖昧さに起因して、１つの文に対して解釈可能な構文木が複数存在し得る。このため、係り受け構文解析は、形態素解析などに比較して解析誤りを生じさせやすい。解析精度は、文節単位では約９０％前後であるが、係り受け構造全体が正しく解析される精度はさらに低くなる。単純な試算では、パターン中に２つの係り受け関係が含まれれば、その解析精度は約８１％となり、３つなら約７３％程度まで低下してしまう。
【０００４】
係り受け構造を考慮して情報検索および情報抽出を行うための従来技術としては、１ベスト法、Ｎベスト法、文内共起と呼ばれる手法が知られている。１ベスト法は、文に対してスコアが最大となるベストの構文解析結果に対してパターンマッチングを行う方法である。Ｎベスト法は、文に対してスコア上位Ｎ通りの構文解析結果を取得して、Ｎ通りの構文解析結果に対してパターンマッチングを行い、いずれかの構文解析結果中にマッチするものがあれば、マッチすると判定する方法である（非特許文献１）。文内共起は、文に対して複数の単語が共起しているか否かでマッチングを行う手法である。また、非特許文献２は、係り受け木からの情報抽出をロバストに行うことを目的として、係り受け木上の距離の期待値を計算する手法を開示している。その他、木構造のパターン抽出に関する従来技術としては、例えば特許第４０４９１４１号公報（特許文献１）、特許第４３４１０７７号公報（特許文献２）、特開２００１−１３４５７５号公報（特許文献３）が知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第４０４９１４１号公報
【特許文献２】特許第４３４１０７７号公報
【特許文献３】特開２００１−１３４５７５号公報
【非特許文献】
【０００６】
【非特許文献１】V. M. Jimenez, A. Marzal，”Computation of the n best parse trees for weighted and stochastic context-free grammars.”，Advances in Pattern Recognition，Lecture Notes in Computer Science，Volume 1876/2000，183-192，2000．
【非特許文献２】海野  裕也、坪井  祐太，”係り受け周辺確率に基づく文節間距離”，言語処理学会第１６回年次大会発表論文集，頁２３−２６，２０１０年３月．
【非特許文献３】J. M. Eisner，”Three New Probabilistic Models for Dependency Parsing: An Exploration”，COLING '96 Proceedings of the 16th conference on Computational linguistics， Volume 1，1996．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した１ベスト法は、構文解析が成功した場合には正しいマッチ結果を与えるが、構文解析が失敗した場合は、正しいマッチ結果が与えられない可能性がある。図２８は、従来技術による構文解析結果に対するマッチングを説明する図である。図２８（Ａ）に示す照会パターンを用いて、図２８（Ｂ）および（Ｃ）に示す構文解析結果に対して１ベスト法でマッチングを行う場合、最良とされた解析結果が正しい図２８（Ｂ）である場合は、正しくパターンにマッチし、文が正しく抽出されるが、最良と判断された解析結果が図２８（Ｃ）のような誤ったものである場合、パターンはマッチせず、抽出漏れを発生させてしまう。さらに、１ベスト法は、マッチしたか否かしか判定することができず、情報検索および情報抽出における適合率および再現率を調整することができない点でも充分なものではなかった。
【０００８】
上述したＮベスト法は、複数通りの構文解析結果に対するマッチングが行われるため、１ベスト法と比較して堅牢性に優れる。しかしながら、上位Ｎ通りの解析結果にはマッチしたものがなく、Ｎ＋１以下の順位にパターンにマッチする解析結果が存在したとしても、その場合ヒットせず、抽出漏れを発生させてしまう。Ｎを増やすことで堅牢性を向上できるが、１つの文に対して存在し得る構文木の数は、文長に対して指数関数的に増大するため、文の構文解析候補を全列挙するためには文長に対し指数個の解析結果が必要となり現実的ではなく、全列挙しない場合でも、取りこぼしを低減するためには少なくとも当該指数個に比例したＮが必要となり、必要な記憶容量および計算量が増大する。また、実用上許容できる現実的なＮ（〜２０）では、全体のほんの一部しか考慮することができず、１ベストと同様に抽出漏れが発生しやすい。さらに、Ｎベストは、構文解析結果のスコアを与えることができるが、Ｎ個中でマッチした構文解析結果の解析候補を足しても大きな値とはならないため、値の大小で解析結果の確からしさを判定することも容易ではない。
【０００９】
上述した文内共起は、単語が共起しているあらゆる文を網羅できるため、再現率１００％を達成することができる。しかしながら、文内共起では、文中における単語間の関係性が考慮されないため、明らかに単語間に係り受け関係がない文も抽出されてしまい、効率的ではなく、適合率を向上させることもできない。さらに、文内共起も同様に、マッチしたか否かしか判定することができず、情報検索および情報抽出における適合率および再現率を調整することができない点では１ベスト法と同様である。また非特許文献２に開示される係り受け木上の距離の期待値を計算する手法は、単語間の距離を確率的に求めることで堅牢性を向上させているが、係り受け構造を有するパターンのマッチングを取り扱えるものではなかった。
【００１０】
情報検索および情報抽出では、単にマッチしたか否かではなく、トレードオフの関係にある適合率および再現率を任意のレベルに調整できることが好ましい。例えば、検索漏れが望ましくない場合には、網羅性を優先し再現率を高めることが好ましい。検索漏れはある程度許容できるが、正確な結果を得たいという場合は、正確性を優先し適合率を高め、信頼性の高い情報だけを検索および抽出することが好ましい。
【００１１】
上述した適合率および再現率を任意のレベルに調整できる、係り受け構造を考慮した情報検索および情報抽出の実用的な技術は現時点では知られておらず、したがって、依然として係り受け構造を有する照会パターンに対する文のマッチング・スコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整することを可能とするマッチング・スコアの演算手法の開発が望まれていた。さらに、適合率および再現率を所望のレベルに調整することができる係り受け構造を考慮した情報検索および情報抽出技術の開発が望まれていた。
【００１２】
本発明は、上記従来技術における問題点に鑑みてなされたものであり、本発明は、係り受け構造を有する照会パターンに対する文のマッチング・スコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整可能とし、ひいては構文解析誤りに高い堅牢性を実現することができる情報処理装置、自然言語解析方法、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記従来技術の課題を解決するために、以下の特徴を有する情報処理装置を提供する。本発明の情報処理装置は、解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得する。情報処理装置は、上記取得したデータを用いて、文が照会パターンにマッチする程度を指標するマッチングのスコアを、照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して演算する。情報処理装置は、スコア演算過程では、上記照会パターンの部分構造と文の範囲との対応付けを試行して、上記指標値を少なくとも変数とする関数の部分演算結果を、再利用するため記憶領域に格納しながら、上記部分構造および範囲の内部に関して再帰的に演算することによって、パターンに対する文のマッチングのスコアを算出する。
【００１４】
本発明によれば、また、上記マッチングのスコアを表す関数は、対応付けられる各指標値の積を含む関数とすることができる。上記関数の部分演算結果は、照会パターンの部分構造を文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数で表される部分スコアとすることができる。
【００１５】
さらに、本発明によれば、上記指標値は、文内の各言語単位間の係り受け周辺確率、または係り易さを指標する重みを用いることができる。上記マッチングのスコアは、文に対する解析候補中の照会パターンを部分木として有する候補が生成されるパターン周辺確率、または文に対する解析候補中の照会パターンが部分木として出現する見込みを意味するパターン出現回数期待値とすることができる。マッチングのスコアを表す関数は、対応付けられる各係り受け周辺確率の積として上記パターン周辺確率を近似することができ、または上記照会パターンが出現する解析候補にわたる該解析候補に含まれる各係り受け関係の各重みの積の総和を規格化した関数で表すことができる。上記部分スコアは、部分構造内の各係り受け関係に対応付けられる各係り受け周辺確率の積の局所最大値、または上記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和とすることができる。また本発明によれば、上述した特徴を有する情報処理装置が実行する自然言語解析方法、上記情報処理装置を実現するためのプログラム、および該プログラムを格納する記録媒体を提供することができる。
【００１６】
上記構成によれば、マッチングのスコアを解析対象の文の言語単位間に与えられる評価値の関数で表し、動的計画法を適用することによって、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標し、確率として取り扱うことができるスコアを、全解析候補を列挙することなく効率的に計算することが可能となる。その際の計算量は、動的計画法を適用して演算コストを記憶コストに交換することができるため、文長Ｌ、パターンサイズＭに対してＯ（Ｌ３Ｍ）程度で済む。
【図面の簡単な説明】
【００１７】
【図１】統計的係り受け構文解析の結果を説明する図。
【図２】本発明の実施形態によるマッチング・スコアの算出方法の概略を説明する図。
【図３】本発明の第１の実施形態によるコンピュータ装置の機能ブロック図。
【図４】本発明の第１の実施形態における（Ａ）解析対象の文および（Ｂ）係り受け周辺確率のデータ構造を例示する模式図。
【図５】本発明の第１の実施形態における照会パターンのデータ構造を例示する図。
【図６】本発明の第１の実施形態によるマッチング・スコア演算方法を説明する概念図。
【図７】左側に親ノードがある場合の照会パターンの構文木を示す図。
【図８】本発明の第１の実施形態における（Ａ）左シーケンス関数および（Ｂ）左リンク関数を説明する図。
【図９】本発明の第１の実施形態における（Ａ，Ｂ）左シーケンス関数の疑似コードおよび再帰呼び出しを説明する概念図、並びに（Ｃ，Ｄ）左リンク関数の疑似コードおよび再帰呼び出しを説明する概念図。
【図１０】本発明の第１の実施形態における（Ａ，Ｂ）右シーケンス関数の疑似コードおよび再帰呼び出しを説明する概念図、並びに（Ｃ，Ｄ）右リンク関数の疑似コードおよび再帰呼び出しを説明する概念図。
【図１１】本発明の第１の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理のメインルーチンを示すフローチャート。
【図１２】本発明の第１の実施形態によるメインルーチンによる、初期の照会パターンと解析対象の文との対応付けを示す図。
【図１３】本発明の第１の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理において呼び出される左シーケンス関数のルーチンを示すフローチャート。
【図１４】本発明の第１の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理で呼び出される左リンク関数のルーチンを示すフローチャート。
【図１５】本発明の第１の実施形態による左シーケンス関数、左リンク関数、右シーケンス関数および右リンク関数の相互再帰的な呼び出しを説明する図。
【図１６】本発明の第１の実施形態において、関数の相互再帰的な呼び出しにより、照会パターンの全体構造から末端までの対応付けが行われる様子を示す図。
【図１７】本発明の第１の実施形態によるマッチング・スコア演算機能を組み込んだ情報検索システムの機能ブロック図。
【図１８】本発明の第２の実施形態によるコンピュータ装置の機能ブロック図。
【図１９】本発明の第２の実施形態によるマッチング・スコア演算方法を説明する概念図。
【図２０】本発明の第２の実施形態における左シーケンス関数を説明する図。
【図２１】本発明の第２の実施形態における（Ａ）左リンク関数および（Ａ）左マッチ関数を説明する図。
【図２２】本発明の第２の実施形態における（Ａ）左シーケンス関数（Ｂ）左リンク関数および（Ｃ）左マッチ関数の疑似コードを示す図。
【図２３】本発明の第２の実施形態における（Ａ）右シーケンス関数（Ｂ）右リンク関数および（Ｃ）右マッチ関数の疑似コードを示す図。
【図２４】本発明の第２の実施形態による左右のシーケンス関数、左右のリンク関数および左右のマッチ関数の相互再帰的な呼び出しを説明する図。
【図２５】実験例１の結果および１ベスト法の比較例１の結果を示すＲＯＣグラフ。
【図２６】実験例２の結果および１ベスト法による比較例２〜４の結果を示すＲＯＣグラフ。
【図２７】実験例３の結果および１ベスト法による比較例５〜７の結果を示すＲＯＣグラフ。
【図２８】従来技術による構文解析結果に対するマッチングを説明する図。
【発明を実施するための形態】
【００１８】
以下、本発明について実施形態をもって説明するが、本発明は、後述する実施形態に限定されるものではない。なお、以下に説明する実施形態では、照会パターンに対する文のマッチング・スコアを演算するコンピュータ装置を一例として説明する。
【００１９】
［用語説明］
以下まず、本発明の実施形態で使用する用語について説明する。図１は、統計的係り受け構文解析の結果を説明する図である。図１は、解析対象の文「エンジンが｜走行中に｜突然｜煙を｜噴いた」に対し、係り受け構文解析を実施した場合の解析結果を模式的に表す。解析対象の文は、事前に形態素解析等の事前処理が施されており、単語列または文節列（単語および文節は、いずれも文から区分される言語単位である。以下、言語単位として文節を例に説明するが、言語に応じてまたは任意に、単語または文節を選択することができる。）として与えられる。
【００２０】
「解析候補」とは、文節列として与えられる解析対象の文に対する統計的（確率的）係り受け構文解析において、該文に対して存在し得る構文木をいう。図１には、便宜上４つの解析候補の構文木が例示されているが、解析候補は文に対して存在可能なあらゆる構文木を含み、その数は文長（文節数）に対して指数的に増大する。「解析候補の解析確率」とは、文に対し統計的係り受け構文解析を実行した場合に、解析候補の構文木に対して与えられる確率をいう。各解析候補の解析確率は、全解析候補にわたって解析確率の総和をとると１になるよう規格化されている。
【００２１】
「係り受け周辺確率」とは、文内の文節間の係りやすさを指標する周辺確率であり、本質的には、係り受けペアを含むすべての構文木の解析候補の解析確率の総和に一致する。文中のｉ番目の文節を係り元としてｊ番目の文節を係り先とした係り受けペアの係り受け周辺確率は、ｐ（ｉ，ｊ）で表される。ある係り受けペアを含む解析候補を全列挙することは現実的には困難であるが、仮に図１中に全解析候補が列挙されているとすると、文「エンジンが｜走行中に｜突然｜煙を｜噴いた」における係り受けペア「エンジンが→噴いた」の係り受け周辺確率は、この係り受けペアが出現している２番目および３番目の候補の解析確率の総和（０．３＋０．２＝０．５）となる。同様に、係り受けペア「煙を→噴いた」の係り受け周辺確率は、この係り受けペアが出現している１〜４番目の解析候補の解析確率の総和（０．４＋０．３＋０．２＋０．１＝１．０）となる。係り受け周辺確率は、動的計画法を適用することにより計算可能であることが知られている。
【００２２】
「パターン周辺確率」とは、全解析候補中のパターンを部分木として含む構文木の解析候補が生成される周辺確率であり、本発明の実施形態では、照会パターンに対する文のマッチング・スコアとして利用することができる。「パターン周辺確率」は、本質的には、全解析候補中のパターンを部分木として含む構文木解析候補の解析確率の総和に一致する。図１に示す例では、文「エンジンが｜走行中に｜突然｜煙を｜噴いた」におけるパターン「エンジンが→噴いた，煙を→噴いた」のパターン周辺確率は、このパターンが出現している２番目および３番目の解析候補に与えられた解析確率の総和（０．３＋０．２＝０．５）となる。なお、パターン周辺確率は、０〜１の実数をとる。
【００２３】
全解析候補を列挙して、各候補がパターンにマッチするか否かを判定して、マッチする候補の解析確率の総和をとることは現実的には困難であるが、以下に説明する本発明の第１の実施形態により、解析候補を全列挙することなく、パターン周辺確率を効率的に近似計算することが可能である。本発明の第１の実施形態では、解析候補を全列挙することなく、確率として取り扱えるパターン周辺確率を求めるために、マッチングに関与した係り受けペアの係り受け周辺確率の積でパターン周辺確率を近似する。図２は、本発明の実施形態によるマッチング・スコアの算出方法の概略を説明する図である。図２（Ａ）は、係り受け構造を有する照会パターンを例示し、図２（Ｂ）は、本発明の第１の実施形態によるパターン周辺確率の近似計算を説明する図である。
【００２４】
図２に示す例では、文「エンジンが｜走行中に｜突然｜煙を｜噴いた」におけるパターン「エンジンが→噴いた，煙を→噴いた」のパターン周辺確率は、マッチングに関与する係り受けペア「エンジンが→噴いた」および「煙を→噴いた」の係り受け周辺確率の積（０．５×１＝０．５）で近似計算することができる。また、係り受けペア「エンジンが→噴いた」および「煙を→噴いた」の各係り受け周辺確率は、上述したように、それぞれ、係り受けペアが出現している２番目および３番目の解析候補に与えられた解析確率の総和（０．３＋０．２＝０．５）、および１〜４番目の解析候補に与えられた解析確率の総和（０．４＋０．３＋０．２＋０．１＝１．０）となり、これらは既存技術で算出することができる。
【００２５】
「パターン出現回数期待値」とは、全解析候補中のパターンが出現する回数の期待値をいい、本発明の実施形態では、照会パターンに対する文のマッチング・スコアとして利用することができる。パターン出現回数期待値は、本質的には、解析候補の構文木に出現するパターンの総数と、該構文木の解析確率との積の全解析候補にわたる総和に一致する。図１に示す例では、文「エンジンが｜走行中に｜突然｜煙を｜噴いた」におけるパターン「エンジンが→噴いた，煙を→噴いた」のパターン出現回数期待値は、各解析候補の解析確率と、候補中の出現回数との積の全解析候補にわたる総和（０．４×０＋０．３×１＋０．２×１＋０．１×０＝０．５）となる。
【００２６】
全解析候補を列挙して、候補中にパターンが出現する回数を計数し、候補の出現回数と解析確率との積を求め、全解析候補にわたり総和をとることは現実的には困難であるが、以下に説明する本発明の第２の実施形態により、全解析候補を列挙することなく、パターン出現回数期待値を効率的に計算することが可能である。図２（Ｃ）は、本発明の第２の実施形態によるパターン出現回数期待値の計算方法を説明する図である。図２（Ｃ）に示す例では、パターン「エンジンが→噴いた，煙を→噴いた」が出現する構文木の解析候補の出現回数が数え上げられ、パターンが出現する解析候補の解析確率と、それぞれの出現回数との積の総和（０．３×１＋０．２×１＝０．５）で計算することができる。
【００２７】
なお、図１に示す例では、第２および第３番目の候補での出現回数はいずれも「１」であるため、上記例のパターン出現回数期待値はパターン周辺確率に一致する。しかしながら、解析候補中に複数回出現することも想定され、その場合パターン出現回数期待値が１以上となる可能性もある。例えば、文「Ａ部長は、Ｂ部長が発言したことに関して発言した」に対して照会パターン「部長…発言…［動詞］」が与えられた場合を考える。この場合、上述したパターン周辺確率をマッチング・スコアとする第１の実施形態では、最大の出現箇所の周辺確率を計算し、「Ａ部長…発言した」か「Ｂ部長…発言した」かのいずれか高い方に対応付けた場合の周辺確率が返される。これに対して、上述したパターン出現回数期待値をマッチング・スコアとする第２の実施形態では、「Ａ部長…発言した」および「Ｂ部長…発言した」の両方をカウントし、１以上の値が返る場合がある。パターン周辺確率は、構文解析の確信度が重要である場合により好適に使用することができ、パターン出現回数期待値は、単純に出現している回数が重要であるときにより好適に用いることができる。
【００２８】
本発明の第１および第２の実施形態によるマッチング・スコアの演算処理では、動的計画法を適用することにより、構文解析候補を全列挙することなく効率的に、それぞれマッチング・スコアとして用いられるパターン周辺確率またはパターン出現回数期待値を演算する。以下、第１実施形態によるマッチング・スコア（パターン周辺確率）の演算処理について説明する。
【００２９】
［第１の実施形態］
以下、上述した用語の説明を踏まえて、本発明の第１の実施形態による照会パターンに対する文のマッチング・スコアを演算するコンピュータ装置について説明する。図３は、本発明の第１の実施形態によるコンピュータ装置１００の機能ブロックを示す。図３に示すコンピュータ装置１００は、概ねパーソナル・コンピュータ、ワークステーションまたはメインフレームなどの汎用コンピュータとして構成されている。コンピュータ装置１００は、図示しないＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）などの記憶装置と、必要に応じてＮＩＣ（Network Interface Card）とを備え、Ｗｉｎｄｏｗｓ（登録商標）、ＵＮＩＸ（登録商標）、ＡＩＸ（登録商標）、Ｌｉｎｕｘ（登録商標）などのＯＳの制御下で稼働する。図３に示す各機能部（詳細は後述する。）は、ＣＰＵの作業領域を提供するメモリ上にプログラムを展開し、ＣＰＵの制御の下プログラムを実行させて、各ハードウェア資源を動作制御することによって、コンピュータ装置１００上に実現される。
【００３０】
本発明の実施形態によるコンピュータ装置１００は、解析対象の文１５０および照会パターン１６０を含む入力データを取得する入力部１１０と、入力データを用いてマッチング・スコアを算出するスコア演算部１２０と、マッチング・スコアを含む解析結果を出力する出力部１４０とを含む。
【００３１】
解析対象の文１５０は、入力部１１０に入力される前段階で、形態素解析などの文字列解析手法で単語列に分割され、各単語には適宜品詞タグ付け（Part-of-Speech Tagging）がなされる。解析対象の文１５０は、自然言語の種類にもよるが、単語列または文節列として与えられる。解析対象の文は、日本語や英語などあらゆる自然言語で記述された文とすることができるが、基本的には非交差（projective）の係り受け関係を扱うものとし、単方向および双方向の係り受け関係が許容される。つまり、交差がほとんど無いほとんどの言語に適用することができる。英語などの双方向の係り受けを有する文に対しても適用することができる。図４（Ａ）は、解析対象の文１５０を例示し、文長Ｌの文節列（ｘ１，ｘ２，…，ｘＬ）が示されている。
【００３２】
本発明の実施形態では、上記解析対象の文１５０に付属し、文内の各文節ペアの係り易さを指標する係り受け周辺確率１７０がさらに入力データとして与えられる。ｉ番目の文節からｊ番目の文節への係り受け周辺確率ｐ（ｉ，ｊ）は、予め文に対して統計的構文解析を施した結果として取得することができる。図４（Ｂ）は、係り受け周辺確率１７０のデータ構造を模式的に例示しており、係り元番号ｉを行とし、係り先番号ｊを列としたテーブルが示されており、係り受け周辺確率の値に比例した面積の正方形がセル内に示されている。
【００３３】
統計的係り受け構文解析は、統計学的手法を取り入れた係り受け構文解析手法であり、与えられた文について各単語または文節の係り先の単語または文節を同定する問題を解く自然言語解析処理である。数学的には、解析対象の文をｉ番目の文節（単語）を表す要素ｘｉを用いて文節列ｘ＝｛ｘ１，ｘ２，…，ｘＬ｝で表し、係り受け構造をｉ番目の文節の係り先インデックスを表す要素ｙｉを用いて列ｙ＝｛ｙ１，ｙ２，…，ｙＬ｝∈ＮＬで表し、文節列と係り受け構造に対する確率変数をそれぞれＸ，Ｙで表すと、１ベスト法は、Ｘ＝ｘが与えられたときのＹ＝ｙの同時分布Ｐ（Ｙ＝ｙ｜Ｘ＝ｘ）を最大化するｙを決定することに対応する。Ｎベスト法は、Ｐ（Ｙ＝ｙ｜Ｘ＝ｘ）が大きい順にｙをＮセット決定することに対応する。なお、統計的構文解析の詳細については、非特許文献３を参照することができる。
【００３４】
上記照会パターン１６０は、文節にマッチさせるパターン要素をノードとし、パターン要素間の係り受け関係をエッジとした木構造で表すことができる。照会パターン１６０は、数学的には、文節にマッチさせるｉ番目のパターン要素を表す要素ｐｉを用いて、長さＭのパターン列ｐ＝｛ｐ１，ｐ２，…，ｐＭ｝を用いて表すことができる。照会パターン１６０の係り受け構造については、パターン要素ｐｉの親ノード（係り先）のインデックスを返す関数ｐａｒ（ｐ，ｉ）で表すことができる。照会パターン１６０は、好適には、非交差係り受け構文木の部分木、すなわち、順序付きであり、左右別に子ノードが定義され得る木構造とすることができる。このため、各ノードを左から右へ辿ったときの順序で文中に出現することがマッチの条件となる。また、照会パターンの文頭または末尾にルートを仮想的に設定し、設定されたルートを頂点として、係り受け構造に対応して木構造が定義される。
【００３５】
ノード間に定義される関係としては、注目するノードをｎとして、親ノードＰＡＲ（ｎ）、最左子ノードＬＣＨ（ｎ）、最右子ノードＲＣＨ（ｎ）、兄弟ノードＳＩＢ（ｎ）を挙げることができる。最左子ノードＬＣＨ（ｎ）は、注目ノードｎの左側の子ノードであって、一番左側にあるノードをいい、最右子ノードＲＣＨ（ｎ）は、注目ノードｎの右側の子ノードであって、一番右側にあるノードをいう。兄弟ノードＳＩＢ（ｎ）は、注目ノードｎと親を同一とするノードであって、注目ノードｎが親の左側に存在する場合には注目ノードｎの右側に存在するノードをいい、注目ノードｎが親の右側に存在する場合には注目ノードｎの左側に存在するノードをいう。照会パターン１６０のあらゆる係り受け構造は、上記ＰＡＲ（ｎ）、最左子ノードＬＣＨ（ｎ）、最右子ノードＲＣＨ（ｎ）、兄弟ノードＳＩＢ（ｎ）を用いて、直接的にまたは間接的に表すことができる。
【００３６】
図５（Ａ）に示す照会パターン１６０ａでは、ルートを注目ノードｎとした場合、注目ノードｎの最左子ノードＬＣＨ（ｎ）としてパターン要素「発言した」が、パターン要素「発言した」の最左子ノードＬＣＨ（ＬＣＨ（ｎ））としてパターン要素「社長が」が規定される。パターン要素「発言した」を注目ノードｎとしてみた場合には、注目ノードｎの親ノードＰＡＲ（ｎ）がルートで、注目ノードｎの最左子ノードＬＣＨ（ｎ）がパターン要素「社長が」に対応する。
【００３７】
図５（Ｂ）に示す照会パターン１６０ｂでは、ルートを注目ノードｎとした場合、注目ノードｎの最左子ノードＬＣＨ（ｎ）としてパターン要素「噴いた」が規定され、パターン要素「噴いた」の最左子ノードＬＣＨ（ＬＣＨ（ｎ））としてパターン要素「エンジンが」が規定され、パターン要素「エンジンが」の兄弟ノードＳＩＢ（ＬＣＨ（ＬＣＨ（ｎ）））としてパターン要素「煙を」が規定されている。パターン要素「エンジンが」を注目ノードｎとしてみた場合は、注目ノードｎの親ノードＰＡＲ（ｎ）がパターン要素「噴いた」に対応し、注目ノードｎの兄弟ノードＳＩＢ（ｎ）がパターン要素「煙を」に対応する。
【００３８】
照会パターン１６０の各ノードを構成するパターン要素としては、上述した「社長」や「エンジンが」といった単語や文節の文字表現そのものとしてもよいし、正規形、「動詞」や「名詞」などの品詞その他のタグ情報に対する制約条件、ワイルドカードを利用した正規表現としてもよく、特に限定されるものではない。ここで、パターン要素ｐｊがｉ番目の文節ｘｉにマッチする場合に「真（１）」を出力し、マッチしない場合に「偽（０）」を出力するパターンマッチング関数Ｍ（ｘｉ，ｐｊ）∈｛０，１｝を定義する。
【００３９】
再び図３を参照すると、スコア演算部１２０は、入力部１１０が取得した入力データを用いて、照会パターン１６０に対する解析対象の文１５０のマッチング・スコアを演算する。上述したように第１の実施形態においては、解析対象の文１５０に対し存在可能な全解析候補の中で上記照会パターン１６０を部分木として有する候補が生成されるパターン周辺確率をマッチング・スコアとして用いる。パターン周辺確率は、照会パターン１６０に規定される各係り受け関係が対応付けられる各係り受け周辺確率ｐ（ｉ，ｊ）の関数で表され、より具体的には、マッチングに関与する各係り受け周辺確率ｐ（ｉ，ｊ）の積で近似される。本実施形態では、スコア演算部１２０により、大域的に最大となるパターン周辺確率が最終的に算出され、同時に照会パターン１６０と解析対象の文１５０との最適な対応付けも決定される。
【００４０】
対応付けは、数学的には、パターン要素ｐｉをマッチさせる文節のインデックスｍｉを用いて、長さＭのマッチング列ｍ＝｛ｍ１，ｍ２，…，ｍＭ｝∈ＮＭとして表すことができる。なお、任意のｉに対してＭ（ｘｍｉ，ｐｉ）＝１である必要がある。また本発明の第１の実施形態において、マッチング・スコアは、数学的には、以下の式（１）で表す値を求めることになる。なお、下記式（１）中のＶ（ｙ，ｍ，ｐ）は、パターン列ｐをマッチング列ｍでマッチさせたとき、パターン列ｐの親と係り受け構造を表す列ｙの親とが一致するときに１を返す関数である。すなわち、Ｖ（ｙ，ｍ，ｐ）は、任意のｉに対してｙｍｉ＝ｍｐａｒ（ｐ，ｉ）であるとき１を返し、妥当性を保証するための制約条件として用いられる。
【００４１】
【数１】
0005710317.tif 000002
【００４２】
上記式（１）は、このままでは計算できないため、同時分布を周辺確率の積で近似する。すなわち、Ｐ（Ｙ＝ｙ｜Ｘ＝ｘ）を下記式（２）で表される係り受け周辺確率の積で近似する。
【００４３】
【数２】
0005710317.tif 000003
【００４４】
スコア演算部１２０は、複数の関数群１２２〜１２８を備えており、これらの関数群１２２〜１２８を再帰的に呼び出すことで、全解析候補を列挙することなく、上記パターン周辺確率を演算する。より具体的には、スコア演算部１２０は、上記関数群１２２〜１２８を用いて、照会パターン１６０の部分構造と解析対象の文１５０の範囲との対応付けを試行し、上記係り受け周辺確率の積の部分演算結果を上記部分構造および範囲の内側に関して再帰的に算出する。一度計算された部分演算結果は、動的計画テーブル１３０内に格納され、演算過程で再び必要になった際に、再度演算する代わりに動的計画テーブル１３０に格納された値が参照され再利用される。動的計画テーブル１３０は、部分演算結果を格納するための記憶領域であり、例えばＲＡＭ、ＨＤＤやＳＳＤなどによる記憶領域により提供される。
【００４５】
本発明の第１の実施形態では、照会パターン１６０の部分構造と解析対象の文１５０の範囲との対応付けが相互再帰的に扱えることを利用し、動的計画法を適用して、本来計算量的に困難のあるパターン周辺確率の効率的な近似計算を可能としている。本実施形態では、上記関数群として、左シーケンス関数１２２、右シーケンス関数１２４、左リンク関数１２６および右リンク関数１２８の４つの関数が定義されるが、これらの関数群を用いたスコア演算部１２０の処理については、詳細を後述する。
【００４６】
出力部１４０は、スコア演算部１２０が算出したパターン周辺確率（マッチング・スコア）を含む演算結果１８０を出力する。また第１の実施形態では、パターン周辺確率の演算とともに、照会パターン１６０の解析対象の文１５０に対する最適なマッチング列ｍも求められるため、上記パターン周辺確率とともに、マッチング列ｍが規定するマッチ位置も演算結果１８０に含めることができる。
【００４７】
以下、図６〜図８を参照しながら、本発明の第１の実施形態によるマッチング・スコア演算処理について説明する。図６は、本発明の第１の実施形態によるマッチング・スコア演算方法を概念的に説明する図である。本発明の第１の実施形態では、照会パターンに対してＥｉｓｎｅｒ構文木と同様の構文木を考える。図６中の三角形および台形は、それぞれ、１次のＥｉｓｎｅｒアルゴリズムにおける、半成分を表す完全スパン（Complete Span）、および係り受け関係を表す非完全スパン（Incomplete Span）に相当するものである。本発明の実施形態では、各図形は、照会パターンの部分構造を表しており、マッチング・スコアの演算過程で、各図形が表す部分構造と、解析対象の文中の範囲（スパン）との最適な対応付けが検索される。
【００４８】
図６には、照会パターンの注目ノードｎに関連して、最左子ノードＬＣＨ（ｎ）、注目ノードｎ、最右子ノードＲＣＨ（ｎ）、兄弟ノードＳＩＢ（ｎ）および親ノードＰＡＲ（ｎ）が順に並べられている。まず、図６中に示した第３の構文木生成規則により、照会パターンのパターン要素を表すこれらノード各々から、それぞれ半成分を表す左向き三角形および右向き三角形の各組が生成される。続いて、図６中に示した第２の構文木生成規則により、最左子ノードＬＣＨ（ｎ）の右向き三角形と、注目ノードｎの左向き三角形とから、左向き台形Ｆが生成される。この左向き台形Ｆは、最左子ノードＬＣＨ（ｎ）および注目ノードｎの間の部分構造を表し、最左子ノードＬＣＨ（ｎ）から注目ノードｎへの係り受け関係を表す。同様に、注目ノードｎの右向き三角形と、最右子ノードＲＣＨ（ｎ）の左向き三角形とから、最右子ノードＲＣＨ（ｎ）から注目ノードｎへの係り受け関係を表す右向き台形Ｈが生成され、兄弟ノードＳＩＢ（ｎ）から親ノードＰＡＲ（ｎ）への係り受け関係を表す左向き台形Ｊについても同様である。
【００４９】
さらに、図６中に示した第１の構文木生成規則により、最左子ノードＬＣＨ（ｎ）の左向き三角形Ｇと、最左子ノードＬＣＨ（ｎ）および注目ノードｎの間の部分構造を表す上記左向き台形Ｆとから、最左子ノードＬＣＨ（ｎ）および注目ノードｎの間の部分構造を表す左向き三角形Ｃが生成される。同様に、上記右向き台形Ｈと、最右子ノードＲＣＨ（ｎ）の右向き三角形Ｉとから右向き三角形Ｄが生成され、兄弟ノードＳＩＢ（ｎ）の左向き三角形Ｋと上記生成された左向き台形Ｊとから左向き三角形Ｅが生成される。
【００５０】
さらに、図６中に示した第２の構文木生成規則により、上記右向き三角形Ｄと左向き三角形Ｅとから、注目ノードｎから親ノードＰＡＲ（ｎ）への係り受け関係を表す左向き台形Ｂが生成される。図６中に示した第１の構文木生成規則により、さらに、左向き三角形Ｃと、左向き台形Ｂとから、最左子ノードＬＣＨ（ｎ）および親ノードＰＡＲ（ｎ）の間の部分構造を表す左向き三角形Ａが生成される。このようにして、ＬＣＨ（ｎ）、ｎ、ＲＣＨ（ｎ）、ＳＩＢ（ｎ）およびＰＡＲ（ｎ）間の部分構造各々を表す図形をノードとしたＥｉｓｎｅｒ構文木と同様の構文木が生成される。
【００５１】
なお、図６は、注目ノードｎを中心とした照会パターンの一部構造を表したものであり、具体的な照会パターンに応じて、さらに詳細な構造が定義される。例えば最左子ノードＬＣＨ（ｎ）を注目ノードとしてさらにＬＣＨ（ＬＣＨ（ｎ））、ＲＣＨ（ＬＣＨ（ｎ））、ＳＩＢ（ＬＣＨ（ｎ））が定義されたり、親ノードＰＡＲ（ｎ）のさらに親ノードＰＡＲ（ＰＡＲ（ｎ））が定義されたりする場合があり、これらは図示を省略されていることに留意されたい。さらに、上記ＲＣＨ（ｎ）を注目ノードとする場合など、注目ノードが親ノードの右側に存在する場合には、図７に示すように、ＰＡＲ（ｎ）、ＳＩＢ（ｎ）ＬＣＨ（ｎ）、ｎおよびＲＣＨ（ｎ）の順となり、各部分構造各々を表す図形をノードとした構文木が生成される。
【００５２】
最終的には、照会パターンの末尾にルートを設定した場合は、ルートから照会パターンの最左子孫までの全体構造を表す左向き三角形が生成される。あるいは、照会パターンの文頭にルートを設定した場合は、ルートから最右子孫までの全体構造を表す右向き三角形が生成される。なお、ルートを頭に設定するか、末尾に設定するかは任意であり、以下の説明では、解析対象の文および照会パターン共に末尾にルートが設定されるものとする。
【００５３】
マッチング・スコア演算では、スコア演算部１２０は、上記照会パターンの構文木の全体構造を表す左向き三角形を、解析対象の文の頭から末尾までの範囲に一旦対応付け、ルートノードの最左子ノードＬＣＨ（ｒｏｏｔ）から順に対応付けを開始させる。本発明の実施形態では、上記左向き三角形および右向き三角形は、図３に示した左シーケンス関数１２２および右シーケンス関数１２４に対応し、上記左向き台形および右向き台形は、左リンク関数１２６および右リンク関数１２８に対応する。スコア演算過程では、スコア演算部１２０は、上記関数群１２２〜１２８を再帰的に呼び出して、各図形が表す部分構造と解析対象の文中の範囲との対応付けを試行し、上記台形で表される係り受け関係に対応して係り受け周辺確率によるスコアを与え、最適なマッチング列ｍと、そのパターン周辺確率とを求める。
【００５４】
以下、上記シーケンス関数１２２，１２４およびリンク関数１２６，１２８の処理について詳細を説明する。図８は、本発明の第１の実施形態における（Ａ）左シーケンス関数および（Ｂ）左リンク関数を説明する図である。図９は、本発明の第１の実施形態における（Ａ，Ｂ）左シーケンス関数の疑似コードおよび左シーケンス関数による再帰呼び出しを説明する概念図、並びに（Ｃ，Ｄ）左リンク関数の疑似コードおよび左リンク関数による再帰呼び出しを説明する概念図である。図１０は、本発明の第１の実施形態における（Ａ，Ｂ）右シーケンス関数の疑似コードおよび右シーケンス関数による再帰呼び出しを説明する概念図、並びに（Ｃ，Ｄ）右リンク関数の疑似コードおよび右リンク関数による再帰呼び出しを説明する概念図である。
【００５５】
図８（Ａ）および図９（Ａ，Ｂ）に示すように、左シーケンス関数１２２は、照会パターンのノードｎと、解析対象の文の範囲における開始位置を示す変数ｌと、終了位置を示す変数ｒとを引数として受け取り、
（１）親ノードＰＡＲ（ｎ）がｒ番目の文節に対応しており、
（２）注目ノードｎおよびその子孫が、ｌ，…，ｒ−１の範囲に存在し、
（３）注目ノードｎがＰＡＲ（ｎ）の左側に存在する
ときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。つまり、左シーケンス関数１２２は、注目ノードｎに関し、最左子孫（ＬＣＨ（ｎ）の子孫の左側末端）と親ノードＰＡＲ（ｎ）との間の部分構造を、変数ｌおよび変数ｒで規定される文の範囲に対応付けする関数である。
【００５６】
左シーケンス関数１２２は、上記部分構造の内側の構造を探索するために、上述した条件（２）により、ｌ，…，ｒ−１のいずれかに対し注目ノードｎの対応付けを試行する。試行位置を変数ｉで表すと、注目ノードｎ（＝ｐｊ）がｉ番目の文節ｘｉにマッチする場合、パターンマッチング関数Ｍ（ｘｉ，ｐｊ）は、「真（１）」を出力する（疑似コードではｍａｔｃｈ（ｎ，ｉ）＝ｔｒｕｅ）。注目ノードｎがｘｉにマッチするとき、照会パターンの部分構造中の注目ノードｎから親ノードＰＡＲ（ｎ）への係り受け関係が、文中のｉ番目→ｒ番目の文節ペア間に対応付けられ、係り受け周辺確率ｐ（ｉ，ｒ）が与えられる。
【００５７】
また、注目ノードｎがｘｉにマッチする場合、非交差条件により、注目ノードｎの最左子ノードＬＣＨ（ｎ）およびその子孫は、範囲ｌ，…，ｉ−１に存在することになるので、ＬＣＨ（ｎ）と、変数ｌと、変数ｉとを引数として与えて左シーケンス関数１２２を再帰的に呼び出す。同様に、注目ノードｎの最右子ノードＲＣＨ（ｎ）およびその子孫、並びに兄弟ノードＳＩＢ（ｎ）およびその子孫たちは、非交差条件により、範囲ｉ＋１，…，ｒ−１に存在することになるので、詳細を後述する左リンク関数１２６を再帰的に呼び出す。
【００５８】
図９（Ａ）で示す疑似コードのように、左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）は、少なくとも注目ノードｎがマッチする各試行位置ｉについて、該試行位置ｉの左半分および右半分の範囲に関して、照会パターンの部分構造のさらに内側の対応付けを試行する左シーケンス関数１２２および左リンク関数１２６を再帰的に呼び出す。左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）は、再帰的に呼び出された左シーケンス関数１２２および左リンク関数１２６から戻された各部分演算結果と、上記与えられた係り受け周辺確率ｐ（ｉ，ｒ）との積を計算する。注目ノードｎがマッチする試行位置ｉが複数ある場合には、その最大値が選択されて、部分演算結果として呼び出し元に返される。
【００５９】
右シーケンス関数１２４については、図１０（Ａ，Ｂ）に疑似コードおよび再帰呼び出しを説明する概念図を示す。右シーケンス関数１２４も、左シーケンス関数と同様に、照会パターンのノードｎと、解析対象の文の範囲における開始位置を示す変数ｌと、終了位置を示す変数ｒとを引数として受け取り、
（１）親ノードＰＡＲ（ｎ）がｌ番目の文節に対応しており、
（２）注目ノードｎおよびその子孫が、ｌ＋１，…，ｒの範囲に存在し、
（３）注目ノードｎがＰＡＲ（ｎ）の右側に存在する
ときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。
【００６０】
つまり、右シーケンス関数１２４は、図１０（Ａ）および（Ｂ）に示すように、注目ノードｎに関し、親ノードＰＡＲ（ｎ）と最右子孫（ＲＣＨ（ｎ）の子孫の右側末端）との間の部分構造を、変数ｌおよび変数ｒで規定される文の範囲に対応付けする関数である。右シーケンス関数１２４は、上記部分構造のさらに内側の構造を探索するために、上述した条件（２）により、ｌ＋１，…，ｒのいずれかに対し注目ノードｎの対応付けを試行する。注目ノードｎが文節ｘｉにマッチするとき、照会パターンの部分構造中の注目ノードｎから親ノードＰＡＲ（ｎ）への係り受け関係が文中のｉ番目→ｌ番目の文節ペア間に対応付けられ、係り受け周辺確率ｐ（ｉ，ｌ）が与えられる。また、非交差条件により、注目ノードｎがマッチする試行位置ｉの左半部に注目ノードｎの兄弟およびその子孫、並びにｎの最左子およびその子孫が存在し、右半部に注目ノードｎの最右子およびその子孫が存在する。そこで、右シーケンス関数１２４は、その内側に関してさらに対応付けを試行する右シーケンス関数１２４および右リンク関数１２８を再帰的に呼び出し、戻された各部分演算結果と、上記与えられた係り受け周辺確率ｐ（ｉ，ｌ）との積の最大値を出力する。
【００６１】
図８（Ｂ）および図９（Ｃ，Ｄ）に示すように、左リンク関数１２６は、照会パターンのノードｎと、解析対象の文の範囲における開始位置を示す変数ｌと、終了位置を示す変数ｒとを引数として受け取り、
（１）親ノードＰＡＲ（ｎ）がｒ番目の文節に対応しており、
（２）注目ノードｎがｌ番目の文節に対応しており、
（３）注目ノードｎの最右子ノードＲＣＨ（ｎ）およびその子孫、並びに兄弟ノードＳＩＢ（ｎ）およびその子孫が、ｌ＋１，…，ｒ−１の間に存在し、
（４）注目ノードｎがＰＡＲ（ｎ）の左側に存在する
ときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。つまり、左リンク関数１２６は、注目ノードｎに関し、当該注目ノードｎと親ノードＰＡＲ（ｎ）との間の部分構造を、変数ｌおよび変数ｒで規定される文の範囲に対応付けする関数である。
【００６２】
非交差条件により、最右子ノードＲＣＨ（ｎ）の子孫右側末端は、兄弟ノードＳＩＢ（ｎ）の子孫左側末端よりも左にある。そこで、左リンク関数１２６は、上記部分構造の内側の構造を探索するために、注目ノードｎの最右子ノードＲＣＨ（ｎ）の子孫右側末端と、兄弟ノードＳＩＢ（ｎ）の子孫左側末端との境界を（ｉ，ｉ＋１）の位置で試行する。なお、両者の間に他の文節が存在することもある。
【００６３】
そして、最右子ノードＲＣＨ（ｎ）およびその子孫たちは、ｌ＋１，…，ｉ−１に存在するはずなので、左リンク関数１２６は、各試行位置ｉについて、ＲＣＨ（ｎ）と、変数ｌと変数ｉとを引数として与えて、右シーケンス関数１２４を再帰的に呼び出す。同様に、兄弟ノードＳＩＢ（ｎ）およびその子孫たちは、非交差条件に従い、ｉ＋１，…，ｒ−１の間に存在するはずなので、左リンク関数１２６は、各試行位置ｉについて、ＳＩＢ（ｎ）と、変数ｉ＋１と変数ｒとを引数として与えて、左シーケンス関数１２２を再帰的に呼び出す。図９（Ｃ）で示す疑似コードのように、左リンク関数ｌｅｆｔ＿ｌｉｎｋ（）は、再帰的に呼び出された右シーケンス関数１２４および左シーケンス関数１２２から戻された各部分演算結果の積を計算し、各試行位置ｉにおける最大値を選択して、部分演算結果として呼び出し元に返す。
【００６４】
右リンク関数１２８については、図１０（Ｃ，Ｄ）に疑似コードおよび再帰呼び出しを説明する概念図を示す。右リンク関数１２８も、左リンク関数と同様に、照会パターンのノードｎと、解析対象の文の範囲における開始位置を示す変数ｌと、終了位置を示す変数ｒとを引数として受け取り、
（１）親ノードＰＡＲ（ｎ）がｌ番目の文節に対応しており、
（２）注目ノードｎがｒ番目の文節に対応しており、
（３）注目ノードｎの最左子ノードＬＣＨ（ｎ）およびその子孫、並びに兄弟ノードＳＩＢ（ｎ）およびその子孫が、ｌ＋１，…，ｒ−１の間に存在し、
（４）注目ノードｎがＰＡＲ（ｎ）の右側に存在する
ときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。
【００６５】
つまり、右リンク関数１２８は、図１０（Ｃ）および（Ｄ）に示すように、注目ノードｎに関し、注目ノードｎの親ノードＰＡＲ（ｎ）と当該注目ノードｎとの間の部分構造を、変数ｌおよび変数ｒで規定される文の範囲に対応付けする関数である。右リンク関数１２８は、上記部分構造のさらに内側の構造を探索するために、注目ノードｎの兄弟ノードＳＩＢ（ｎ）の子孫右側末端と、最左子ノードLＣＨ（ｎ）の子孫左側末端との境界を（ｉ，ｉ＋１）の位置で試行する。そして、右リンク関数１２８は、各試行位置ｉについて、兄弟ノードＳＩＢ（ｎ）と変数ｌと変数ｉとを引数として与えて右シーケンス関数１２４を再帰的に呼び出し、最左子ノードＬＣＨ（ｎ）と変数ｉ＋１と変数ｒとを引数として与えて、左シーケンス関数１２２を再帰的に呼び出す。図１０（Ｃ）で示す疑似コードのように、右リンク関数ｒｉｇｈｔ＿ｌｉｎｋ（）は、再帰的に呼び出された右シーケンス関数１２４および左シーケンス関数１２２から戻された各部分演算結果の積を計算し、各試行位置ｉにおける最大値を選択して、部分演算結果として呼び出し元に返す。
【００６６】
以下、本発明の第１の実施形態による、上述した関数群を用いたマッチング・スコア演算処理の詳細について説明する。図１１は、本発明の第１の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理のメインルーチンを示すフローチャートである。図１１に示す処理は、解析対象の文１５０、照会パターン１６０および係り受け周辺確率１７０が指定されたマッチング・スコア演算の指令が与えられたことに応答して、ステップＳ１００から開始する。
【００６７】
ステップＳ１０１では、入力部１１０は、指定された解析対象の文１５０、照会パターン１６０、係り受け周辺確率１７０を入力データとして取得する。解析対象の文は、データベースやファイルなどから取得することができる。係り受け周辺確率は、解析対象の文に対して事前に統計的構文解析が施されている場合は、その解析データとして取得することができる。統計的構文解析が事前に施されていなければ、解析対象の文に対し統計的構文解析を実行して、その解析データとして取得することができる。照会パターンは、データベースやファイルなどから取得することができ、またはユーザ指定された照会文を解釈して取得することができる。
【００６８】
ステップＳ１０２では、スコア演算部１２０は、照会パターンのルートと、０と文長Ｌとを与えて、左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｒｏｏｔ，０、Ｌ）を呼び出す。図１２は、マッチング・スコア演算処理のメインルーチンによる、初期の照会パターンと解析対象の文との対応付けを示す図である。図１２に示すように、照会パターンの左向き三角形によって表される最左子孫からルートまでの全体構造が、解析対象の文頭から末尾までの全範囲に対して対応付けられる。
【００６９】
再び図１１を参照すると、左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｒｏｏｔ，０、Ｌ）以降のすべての再帰的な演算が完了して、戻された演算結果を取得すると、ステップＳ１０３では、出力部１４０は、得られたマッチング・スコアＡと、マッチング列ｍとを演算結果として出力し、ステップＳ１０４で本マッチング演算処理を終了する。
【００７０】
図１３は、本発明の第１の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理において呼び出される左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｎ，ｌ，ｒ）のルーチンを示すフローチャートである。図１３に示す処理は、例えば図１１に示したステップＳ１０２の処理で呼び出され、ステップＳ２００から開始する。ステップＳ２０１では、スコア演算部１２０は、引数として与えられたノードｎが空の値（ｎｕｌｌ）であるか否かを判定する。ステップＳ２０１で、ノードｎがｎｕｌｌであると判定された場合（ＹＥＳ）は、ステップＳ２０２へ処理を分岐し、値「１」を戻り値として、ステップＳ２１７で本処理を終了し、呼び出し元に返す。これは、照会パターンの木構造において枝の末端まで辿り着いたことを意味する。一方、ステップＳ２０１で、ノードｎがｎｕｌｌではないと判定された場合（ＮＯ）は、ステップＳ２０３へ処理を分岐する。
【００７１】
ステップＳ２０３では、スコア演算部１２０は、引数として与えられた変数ｌと変数ｒとが同じ値であるか否かを判定する。ステップＳ２０３で、変数ｌと変数ｒとが同じ値であると判定された場合（ＹＥＳ）は、ステップＳ２０４へ処理を分岐させる。ステップＳ２０４では、スコア演算部１２０は、値「０」を戻り値として、ステップＳ２１７で本処理を終了し、呼び出し元に返す。一方、ステップＳ２０３で、変数ｌと変数ｒとが異なる値であると判定された場合（ＮＯ）は、ステップＳ２０５へ処理を分岐させる。
【００７２】
ステップＳ２０５では、スコア演算部１２０は、動的計画テーブル１３０を参照し、引数（ｎ，ｌ，ｒ）に対応して既に左シーケンス関数の演算結果がキャッシュされているか否かを判定する。ステップＳ２０５で、引数（ｎ，ｌ，ｒ）に対応して演算結果がキャッシュされており、利用可能である場合（ＹＥＳ）は、ステップＳ２０６へ処理を分岐させる。ステップＳ２０６では、スコア演算部１２０は、再度演算する代わりに、動的計画テーブル１３０から引数（ｎ，ｌ，ｒ）に対応するキャッシュ値を読み出し、ステップＳ２１７で本処理を終了させ、呼び出し元にキャッシュ値を返す。本発明の実施形態では、同じ引数のセットに対して、２度以上計算が繰り返されないため、照会パターンのサイズ、解析対象の文の長さに対して、多項式時間で計算することができる。
【００７３】
一方、ステップＳ２０５で、未だキャッシュされていないと判定された場合（ＮＯ）は、ステップＳ２０７へ処理を分岐する。ステップＳ２０７では、スコア演算部１２０は、演算結果の戻り値として返すための部分スコアの最大値を保持する変数ｍａｘを初期化し、ステップＳ２０８〜ステップＳ２１４のループを実行する。ステップＳ２０８〜ステップＳ２１４のループでは、スコア演算部１２０は、現在対応付けを行っている範囲の開始位置ｌから終了位置ｒ−１までの各試行位置ｉについて、ステップＳ２０９〜ステップＳ２１３の処理を実施する。ステップＳ２０９では、スコア演算部１２０は、引数として与えられたノードｎが試行位置ｉの文節ｘｉにマッチするか否かを判定する。ステップＳ２０９で、マッチしないと判定された場合（ＮＯ）には、ステップＳ２１４へ分岐し、次のｉへ処理を進める。
【００７４】
一方、ステップＳ２０９で、ノードｎが試行位置ｉの文節ｘｉにマッチすると判定された場合（ＹＥＳ）には、ステップＳ２１０へ処理を分岐させる。この場合、現在対応付けを行っている範囲の開始位置ｌから試行位置ｉ−１までの範囲内に最左子ノードＬＣＨ（ｎ）およびその子孫が存在し得るため、ステップＳ２１０では、スコア演算部１２０は、ノードｎの最左子ノードＬＣＨ（ｎ）と、変数ｌと、変数ｉとを与えて、左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）を再帰的に呼び出す。左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）から演算結果が戻されると、戻り値は変数Ａに代入される。またマッチする場合、試行位置ｉ＋１から現在対応付けを行っている範囲の終了位置ｌまでの範囲内に最右子ノードＲＣＨ（ｎ）および兄弟ノードＳＩＢ（ｎ）並びにこれらの子孫が存在し得るため、ステップＳ２１１では、スコア演算部１２０は、ノードｎと、変数ｉと、変数ｒとを与えて、左リンク関数ｌｅｆｔ＿ｌｉｎｋ（）を再帰的に呼び出す。左リンク関数ｌｅｆｔ＿ｌｉｎｋ（）から演算結果が戻されると、戻り値は変数Ｂに代入される。
【００７５】
ステップＳ２１２では、スコア演算部１２０は、マッチする試行位置ｉと変数ｒとに対応する係り受け周辺確率ｐ（ｉ，ｒ）と、ステップＳ２１０の左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ＬＣＨ（ｎ），ｌ，ｉ）からの戻り値Ａと、ステップＳ２１１の左リンク関数ｌｅｆｔ＿ｌｉｎｋ（ｎ，ｉ，ｒ）からの戻り値Ｂとの積ｓを計算する。ステップＳ２１３では、スコア演算部１２０は、現在保持しているｍａｘの値と、ステップＳ２１３で計算された積ｓとを比較して、大きな方の値でｍａｘを更新する。
【００７６】
ステップＳ２０８〜ステップＳ２１４では、変数ｌから変数ｒ−１までの各試行位置ｉのうち、ｎにマッチするものに関して、上記係り受け周辺確率ｐ（ｉ，ｒ）と、最左子ノードの左シーケンス関数の演算結果Ａと、左リンク関数の演算結果Ｂとの積ｓがそれぞれ計算され、その中で局所最大の値がｍａｘに保持される。ステップＳ２０８〜ステップＳ２１４のループを抜けると、ステップＳ２１５では、スコア演算部１２０は、動的計画テーブル１３０のｃａｃｈｅ＿ｌｓｅｑ［ｎ，ｌ，ｒ］の配列にｍａｘの値を記憶し、（ｎ，ｌ，ｒ）を計算済みに設定する。ステップＳ２１６では、スコア演算部１２０は、ｍａｘを戻り値として、ステップＳ２１７で本処理を終了させ、呼び出し元に返す。
【００７７】
図１４は、本発明の第１の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理で呼び出される左リンク関数ｌｅｆｔ＿ｌｉｎｋ（ｎ，ｌ，ｒ）のルーチンを示すフローチャートである。図１４に示す処理は、例えば図１３に示したステップＳ２１１の処理で呼び出され、ステップＳ３００から開始する。ステップＳ３０１では、スコア演算部１２０は、引数として与えられた変数ｌと変数ｒとが同じ値であるか否かを判定する。ステップＳ３０１で、変数ｌと変数ｒとが同じ値であると判定された場合（ＹＥＳ）は、ステップＳ３０２へ処理を分岐させる。ステップＳ３０２では、スコア演算部１２０は、値「０」を戻り値として、ステップＳ３１４で本処理を終了し、呼び出し元に返す。一方、ステップＳ３０１で、変数ｌと変数ｒとが異なる値であると判定された場合（ＮＯ）は、ステップＳ３０３へ処理を分岐する。ステップＳ３０３では、スコア演算部１２０は、動的計画テーブル１３０を参照し、引数（ｎ，ｌ，ｒ）に対応して既に左リンク関数の演算結果がキャッシュされているか否かを判定する。ステップＳ３０３で、対応する演算結果がキャッシュされており、利用可能であると判定された場合（ＹＥＳ）は、ステップＳ３０４へ処理を分岐させる。ステップＳ３０４では、スコア演算部１２０は、動的計画テーブル１３０から引数（ｎ，ｌ，ｒ）に対応するキャッシュ値を読み出し、ステップＳ３１４で本処理を終了させ、呼び出し元にキャッシュ値を返す。
【００７８】
一方、ステップＳ３０３で、未だ計算されていないと判定された場合（ＮＯ）は、ステップＳ３０５へ処理を分岐する。ステップＳ３０５では、スコア演算部１２０は、演算結果の戻り値として返すための最大値を保持する変数ｍａｘをで初期化し、ステップＳ３０６〜ステップＳ３１１のループへ処理を進める。ステップＳ３０６〜ステップＳ３１１では、スコア演算部１２０は、現在対応付けを行っている範囲の開始位置ｌから終了位置ｒ−１までの各試行位置ｉについて、ステップＳ３０７〜ステップＳ３１０の処理を実行する。
【００７９】
試行位置ｉは、最右子ノードＲＣＨ（ｎ）の子孫の右側末端と、兄弟ノードＳＩＢ（ｎ）の子孫の左側末端との境界を表す。現在対応付けを行っている範囲の開始位置ｌから試行位置ｉ−１までの範囲内に最右子ノードＲＣＨ（ｎ）およびその子孫が存在し得る。そこで、ステップＳ３０７では、スコア演算部１２０は、引数として与えられたノードｎの最右子ノードＲＣＨ（ｎ）と、変数ｌと、変数ｉとを与えて、右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（）を再帰的に呼び出す。右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（）から演算結果が戻されると、戻り値は変数Ａに代入される。
【００８０】
また、試行位置ｉ＋１から、現在対応付けを行っている範囲の終了位置ｒ−１までの範囲内に兄弟ノードＳＩＢ（ｎ）およびその子孫が存在するため、ステップＳ３０８では、スコア演算部１２０は、引数として与えられたノードｎの兄弟ノードＳＩＢ（ｎ）と、変数ｉ＋１と、変数ｒとを与えて、左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）を再帰的に呼び出す。左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）から演算結果が戻されると、戻り値は変数Ｂに代入される。ステップＳ３０９では、ステップＳ３０７の右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（）からの戻り値Ａと、ステップＳ３０８の左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）からの戻り値Ｂとの積ｓを計算する。ステップＳ３１０では、現在保持しているｍａｘの値と、ステップＳ３０９で計算された積ｓとを比較して、大きな方の値でｍａｘを更新する。
【００８１】
ステップＳ３０６〜ステップＳ３１１では、変数ｌから変数ｒ−１までの各試行位置ｉについて、上記最右子ノードに関する右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（）の演算結果Ａと、兄弟ノードに関する左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）の演算結果Ｂとの積ｓが求められ、その中で局所最大の値がｍａｘに保持される。ステップＳ３０６〜ステップＳ３１１のループを抜けると、ステップＳ３１２では、スコア演算部１２０は、動的計画テーブル１３０のｃａｃｈｅ＿ｌｌｉｎｋ［ｎ，ｌ，ｒ］の配列にｍａｘの値を記憶して、（ｎ，ｌ，ｒ）を計算済みに設定する。ステップＳ３１３では、スコア演算部１２０は、ｍａｘの値を戻り値として、ステップＳ３１４で本処理を終了させ、呼び出し元に返す。
【００８２】
図１５は、上記左シーケンス関数、左リンク関数、右シーケンス関数および右リンク関数の相互再帰的な呼び出しを説明する図である。マッチング・スコア演算処理は、メインルーチンから、照会パターンのＥｉｓｎｅｒ構文木のルートノード（全体構造を表す。）および解析対象の文の全範囲を引数として左シーケンス関数ｌｅｆｔ＿ｓｅｑ（）が呼び出されて開始する。なお、文頭にルートが設定される場合には、右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（）が呼び出される。左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｎ，ｌ，ｒ）は、ノードｎにマッチする各試行位置ｉ＊で、現在対応付けを行っている範囲（ｌ，…，ｒ）を分割し、親反対側の左半分の範囲（ｌ，…，ｉ）について最左子ノードＬＣＨ（ｎ）を引数として順方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ＬＣＨ（ｎ），ｌ，ｉ）を再帰的に呼び出すとともに、親側の右半分の範囲（ｉ，…，ｒ）についてノードｎを引数として順方向の左リンク関数ｌｅｆｔ＿ｌｉｎｋ（ｎ，ｉ，ｒ）を再帰的に呼び出す。
【００８３】
左リンク関数ｌｅｆｔ＿ｌｉｎｋ（ｎ，ｌ，ｒ）は、各試行位置ｉで現在対応付けを行っている範囲（ｌ，…，ｒ）を分割し、親反対側の左半分の範囲（ｌ，…，ｉ）について最右子ノードＲＣＨ（ｎ）を引数として逆方向の右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（ＲＣＨ（ｎ），ｌ，ｉ）を再帰的に呼び出し、親側の右半分の範囲（ｉ＋１，…，ｒ）について兄弟ノードＳＩＢ（ｎ）を引数として順方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ＳＩＢ（ｎ），ｉ＋１，ｒ）を再帰的に呼び出す。
【００８４】
右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（ｎ，ｌ，ｒ）は、ノードｎにマッチする各試行位置ｉ＊で現在対応付けを行っている範囲を分割し、親側の左半分の範囲（ｌ，…，ｉ）についてｎを引数として順方向の右リンク関数ｒｉｇｈｔ＿ｌｉｎｋ（ｎ，ｌ，ｉ）を再帰的に呼び出すとともに、親反対側の右半分の範囲（ｉ，…，ｒ）について最右子ノードＲＣＨ（ｎ）を引数として順方向の右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（ＲＣＨ（ｎ），ｉ，ｒ）を再帰的に呼び出す。右リンク関数ｒｉｇｈｔ＿ｌｉｎｋ（ｎ，ｌ，ｒ）は、各試行位置ｉで現在の範囲を分割し、親側の左半分の範囲（ｌ，…，ｉ）について兄弟ノードＳＩＢ（ｎ）を引数として順方向の右シーケンス関数ｒｉｈｇｔ＿ｓｅｑ（ＳＩＢ（ｎ），ｌ，ｉ）を再帰的に呼び出し、親反対側の右半分の範囲（ｉ＋１，…，ｒ）について最左子ノードＬＣＨ（ｎ）を引数として逆方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ＬＣＨ（ｎ），ｉ＋１，ｒ）を再帰的に呼び出しする。
【００８５】
図１６は、上記左シーケンス関数、左リンク関数、右シーケンス関数および右リンク関数の相互再帰的な呼び出しにより、照会パターンの全体構造から末端までの対応付けが行われる様子を示す図である。まず、最上段の左向き三角形で表される照会パターンの全体構造が、解析対象の文の文頭から末尾までの全範囲に対応付けられて、ルートの最左子ノードＬＣＨ（ｒｏｏｔ）を引数とした左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ｂ）が呼び出される。左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ｂ）は、ノードＢにマッチする試行位置で、対応付けを行っている範囲を分割し、左半分の範囲について最左子ノードＬＣＨ（Ｂ）を引数とした左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ａ）を再帰的に呼び出す。同時に、左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ｂ）は、右半分の範囲については、ノードＢを引数とした左リンク関数ｌｅｆｔ＿ｌｉｎｋ（Ｂ）を再帰的に呼び出す。ここで、ノードＢからルートへの係り受け周辺確率がスコアとして与えられる。
【００８６】
左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ａ）は、ノードＡにマッチする試行位置で、左半分の範囲について最左子ノードＬＣＨ（Ａ）を引数とした左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｎｕｌｌ）を呼び出す。左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ａ）は、同時に、右半分の範囲については、ノードＡを引数とした左リンク関数ｌｅｆｔ＿ｌｉｎｋ（Ａ）を呼び出す。ここで、ノードＡからノードＢへの係り受け周辺確率がスコアとして与えられる。左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｎｕｌｌ）に対しては、照会パターンの末端に達したことを示す１が返される。
【００８７】
一方、左リンク関数ｌｅｆｔ＿ｌｉｎｋ（Ｂ）は、対応付けている範囲内で、最右子ノードＲＣＨ（Ｂ）および兄弟ノードＳＩＢ（Ｂ）の子孫間を境界する位置を試行し、左半分の範囲について最右子ノードＲＣＨ（Ｂ）を引数とした右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（Ｃ）を、右半分の範囲について兄弟ノードＳＩＢ（Ｂ）を引数とした左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ｄ）を、各試行位置毎に呼び出す。
【００８８】
右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（Ｃ）について説明を続けると、右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（Ｃ）は、ノードＣにマッチする試行位置があればその位置で、左半分の範囲についてノードＣを引数とした右リンク関数ｒｉｇｈｔ＿ｌｉｎｋ（Ｃ）を呼び出す。ここで、ノードＣにマッチする試行位置があればノードＣからノードＢへの係り受け周辺確率がスコアとして与えられる。ノードＣにマッチする試行位置がなければ０が戻される。右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（Ｃ）は、同時に、右半分の範囲については、最右子ノードＲＣＨ（Ｃ）を引数とした右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（ｎｕｌｌ）を呼び出す。右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（ｎｕｌｌ）に対しては、照会パターンの末端まで達したため１が返される。右リンク関数ｒｉｇｈｔ＿ｌｉｎｋ（Ｃ）は、対応付けている範囲内で、兄弟ノードＳＩＢ（Ｃ）および最左子ノードＬＣＨ（Ｃ）の子孫間を境界する位置を試行し、左半分の範囲について兄弟ノードＳＩＢ（Ｃ）を引数とした右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（ｎｕｌｌ）を、右半分の範囲について最左子ノードＬＣＨ（Ｃ）を引数とした左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｎｕｌｌ）を、それぞれ試行位置毎に呼び出す。右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（ｎｕｌｌ）および左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｎｕｌｌ）に対しては、照会パターンの末端まで達したため１が返される。上述した処理は、左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ｄ）についても同様である。
【００８９】
さらに図１６中に吹き出しで、照会パターンのノードＡ’とノードＢ’との間にノードＡ’の兄弟ノードであるノードＥ’が存在する場合は、上記左リンク関数ｌｅｆｔ＿ｌｉｎｋ（Ａ）は、対応付けている範囲内で、最右子ノードＲＣＨ（Ａ）および兄弟ノードＳＩＢ（Ａ）の子孫間を境界する位置を試行し、左半分の範囲について最右子ノードＲＣＨ（Ａ）を引数とした右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ（ｎｕｌｌ）を、右半分の範囲について兄弟ノードＳＩＢ（Ａ）を引数とした左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ｅ）を各試行位置毎に呼び出す。左シーケンス関数ｌｅｆｔ＿ｓｅｑ（Ｅ）については、上記と同様であり、ノードＥにマッチする試行位置が見つかった段階でノードＥ’からノードＢへの係り受け周辺確率がスコアとして与えられ返される。
【００９０】
上述したような再帰的な呼び出しを繰り返すことによって、照会パターンの各末端を対応付けた段階でその系列の再帰的な呼び出しを終了し、各部分演算における係り受け周辺確率の積の最大値が戻されていく。最終的に、最適なマッチングｍでのパターン周辺確率を近似する最大化された係り受け周辺確率の積が、左シーケンス関数ｌｅｆｔ＿ｓｅｑ（ｒｏｏｔ）に返される。
【００９１】
図１５および図１６に示すような再帰的な呼び出しを相互に行うことによって、照会パターンの全体構造から末端のノードの対応付けまでが行われ、局所最大の周辺確率を与える各マッチング位置が検索され、大域的最大となるパターン周辺確率の近似値を与える最適なマッチング列ｍが決定され、同時に、大域的最大となるパターン周辺確率が近似計算される。
【００９２】
なお、上述までは、解析対象の文に対するマッチング・スコアの演算処理について説明してきた。以下、上記マッチング・スコアの演算処理組み込んで、係り受け構造を考慮した情報検索を行う情報検索システムについて説明する。図１７は、第１の実施形態によるマッチング・スコア演算機能を組み込んだ情報検索システムの機能ブロック図である。図１７に示す情報検索システムを構成する検索エンジン１９０は、同様に、コンピュータ装置上に実現される。検索エンジン１９０は、ユーザとの入出力のインタフェースとなる検索インタフェース１９２と、上述までの入力部１１０と、スコア演算部１２０と、出力部１４０とを含む。さらに、情報検索システムは、検索対象の文書を格納する文書データベース１９４を含み、検索エンジン１９０は、文書データベース１９４にアクセス可能とされている。なお、各文書は、１以上の文を含み、各文書と各文との関係、例えば文書内の文の位置などは、予め対応付けられているものとする。同様に、各文は、予め形態素解析などの文字列解析が実施されており、文節または単語の列として構成され、係り受け周辺確率のデータも与えられているものとする。
【００９３】
検索インタフェース１９２は、ユーザから、照会パターンを規定する検索クエリと、必要に応じて条件とを含むユーザ入力１９６を取得する。条件は、検索結果に含めるマッチング・スコアに対する閾値、その他文書の検索範囲を指定したりするための条件を含む。なお、条件は、ユーザから与えられてもよいし、システムのデフォルト値として与えられてもよい。検索クエリは、照会パターンを規定するパターン列ｐおよびその親子関係を定義するｐａｒ（ｐ，ｉ）を直接与えてもよいし、所定のフォーマットに従って記述された文字列を解釈して照会パターンのパターン列ｐおよびｐａｒ（ｐ，ｉ）を与えてもよし、さらに予め照会パターンを記述したファイルなどがあれば、そのファイル名等で与えてもよい。
【００９４】
検索インタフェース１９２は、ユーザ入力１９６を受け取ると、照会パターンと検索範囲の文集合の各文を指定する文識別値を入力部１１０に渡し、各文のマッチング・スコアの演算を依頼する。入力部１１０は、解析対象の文を指定する情報に従い、文書データベース１９４から文およびその係り受け周辺確率のデータを取得して、解析対象の文と、照会パターンと、係り受け周辺確率とを入力データとしてスコア演算１２０に渡す。あるいは、他の実施形態では、検索インタフェース１９２は、文書データベース１９４から解析対象の文およびその係り受け周辺確率のデータを取得して、直接入力部１１０に渡して、各文のマッチング・スコアの演算を依頼することもできる。
【００９５】
スコア演算部１２０は、与えられた文に対してマッチング・スコアを計算し、出力部１４０は、与えられた各文に対するマッチング列ｍおよびスコアを検索インタフェース１９２に返す。検索インタフェース１９２は、依頼した各文に対するマッチング・スコアおよびマッチング列を取得すると、ユーザ指定された閾値、またはデフォルトの閾値を基準として、閾値以上のスコアが与えられた文の集合を取得し、検索結果１９８をユーザに提示する。ここで、閾値のレベルを調整することで、情報検索における適合率および再現率を調整することが可能となる。これにより、より適合率を高めて正確な評判情報を取得したり、再現率を高めて製品の不具合を示す全ての文を網羅して取得したりすることができる。
【００９６】
また、文書と文との関係が予め対応付けられてれば、例えばマッチした文書のサマリや、文書内のマッチした箇所周辺のサマリ上で、マッチングした箇所を強調表示することができる。さらに他の実施形態では、文書等の文集合内の各文にわたるスコアの総和を求めることもできる。これにより、例えば製品の不具合を示す文がどの程度存在するのかを知ることができるようになる。
【００９７】
以上説明した第１の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標し、確率として取り扱うことができるパターン周辺確率を効率的に近似計算することができる。上述したようにパターン周辺確率は、全解析候補中のパターンを部分木として含む構文木の解析候補が生成される周辺確率であり、全解析候補中のパターンを部分木として含む構文木解析候補の解析確率の総和に一致する。したがって、従来では、全解析候補を列挙し、パターンマッチングにより照会パターンにマッチする構文木の候補を抽出し、その候補の解析確率の総和を求める必要があった。この場合、解析候補が文長に対して指数的に増大してしまうため、計算量的に困難があり、現実的ではなかった。
【００９８】
これに対して本発明の第１の実施形態によるコンピュータ装置１００では、パターン周辺確率を上記解析対象の文の文節ペア間に与えられる係り受け周辺確率の積で近似し、動的計画法を適用することによって、全解析候補を列挙することなく効率的に近似計算することができる。本発明の第１の実施形態による動的計画法が適用されたスコア演算処理では、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行する関数群が再帰的に呼び出され、上記部分演算結果が照会パターンの部分構造および文の範囲の内側に関して再帰的に算出され、これにより、大域的な照会パターンに対するパターン周辺確率が求められる。なお、計算量は、動的計画法が適用でき、演算コストを記憶コストに交換することができるため、文長Ｌ、パターンサイズＭに対してＯ（Ｌ３Ｍ）程度で済む。
【００９９】
［第２の実施形態］
以下、本発明の第２の実施形態によるマッチング・スコアを演算するコンピュータ装置について説明する。第２の実施形態によるコンピュータ装置は、第１の実施形態で算出したパターン周辺確率に代えて、パターン出現回数期待値をマッチング・スコアとして算出する。図１８は、本発明の第２の実施形態によるコンピュータ装置２００の機能ブロックを示す。図１８に示すコンピュータ装置２００は、第１の実施形態と同様の構成を有しているが、入力部２１０に入力される入力データと、スコア演算部２２０が備える関数群と、出力部２４０が出力する演算結果が相違する。
【０１００】
本発明の第２の実施形態における入力データは、解析対象の文２５０と、照会パターン２６０とを含む点で第１の実施形態と同様であるが、第１の実施形態における係り受け周辺確率ｐ（ｉ，ｊ）に代えて、重みｆ（ｉ，ｊ）が取得される点で相違する。重みｆ（ｉ，ｊ）は、第１の実施形態の係り受け周辺確率と同様に、ｉ番目の文節からｊ番目の文節への係りやすさを指標するものである。重みｆ（ｉ，ｊ）は、係り受け条件付き対数線形モデルで定義されるものであり、文節ｉおよび文節ｊ間の特徴ベクトルφ（ｉ，ｊ）と、学習データより推定される重みベクトルｗとの内積の指数関数で計算することができる。重みｆ（ｉ，ｊ）は、統計的構文解析の過程で生成されるデータである。
【０１０１】
スコア演算部２２０は、入力部２１０が取得した入力データを用いて、照会パターン２６０に対する解析対象の文２５０のマッチング・スコアを演算する。第２の実施形態においては、解析対象の文２５０に対し存在可能な全解析候補の中のパターンが出現する回数の期待値、すなわちパターン出現回数期待値をマッチング・スコアとして算出する。パターン出現回数期待値は、本質的には、解析候補の構文木に出現するパターンの総数と、該構文木の解析確率との積の全解析候補にわたる総和に一致する。各解析候補の解析確率Ｐは、解析候補の構文木に含まれる係り受けペアの上記重みｆ（ｉ，ｊ）の関数として表される。より具体的には、各解析候補の解析確率Ｐは、解析候補の構文木に含まれる係り受けペアの重みｆ（ｉ，ｊ）の積、すなわち下記式（３）で表される。なお、下記式（３）中のＺは、分配関数であり、各解析候補の重みｆの積を全候補にわたり総和を取った値であり、上記重みｆの積を分配関数Ｚで割ることにより、全候補での総和が１となり、規格化された解析確率として用いることができるようになる。
【０１０２】
【数３】
0005710317.tif 000004
【０１０３】
本発明の第２の実施形態において、マッチング・スコアは、数学的には、以下の式（４）で表す値を求めることになる。下記式（４）は、本実施形態では、第１の実施形態とは異なり、重みｆ（ｉ，ｊ）が与えられ、外側が第１の実施形態のｍａｘ関数ではなくマッチング列ｍでの総和Σとなっており、分配関数Ｚも計算可能であるため、最大のスコアを与えるマッチング列ｍを決定することはできないが、近似なしに確率Ｐをそのまま計算することができる。また、外側がｍについての総和Σとなっているため、照会パターンが解析候補中に出現する事象分だけ確率Ｐが加算されていき、結果として、解析候補での照会パターンの出現回数とその解析確率との積の総和が求められる。
【０１０４】
【数４】
0005710317.tif 000005
【０１０５】
スコア演算部２２０は、左右のシーケンス関数２２２，２２４、左右のリンク関数２２６，２２８および左右のマッチ関数２３０，２３２を備えており、これらの関数群を再帰的に呼び出すことで、全解析候補を列挙することなく、上記パターン出現回数期待値を演算する。より具体的には、スコア演算部２２０は、複数の関数群２２２〜２３２を用いて、照会パターン２６０の部分構造と解析対象の文２５０の範囲との対応付けを試行し、照会パターンが出現する事象にわたる上記重みの積和の部分演算結果を、上記部分構造および範囲の内側に関して再帰的に算出する。一度計算された部分演算結果は、第１の実施形態と同様に、動的計画テーブル２３４内に格納され、演算過程で再び必要になった際に、再度演算する代わりに動的計画テーブル２３４に格納された値が再利用される。第２の実施形態では、照会パターン２６０の部分構造と解析対象の文２５０の範囲との対応付けを試行の過程では、パターンの構造が再帰的にたどられていたが、第２の実施形態における対応付けの試行過程では、解析対象の文の構造が再帰的にたどられながら、パターンの構造も再帰的にたどられる。
【０１０６】
出力部２４０は、スコア演算部２２０が算出したパターン出現回数期待値（マッチング・スコア）を含む演算結果２８０を出力する。第２の実施形態では、マッチング列ｍの総和が計算されるため、マッチング列ｍは求められず、上記パターン出現回数期待値のみが演算結果２８０に含められる。
【０１０７】
以下、図１９〜図２３を参照しながら、本発明の第２の実施形態によるマッチング・スコア演算処理について説明する。図１９は、本発明の第２の実施形態によるマッチング・スコア演算方法を概念的に説明する図である。本発明の第２の実施形態では、解析対象の文に対してＥｉｓｎｅｒ構文木と同様の構文木を考える。図１９中の三角形および台形は、それぞれ、１次のＥｉｓｎｅｒアルゴリズムにおける完全スパンおよび非完全スパンに相当する。さらに図１９中の「＊」が付された台形は、照会パターンに規定される係り受け関係に対応付けられた文の構文木上の係り受け関係であることを意味している。なお、図１８には、構文解析結果の構文木の一例を示すが、実際には、あらゆる構文解析結果に対してマッチング・スコアの総和を計算する。
【０１０８】
本発明の第２の実施形態では、照会パターンおよび解析対象の文の両方に関して動的計画法を適用し、解析対象の構文木の構築を行うと同時に、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行する。スコア演算部２２０は、照会パターンのルートノード（全体構造）を上記文の構文木のルートノード（全体範囲）に対応付けるところから開始する。まず、照会パターンの全体構造を表す左向き三角形を、解析対象の文の頭から末尾までの範囲に一旦対応付け、照会パターンのルートノードの最左子ノードＬＣＨ（ｒｏｏｔ）から順に対応付けを行う。
【０１０９】
本発明の実施形態では、上記左向き三角形および右向き三角形は、図１８に示した左シーケンス関数２２２および右シーケンス関数２２４に対応し、印なし上記左向き台形および右向き台形は、左リンク関数２２６および右リンク関数２２８に対応し、「＊」印有りの上記左向き台形および右向き台形は、左マッチ関数２３０および右マッチ関数２３２に対応する。スコア演算過程では、スコア演算部２２０は、上記関数群２２２〜２３２を再帰的に呼び出して、照会パターンの部分構造と解析対象の文中の範囲との対応付けを試行し、上記台形で表される係り受け関係に対応して重み（ｉ，ｊ）によるスコアを与えるとともに、照会パターンの係り受け関係をマッチする（「＊」印有り）か、マッチしない（印なし）かの場合に分けてそれぞれ処理を進め、照会パターンの構造と文の構造との両方を辿りながら、マッチング・スコアを算出する。
【０１１０】
以下、本発明の第２の実施形態で用いられるシーケンス関数２２２，２２４、リンク関数２２６，２２８およびマッチ関数２３０，２３２について詳細を説明する。図２０は、本発明の第２の実施形態における左シーケンス関数を説明する図である。図２１は、本発明の第２の実施形態における（Ａ）左リンク関数および（Ｂ）左マッチ関数を説明する図である。図２２は、本発明の第２の実施形態における（Ａ）左シーケンス関数（Ｂ）左リンク関数および（Ｃ）左マッチ関数の疑似コードを示す図である。図２３は、本発明の第２の実施形態における（Ａ）右シーケンス関数（Ｂ）右リンク関数および（Ｃ）右マッチ関数の疑似コードを示す図である。
【０１１１】
図２０および図２２（Ａ）に示すように、第２の実施形態の左シーケンス関数２２２は、照会パターンのノードｎと、解析対象の文の範囲における開始位置を示す変数ｌと、終了位置を示す変数ｒとを引数として受け取り、
（１）親ノードＰＡＲ（ｎ）がｒ番目の文節に対応しており、
（２）文の構文木上でのＰＡＲ（ｎ）の左子孫末端がｌで、したがってｎとその子孫はｌ，…ｒ−１の範囲に存在し、
（３）注目ノードｎがＰＡＲ（ｎ）の左側に存在する
ときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左シーケンス関数２２２は、注目ノードｎに関し、注目ノードｎの親ノードＰＡＲ（ｎ）の左子孫末端と親ノードＰＡＲ（ｎ）との間の部分構造を、変数ｌおよび変数ｒで規定される文の範囲に対応付けする関数である。
【０１１２】
左シーケンス関数２２２は、上記照会パターンの部分構造および上記文の範囲について内側の構造を探索するために、上述した条件（２）により、範囲ｌ，…，ｒ−１のいずれかに対し、文の構文木上の親ノードＰＡＲ（ｎ）の最左子ノード（最左子ノードがパターン上の注目ノードｎにマッチする場合もあり、マッチしない場合もある。）の対応付けを試行する。試行位置を変数ｉで表すと、このとき文中のｉ番目→ｒ番目の文節ペア間に親ノードＰＡＲ（ｎ）の最左子ノードから親ノードＰＡＲ（ｎ）への係り受け関係が試行され、重みｆ（ｉ，ｒ）が与えられる。なお、ここでいう試行位置ｉは、照会パターン上の最左子ノードではなく、文の構文木上での親ノードＰＡＲ（ｎ）の最左子ノード（注目ノードｎにマッチする場合には、パターン上の最左子ノードにも一致する。）の位置である点に留意されたい。
【０１１３】
注目ノードｎが、親ノードＰＡＲ（ｎ）の最左子ノードが対応付けられている文節ｘｉにマッチする場合（図２０（Ａ））、注目ノードｎの最右子ノードＲＣＨ（ｎ）およびその子孫、並びに兄弟ノードＳＩＢ（ｎ）およびその子孫たちは、非交差条件により、範囲ｉ＋１，…，ｒ−１に存在し得るので、詳細を後述する左マッチ関数２３０を再帰的に呼び出す。同時に、注目ノードｎの最左子ノードＬＣＨ（ｎ）およびその子孫は、範囲ｌ，…，ｉ−１に存在し得るので、ＬＣＨ（ｎ）と、変数ｌと、変数ｉとを引数として与えて左シーケンス関数２２２を再帰的に呼び出す。
【０１１４】
一方、注目ノードｎが、親ノードＰＡＲ（ｎ）の最左子ノードが対応付けられている文節ｘｉにマッチしない場合（図２０（Ｂ）。マッチさせない場合を含む。）は、注目ノードｎおよびその子孫たちは、範囲ｉ＋１，…，ｒ−１に存在し得るので、詳細を後述する左リンク関数２２６を再帰的に呼び出す。残りに対応するパターン要素は無いので、範囲ｌ，…，ｉ−１については、ｎｕｌｌと、変数ｌと、変数ｉとを引数として与えて左シーケンス関数２２２を呼び出す。
【０１１５】
図２２（Ａ）で示す疑似コードのように、左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（）は、注目ノードｎがマッチする各試行位置ｉについて、試行位置ｉの左半分および右半分の範囲に関して、着目している照会パターンの構造の内側の次の部分構造に進め、対応付けを試行する左シーケンス関数２２２および左マッチ関数２３０を再帰的に呼び出す。左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（）は、再帰的に呼び出された左シーケンス関数２２２および左マッチ関数２３０から戻された各部分演算結果と、上記与えられた重みｆ（ｉ，ｒ）との積を計算し、部分スコアに加算する。本実施形態では、さらに、左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（）は、各試行位置ｉについて、試行位置ｉの左半分の範囲に関して、ｎｕｌｌを与えて左シーケンス関数２２２を呼び出すとともに、試行位置ｉの右半分の範囲に関して、着目している照会パターンの部分構造のまま、対応付けを試行する左リンク関数２２６を再帰的に呼び出す。左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（）は、各試行位置ｉについて、左シーケンス関数２２２から戻された部分演算結果（１である）と、再帰的に呼び出された左リンク関数２２６から戻された部分演算結果と、上記与えられた重みｆ（ｉ，ｒ）との積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。
【０１１６】
左リンク関数２２６は、図２１（Ａ）および図２２（Ｂ）に示すように、照会パターンのノードｎと、解析対象の文の範囲における開始位置を示す変数ｌと、終了位置を示す変数ｒとを引数として受け取り、
（１）親ノードＰＡＲ（ｎ）がｒ番目の文節に対応しており、
（２）文の構文木上でのＰＡＲ（ｎ）の最左子ノードがｌ番目の文節に対応しており、かつ、注目ノードｎとマッチしておらず、
（３）文の構文木上でのＰＡＲ（ｎ）の最左子ノード（ｌ番目の文節）の右子孫と、最左子ノードの兄弟とが、非交差条件より、ｌ＋１，…，ｒ−１の間に存在し、
（４）注目ノードｎがＰＡＲ（ｎ）の左側に存在する
ときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左リンク関数２２６は、注目ノードｎに関し、親ノードＰＡＲ（ｎ）の最左子ノードの左側末端と親ノードＰＡＲ（ｎ）との間の部分構造を、変数ｌおよび変数ｒで規定される文の範囲に対応付けする関数である。
【０１１７】
非交差条件により、最左子ノードの右子孫と、最左子ノードの兄弟ノードの子孫とは隣り合っている。そこで、左リンク関数２２６は、最左子ノードの右子孫の右側末端と、最左子ノードの兄弟ノードの子孫左側末端との境界を（ｉ，ｉ＋１）の位置で試行する。
【０１１８】
そして、最左子ノードの兄弟の子孫は、ｉ＋１，…，ｒ−１の間に存在し得るので、左リンク関数２２６は、ここに注目ノードｎを対応させて、注目ノードｎと、変数ｉ＋１と変数ｒとを引数として与えて左シーケンス関数２２２を再帰的に呼び出す。一方、最左子ノードの右子孫はｌ＋１，…，ｉ−１に存在し得るが、ここに対応させる照会パターンのノードは無いので、ｎｕｌｌと、変数ｌと変数ｉとを引数として与えて、右シーケンス関数２２４を呼び出す。図２２（Ｂ）で示す疑似コードのように、左リンク関数ｌｅｆｔ＿ｌｉｎｋ＿ｅ（）は、各試行位置ｉについて、右シーケンス関数２２４の部分演算結果と、再帰的に呼び出された左シーケンス関数２２２から戻された部分演算結果の積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。
【０１１９】
左マッチ関数２３０は、図２１（Ｂ）および図２２（Ｃ）に示すように、照会パターンのノードｎと、解析対象の文の範囲における開始位置を示す変数ｌと、終了位置を示す変数ｒとを引数として受け取り、
（１）親ノードＰＡＲ（ｎ）がｒ番目の文節に対応しており、
（２）文の構文木上でのＰＡＲ（ｎ）の最左子ノードがｌ番目の文節に対応しており、かつ、注目ノードｎとマッチしており、
（３）文の構文木上でのＰＡＲ（ｎ）の最左子ノードの右子孫と、最左子ノードの兄弟とが、非交差条件より、ｌ＋１，…，ｒ−１の間に存在し、
（４）注目ノードｎがＰＡＲ（ｎ）の左側に存在する
ときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左マッチ関数２３０は、注目ノードｎに関し、注目ノードｎの左側末端と親ノードＰＡＲ（ｎ）との間の部分構造を、変数ｌおよび変数ｒで規定される文の範囲に対応付けする関数である。
【０１２０】
非交差条件により、最左子ノードの右子孫と、最左子ノードの兄弟ノードの子孫とは隣り合っている。そこで、左マッチ関数２３０は、最左子ノードの右子孫の末端と、最左子ノードの兄弟ノードの子孫左側末端との境界を（ｉ，ｉ＋１）の位置で試行する。そして、最左子ノードの右子孫は、ｌ＋１，…，ｉの間に存在し得るので、左マッチ関数２３０は、ここに最右子ノードＲＣＨ（ｎ）を対応させて、最右子ノードＲＣＨ（ｎ）と、変数ｌと変数ｉとを引数として与えて右シーケンス関数２２４を再帰的に呼び出す。同時に、最左子ノードの兄弟の子孫は、ｉ＋１，…，ｒ−１の間に存在し得るので、左マッチ関数２３０は、ここに兄弟ノードＳＩＢ（ｎ）を対応させて、兄弟ノードＳＩＢ（ｎ）と、変数ｉ＋１と変数ｒとを引数として与えて左シーケンス関数２２２を再帰的に呼び出す。図２２（Ｃ）で示す疑似コードのように、左マッチ関数ｌｅｆｔ＿ｍａｔｃｈ＿ｅ（）は、各試行位置ｉについて、再帰的に呼び出された右シーケンス関数２２４および左シーケンス関数２２２から戻された各部分演算結果の積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。
【０１２１】
なお、右シーケンス関数２２４、右リンク関数２２８および右マッチ関数２３２については、図２３（Ａ）、（Ｂ）および（Ｃ）にそれぞれ疑似コードが示されており、上述までの左シーケンス関数２２２、左リンク関数２２６および左マッチ関数２３０についての説明や、第１の実施形態での説明から容易に理解できるため、詳細な説明は割愛する。
【０１２２】
図２４は、上記左右のシーケンス関数、左右のリンク関数および左右のマッチ関数の相互再帰的な呼び出しを説明する図である。マッチング・スコア演算処理は、メインルーチンから、照会パターンの構文木のルートノード（全体構造を表す。）と解析対象の文の全範囲とを引数として左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（）が呼び出されて開始する。
【０１２３】
左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（ｎ，ｌ，ｒ）は、ノードｎにマッチする場合として、ノードｎにマッチする各試行位置ｉ＊で、現在対応付けを行っている範囲（ｌ，…，ｒ）を分割し、親反対側の左半分の範囲（ｌ，…，ｉ）について順方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（ＬＣＨ（ｎ），ｌ，ｉ）を再帰的に呼び出すとともに、親側の右半分の範囲（ｉ，…，ｒ）について順方向の左マッチ関数ｌｅｆｔ＿ｍａｔｃｈ＿ｅ（ｎ，ｉ，ｒ）を再帰的に呼び出す。左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（ｎ，ｌ，ｒ）は、さらにノードｎにマッチしない場合として、各試行位置ｉで現在対応付けを行っている範囲（ｌ，…，ｒ）を分割し、親反対側の左半分の範囲（ｌ，…，ｉ）について順方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（ｎｕｌｌ，ｌ，ｉ）を再帰的に呼び出すとともに、親側の右半分の範囲（ｉ，…，ｒ）について順方向の左リンク関数ｌｅｆｔ＿ｌｉｎｋ＿ｅ（ｎ，ｉ，ｒ）を再帰的に呼び出す。
【０１２４】
左リンク関数ｌｅｆｔ＿ｌｉｎｋ＿ｅ（ｎ，ｌ，ｒ）は、各試行位置ｉで現在対応付けを行っている範囲（ｌ，…，ｒ）を分割し、親反対側の左半分の範囲（ｌ，…，ｉ）について逆方向の右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ＿ｅ（ｎｕｌｌ，ｌ，ｉ）を再帰的に呼び出し、親側の右半分の範囲（ｉ＋１，…，ｒ）について順方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（ｎ，ｉ＋１，ｒ）を再帰的に呼び出す。一方、左マッチ関数ｌｅｆｔ＿ｍａｔｃｈ＿ｅ（ｎ，ｌ，ｒ）は、各試行位置ｉで現在対応付けを行っている範囲（ｌ，…，ｒ）を分割し、親反対側の左半分の範囲（ｌ，…，ｉ）について、逆方向の右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ＿ｅ（ＲＣＨ（ｎ），ｌ，ｉ）を再帰的に呼び出し、親側の右半分の範囲（ｉ＋１，…，ｒ）について順方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（ＳＩＢ（ｎ），ｉ＋１，ｒ）を再帰的に呼び出す。
【０１２５】
右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ＿ｅ（ｎ，ｌ，ｒ）は、ノードｎにマッチする場合として、ノードｎにマッチする各試行位置ｉ＊で範囲を分割し、親側の左半分の範囲（ｌ，…，ｉ）について順方向の右マッチ関数ｒｉｇｈｔ＿ｍａｔｃｈ＿ｅ（ｎ，ｌ，ｉ）を再帰的に呼び出すとともに、親反対側の右半分の範囲（ｉ，…，ｒ）について順方向の右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ＿ｅ（ＲＣＨ（ｎ），ｉ，ｒ）を再帰的に呼び出す。右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ＿ｅ（ｎ，ｌ，ｒ）は、さらにノードｎにマッチしない場合として、各試行位置ｉで範囲（ｌ，…，ｒ）を分割し、親側の左半分の範囲（ｌ，…，ｉ）について、順方向の右リンク関数ｒｉｇｈｔ＿ｌｉｎｋ＿ｅ（ｎ，ｌ，ｉ）を再帰的に呼び出すとともに、親反対側の右半分の範囲（ｉ，…，ｒ）について順方向の右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ＿ｅ（ｎｕｌｌ，ｉ，ｒ）を再帰的に呼び出す。
【０１２６】
右リンク関数ｒｉｇｈｔ＿ｌｉｎｋ＿ｅ（ｎ，ｌ，ｒ）は、各試行位置ｉで範囲（ｌ，…，ｒ）を分割し、親側の左半分の範囲（ｌ，…，ｉ）について順方向の右シーケンス関数ｒｉｇｈｔ＿ｓｅｑ＿ｅ（ｎ，ｌ，ｉ）を再帰的に呼び出し、親反対側の右半分の範囲（ｉ＋１，…，ｒ）について逆方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（ｎｕｌｌ，ｉ＋１，ｒ）を再帰的に呼び出す。右マッチ関数ｒｉｇｈｔ＿ｍａｔｃｈ（ｎ，ｌ，ｒ）は、各試行位置ｉで現在の範囲を分割し、親側の左半分の範囲（ｌ，…，ｉ）について順方向の右シーケンス関数ｒｉｈｇｔ＿ｓｅｑ＿ｅ（ＳＩＢ（ｎ），ｌ，ｉ）を再帰的に呼び出し、親反対側の右半分の範囲（ｉ＋１，…，ｒ）について逆方向の左シーケンス関数ｌｅｆｔ＿ｓｅｑ＿ｅ（ＬＣＨ（ｎ），ｉ＋１，ｒ）を再帰的に呼び出す。
【０１２７】
図２４に示すような再帰的な呼び出しを相互に行うことによって、解析対象の文の構文木を構築するとともに、照会パターンの全体構造から末端のノードまでの対応付けが行われ、照会パターンが構文木中に出現する事象を数え上げながら、構文木での照会パターンの出現回数とその解析確率と積の総和であるパターン出現回数期待値が計算される。なお、得られる重みｆ（ｉ，ｊ）の積は、そのままでは、規格化されておらず、確率として取り扱うことができない。そこで、上記マッチング・スコアの計算過程で同時に求められる全解析候補にわたる規格化されていない確率の総和Ｚで割り、重みｆ（ｉ，ｊ）の積を確率として扱う形に処理することが好ましい。
【０１２８】
以上説明した第２の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標するパターン出現回数期待値を、効率的に近似なしに計算することができる。上述したようにパターン出現回数期待値は、全解析候補中のパターンが出現する出現回数の期待値であり、解析候補中のパターンの出現回数とその解析確率との積の全解析候補にわたる総和に一致する。したがって、従来では、全解析候補を列挙し、パターンマッチングにより照会パターンにマッチする構文木の候補を抽出するとともにマッチする回数を計数し、その候補の解析確率とマッチ回数と積の総和を求める必要があった。この場合、解析候補が文長に対して指数的に増大してしまうため、計算量的に困難があり、現実的ではなかった。
【０１２９】
これに対して本発明の第２の実施形態によるコンピュータ装置２００では、解析候補の確率を上記解析対象の文の文節ペア間に与えられる重みの積に比例する関数で表し、動的計画法を適用することによって、全解析候補を列挙することなく効率的に近似なしに、パターン出現回数期待値を計算することができる。本発明の第２の実施形態による動的計画法が適用されたスコア演算処理では、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行し、同時に解析対象の文の構造を探索する関数群が再帰的に呼び出され、上記部分演算結果が照会パターンの部分構造および文の範囲の内側に関して再帰的に算出され、これにより、パターン出現回数期待値が求められる。なお、計算量は、動的計画法が適用でき、演算コストを記憶コストに交換することができるため、文長Ｌ、パターンサイズＭに対してＯ（Ｌ３Ｍ）程度で済む。なお、上述までは、解析対象の文に対するマッチング・スコアの演算処理について説明してきたが、第１の実施形態と同様に、上記マッチング・スコアの演算処理組み込んで、係り受け構造を考慮した情報検索や情報抽出を行うこともできる。
【０１３０】
［実験］
１．コンピュータにおける実装
クロック数３．０ＧＨｚのマルチコア・プロセッサ（インテル（登録商標）Ｃｏｒｅ（登録商標）２Ｄｕｏ）と２ＧＢのＲＡＭを備えるＴｈｉｎｋＳｔａｔｉｏｎ（登録商標）を用いて、本発明の第１実施形態によるマッチング・スコア演算のプログラムを実装するコンピュータ・システムを実装した。このコンピュータ・システムのオペレーティング・システムは、ＷＩＮＤＯＷＳ（登録商標）ＸＰとした。上記プログラムは、Ｊａｖａ（登録商標）のプログラミング言語によって記述した。
【０１３１】
２．実験結果
２．１．実験例１および比較例１
解析対象データとして毎日新聞（登録商標）の９５年データを用い、照会パターンは、「首相…発言…［動詞］」（首相と発言とが［動詞］に係っていることを意味する。）を用いた。マッチング・スコアとしてパターン周辺確率を用いて、上記解析対象データの各文に対してマッチング・スコア演算プログラムを適用し、マッチング・スコア順にソートし、上位ｋ件のＦａｌｓｅ−ＰｏｓｉｔｉｖｅおよびＴｒｕｅ−ｐｏｓｉｔｉｖｅの件数をプロットし、ＲＯＣ（Receiver Operating Characteristic）グラフを作成した。なお、図２５は、実験例１の結果および１ベスト法による比較例１の結果を示す。
【０１３２】
図２５に示すように、人手で与えられる正解１８件中、１ベスト法の比較例では、３件が解析誤りのため検出できず１５件のみ検出し、１６件の誤検出があったのに対し、実験例１では、上位５１件で全ての正解を網羅することができ、上位１２件目では１０件（約８割）が正解し、高い適合率が得られた。
【０１３３】
２．２．実験例２および比較例２〜４
解析対象データとして同じく毎日新聞（登録商標）の９５年データを用い、照会パターンは、「首相…選挙…［動詞］」（首相と選挙とが［動詞］に係っていることを意味する。）を用いた。マッチング・スコアとしてパターン周辺確率を用いて、上記解析対象データの各文に対してマッチング・スコア演算のプログラムを適用し、マッチング・スコア順にソートし、上位ｋ件のＦａｌｓｅ−ＰｏｓｉｔｉｖｅおよびＴｒｕｅ−Ｐｏｓｉｔｉｖｅの件数をプロットし、ＲＯＣグラフを作成した。なお、図２６（Ａ）は、実験例２の結果および１ベスト法による比較例２の結果を示す。図２６（Ｂ）は、実験例２の結果および５ベスト法による比較例３の結果を示す。図２６（Ｃ）は、実験例２の結果および１０ベスト法による比較例４の結果を示す。なお、上記条件では、単純な文字列一致の場合３０２件ヒットした。また、Ｎベスト法では、出力されたＮ個の構文木それぞれとマッチングを行い、マッチした構文木のスコアの総和をマッチング・スコアとした。さらに、上記Ｎベストのマッチング・スコアを、Ｎ個の構文木のスコアの総和で割り、正規化したものを比較例３’、比較例４’で示す。
【０１３４】
図２６に示すように、人手で与えられる正解３４件中、１ベスト法の比較例２では、１０件は解析誤りのため検出できず２４件のみ検出し、１６件の誤検出があった。また５ベスト法の比較例３では、４件の正解が見つからず、また１０ベスト法の比較例４では、１件の正解が見つからなかった。これに対し、実験例２では、上位５５件で全ての正解を網羅することができた。
【０１３５】
２．３．実験例３および比較例５〜７
解析対象データとして同じく毎日新聞（登録商標）の９５年データを用い、照会パターンは、「首相（…の…に）…を…［動詞］」（「…の」が「…に」に係り、「首相」、「…に」、「…を」は［動詞］に係っていることを意味する。）を用いた。マッチング・スコアとしてパターン周辺確率を用いて、上記データの各文に対してマッチング・スコア演算のプログラムを適用し、マッチング・スコア順にソートし、上位ｋ件のＦａｌｓｅ−ＰｏｓｉｔｉｖｅおよびＴｒｕｅ−Ｐｏｓｉｔｉｖｅの件数をプロットし、ＲＯＣグラフを作成した。なお、図２７（Ａ）は、実験例３の結果および１ベスト法による比較例５の結果を示す。図２７（Ｂ）は、実験例２の結果および５ベスト法による比較例６の結果を示す。図２７（Ｃ）は、実験例２の結果および１０ベスト法による比較例７の結果を示す。なお、単純な文字列一致の場合２０５４件ヒットした。Ｎベストの比較例６および比較例７のマッチング・スコアを正規化したものを比較例６’、比較例７’で示す。
【０１３６】
図２７に示すように、人手で与えられる正解８０件中、１ベスト法の比較例５では、１０件は解析誤りのため検出できず７０件のみ検出し、２５件の誤検出があった。また５ベスト法の比較例６では、４件の正解が見つからず、また１０ベスト法の比較例７では、２件の正解が見つからなかった。これに対して、実験例３では、上位１４９件で、正解の８０件全てを網羅することができた。さらに、１ベスト法の比較例５では、上位２０件中４件が誤りであるのに対し、実験例３では、上位２０件が全て正解であった。上位側で、５ベストおよび１０ベストに比較して高い正解率が得られた。また、正規化すると、比較例６’および比較例７’ともに、上位のスコアが１につぶれてしまい、順位付けができなくなった。
【０１３７】
図２５〜図２７に示す実験結果から、本発明のマッチング・スコアの演算処理は、従来の１ベスト法、Ｎベスト法を用いる場合に比べて、再現性が高く、再現性および適合率を調整することが可能であることが示された。また、検索結果のスコアがばらつき、再現性および適合率を好適に調整することが可能であることが示された。
【０１３８】
以上説明したように、本発明の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチング・スコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整可能とし、ひいては構文解析誤りに高い堅牢性を実現することができる、情報処理装置、自然言語解析方法、プログラムおよび記録媒体を提供することが可能となる。
【０１３９】
なお、本発明につき、発明の理解を容易にするために各機能部および各機能部の処理を記述したが、本発明は、上述した特定の機能部が特定の処理を実行するほか、処理効率や実装上のプログラミングなどの効率を考慮して、いかなる機能部に、上述した処理を実行するための機能を割当てることができる。
【０１４０】
また、本発明では、好適に適用できる言語としては、上記例示した日本語、英語の他、中国語、アラビア語、ドイツ語、フランス語、ロシア語、韓国語など、上述した以外の言語についても適用可能である。
【０１４１】
本発明の上記機能は、Ｃ＋＋、Ｊａｖａ（登録商標）、Ｊａｖａ（登録商標）Ｂｅａｎｓ、Ｊａｖａ（登録商標）Ａｐｐｌｅｔ、Ｊａｖａ（登録商標）Ｓｃｒｉｐｔ、Ｐｅｒｌ、Ｐｙｔｈｏｎ，Ｒｕｂｙなどのオブジェクト指向プログラミング言語などで記述された装置実行可能なプログラムにより実現でき、装置可読な記録媒体に格納して頒布または伝送して頒布することができる。
【０１４２】
これまで本発明を、特定の実施形態をもって説明してきたが、本発明は、実施形態に限定されるものではなく、他の実施形態、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【符号の説明】
【０１４３】
１００，２００…コンピュータ装置、１１０，２１０…入力部、１２０，２２０…スコア演算部、１２２，２２２…左シーケンス関数、１２４，２２４…右シーケンス関数、１２６，２２６…左リンク関数、１２８，２２８…右リンク関数、１３０…動的計画テーブル、１４０，２４０…出力部、１５０，２５０…解析対象の文、１６０，２６０…照会パターン、１７０…係り受け周辺確率、１８０，２８０…演算結果、１９０…検索エンジン、１９２…検索インタフェース、１９４…文書データベース、１９６…ユーザ入力、１９８…検索結果、２３０…左マッチ関数、２３２…右マッチ関数、２３４…動的計画テーブル、２７０…重み
【図１】
0005710317.tif 000006
【図２】
0005710317.tif 000007
【図３】
0005710317.tif 000008
【図４】
0005710317.tif 000009
【図５】
0005710317.tif 000010
【図６】
0005710317.tif 000011
【図７】
0005710317.tif 000012
【図８】
0005710317.tif 000013
【図９】
0005710317.tif 000014
【図１０】
0005710317.tif 000015
【図１１】
0005710317.tif 000016
【図１２】
0005710317.tif 000017
【図１３】
0005710317.tif 000018
【図１４】
0005710317.tif 000019
【図１５】
0005710317.tif 000020
【図１６】
0005710317.tif 000021
【図１７】
0005710317.tif 000022
【図１８】
0005710317.tif 000023
【図１９】
0005710317.tif 000024
【図２０】
0005710317.tif 000025
【図２１】
0005710317.tif 000026
【図２２】
0005710317.tif 000027
【図２３】
0005710317.tif 000028
【図２４】
0005710317.tif 000029
【図２５】
0005710317.tif 000030
【図２６】
0005710317.tif 000031
【図２７】
0005710317.tif 000032
【図２８】
0005710317.tif 000033