"パターンに対する文のマッチングのスコアを算出する情報処理装置であって、解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得する入力部と、前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して、演算するスコア演算部とを含み、前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら、前記部分構造および前記範囲の内部に関して再帰的に演算することによって、前記スコアを算出する、情報処理装置。前記マッチングのスコアを表す関数は、前記対応付けられる各指標値の積を含む関数であり、前記関数の部分演算結果は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数で表される部分スコアであり、前記スコア演算部は、前記再帰的な演算によって前記照会パターンの構造を辿る、請求項1に記載の情報処理装置。前記指標値は、前記文内の各言語単位間の係り受け周辺確率であり、前記マッチングのスコアは、前記文に対する解析候補中の前記照会パターンを部分木として有する候補が生成されるパターン周辺確率であり、前記マッチングのスコアを表す関数は、前記対応付けられる各係り受け周辺確率の積であり、前記パターン周辺確率を近似し、前記部分スコアは、前記部分構造内の各係り受け関係に対応付けられる各係り受け周辺確率の積の局所最大値であり、前記スコア演算部は、前記再帰的な演算によって、前記照会パターンの構造を辿りながら、前記パターン周辺確率を大域的に最大化することを特徴とする、請求項2に記載の情報処理装置。前記指標値は、前記文内の各言語単位ペア間の係り易さを指標する重みであり、前記マッチングのスコアは、前記文に対する解析候補中の前記照会パターンが部分木として出現する見込みを意味するパターン出現回数期待値であり、前記マッチングのスコアを表す関数は、前記照会パターンが出現する解析候補に含まれる各係り受け関係の各重みの積を規格化して該解析候補の確率を表し、前記照会パターンが出現する解析候補にわたる該解析候補の確率と出現回数との積の総和であり、前記部分スコアは、前記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和であり、前記スコア演算部は、前記再帰的な演算によって、前記照会パターンの構造および前記文の構造を辿りながら、前記照会パターンが出現する事象を数え上げ、前記照会パターンが出現した解析候補の確率を加算して、前記パターン出現回数期待値を算出することを特徴とする、請求項2に記載の情報処理装置。前記照会パターンは、言語単位にマッチさせるノードと係り受け関係を表すエッジとからなる木構造を構成し、前記スコア演算部は、前記再帰的な演算を行うための関数群として、前記照会パターン内の第1注目ノードの子孫親反対側末端と親ノードと間の部分構造を文の第1範囲に対応付けて、前記第1注目ノードをマッチさせ得る各試行位置に関して、該試行位置から前記親ノードの位置への係り受け関係に対応付けられる前記指標値を与えるとともに、前記第1範囲内の該試行位置を境界とした親反対側範囲について順方向の第1型関数を再帰的に呼び出し、全試行位置にわたる前記部分スコアを出力する前記第1型関数を含む、請求項2に記載の情報処理装置。前記スコア演算部は、前記再帰的な演算を行うための関数群として、さらに、前記照会パターン内の第2注目ノードと親ノードとの間の部分構造を文の第2範囲に対応付けて、前記第2注目ノードの親側末端の子ノードと兄弟ノードとの子孫間を境界させる各試行位置に関して、前記第2範囲内の該試行位置を境界とした親反対側範囲について逆方向の前記第1型関数を再帰的に呼び出し、前記第2範囲内の該試行位置を境界とした親側範囲について順方向の前記第1型関数を再帰的に呼び出し、全試行位置にわたる部分スコアを出力する第2型関数を含み、前記第1型関数は、前記順方向の第1型関数の呼び出しとともに、前記第1範囲の前記試行位置を境界とした親側範囲について順方向の前記第2型関数を再帰的に呼び出すことを特徴とする、請求項5に記載の情報処理装置。前記第1型関数は、前記順方向の第1型関数の呼び出しの際に前記第1注目ノードの親反対側末端の子ノードを与え、前記順方向の第2型関数の呼び出しの際に当該第1注目ノードを与え、前記第2型関数は、前記逆方向の第1型関数の呼び出しの際に前記第2注目ノードの親側末端の子ノードを与え、前記順方向の第1型関数の呼び出しの際に前記第2注目ノードの兄弟ノードを与えることを特徴とする、請求項6に記載の情報処理装置。前記スコア演算部は、前記再帰的な演算を行うための関数群として、さらに、前記照会パターン内の第3注目ノードの親ノード子孫末端と該親ノードとの間の部分構造を文の第3範囲に対応付けて、前記第3注目ノードの子孫の親反対側末端を境界させる各試行位置に関して、前記第3範囲の試行位置を境界とした親側範囲について順方向の前記第1型関数を再帰的に呼び出し、全試行位置にわたる部分スコアを出力する第3型関数を含み、前記第1型関数は、前記第1注目ノードがマッチしない場合の各試行位置に関して、前記第1範囲内の該試行位置を境界とした親側範囲について順方向の前記第3型関数を再帰的に呼び出すことを特徴とする、請求項6に記載の情報処理装置。前記第1型関数は、前記順方向の第1型関数の呼び出しの際に前記第1注目ノードの親反対側末端の子ノードを与え、前記順方向の第2型関数の呼び出しの際に当該第1注目ノードを与え、前記第2型関数は、前記照会パターンの部分構造の内側に処理を進めて、前記逆方向の第1型関数の呼び出しの際に前記第2注目ノードの親側末端の子ノードを与え、前記順方向の第1型関数の呼び出しの際に前記第2注目ノードの兄弟ノードを与え、前記第3型関数は、前記照会パターンの部分構造の内側に処理を進めず、前記順方向の第1型関数の呼び出しの際に前記第3注目ノードを与えることを特徴とする、請求項8に記載の情報処理装置。前記関数群は、それぞれ、前記照会パターンの部分構造の右端に注目ノードの親ノードが位置する左方向関数と、前記照会パターンの部分構造の左端に注目ノードの親ノードが位置する右方向関数とを含む、請求項5に記載の情報処理装置。前記解析対象の文は、複数の文からなる文集合の各要素として与えられ、検索依頼に応答して、前記文集合の要素のうち、該要素に対して取得されたマッチングのスコアが検索条件を満たすものを検索結果として出力する情報検索インタフェースをさらに含むことを特徴とする、請求項1に記載の情報処理装置。前記情報検索インタフェースは、前記検索条件を受け付けることを特徴とする、請求項11に記載の情報処理装置。前記解析対象の文は、複数の文からなる文集合の各要素として与えられ、前記文集合の各要素に対して取得されたマッチングのスコアの総和を求めて出力する機能部をさらに含むことを特徴とする、請求項1に記載の情報処理装置。前記解析対象の文は、非交差であり、双方向または単方向であり、前記照会パターンは、非交差係り受け木の部分木である、請求項1に記載の情報処理装置。パターンに対する文のマッチングのスコアを算出する情報処理装置であって、解析対象の文と、該文内の各言語単位間の係り受け周辺確率と、照会パターンとを入力として取得する入力部と、前記文に対する解析候補中の前記照会パターンを部分木として有する候補が生成されるパターン周辺確率を、前記照会パターンに規定される各係り受け関係が対応付けられる各係り受け周辺確率の関数で表して、前記スコアとして演算するスコア演算部とを含み、前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用のため記憶領域に格納しながら前記部分構造および前記範囲の内側に関して再帰的に演算することによって、前記パターン周辺確率を算出する、情報処理装置。前記パターン周辺確率を表す関数は、前記各係り受け周辺確率の積であり、前記パターン周辺確率を近似し、前記関数の部分演算結果は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係が対応付けられる各係り受け周辺確率の積の局所最大値であり、前記スコア演算部は、前記再帰的な演算によって前記パターン周辺確率を大域的に最大化することを特徴とする、請求項15に記載の情報処理装置。パターンに対する文のマッチングのスコアを算出する情報処理装置であって、解析対象の文と、該文内の各言語単位間の係り易さを指標する重みと、照会パターンとを入力として取得する入力部と、前記文に対する解析候補中の前記照会パターンが部分木として出現するパターン出現回数期待値を、前記照会パターンが出現する候補に含まれる各係り受け関係の各重みを変数とする関数で表して、前記スコアとして演算するスコア演算部とを含み、前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら前記部分構造および前記範囲の内部に関して再帰的に算出することによって、前記パターン出現回数期待値の演算する、情報処理装置。前記パターン出現回数期待値を表す関数は、前記照会パターンが出現する解析候補に含まれる各係り受け関係の各重みの積を規格化して該解析候補の確率を表し、前記照会パターンが出現する解析候補にわたる該解析候補の確率と出現回数との積の総和であり、前記関数の部分演算結果は、前記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和であり、前記スコア演算部は、前記再帰的な演算によって前記照会パターンが出現する事象を数え上げながら、前記照会パターンが出現した解析候補の確率を加算して、前記パターン出現回数期待値を算出することを特徴とする、請求項17に記載の情報処理装置。コンピュータシステムが実行する、係り受け構造を有するパターンに対する自然言語で記述された文のマッチングのスコアを算出する自然言語解析方法であって、コンピュータシステムが、解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得し、記憶領域に記憶するステップと、コンピュータシステムが、前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して、プロセッサにより演算するステップとを含み、前記演算するステップは、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら演算するサブステップを前記部分構造および前記範囲の内部に関して再帰的に呼び出すステップを含む、自然言語解析方法。前記マッチングのスコアを表す関数は、前記対応付けられる各指標値の積を含む関数であり、前記関数の部分演算結果は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数で表される部分スコアであり、前記再帰的に呼び出すステップにより、前記照会パターンの構造が辿られることを特徴とする、請求項19に記載の自然言語解析方法。コンピュータシステム上に、パターンに対する文のマッチングのスコアを算出する情報処理装置を実現するためのコンピュータ実行可能なプログラムであって、前記コンピュータシステムを、解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得する入力部、および前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して、演算するスコア演算部であって、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら前記部分構造および前記範囲の内部に関して再帰的に演算することによって、前記スコアを算出する、当該スコア演算部として機能させるためのプログラム。請求項21に記載のコンピュータ実行可能なプログラムをコンピュータ読取可能に格納する記録媒体。しかしながら、上述した1ベスト法は、構文解析が成功した場合には正しいマッチ結果を与えるが、構文解析が失敗した場合は、正しいマッチ結果が与えられない可能性がある。図28は、従来技術による構文解析結果に対するマッチングを説明する図である。図28Aに示す照会パターンを用いて、図28BおよびCに示す構文解析結果に対して1ベスト法でマッチングを行う場合、最良とされた解析結果が正しい図28Bである場合は、正しくパターンにマッチし、文が正しく抽出されるが、最良と判断された解析結果が図28Cのような誤ったものである場合、パターンはマッチせず、抽出漏れを発生させてしまう。さらに、1ベスト法は、マッチしたか否かしか判定することができず、情報検索および情報抽出における適合率および再現率を調整することができない点でも充分なものではなかった。上述したNベスト法は、複数通りの構文解析結果に対するマッチングが行われるため、1ベスト法と比較して堅牢性に優れる。しかしながら、上位N通りの解析結果にはマッチしたものがなく、N1以下の順位にパターンにマッチする解析結果が存在したとしても、その場合ヒットせず、抽出漏れを発生させてしまう。Nを増やすことで堅牢性を向上できるが、1つの文に対して存在し得る構文木の数は、文長に対して指数関数的に増大するため、文の構文解析候補を全列挙するためには文長に対し指数個の解析結果が必要となり現実的ではなく、全列挙しない場合でも、取りこぼしを低減するためには少なくとも当該指数個に比例したNが必要となり、必要な記憶容量および計算量が増大する。また、実用上許容できる現実的なN~20では、全体のほんの一部しか考慮することができず、1ベストと同様に抽出漏れが発生しやすい。さらに、Nベストは、構文解析結果のスコアを与えることができるが、N個中でマッチした構文解析結果の解析候補を足しても大きな値とはならないため、値の大小で解析結果の確からしさを判定することも容易ではない。上述した文内共起は、単語が共起しているあらゆる文を網羅できるため、再現率100を達成することができる。しかしながら、文内共起では、文中における単語間の関係性が考慮されないため、明らかに単語間に係り受け関係がない文も抽出されてしまい、効率的ではなく、適合率を向上させることもできない。さらに、文内共起も同様に、マッチしたか否かしか判定することができず、情報検索および情報抽出における適合率および再現率を調整することができない点では1ベスト法と同様である。また非特許文献2に開示される係り受け木上の距離の期待値を計算する手法は、単語間の距離を確率的に求めることで堅牢性を向上させているが、係り受け構造を有するパターンのマッチングを取り扱えるものではなかった。情報検索および情報抽出では、単にマッチしたか否かではなく、トレードオフの関係にある適合率および再現率を任意のレベルに調整できることが好ましい。例えば、検索漏れが望ましくない場合には、網羅性を優先し再現率を高めることが好ましい。検索漏れはある程度許容できるが、正確な結果を得たいという場合は、正確性を優先し適合率を高め、信頼性の高い情報だけを検索および抽出することが好ましい。上述した適合率および再現率を任意のレベルに調整できる、係り受け構造を考慮した情報検索および情報抽出の実用的な技術は現時点では知られておらず、したがって、依然として係り受け構造を有する照会パターンに対する文のマッチングスコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整することを可能とするマッチングスコアの演算手法の開発が望まれていた。さらに、適合率および再現率を所望のレベルに調整することができる係り受け構造を考慮した情報検索および情報抽出技術の開発が望まれていた。本発明は、上記従来技術における問題点に鑑みてなされたものであり、本発明は、係り受け構造を有する照会パターンに対する文のマッチングスコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整可能とし、ひいては構文解析誤りに高い堅牢性を実現することができる情報処理装置、自然言語解析方法、プログラムおよび記録媒体を提供することを目的とする。本発明は、上記従来技術の課題を解決するために、以下の特徴を有する情報処理装置を提供する。本発明の情報処理装置は、解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得する。情報処理装置は、上記取得したデータを用いて、文が照会パターンにマッチする程度を指標するマッチングのスコアを、照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して演算する。情報処理装置は、スコア演算過程では、上記照会パターンの部分構造と文の範囲との対応付けを試行して、上記指標値を少なくとも変数とする関数の部分演算結果を、再利用するため記憶領域に格納しながら、上記部分構造および範囲の内部に関して再帰的に演算することによって、パターンに対する文のマッチングのスコアを算出する。本発明によれば、また、上記マッチングのスコアを表す関数は、対応付けられる各指標値の積を含む関数とすることができる。上記関数の部分演算結果は、照会パターンの部分構造を文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数で表される部分スコアとすることができる。さらに、本発明によれば、上記指標値は、文内の各言語単位間の係り受け周辺確率、または係り易さを指標する重みを用いることができる。上記マッチングのスコアは、文に対する解析候補中の照会パターンを部分木として有する候補が生成されるパターン周辺確率、または文に対する解析候補中の照会パターンが部分木として出現する見込みを意味するパターン出現回数期待値とすることができる。マッチングのスコアを表す関数は、対応付けられる各係り受け周辺確率の積として上記パターン周辺確率を近似することができ、または上記照会パターンが出現する解析候補にわたる該解析候補に含まれる各係り受け関係の各重みの積の総和を規格化した関数で表すことができる。上記部分スコアは、部分構造内の各係り受け関係に対応付けられる各係り受け周辺確率の積の局所最大値、または上記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和とすることができる。また本発明によれば、上述した特徴を有する情報処理装置が実行する自然言語解析方法、上記情報処理装置を実現するためのプログラム、および該プログラムを格納する記録媒体を提供することができる。上記構成によれば、マッチングのスコアを解析対象の文の言語単位間に与えられる評価値の関数で表し、動的計画法を適用することによって、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標し、確率として取り扱うことができるスコアを、全解析候補を列挙することなく効率的に計算することが可能となる。その際の計算量は、動的計画法を適用して演算コストを記憶コストに交換することができるため、文長L、パターンサイズMに対してOL3M程度で済む。以下、本発明について実施形態をもって説明するが、本発明は、後述する実施形態に限定されるものではない。なお、以下に説明する実施形態では、照会パターンに対する文のマッチングスコアを演算するコンピュータ装置を一例として説明する。[用語説明]以下まず、本発明の実施形態で使用する用語について説明する。図1は、統計的係り受け構文解析の結果を説明する図である。図1は、解析対象の文エンジンが|走行中に|突然|煙を|噴いたに対し、係り受け構文解析を実施した場合の解析結果を模式的に表す。解析対象の文は、事前に形態素解析等の事前処理が施されており、単語列または文節列単語および文節は、いずれも文から区分される言語単位である。以下、言語単位として文節を例に説明するが、言語に応じてまたは任意に、単語または文節を選択することができる。として与えられる。解析候補とは、文節列として与えられる解析対象の文に対する統計的確率的係り受け構文解析において、該文に対して存在し得る構文木をいう。図1には、便宜上4つの解析候補の構文木が例示されているが、解析候補は文に対して存在可能なあらゆる構文木を含み、その数は文長文節数に対して指数的に増大する。解析候補の解析確率とは、文に対し統計的係り受け構文解析を実行した場合に、解析候補の構文木に対して与えられる確率をいう。各解析候補の解析確率は、全解析候補にわたって解析確率の総和をとると1になるよう規格化されている。係り受け周辺確率とは、文内の文節間の係りやすさを指標する周辺確率であり、本質的には、係り受けペアを含むすべての構文木の解析候補の解析確率の総和に一致する。文中のi番目の文節を係り元としてj番目の文節を係り先とした係り受けペアの係り受け周辺確率は、pi,jで表される。ある係り受けペアを含む解析候補を全列挙することは現実的には困難であるが、仮に図1中に全解析候補が列挙されているとすると、文エンジンが|走行中に|突然|煙を|噴いたにおける係り受けペアエンジンが→噴いたの係り受け周辺確率は、この係り受けペアが出現している2番目および3番目の候補の解析確率の総和0.30.2=0.5となる。同様に、係り受けペア煙を→噴いたの係り受け周辺確率は、この係り受けペアが出現している1~4番目の解析候補の解析確率の総和0.40.30.20.1=1.0となる。係り受け周辺確率は、動的計画法を適用することにより計算可能であることが知られている。パターン周辺確率とは、全解析候補中のパターンを部分木として含む構文木の解析候補が生成される周辺確率であり、本発明の実施形態では、照会パターンに対する文のマッチングスコアとして利用することができる。パターン周辺確率は、本質的には、全解析候補中のパターンを部分木として含む構文木解析候補の解析確率の総和に一致する。図1に示す例では、文エンジンが|走行中に|突然|煙を|噴いたにおけるパターンエンジンが→噴いた,煙を→噴いたのパターン周辺確率は、このパターンが出現している2番目および3番目の解析候補に与えられた解析確率の総和0.30.2=0.5となる。なお、パターン周辺確率は、0~1の実数をとる。全解析候補を列挙して、各候補がパターンにマッチするか否かを判定して、マッチする候補の解析確率の総和をとることは現実的には困難であるが、以下に説明する本発明の第1の実施形態により、解析候補を全列挙することなく、パターン周辺確率を効率的に近似計算することが可能である。本発明の第1の実施形態では、解析候補を全列挙することなく、確率として取り扱えるパターン周辺確率を求めるために、マッチングに関与した係り受けペアの係り受け周辺確率の積でパターン周辺確率を近似する。図2は、本発明の実施形態によるマッチングスコアの算出方法の概略を説明する図である。図2Aは、係り受け構造を有する照会パターンを例示し、図2Bは、本発明の第1の実施形態によるパターン周辺確率の近似計算を説明する図である。図2に示す例では、文エンジンが|走行中に|突然|煙を|噴いたにおけるパターンエンジンが→噴いた,煙を→噴いたのパターン周辺確率は、マッチングに関与する係り受けペアエンジンが→噴いたおよび煙を→噴いたの係り受け周辺確率の積0.5×1=0.5で近似計算することができる。また、係り受けペアエンジンが→噴いたおよび煙を→噴いたの各係り受け周辺確率は、上述したように、それぞれ、係り受けペアが出現している2番目および3番目の解析候補に与えられた解析確率の総和0.30.2=0.5、および1~4番目の解析候補に与えられた解析確率の総和0.40.30.20.1=1.0となり、これらは既存技術で算出することができる。パターン出現回数期待値とは、全解析候補中のパターンが出現する回数の期待値をいい、本発明の実施形態では、照会パターンに対する文のマッチングスコアとして利用することができる。パターン出現回数期待値は、本質的には、解析候補の構文木に出現するパターンの総数と、該構文木の解析確率との積の全解析候補にわたる総和に一致する。図1に示す例では、文エンジンが|走行中に|突然|煙を|噴いたにおけるパターンエンジンが→噴いた,煙を→噴いたのパターン出現回数期待値は、各解析候補の解析確率と、候補中の出現回数との積の全解析候補にわたる総和0.4×00.3×10.2×10.1×0=0.5となる。全解析候補を列挙して、候補中にパターンが出現する回数を計数し、候補の出現回数と解析確率との積を求め、全解析候補にわたり総和をとることは現実的には困難であるが、以下に説明する本発明の第2の実施形態により、全解析候補を列挙することなく、パターン出現回数期待値を効率的に計算することが可能である。図2Cは、本発明の第2の実施形態によるパターン出現回数期待値の計算方法を説明する図である。図2Cに示す例では、パターンエンジンが→噴いた,煙を→噴いたが出現する構文木の解析候補の出現回数が数え上げられ、パターンが出現する解析候補の解析確率と、それぞれの出現回数との積の総和0.3×10.2×1=0.5で計算することができる。なお、図1に示す例では、第2および第3番目の候補での出現回数はいずれも1であるため、上記例のパターン出現回数期待値はパターン周辺確率に一致する。しかしながら、解析候補中に複数回出現することも想定され、その場合パターン出現回数期待値が1以上となる可能性もある。例えば、文A部長は、B部長が発言したことに関して発言したに対して照会パターン部長...発言...[動詞]が与えられた場合を考える。この場合、上述したパターン周辺確率をマッチングスコアとする第1の実施形態では、最大の出現箇所の周辺確率を計算し、A部長...発言したかB部長...発言したかのいずれか高い方に対応付けた場合の周辺確率が返される。これに対して、上述したパターン出現回数期待値をマッチングスコアとする第2の実施形態では、A部長...発言したおよびB部長...発言したの両方をカウントし、1以上の値が返る場合がある。パターン周辺確率は、構文解析の確信度が重要である場合により好適に使用することができ、パターン出現回数期待値は、単純に出現している回数が重要であるときにより好適に用いることができる。本発明の第1および第2の実施形態によるマッチングスコアの演算処理では、動的計画法を適用することにより、構文解析候補を全列挙することなく効率的に、それぞれマッチングスコアとして用いられるパターン周辺確率またはパターン出現回数期待値を演算する。以下、第1実施形態によるマッチングスコアパターン周辺確率の演算処理について説明する。[第1の実施形態]以下、上述した用語の説明を踏まえて、本発明の第1の実施形態による照会パターンに対する文のマッチングスコアを演算するコンピュータ装置について説明する。図3は、本発明の第1の実施形態によるコンピュータ装置100の機能ブロックを示す。図3に示すコンピュータ装置100は、概ねパーソナルコンピュータ、ワークステーションまたはメインフレームなどの汎用コンピュータとして構成されている。コンピュータ装置100は、図示しないCPUCentralProcessingUnitと、RAMRandomAccessMemoryと、HDDHardDiskDriveやSSDSolidStateDriveなどの記憶装置と、必要に応じてNICNetworkInterfaceCardとを備え、Windows登録商標、UNIX登録商標、AIX登録商標、Linux登録商標などのOSの制御下で稼働する。図3に示す各機能部詳細は後述する。は、CPUの作業領域を提供するメモリ上にプログラムを展開し、CPUの制御の下プログラムを実行させて、各ハードウェア資源を動作制御することによって、コンピュータ装置100上に実現される。本発明の実施形態によるコンピュータ装置100は、解析対象の文150および照会パターン160を含む入力データを取得する入力部110と、入力データを用いてマッチングスコアを算出するスコア演算部120と、マッチングスコアを含む解析結果を出力する出力部140とを含む。解析対象の文150は、入力部110に入力される前段階で、形態素解析などの文字列解析手法で単語列に分割され、各単語には適宜品詞タグ付けPartofSpeechTaggingがなされる。解析対象の文150は、自然言語の種類にもよるが、単語列または文節列として与えられる。解析対象の文は、日本語や英語などあらゆる自然言語で記述された文とすることができるが、基本的には非交差projectiveの係り受け関係を扱うものとし、単方向および双方向の係り受け関係が許容される。つまり、交差がほとんど無いほとんどの言語に適用することができる。英語などの双方向の係り受けを有する文に対しても適用することができる。図4Aは、解析対象の文150を例示し、文長Lの文節列x1,x2,...,xLが示されている。本発明の実施形態では、上記解析対象の文150に付属し、文内の各文節ペアの係り易さを指標する係り受け周辺確率170がさらに入力データとして与えられる。i番目の文節からj番目の文節への係り受け周辺確率pi,jは、予め文に対して統計的構文解析を施した結果として取得することができる。図4Bは、係り受け周辺確率170のデータ構造を模式的に例示しており、係り元番号iを行とし、係り先番号jを列としたテーブルが示されており、係り受け周辺確率の値に比例した面積の正方形がセル内に示されている。統計的係り受け構文解析は、統計学的手法を取り入れた係り受け構文解析手法であり、与えられた文について各単語または文節の係り先の単語または文節を同定する問題を解く自然言語解析処理である。数学的には、解析対象の文をi番目の文節単語を表す要素xiを用いて文節列x={x1,x2,...,xL}で表し、係り受け構造をi番目の文節の係り先インデックスを表す要素yiを用いて列y={y1,y2,...,yL}∈NLで表し、文節列と係り受け構造に対する確率変数をそれぞれX,Yで表すと、1ベスト法は、X=xが与えられたときのY=yの同時分布PY=y|X=xを最大化するyを決定することに対応する。Nベスト法は、PY=y|X=xが大きい順にyをNセット決定することに対応する。なお、統計的構文解析の詳細については、非特許文献3を参照することができる。上記照会パターン160は、文節にマッチさせるパターン要素をノードとし、パターン要素間の係り受け関係をエッジとした木構造で表すことができる。照会パターン160は、数学的には、文節にマッチさせるi番目のパターン要素を表す要素piを用いて、長さMのパターン列p={p1,p2,...,pM}を用いて表すことができる。照会パターン160の係り受け構造については、パターン要素piの親ノード係り先のインデックスを返す関数parp,iで表すことができる。照会パターン160は、好適には、非交差係り受け構文木の部分木、すなわち、順序付きであり、左右別に子ノードが定義され得る木構造とすることができる。このため、各ノードを左から右へ辿ったときの順序で文中に出現することがマッチの条件となる。また、照会パターンの文頭または末尾にルートを仮想的に設定し、設定されたルートを頂点として、係り受け構造に対応して木構造が定義される。ノード間に定義される関係としては、注目するノードをnとして、親ノードPARn、最左子ノードLCHn、最右子ノードRCHn、兄弟ノードSIBnを挙げることができる。最左子ノードLCHnは、注目ノードnの左側の子ノードであって、一番左側にあるノードをいい、最右子ノードRCHnは、注目ノードnの右側の子ノードであって、一番右側にあるノードをいう。兄弟ノードSIBnは、注目ノードnと親を同一とするノードであって、注目ノードnが親の左側に存在する場合には注目ノードnの右側に存在するノードをいい、注目ノードnが親の右側に存在する場合には注目ノードnの左側に存在するノードをいう。照会パターン160のあらゆる係り受け構造は、上記PARn、最左子ノードLCHn、最右子ノードRCHn、兄弟ノードSIBnを用いて、直接的にまたは間接的に表すことができる。図5Aに示す照会パターン160aでは、ルートを注目ノードnとした場合、注目ノードnの最左子ノードLCHnとしてパターン要素発言したが、パターン要素発言したの最左子ノードLCHLCHnとしてパターン要素社長がが規定される。パターン要素発言したを注目ノードnとしてみた場合には、注目ノードnの親ノードPARnがルートで、注目ノードnの最左子ノードLCHnがパターン要素社長がに対応する。図5Bに示す照会パターン160bでは、ルートを注目ノードnとした場合、注目ノードnの最左子ノードLCHnとしてパターン要素噴いたが規定され、パターン要素噴いたの最左子ノードLCHLCHnとしてパターン要素エンジンがが規定され、パターン要素エンジンがの兄弟ノードSIBLCHLCHnとしてパターン要素煙をが規定されている。パターン要素エンジンがを注目ノードnとしてみた場合は、注目ノードnの親ノードPARnがパターン要素噴いたに対応し、注目ノードnの兄弟ノードSIBnがパターン要素煙をに対応する。照会パターン160の各ノードを構成するパターン要素としては、上述した社長やエンジンがといった単語や文節の文字表現そのものとしてもよいし、正規形、動詞や名詞などの品詞その他のタグ情報に対する制約条件、ワイルドカードを利用した正規表現としてもよく、特に限定されるものではない。ここで、パターン要素pjがi番目の文節xiにマッチする場合に真1を出力し、マッチしない場合に偽0を出力するパターンマッチング関数Mxi,pj∈{0,1}を定義する。再び図3を参照すると、スコア演算部120は、入力部110が取得した入力データを用いて、照会パターン160に対する解析対象の文150のマッチングスコアを演算する。上述したように第1の実施形態においては、解析対象の文150に対し存在可能な全解析候補の中で上記照会パターン160を部分木として有する候補が生成されるパターン周辺確率をマッチングスコアとして用いる。パターン周辺確率は、照会パターン160に規定される各係り受け関係が対応付けられる各係り受け周辺確率pi,jの関数で表され、より具体的には、マッチングに関与する各係り受け周辺確率pi,jの積で近似される。本実施形態では、スコア演算部120により、大域的に最大となるパターン周辺確率が最終的に算出され、同時に照会パターン160と解析対象の文150との最適な対応付けも決定される。対応付けは、数学的には、パターン要素piをマッチさせる文節のインデックスmiを用いて、長さMのマッチング列m={m1,m2,...,mM}∈NMとして表すことができる。なお、任意のiに対してMxmi,pi=1である必要がある。また本発明の第1の実施形態において、マッチングスコアは、数学的には、以下の式1で表す値を求めることになる。なお、下記式1中のVy,m,pは、パターン列pをマッチング列mでマッチさせたとき、パターン列pの親と係り受け構造を表す列yの親とが一致するときに1を返す関数である。すなわち、Vy,m,pは、任意のiに対してymi=mparp,iであるとき1を返し、妥当性を保証するための制約条件として用いられる。上記式1は、このままでは計算できないため、同時分布を周辺確率の積で近似する。すなわち、PY=y|X=xを下記式2で表される係り受け周辺確率の積で近似する。スコア演算部120は、複数の関数群122~128を備えており、これらの関数群122~128を再帰的に呼び出すことで、全解析候補を列挙することなく、上記パターン周辺確率を演算する。より具体的には、スコア演算部120は、上記関数群122~128を用いて、照会パターン160の部分構造と解析対象の文150の範囲との対応付けを試行し、上記係り受け周辺確率の積の部分演算結果を上記部分構造および範囲の内側に関して再帰的に算出する。一度計算された部分演算結果は、動的計画テーブル130内に格納され、演算過程で再び必要になった際に、再度演算する代わりに動的計画テーブル130に格納された値が参照され再利用される。動的計画テーブル130は、部分演算結果を格納するための記憶領域であり、例えばRAM、HDDやSSDなどによる記憶領域により提供される。本発明の第1の実施形態では、照会パターン160の部分構造と解析対象の文150の範囲との対応付けが相互再帰的に扱えることを利用し、動的計画法を適用して、本来計算量的に困難のあるパターン周辺確率の効率的な近似計算を可能としている。本実施形態では、上記関数群として、左シーケンス関数122、右シーケンス関数124、左リンク関数126および右リンク関数128の4つの関数が定義されるが、これらの関数群を用いたスコア演算部120の処理については、詳細を後述する。出力部140は、スコア演算部120が算出したパターン周辺確率マッチングスコアを含む演算結果180を出力する。また第1の実施形態では、パターン周辺確率の演算とともに、照会パターン160の解析対象の文150に対する最適なマッチング列mも求められるため、上記パターン周辺確率とともに、マッチング列mが規定するマッチ位置も演算結果180に含めることができる。以下、図6~図8を参照しながら、本発明の第1の実施形態によるマッチングスコア演算処理について説明する。図6は、本発明の第1の実施形態によるマッチングスコア演算方法を概念的に説明する図である。本発明の第1の実施形態では、照会パターンに対してEisner構文木と同様の構文木を考える。図6中の三角形および台形は、それぞれ、1次のEisnerアルゴリズムにおける、半成分を表す完全スパンCompleteSpan、および係り受け関係を表す非完全スパンIncompleteSpanに相当するものである。本発明の実施形態では、各図形は、照会パターンの部分構造を表しており、マッチングスコアの演算過程で、各図形が表す部分構造と、解析対象の文中の範囲スパンとの最適な対応付けが検索される。図6には、照会パターンの注目ノードnに関連して、最左子ノードLCHn、注目ノードn、最右子ノードRCHn、兄弟ノードSIBnおよび親ノードPARnが順に並べられている。まず、図6中に示した第3の構文木生成規則により、照会パターンのパターン要素を表すこれらノード各々から、それぞれ半成分を表す左向き三角形および右向き三角形の各組が生成される。続いて、図6中に示した第2の構文木生成規則により、最左子ノードLCHnの右向き三角形と、注目ノードnの左向き三角形とから、左向き台形Fが生成される。この左向き台形Fは、最左子ノードLCHnおよび注目ノードnの間の部分構造を表し、最左子ノードLCHnから注目ノードnへの係り受け関係を表す。同様に、注目ノードnの右向き三角形と、最右子ノードRCHnの左向き三角形とから、最右子ノードRCHnから注目ノードnへの係り受け関係を表す右向き台形Hが生成され、兄弟ノードSIBnから親ノードPARnへの係り受け関係を表す左向き台形Jについても同様である。さらに、図6中に示した第1の構文木生成規則により、最左子ノードLCHnの左向き三角形Gと、最左子ノードLCHnおよび注目ノードnの間の部分構造を表す上記左向き台形Fとから、最左子ノードLCHnおよび注目ノードnの間の部分構造を表す左向き三角形Cが生成される。同様に、上記右向き台形Hと、最右子ノードRCHnの右向き三角形Iとから右向き三角形Dが生成され、兄弟ノードSIBnの左向き三角形Kと上記生成された左向き台形Jとから左向き三角形Eが生成される。さらに、図6中に示した第2の構文木生成規則により、上記右向き三角形Dと左向き三角形Eとから、注目ノードnから親ノードPARnへの係り受け関係を表す左向き台形Bが生成される。図6中に示した第1の構文木生成規則により、さらに、左向き三角形Cと、左向き台形Bとから、最左子ノードLCHnおよび親ノードPARnの間の部分構造を表す左向き三角形Aが生成される。このようにして、LCHn、n、RCHn、SIBnおよびPARn間の部分構造各々を表す図形をノードとしたEisner構文木と同様の構文木が生成される。なお、図6は、注目ノードnを中心とした照会パターンの一部構造を表したものであり、具体的な照会パターンに応じて、さらに詳細な構造が定義される。例えば最左子ノードLCHnを注目ノードとしてさらにLCHLCHn、RCHLCHn、SIBLCHnが定義されたり、親ノードPARnのさらに親ノードPARPARnが定義されたりする場合があり、これらは図示を省略されていることに留意されたい。さらに、上記RCHnを注目ノードとする場合など、注目ノードが親ノードの右側に存在する場合には、図7に示すように、PARn、SIBnLCHn、nおよびRCHnの順となり、各部分構造各々を表す図形をノードとした構文木が生成される。最終的には、照会パターンの末尾にルートを設定した場合は、ルートから照会パターンの最左子孫までの全体構造を表す左向き三角形が生成される。あるいは、照会パターンの文頭にルートを設定した場合は、ルートから最右子孫までの全体構造を表す右向き三角形が生成される。なお、ルートを頭に設定するか、末尾に設定するかは任意であり、以下の説明では、解析対象の文および照会パターン共に末尾にルートが設定されるものとする。マッチングスコア演算では、スコア演算部120は、上記照会パターンの構文木の全体構造を表す左向き三角形を、解析対象の文の頭から末尾までの範囲に一旦対応付け、ルートノードの最左子ノードLCHrootから順に対応付けを開始させる。本発明の実施形態では、上記左向き三角形および右向き三角形は、図3に示した左シーケンス関数122および右シーケンス関数124に対応し、上記左向き台形および右向き台形は、左リンク関数126および右リンク関数128に対応する。スコア演算過程では、スコア演算部120は、上記関数群122~128を再帰的に呼び出して、各図形が表す部分構造と解析対象の文中の範囲との対応付けを試行し、上記台形で表される係り受け関係に対応して係り受け周辺確率によるスコアを与え、最適なマッチング列mと、そのパターン周辺確率とを求める。以下、上記シーケンス関数122,124およびリンク関数126,128の処理について詳細を説明する。図8は、本発明の第1の実施形態におけるA左シーケンス関数およびB左リンク関数を説明する図である。図9は、本発明の第1の実施形態におけるA,B左シーケンス関数の疑似コードおよび左シーケンス関数による再帰呼び出しを説明する概念図、並びにC,D左リンク関数の疑似コードおよび左リンク関数による再帰呼び出しを説明する概念図である。図10は、本発明の第1の実施形態におけるA,B右シーケンス関数の疑似コードおよび右シーケンス関数による再帰呼び出しを説明する概念図、並びにC,D右リンク関数の疑似コードおよび右リンク関数による再帰呼び出しを説明する概念図である。図8Aおよび図9A,Bに示すように、左シーケンス関数122は、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、1親ノードPARnがr番目の文節に対応しており、2注目ノードnおよびその子孫が、l,...,r-1の範囲に存在し、3注目ノードnがPARnの左側に存在するときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。つまり、左シーケンス関数122は、注目ノードnに関し、最左子孫LCHnの子孫の左側末端と親ノードPARnとの間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。左シーケンス関数122は、上記部分構造の内側の構造を探索するために、上述した条件2により、l,...,r-1のいずれかに対し注目ノードnの対応付けを試行する。試行位置を変数iで表すと、注目ノードn=pjがi番目の文節xiにマッチする場合、パターンマッチング関数Mxi,pjは、真1を出力する疑似コードではmatchn,i=true。注目ノードnがxiにマッチするとき、照会パターンの部分構造中の注目ノードnから親ノードPARnへの係り受け関係が、文中のi番目→r番目の文節ペア間に対応付けられ、係り受け周辺確率pi,rが与えられる。また、注目ノードnがxiにマッチする場合、非交差条件により、注目ノードnの最左子ノードLCHnおよびその子孫は、範囲l,...,i-1に存在することになるので、LCHnと、変数lと、変数iとを引数として与えて左シーケンス関数122を再帰的に呼び出す。同様に、注目ノードnの最右子ノードRCHnおよびその子孫、並びに兄弟ノードSIBnおよびその子孫たちは、非交差条件により、範囲i1,...,r-1に存在することになるので、詳細を後述する左リンク関数126を再帰的に呼び出す。図9Aで示す疑似コードのように、左シーケンス関数left_seqは、少なくとも注目ノードnがマッチする各試行位置iについて、該試行位置iの左半分および右半分の範囲に関して、照会パターンの部分構造のさらに内側の対応付けを試行する左シーケンス関数122および左リンク関数126を再帰的に呼び出す。左シーケンス関数left_seqは、再帰的に呼び出された左シーケンス関数122および左リンク関数126から戻された各部分演算結果と、上記与えられた係り受け周辺確率pi,rとの積を計算する。注目ノードnがマッチする試行位置iが複数ある場合には、その最大値が選択されて、部分演算結果として呼び出し元に返される。右シーケンス関数124については、図10A,Bに疑似コードおよび再帰呼び出しを説明する概念図を示す。右シーケンス関数124も、左シーケンス関数と同様に、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、1親ノードPARnがl番目の文節に対応しており、2注目ノードnおよびその子孫が、l1,...,rの範囲に存在し、3注目ノードnがPARnの右側に存在するときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。つまり、右シーケンス関数124は、図10AおよびBに示すように、注目ノードnに関し、親ノードPARnと最右子孫RCHnの子孫の右側末端との間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。右シーケンス関数124は、上記部分構造のさらに内側の構造を探索するために、上述した条件2により、l1,...,rのいずれかに対し注目ノードnの対応付けを試行する。注目ノードnが文節xiにマッチするとき、照会パターンの部分構造中の注目ノードnから親ノードPARnへの係り受け関係が文中のi番目→l番目の文節ペア間に対応付けられ、係り受け周辺確率pi,lが与えられる。また、非交差条件により、注目ノードnがマッチする試行位置iの左半部に注目ノードnの兄弟およびその子孫、並びにnの最左子およびその子孫が存在し、右半部に注目ノードnの最右子およびその子孫が存在する。そこで、右シーケンス関数124は、その内側に関してさらに対応付けを試行する右シーケンス関数124および右リンク関数128を再帰的に呼び出し、戻された各部分演算結果と、上記与えられた係り受け周辺確率pi,lとの積の最大値を出力する。図8Bおよび図9C,Dに示すように、左リンク関数126は、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、1親ノードPARnがr番目の文節に対応しており、2注目ノードnがl番目の文節に対応しており、3注目ノードnの最右子ノードRCHnおよびその子孫、並びに兄弟ノードSIBnおよびその子孫が、l1,...,r-1の間に存在し、4注目ノードnがPARnの左側に存在するときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。つまり、左リンク関数126は、注目ノードnに関し、当該注目ノードnと親ノードPARnとの間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。非交差条件により、最右子ノードRCHnの子孫右側末端は、兄弟ノードSIBnの子孫左側末端よりも左にある。そこで、左リンク関数126は、上記部分構造の内側の構造を探索するために、注目ノードnの最右子ノードRCHnの子孫右側末端と、兄弟ノードSIBnの子孫左側末端との境界をi,i1の位置で試行する。なお、両者の間に他の文節が存在することもある。そして、最右子ノードRCHnおよびその子孫たちは、l1,...,i-1に存在するはずなので、左リンク関数126は、各試行位置iについて、RCHnと、変数lと変数iとを引数として与えて、右シーケンス関数124を再帰的に呼び出す。同様に、兄弟ノードSIBnおよびその子孫たちは、非交差条件に従い、i1,...,r-1の間に存在するはずなので、左リンク関数126は、各試行位置iについて、SIBnと、変数i1と変数rとを引数として与えて、左シーケンス関数122を再帰的に呼び出す。図9Cで示す疑似コードのように、左リンク関数left_linkは、再帰的に呼び出された右シーケンス関数124および左シーケンス関数122から戻された各部分演算結果の積を計算し、各試行位置iにおける最大値を選択して、部分演算結果として呼び出し元に返す。右リンク関数128については、図10C,Dに疑似コードおよび再帰呼び出しを説明する概念図を示す。右リンク関数128も、左リンク関数と同様に、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、1親ノードPARnがl番目の文節に対応しており、2注目ノードnがr番目の文節に対応しており、3注目ノードnの最左子ノードLCHnおよびその子孫、並びに兄弟ノードSIBnおよびその子孫が、l1,...,r-1の間に存在し、4注目ノードnがPARnの右側に存在するときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。つまり、右リンク関数128は、図10CおよびDに示すように、注目ノードnに関し、注目ノードnの親ノードPARnと当該注目ノードnとの間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。右リンク関数128は、上記部分構造のさらに内側の構造を探索するために、注目ノードnの兄弟ノードSIBnの子孫右側末端と、最左子ノードLCHnの子孫左側末端との境界をi,i1の位置で試行する。そして、右リンク関数128は、各試行位置iについて、兄弟ノードSIBnと変数lと変数iとを引数として与えて右シーケンス関数124を再帰的に呼び出し、最左子ノードLCHnと変数i1と変数rとを引数として与えて、左シーケンス関数122を再帰的に呼び出す。図10Cで示す疑似コードのように、右リンク関数right_linkは、再帰的に呼び出された右シーケンス関数124および左シーケンス関数122から戻された各部分演算結果の積を計算し、各試行位置iにおける最大値を選択して、部分演算結果として呼び出し元に返す。以下、本発明の第1の実施形態による、上述した関数群を用いたマッチングスコア演算処理の詳細について説明する。図11は、本発明の第1の実施形態によるコンピュータ装置が実行する、マッチングスコア演算処理のメインルーチンを示すフローチャートである。図11に示す処理は、解析対象の文150、照会パターン160および係り受け周辺確率170が指定されたマッチングスコア演算の指令が与えられたことに応答して、ステップS100から開始する。ステップS101では、入力部110は、指定された解析対象の文150、照会パターン160、係り受け周辺確率170を入力データとして取得する。解析対象の文は、データベースやファイルなどから取得することができる。係り受け周辺確率は、解析対象の文に対して事前に統計的構文解析が施されている場合は、その解析データとして取得することができる。統計的構文解析が事前に施されていなければ、解析対象の文に対し統計的構文解析を実行して、その解析データとして取得することができる。照会パターンは、データベースやファイルなどから取得することができ、またはユーザ指定された照会文を解釈して取得することができる。ステップS102では、スコア演算部120は、照会パターンのルートと、0と文長Lとを与えて、左シーケンス関数left_seqroot,0、Lを呼び出す。図12は、マッチングスコア演算処理のメインルーチンによる、初期の照会パターンと解析対象の文との対応付けを示す図である。図12に示すように、照会パターンの左向き三角形によって表される最左子孫からルートまでの全体構造が、解析対象の文頭から末尾までの全範囲に対して対応付けられる。再び図11を参照すると、左シーケンス関数left_seqroot,0、L以降のすべての再帰的な演算が完了して、戻された演算結果を取得すると、ステップS103では、出力部140は、得られたマッチングスコアAと、マッチング列mとを演算結果として出力し、ステップS104で本マッチング演算処理を終了する。図13は、本発明の第1の実施形態によるコンピュータ装置が実行する、マッチングスコア演算処理において呼び出される左シーケンス関数left_seqn,l,rのルーチンを示すフローチャートである。図13に示す処理は、例えば図11に示したステップS102の処理で呼び出され、ステップS200から開始する。ステップS201では、スコア演算部120は、引数として与えられたノードnが空の値nullであるか否かを判定する。ステップS201で、ノードnがnullであると判定された場合YESは、ステップS202へ処理を分岐し、値1を戻り値として、ステップS217で本処理を終了し、呼び出し元に返す。これは、照会パターンの木構造において枝の末端まで辿り着いたことを意味する。一方、ステップS201で、ノードnがnullではないと判定された場合NOは、ステップS203へ処理を分岐する。ステップS203では、スコア演算部120は、引数として与えられた変数lと変数rとが同じ値であるか否かを判定する。ステップS203で、変数lと変数rとが同じ値であると判定された場合YESは、ステップS204へ処理を分岐させる。ステップS204では、スコア演算部120は、値0を戻り値として、ステップS217で本処理を終了し、呼び出し元に返す。一方、ステップS203で、変数lと変数rとが異なる値であると判定された場合NOは、ステップS205へ処理を分岐させる。ステップS205では、スコア演算部120は、動的計画テーブル130を参照し、引数n,l,rに対応して既に左シーケンス関数の演算結果がキャッシュされているか否かを判定する。ステップS205で、引数n,l,rに対応して演算結果がキャッシュされており、利用可能である場合YESは、ステップS206へ処理を分岐させる。ステップS206では、スコア演算部120は、再度演算する代わりに、動的計画テーブル130から引数n,l,rに対応するキャッシュ値を読み出し、ステップS217で本処理を終了させ、呼び出し元にキャッシュ値を返す。本発明の実施形態では、同じ引数のセットに対して、2度以上計算が繰り返されないため、照会パターンのサイズ、解析対象の文の長さに対して、多項式時間で計算することができる。一方、ステップS205で、未だキャッシュされていないと判定された場合NOは、ステップS207へ処理を分岐する。ステップS207では、スコア演算部120は、演算結果の戻り値として返すための部分スコアの最大値を保持する変数maxを初期化し、ステップS208~ステップS214のループを実行する。ステップS208~ステップS214のループでは、スコア演算部120は、現在対応付けを行っている範囲の開始位置lから終了位置r-1までの各試行位置iについて、ステップS209~ステップS213の処理を実施する。ステップS209では、スコア演算部120は、引数として与えられたノードnが試行位置iの文節xiにマッチするか否かを判定する。ステップS209で、マッチしないと判定された場合NOには、ステップS214へ分岐し、次のiへ処理を進める。一方、ステップS209で、ノードnが試行位置iの文節xiにマッチすると判定された場合YESには、ステップS210へ処理を分岐させる。この場合、現在対応付けを行っている範囲の開始位置lから試行位置i-1までの範囲内に最左子ノードLCHnおよびその子孫が存在し得るため、ステップS210では、スコア演算部120は、ノードnの最左子ノードLCHnと、変数lと、変数iとを与えて、左シーケンス関数left_seqを再帰的に呼び出す。左シーケンス関数left_seqから演算結果が戻されると、戻り値は変数Aに代入される。またマッチする場合、試行位置i1から現在対応付けを行っている範囲の終了位置lまでの範囲内に最右子ノードRCHnおよび兄弟ノードSIBn並びにこれらの子孫が存在し得るため、ステップS211では、スコア演算部120は、ノードnと、変数iと、変数rとを与えて、左リンク関数left_linkを再帰的に呼び出す。左リンク関数left_linkから演算結果が戻されると、戻り値は変数Bに代入される。ステップS212では、スコア演算部120は、マッチする試行位置iと変数rとに対応する係り受け周辺確率pi,rと、ステップS210の左シーケンス関数left_seqLCHn,l,iからの戻り値Aと、ステップS211の左リンク関数left_linkn,i,rからの戻り値Bとの積sを計算する。ステップS213では、スコア演算部120は、現在保持しているmaxの値と、ステップS213で計算された積sとを比較して、大きな方の値でmaxを更新する。ステップS208~ステップS214では、変数lから変数r-1までの各試行位置iのうち、nにマッチするものに関して、上記係り受け周辺確率pi,rと、最左子ノードの左シーケンス関数の演算結果Aと、左リンク関数の演算結果Bとの積sがそれぞれ計算され、その中で局所最大の値がmaxに保持される。ステップS208~ステップS214のループを抜けると、ステップS215では、スコア演算部120は、動的計画テーブル130のcache_lseq[n,l,r]の配列にmaxの値を記憶し、n,l,rを計算済みに設定する。ステップS216では、スコア演算部120は、maxを戻り値として、ステップS217で本処理を終了させ、呼び出し元に返す。図14は、本発明の第1の実施形態によるコンピュータ装置が実行する、マッチングスコア演算処理で呼び出される左リンク関数left_linkn,l,rのルーチンを示すフローチャートである。図14に示す処理は、例えば図13に示したステップS211の処理で呼び出され、ステップS300から開始する。ステップS301では、スコア演算部120は、引数として与えられた変数lと変数rとが同じ値であるか否かを判定する。ステップS301で、変数lと変数rとが同じ値であると判定された場合YESは、ステップS302へ処理を分岐させる。ステップS302では、スコア演算部120は、値0を戻り値として、ステップS314で本処理を終了し、呼び出し元に返す。一方、ステップS301で、変数lと変数rとが異なる値であると判定された場合NOは、ステップS303へ処理を分岐する。ステップS303では、スコア演算部120は、動的計画テーブル130を参照し、引数n,l,rに対応して既に左リンク関数の演算結果がキャッシュされているか否かを判定する。ステップS303で、対応する演算結果がキャッシュされており、利用可能であると判定された場合YESは、ステップS304へ処理を分岐させる。ステップS304では、スコア演算部120は、動的計画テーブル130から引数n,l,rに対応するキャッシュ値を読み出し、ステップS314で本処理を終了させ、呼び出し元にキャッシュ値を返す。一方、ステップS303で、未だ計算されていないと判定された場合NOは、ステップS305へ処理を分岐する。ステップS305では、スコア演算部120は、演算結果の戻り値として返すための最大値を保持する変数maxをで初期化し、ステップS306~ステップS311のループへ処理を進める。ステップS306~ステップS311では、スコア演算部120は、現在対応付けを行っている範囲の開始位置lから終了位置r-1までの各試行位置iについて、ステップS307~ステップS310の処理を実行する。試行位置iは、最右子ノードRCHnの子孫の右側末端と、兄弟ノードSIBnの子孫の左側末端との境界を表す。現在対応付けを行っている範囲の開始位置lから試行位置i-1までの範囲内に最右子ノードRCHnおよびその子孫が存在し得る。そこで、ステップS307では、スコア演算部120は、引数として与えられたノードnの最右子ノードRCHnと、変数lと、変数iとを与えて、右シーケンス関数right_seqを再帰的に呼び出す。右シーケンス関数right_seqから演算結果が戻されると、戻り値は変数Aに代入される。また、試行位置i1から、現在対応付けを行っている範囲の終了位置r-1までの範囲内に兄弟ノードSIBnおよびその子孫が存在するため、ステップS308では、スコア演算部120は、引数として与えられたノードnの兄弟ノードSIBnと、変数i1と、変数rとを与えて、左シーケンス関数left_seqを再帰的に呼び出す。左シーケンス関数left_seqから演算結果が戻されると、戻り値は変数Bに代入される。ステップS309では、ステップS307の右シーケンス関数right_seqからの戻り値Aと、ステップS308の左シーケンス関数left_seqからの戻り値Bとの積sを計算する。ステップS310では、現在保持しているmaxの値と、ステップS309で計算された積sとを比較して、大きな方の値でmaxを更新する。ステップS306~ステップS311では、変数lから変数r-1までの各試行位置iについて、上記最右子ノードに関する右シーケンス関数right_seqの演算結果Aと、兄弟ノードに関する左シーケンス関数left_seqの演算結果Bとの積sが求められ、その中で局所最大の値がmaxに保持される。ステップS306~ステップS311のループを抜けると、ステップS312では、スコア演算部120は、動的計画テーブル130のcache_llink[n,l,r]の配列にmaxの値を記憶して、n,l,rを計算済みに設定する。ステップS313では、スコア演算部120は、maxの値を戻り値として、ステップS314で本処理を終了させ、呼び出し元に返す。図15は、上記左シーケンス関数、左リンク関数、右シーケンス関数および右リンク関数の相互再帰的な呼び出しを説明する図である。マッチングスコア演算処理は、メインルーチンから、照会パターンのEisner構文木のルートノード全体構造を表す。および解析対象の文の全範囲を引数として左シーケンス関数left_seqが呼び出されて開始する。なお、文頭にルートが設定される場合には、右シーケンス関数right_seqが呼び出される。左シーケンス関数left_seqn,l,rは、ノードnにマッチする各試行位置iで、現在対応付けを行っている範囲l,...,rを分割し、親反対側の左半分の範囲l,...,iについて最左子ノードLCHnを引数として順方向の左シーケンス関数left_seqLCHn,l,iを再帰的に呼び出すとともに、親側の右半分の範囲i,...,rについてノードnを引数として順方向の左リンク関数left_linkn,i,rを再帰的に呼び出す。左リンク関数left_linkn,l,rは、各試行位置iで現在対応付けを行っている範囲l,...,rを分割し、親反対側の左半分の範囲l,...,iについて最右子ノードRCHnを引数として逆方向の右シーケンス関数right_seqRCHn,l,iを再帰的に呼び出し、親側の右半分の範囲i1,...,rについて兄弟ノードSIBnを引数として順方向の左シーケンス関数left_seqSIBn,i1,rを再帰的に呼び出す。右シーケンス関数right_seqn,l,rは、ノードnにマッチする各試行位置iで現在対応付けを行っている範囲を分割し、親側の左半分の範囲l,...,iについてnを引数として順方向の右リンク関数right_linkn,l,iを再帰的に呼び出すとともに、親反対側の右半分の範囲i,...,rについて最右子ノードRCHnを引数として順方向の右シーケンス関数right_seqRCHn,i,rを再帰的に呼び出す。右リンク関数right_linkn,l,rは、各試行位置iで現在の範囲を分割し、親側の左半分の範囲l,...,iについて兄弟ノードSIBnを引数として順方向の右シーケンス関数rihgt_seqSIBn,l,iを再帰的に呼び出し、親反対側の右半分の範囲i1,...,rについて最左子ノードLCHnを引数として逆方向の左シーケンス関数left_seqLCHn,i1,rを再帰的に呼び出しする。図16は、上記左シーケンス関数、左リンク関数、右シーケンス関数および右リンク関数の相互再帰的な呼び出しにより、照会パターンの全体構造から末端までの対応付けが行われる様子を示す図である。まず、最上段の左向き三角形で表される照会パターンの全体構造が、解析対象の文の文頭から末尾までの全範囲に対応付けられて、ルートの最左子ノードLCHrootを引数とした左シーケンス関数left_seqBが呼び出される。左シーケンス関数left_seqBは、ノードBにマッチする試行位置で、対応付けを行っている範囲を分割し、左半分の範囲について最左子ノードLCHBを引数とした左シーケンス関数left_seqAを再帰的に呼び出す。同時に、左シーケンス関数left_seqBは、右半分の範囲については、ノードBを引数とした左リンク関数left_linkBを再帰的に呼び出す。ここで、ノードBからルートへの係り受け周辺確率がスコアとして与えられる。左シーケンス関数left_seqAは、ノードAにマッチする試行位置で、左半分の範囲について最左子ノードLCHAを引数とした左シーケンス関数left_seqnullを呼び出す。左シーケンス関数left_seqAは、同時に、右半分の範囲については、ノードAを引数とした左リンク関数left_linkAを呼び出す。ここで、ノードAからノードBへの係り受け周辺確率がスコアとして与えられる。左シーケンス関数left_seqnullに対しては、照会パターンの末端に達したことを示す1が返される。一方、左リンク関数left_linkBは、対応付けている範囲内で、最右子ノードRCHBおよび兄弟ノードSIBBの子孫間を境界する位置を試行し、左半分の範囲について最右子ノードRCHBを引数とした右シーケンス関数right_seqCを、右半分の範囲について兄弟ノードSIBBを引数とした左シーケンス関数left_seqDを、各試行位置毎に呼び出す。右シーケンス関数right_seqCについて説明を続けると、右シーケンス関数right_seqCは、ノードCにマッチする試行位置があればその位置で、左半分の範囲についてノードCを引数とした右リンク関数right_linkCを呼び出す。ここで、ノードCにマッチする試行位置があればノードCからノードBへの係り受け周辺確率がスコアとして与えられる。ノードCにマッチする試行位置がなければ0が戻される。右シーケンス関数right_seqCは、同時に、右半分の範囲については、最右子ノードRCHCを引数とした右シーケンス関数right_seqnullを呼び出す。右シーケンス関数right_seqnullに対しては、照会パターンの末端まで達したため1が返される。右リンク関数right_linkCは、対応付けている範囲内で、兄弟ノードSIBCおよび最左子ノードLCHCの子孫間を境界する位置を試行し、左半分の範囲について兄弟ノードSIBCを引数とした右シーケンス関数right_seqnullを、右半分の範囲について最左子ノードLCHCを引数とした左シーケンス関数left_seqnullを、それぞれ試行位置毎に呼び出す。右シーケンス関数right_seqnullおよび左シーケンス関数left_seqnullに対しては、照会パターンの末端まで達したため1が返される。上述した処理は、左シーケンス関数left_seqDについても同様である。さらに図16中に吹き出しで、照会パターンのノードA’とノードB’との間にノードA’の兄弟ノードであるノードE’が存在する場合は、上記左リンク関数left_linkAは、対応付けている範囲内で、最右子ノードRCHAおよび兄弟ノードSIBAの子孫間を境界する位置を試行し、左半分の範囲について最右子ノードRCHAを引数とした右シーケンス関数right_seqnullを、右半分の範囲について兄弟ノードSIBAを引数とした左シーケンス関数left_seqEを各試行位置毎に呼び出す。左シーケンス関数left_seqEについては、上記と同様であり、ノードEにマッチする試行位置が見つかった段階でノードE’からノードBへの係り受け周辺確率がスコアとして与えられ返される。上述したような再帰的な呼び出しを繰り返すことによって、照会パターンの各末端を対応付けた段階でその系列の再帰的な呼び出しを終了し、各部分演算における係り受け周辺確率の積の最大値が戻されていく。最終的に、最適なマッチングmでのパターン周辺確率を近似する最大化された係り受け周辺確率の積が、左シーケンス関数left_seqrootに返される。図15および図16に示すような再帰的な呼び出しを相互に行うことによって、照会パターンの全体構造から末端のノードの対応付けまでが行われ、局所最大の周辺確率を与える各マッチング位置が検索され、大域的最大となるパターン周辺確率の近似値を与える最適なマッチング列mが決定され、同時に、大域的最大となるパターン周辺確率が近似計算される。なお、上述までは、解析対象の文に対するマッチングスコアの演算処理について説明してきた。以下、上記マッチングスコアの演算処理組み込んで、係り受け構造を考慮した情報検索を行う情報検索システムについて説明する。図17は、第1の実施形態によるマッチングスコア演算機能を組み込んだ情報検索システムの機能ブロック図である。図17に示す情報検索システムを構成する検索エンジン190は、同様に、コンピュータ装置上に実現される。検索エンジン190は、ユーザとの入出力のインタフェースとなる検索インタフェース192と、上述までの入力部110と、スコア演算部120と、出力部140とを含む。さらに、情報検索システムは、検索対象の文書を格納する文書データベース194を含み、検索エンジン190は、文書データベース194にアクセス可能とされている。なお、各文書は、1以上の文を含み、各文書と各文との関係、例えば文書内の文の位置などは、予め対応付けられているものとする。同様に、各文は、予め形態素解析などの文字列解析が実施されており、文節または単語の列として構成され、係り受け周辺確率のデータも与えられているものとする。検索インタフェース192は、ユーザから、照会パターンを規定する検索クエリと、必要に応じて条件とを含むユーザ入力196を取得する。条件は、検索結果に含めるマッチングスコアに対する閾値、その他文書の検索範囲を指定したりするための条件を含む。なお、条件は、ユーザから与えられてもよいし、システムのデフォルト値として与えられてもよい。検索クエリは、照会パターンを規定するパターン列pおよびその親子関係を定義するparp,iを直接与えてもよいし、所定のフォーマットに従って記述された文字列を解釈して照会パターンのパターン列pおよびparp,iを与えてもよし、さらに予め照会パターンを記述したファイルなどがあれば、そのファイル名等で与えてもよい。検索インタフェース192は、ユーザ入力196を受け取ると、照会パターンと検索範囲の文集合の各文を指定する文識別値を入力部110に渡し、各文のマッチングスコアの演算を依頼する。入力部110は、解析対象の文を指定する情報に従い、文書データベース194から文およびその係り受け周辺確率のデータを取得して、解析対象の文と、照会パターンと、係り受け周辺確率とを入力データとしてスコア演算120に渡す。あるいは、他の実施形態では、検索インタフェース192は、文書データベース194から解析対象の文およびその係り受け周辺確率のデータを取得して、直接入力部110に渡して、各文のマッチングスコアの演算を依頼することもできる。スコア演算部120は、与えられた文に対してマッチングスコアを計算し、出力部140は、与えられた各文に対するマッチング列mおよびスコアを検索インタフェース192に返す。検索インタフェース192は、依頼した各文に対するマッチングスコアおよびマッチング列を取得すると、ユーザ指定された閾値、またはデフォルトの閾値を基準として、閾値以上のスコアが与えられた文の集合を取得し、検索結果198をユーザに提示する。ここで、閾値のレベルを調整することで、情報検索における適合率および再現率を調整することが可能となる。これにより、より適合率を高めて正確な評判情報を取得したり、再現率を高めて製品の不具合を示す全ての文を網羅して取得したりすることができる。また、文書と文との関係が予め対応付けられてれば、例えばマッチした文書のサマリや、文書内のマッチした箇所周辺のサマリ上で、マッチングした箇所を強調表示することができる。さらに他の実施形態では、文書等の文集合内の各文にわたるスコアの総和を求めることもできる。これにより、例えば製品の不具合を示す文がどの程度存在するのかを知ることができるようになる。以上説明した第1の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標し、確率として取り扱うことができるパターン周辺確率を効率的に近似計算することができる。上述したようにパターン周辺確率は、全解析候補中のパターンを部分木として含む構文木の解析候補が生成される周辺確率であり、全解析候補中のパターンを部分木として含む構文木解析候補の解析確率の総和に一致する。したがって、従来では、全解析候補を列挙し、パターンマッチングにより照会パターンにマッチする構文木の候補を抽出し、その候補の解析確率の総和を求める必要があった。この場合、解析候補が文長に対して指数的に増大してしまうため、計算量的に困難があり、現実的ではなかった。これに対して本発明の第1の実施形態によるコンピュータ装置100では、パターン周辺確率を上記解析対象の文の文節ペア間に与えられる係り受け周辺確率の積で近似し、動的計画法を適用することによって、全解析候補を列挙することなく効率的に近似計算することができる。本発明の第1の実施形態による動的計画法が適用されたスコア演算処理では、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行する関数群が再帰的に呼び出され、上記部分演算結果が照会パターンの部分構造および文の範囲の内側に関して再帰的に算出され、これにより、大域的な照会パターンに対するパターン周辺確率が求められる。なお、計算量は、動的計画法が適用でき、演算コストを記憶コストに交換することができるため、文長L、パターンサイズMに対してOL3M程度で済む。[第2の実施形態]以下、本発明の第2の実施形態によるマッチングスコアを演算するコンピュータ装置について説明する。第2の実施形態によるコンピュータ装置は、第1の実施形態で算出したパターン周辺確率に代えて、パターン出現回数期待値をマッチングスコアとして算出する。図18は、本発明の第2の実施形態によるコンピュータ装置200の機能ブロックを示す。図18に示すコンピュータ装置200は、第1の実施形態と同様の構成を有しているが、入力部210に入力される入力データと、スコア演算部220が備える関数群と、出力部240が出力する演算結果が相違する。本発明の第2の実施形態における入力データは、解析対象の文250と、照会パターン260とを含む点で第1の実施形態と同様であるが、第1の実施形態における係り受け周辺確率pi,jに代えて、重みfi,jが取得される点で相違する。重みfi,jは、第1の実施形態の係り受け周辺確率と同様に、i番目の文節からj番目の文節への係りやすさを指標するものである。重みfi,jは、係り受け条件付き対数線形モデルで定義されるものであり、文節iおよび文節j間の特徴ベクトルφi,jと、学習データより推定される重みベクトルwとの内積の指数関数で計算することができる。重みfi,jは、統計的構文解析の過程で生成されるデータである。スコア演算部220は、入力部210が取得した入力データを用いて、照会パターン260に対する解析対象の文250のマッチングスコアを演算する。第2の実施形態においては、解析対象の文250に対し存在可能な全解析候補の中のパターンが出現する回数の期待値、すなわちパターン出現回数期待値をマッチングスコアとして算出する。パターン出現回数期待値は、本質的には、解析候補の構文木に出現するパターンの総数と、該構文木の解析確率との積の全解析候補にわたる総和に一致する。各解析候補の解析確率Pは、解析候補の構文木に含まれる係り受けペアの上記重みfi,jの関数として表される。より具体的には、各解析候補の解析確率Pは、解析候補の構文木に含まれる係り受けペアの重みfi,jの積、すなわち下記式3で表される。なお、下記式3中のZは、分配関数であり、各解析候補の重みfの積を全候補にわたり総和を取った値であり、上記重みfの積を分配関数Zで割ることにより、全候補での総和が1となり、規格化された解析確率として用いることができるようになる。本発明の第2の実施形態において、マッチングスコアは、数学的には、以下の式4で表す値を求めることになる。下記式4は、本実施形態では、第1の実施形態とは異なり、重みfi,jが与えられ、外側が第1の実施形態のmax関数ではなくマッチング列mでの総和Σとなっており、分配関数Zも計算可能であるため、最大のスコアを与えるマッチング列mを決定することはできないが、近似なしに確率Pをそのまま計算することができる。また、外側がmについての総和Σとなっているため、照会パターンが解析候補中に出現する事象分だけ確率Pが加算されていき、結果として、解析候補での照会パターンの出現回数とその解析確率との積の総和が求められる。スコア演算部220は、左右のシーケンス関数222,224、左右のリンク関数226,228および左右のマッチ関数230,232を備えており、これらの関数群を再帰的に呼び出すことで、全解析候補を列挙することなく、上記パターン出現回数期待値を演算する。より具体的には、スコア演算部220は、複数の関数群222~232を用いて、照会パターン260の部分構造と解析対象の文250の範囲との対応付けを試行し、照会パターンが出現する事象にわたる上記重みの積和の部分演算結果を、上記部分構造および範囲の内側に関して再帰的に算出する。一度計算された部分演算結果は、第1の実施形態と同様に、動的計画テーブル234内に格納され、演算過程で再び必要になった際に、再度演算する代わりに動的計画テーブル234に格納された値が再利用される。第2の実施形態では、照会パターン260の部分構造と解析対象の文250の範囲との対応付けを試行の過程では、パターンの構造が再帰的にたどられていたが、第2の実施形態における対応付けの試行過程では、解析対象の文の構造が再帰的にたどられながら、パターンの構造も再帰的にたどられる。出力部240は、スコア演算部220が算出したパターン出現回数期待値マッチングスコアを含む演算結果280を出力する。第2の実施形態では、マッチング列mの総和が計算されるため、マッチング列mは求められず、上記パターン出現回数期待値のみが演算結果280に含められる。以下、図19~図23を参照しながら、本発明の第2の実施形態によるマッチングスコア演算処理について説明する。図19は、本発明の第2の実施形態によるマッチングスコア演算方法を概念的に説明する図である。本発明の第2の実施形態では、解析対象の文に対してEisner構文木と同様の構文木を考える。図19中の三角形および台形は、それぞれ、1次のEisnerアルゴリズムにおける完全スパンおよび非完全スパンに相当する。さらに図19中のが付された台形は、照会パターンに規定される係り受け関係に対応付けられた文の構文木上の係り受け関係であることを意味している。なお、図18には、構文解析結果の構文木の一例を示すが、実際には、あらゆる構文解析結果に対してマッチングスコアの総和を計算する。本発明の第2の実施形態では、照会パターンおよび解析対象の文の両方に関して動的計画法を適用し、解析対象の構文木の構築を行うと同時に、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行する。スコア演算部220は、照会パターンのルートノード全体構造を上記文の構文木のルートノード全体範囲に対応付けるところから開始する。まず、照会パターンの全体構造を表す左向き三角形を、解析対象の文の頭から末尾までの範囲に一旦対応付け、照会パターンのルートノードの最左子ノードLCHrootから順に対応付けを行う。本発明の実施形態では、上記左向き三角形および右向き三角形は、図18に示した左シーケンス関数222および右シーケンス関数224に対応し、印なし上記左向き台形および右向き台形は、左リンク関数226および右リンク関数228に対応し、印有りの上記左向き台形および右向き台形は、左マッチ関数230および右マッチ関数232に対応する。スコア演算過程では、スコア演算部220は、上記関数群222~232を再帰的に呼び出して、照会パターンの部分構造と解析対象の文中の範囲との対応付けを試行し、上記台形で表される係り受け関係に対応して重みi,jによるスコアを与えるとともに、照会パターンの係り受け関係をマッチする印有りか、マッチしない印なしかの場合に分けてそれぞれ処理を進め、照会パターンの構造と文の構造との両方を辿りながら、マッチングスコアを算出する。以下、本発明の第2の実施形態で用いられるシーケンス関数222,224、リンク関数226,228およびマッチ関数230,232について詳細を説明する。図20は、本発明の第2の実施形態における左シーケンス関数を説明する図である。図21は、本発明の第2の実施形態におけるA左リンク関数およびB左マッチ関数を説明する図である。図22は、本発明の第2の実施形態におけるA左シーケンス関数B左リンク関数およびC左マッチ関数の疑似コードを示す図である。図23は、本発明の第2の実施形態におけるA右シーケンス関数B右リンク関数およびC右マッチ関数の疑似コードを示す図である。図20および図22Aに示すように、第2の実施形態の左シーケンス関数222は、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、1親ノードPARnがr番目の文節に対応しており、2文の構文木上でのPARnの左子孫末端がlで、したがってnとその子孫はl,...r-1の範囲に存在し、3注目ノードnがPARnの左側に存在するときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左シーケンス関数222は、注目ノードnに関し、注目ノードnの親ノードPARnの左子孫末端と親ノードPARnとの間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。左シーケンス関数222は、上記照会パターンの部分構造および上記文の範囲について内側の構造を探索するために、上述した条件2により、範囲l,...,r-1のいずれかに対し、文の構文木上の親ノードPARnの最左子ノード最左子ノードがパターン上の注目ノードnにマッチする場合もあり、マッチしない場合もある。の対応付けを試行する。試行位置を変数iで表すと、このとき文中のi番目→r番目の文節ペア間に親ノードPARnの最左子ノードから親ノードPARnへの係り受け関係が試行され、重みfi,rが与えられる。なお、ここでいう試行位置iは、照会パターン上の最左子ノードではなく、文の構文木上での親ノードPARnの最左子ノード注目ノードnにマッチする場合には、パターン上の最左子ノードにも一致する。の位置である点に留意されたい。注目ノードnが、親ノードPARnの最左子ノードが対応付けられている文節xiにマッチする場合図20A、注目ノードnの最右子ノードRCHnおよびその子孫、並びに兄弟ノードSIBnおよびその子孫たちは、非交差条件により、範囲i1,...,r-1に存在し得るので、詳細を後述する左マッチ関数230を再帰的に呼び出す。同時に、注目ノードnの最左子ノードLCHnおよびその子孫は、範囲l,...,i-1に存在し得るので、LCHnと、変数lと、変数iとを引数として与えて左シーケンス関数222を再帰的に呼び出す。一方、注目ノードnが、親ノードPARnの最左子ノードが対応付けられている文節xiにマッチしない場合図20B。マッチさせない場合を含む。は、注目ノードnおよびその子孫たちは、範囲i1,...,r-1に存在し得るので、詳細を後述する左リンク関数226を再帰的に呼び出す。残りに対応するパターン要素は無いので、範囲l,...,i-1については、nullと、変数lと、変数iとを引数として与えて左シーケンス関数222を呼び出す。図22Aで示す疑似コードのように、左シーケンス関数left_seq_eは、注目ノードnがマッチする各試行位置iについて、試行位置iの左半分および右半分の範囲に関して、着目している照会パターンの構造の内側の次の部分構造に進め、対応付けを試行する左シーケンス関数222および左マッチ関数230を再帰的に呼び出す。左シーケンス関数left_seq_eは、再帰的に呼び出された左シーケンス関数222および左マッチ関数230から戻された各部分演算結果と、上記与えられた重みfi,rとの積を計算し、部分スコアに加算する。本実施形態では、さらに、左シーケンス関数left_seq_eは、各試行位置iについて、試行位置iの左半分の範囲に関して、nullを与えて左シーケンス関数222を呼び出すとともに、試行位置iの右半分の範囲に関して、着目している照会パターンの部分構造のまま、対応付けを試行する左リンク関数226を再帰的に呼び出す。左シーケンス関数left_seq_eは、各試行位置iについて、左シーケンス関数222から戻された部分演算結果1であると、再帰的に呼び出された左リンク関数226から戻された部分演算結果と、上記与えられた重みfi,rとの積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。左リンク関数226は、図21Aおよび図22Bに示すように、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、1親ノードPARnがr番目の文節に対応しており、2文の構文木上でのPARnの最左子ノードがl番目の文節に対応しており、かつ、注目ノードnとマッチしておらず、3文の構文木上でのPARnの最左子ノードl番目の文節の右子孫と、最左子ノードの兄弟とが、非交差条件より、l1,...,r-1の間に存在し、4注目ノードnがPARnの左側に存在するときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左リンク関数226は、注目ノードnに関し、親ノードPARnの最左子ノードの左側末端と親ノードPARnとの間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。非交差条件により、最左子ノードの右子孫と、最左子ノードの兄弟ノードの子孫とは隣り合っている。そこで、左リンク関数226は、最左子ノードの右子孫の右側末端と、最左子ノードの兄弟ノードの子孫左側末端との境界をi,i1の位置で試行する。そして、最左子ノードの兄弟の子孫は、i1,...,r-1の間に存在し得るので、左リンク関数226は、ここに注目ノードnを対応させて、注目ノードnと、変数i1と変数rとを引数として与えて左シーケンス関数222を再帰的に呼び出す。一方、最左子ノードの右子孫はl1,...,i-1に存在し得るが、ここに対応させる照会パターンのノードは無いので、nullと、変数lと変数iとを引数として与えて、右シーケンス関数224を呼び出す。図22Bで示す疑似コードのように、左リンク関数left_link_eは、各試行位置iについて、右シーケンス関数224の部分演算結果と、再帰的に呼び出された左シーケンス関数222から戻された部分演算結果の積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。左マッチ関数230は、図21Bおよび図22Cに示すように、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、1親ノードPARnがr番目の文節に対応しており、2文の構文木上でのPARnの最左子ノードがl番目の文節に対応しており、かつ、注目ノードnとマッチしており、3文の構文木上でのPARnの最左子ノードの右子孫と、最左子ノードの兄弟とが、非交差条件より、l1,...,r-1の間に存在し、4注目ノードnがPARnの左側に存在するときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左マッチ関数230は、注目ノードnに関し、注目ノードnの左側末端と親ノードPARnとの間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。非交差条件により、最左子ノードの右子孫と、最左子ノードの兄弟ノードの子孫とは隣り合っている。そこで、左マッチ関数230は、最左子ノードの右子孫の末端と、最左子ノードの兄弟ノードの子孫左側末端との境界をi,i1の位置で試行する。そして、最左子ノードの右子孫は、l1,...,iの間に存在し得るので、左マッチ関数230は、ここに最右子ノードRCHnを対応させて、最右子ノードRCHnと、変数lと変数iとを引数として与えて右シーケンス関数224を再帰的に呼び出す。同時に、最左子ノードの兄弟の子孫は、i1,...,r-1の間に存在し得るので、左マッチ関数230は、ここに兄弟ノードSIBnを対応させて、兄弟ノードSIBnと、変数i1と変数rとを引数として与えて左シーケンス関数222を再帰的に呼び出す。図22Cで示す疑似コードのように、左マッチ関数left_match_eは、各試行位置iについて、再帰的に呼び出された右シーケンス関数224および左シーケンス関数222から戻された各部分演算結果の積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。なお、右シーケンス関数224、右リンク関数228および右マッチ関数232については、図23A、BおよびCにそれぞれ疑似コードが示されており、上述までの左シーケンス関数222、左リンク関数226および左マッチ関数230についての説明や、第1の実施形態での説明から容易に理解できるため、詳細な説明は割愛する。図24は、上記左右のシーケンス関数、左右のリンク関数および左右のマッチ関数の相互再帰的な呼び出しを説明する図である。マッチングスコア演算処理は、メインルーチンから、照会パターンの構文木のルートノード全体構造を表す。と解析対象の文の全範囲とを引数として左シーケンス関数left_seq_eが呼び出されて開始する。左シーケンス関数left_seq_en,l,rは、ノードnにマッチする場合として、ノードnにマッチする各試行位置iで、現在対応付けを行っている範囲l,...,rを分割し、親反対側の左半分の範囲l,...,iについて順方向の左シーケンス関数left_seq_eLCHn,l,iを再帰的に呼び出すとともに、親側の右半分の範囲i,...,rについて順方向の左マッチ関数left_match_en,i,rを再帰的に呼び出す。左シーケンス関数left_seq_en,l,rは、さらにノードnにマッチしない場合として、各試行位置iで現在対応付けを行っている範囲l,...,rを分割し、親反対側の左半分の範囲l,...,iについて順方向の左シーケンス関数left_seq_enull,l,iを再帰的に呼び出すとともに、親側の右半分の範囲i,...,rについて順方向の左リンク関数left_link_en,i,rを再帰的に呼び出す。左リンク関数left_link_en,l,rは、各試行位置iで現在対応付けを行っている範囲l,...,rを分割し、親反対側の左半分の範囲l,...,iについて逆方向の右シーケンス関数right_seq_enull,l,iを再帰的に呼び出し、親側の右半分の範囲i1,...,rについて順方向の左シーケンス関数left_seq_en,i1,rを再帰的に呼び出す。一方、左マッチ関数left_match_en,l,rは、各試行位置iで現在対応付けを行っている範囲l,...,rを分割し、親反対側の左半分の範囲l,...,iについて、逆方向の右シーケンス関数right_seq_eRCHn,l,iを再帰的に呼び出し、親側の右半分の範囲i1,...,rについて順方向の左シーケンス関数left_seq_eSIBn,i1,rを再帰的に呼び出す。右シーケンス関数right_seq_en,l,rは、ノードnにマッチする場合として、ノードnにマッチする各試行位置iで範囲を分割し、親側の左半分の範囲l,...,iについて順方向の右マッチ関数right_match_en,l,iを再帰的に呼び出すとともに、親反対側の右半分の範囲i,...,rについて順方向の右シーケンス関数right_seq_eRCHn,i,rを再帰的に呼び出す。右シーケンス関数right_seq_en,l,rは、さらにノードnにマッチしない場合として、各試行位置iで範囲l,...,rを分割し、親側の左半分の範囲l,...,iについて、順方向の右リンク関数right_link_en,l,iを再帰的に呼び出すとともに、親反対側の右半分の範囲i,...,rについて順方向の右シーケンス関数right_seq_enull,i,rを再帰的に呼び出す。右リンク関数right_link_en,l,rは、各試行位置iで範囲l,...,rを分割し、親側の左半分の範囲l,...,iについて順方向の右シーケンス関数right_seq_en,l,iを再帰的に呼び出し、親反対側の右半分の範囲i1,...,rについて逆方向の左シーケンス関数left_seq_enull,i1,rを再帰的に呼び出す。右マッチ関数right_matchn,l,rは、各試行位置iで現在の範囲を分割し、親側の左半分の範囲l,...,iについて順方向の右シーケンス関数rihgt_seq_eSIBn,l,iを再帰的に呼び出し、親反対側の右半分の範囲i1,...,rについて逆方向の左シーケンス関数left_seq_eLCHn,i1,rを再帰的に呼び出す。図24に示すような再帰的な呼び出しを相互に行うことによって、解析対象の文の構文木を構築するとともに、照会パターンの全体構造から末端のノードまでの対応付けが行われ、照会パターンが構文木中に出現する事象を数え上げながら、構文木での照会パターンの出現回数とその解析確率と積の総和であるパターン出現回数期待値が計算される。なお、得られる重みfi,jの積は、そのままでは、規格化されておらず、確率として取り扱うことができない。そこで、上記マッチングスコアの計算過程で同時に求められる全解析候補にわたる規格化されていない確率の総和Zで割り、重みfi,jの積を確率として扱う形に処理することが好ましい。以上説明した第2の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標するパターン出現回数期待値を、効率的に近似なしに計算することができる。上述したようにパターン出現回数期待値は、全解析候補中のパターンが出現する出現回数の期待値であり、解析候補中のパターンの出現回数とその解析確率との積の全解析候補にわたる総和に一致する。したがって、従来では、全解析候補を列挙し、パターンマッチングにより照会パターンにマッチする構文木の候補を抽出するとともにマッチする回数を計数し、その候補の解析確率とマッチ回数と積の総和を求める必要があった。この場合、解析候補が文長に対して指数的に増大してしまうため、計算量的に困難があり、現実的ではなかった。これに対して本発明の第2の実施形態によるコンピュータ装置200では、解析候補の確率を上記解析対象の文の文節ペア間に与えられる重みの積に比例する関数で表し、動的計画法を適用することによって、全解析候補を列挙することなく効率的に近似なしに、パターン出現回数期待値を計算することができる。本発明の第2の実施形態による動的計画法が適用されたスコア演算処理では、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行し、同時に解析対象の文の構造を探索する関数群が再帰的に呼び出され、上記部分演算結果が照会パターンの部分構造および文の範囲の内側に関して再帰的に算出され、これにより、パターン出現回数期待値が求められる。なお、計算量は、動的計画法が適用でき、演算コストを記憶コストに交換することができるため、文長L、パターンサイズMに対してOL3M程度で済む。なお、上述までは、解析対象の文に対するマッチングスコアの演算処理について説明してきたが、第1の実施形態と同様に、上記マッチングスコアの演算処理組み込んで、係り受け構造を考慮した情報検索や情報抽出を行うこともできる。[実験]1.コンピュータにおける実装クロック数3.0GHzのマルチコアプロセッサインテル登録商標Core登録商標2Duoと2GBのRAMを備えるThinkStation登録商標を用いて、本発明の第1実施形態によるマッチングスコア演算のプログラムを実装するコンピュータシステムを実装した。このコンピュータシステムのオペレーティングシステムは、WINDOWS登録商標XPとした。上記プログラムは、Java登録商標のプログラミング言語によって記述した。2.実験結果2.1.実験例1および比較例1解析対象データとして毎日新聞登録商標の95年データを用い、照会パターンは、首相...発言...[動詞]首相と発言とが[動詞]に係っていることを意味する。を用いた。マッチングスコアとしてパターン周辺確率を用いて、上記解析対象データの各文に対してマッチングスコア演算プログラムを適用し、マッチングスコア順にソートし、上位k件のFalse-PositiveおよびTrue-positiveの件数をプロットし、ROCReceiverOperatingCharacteristicグラフを作成した。なお、図25は、実験例1の結果および1ベスト法による比較例1の結果を示す。図25に示すように、人手で与えられる正解18件中、1ベスト法の比較例では、3件が解析誤りのため検出できず15件のみ検出し、16件の誤検出があったのに対し、実験例1では、上位51件で全ての正解を網羅することができ、上位12件目では10件約8割が正解し、高い適合率が得られた。2.2.実験例2および比較例2~4解析対象データとして同じく毎日新聞登録商標の95年データを用い、照会パターンは、首相...選挙...[動詞]首相と選挙とが[動詞]に係っていることを意味する。を用いた。マッチングスコアとしてパターン周辺確率を用いて、上記解析対象データの各文に対してマッチングスコア演算のプログラムを適用し、マッチングスコア順にソートし、上位k件のFalse-PositiveおよびTrue-Positiveの件数をプロットし、ROCグラフを作成した。なお、図26Aは、実験例2の結果および1ベスト法による比較例2の結果を示す。図26Bは、実験例2の結果および5ベスト法による比較例3の結果を示す。図26Cは、実験例2の結果および10ベスト法による比較例4の結果を示す。なお、上記条件では、単純な文字列一致の場合302件ヒットした。また、Nベスト法では、出力されたN個の構文木それぞれとマッチングを行い、マッチした構文木のスコアの総和をマッチングスコアとした。さらに、上記Nベストのマッチングスコアを、N個の構文木のスコアの総和で割り、正規化したものを比較例3’、比較例4’で示す。図26に示すように、人手で与えられる正解34件中、1ベスト法の比較例2では、10件は解析誤りのため検出できず24件のみ検出し、16件の誤検出があった。また5ベスト法の比較例3では、4件の正解が見つからず、また10ベスト法の比較例4では、1件の正解が見つからなかった。これに対し、実験例2では、上位55件で全ての正解を網羅することができた。2.3.実験例3および比較例5~7解析対象データとして同じく毎日新聞登録商標の95年データを用い、照会パターンは、首相...の...に...を...[動詞]...のが...にに係り、首相、...に、...をは[動詞]に係っていることを意味する。を用いた。マッチングスコアとしてパターン周辺確率を用いて、上記データの各文に対してマッチングスコア演算のプログラムを適用し、マッチングスコア順にソートし、上位k件のFalse-PositiveおよびTrue-Positiveの件数をプロットし、ROCグラフを作成した。なお、図27Aは、実験例3の結果および1ベスト法による比較例5の結果を示す。図27Bは、実験例2の結果および5ベスト法による比較例6の結果を示す。図27Cは、実験例2の結果および10ベスト法による比較例7の結果を示す。なお、単純な文字列一致の場合2054件ヒットした。Nベストの比較例6および比較例7のマッチングスコアを正規化したものを比較例6’、比較例7’で示す。図27に示すように、人手で与えられる正解80件中、1ベスト法の比較例5では、10件は解析誤りのため検出できず70件のみ検出し、25件の誤検出があった。また5ベスト法の比較例6では、4件の正解が見つからず、また10ベスト法の比較例7では、2件の正解が見つからなかった。これに対して、実験例3では、上位149件で、正解の80件全てを網羅することができた。さらに、1ベスト法の比較例5では、上位20件中4件が誤りであるのに対し、実験例3では、上位20件が全て正解であった。上位側で、5ベストおよび10ベストに比較して高い正解率が得られた。また、正規化すると、比較例6’および比較例7’ともに、上位のスコアが1につぶれてしまい、順位付けができなくなった。図25~図27に示す実験結果から、本発明のマッチングスコアの演算処理は、従来の1ベスト法、Nベスト法を用いる場合に比べて、再現性が高く、再現性および適合率を調整することが可能であることが示された。また、検索結果のスコアがばらつき、再現性および適合率を好適に調整することが可能であることが示された。以上説明したように、本発明の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチングスコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整可能とし、ひいては構文解析誤りに高い堅牢性を実現することができる、情報処理装置、自然言語解析方法、プログラムおよび記録媒体を提供することが可能となる。なお、本発明につき、発明の理解を容易にするために各機能部および各機能部の処理を記述したが、本発明は、上述した特定の機能部が特定の処理を実行するほか、処理効率や実装上のプログラミングなどの効率を考慮して、いかなる機能部に、上述した処理を実行するための機能を割当てることができる。また、本発明では、好適に適用できる言語としては、上記例示した日本語、英語の他、中国語、アラビア語、ドイツ語、フランス語、ロシア語、韓国語など、上述した以外の言語についても適用可能である。本発明の上記機能は、C、Java登録商標、Java登録商標Beans、Java登録商標Applet、Java登録商標Script、Perl、Python,Rubyなどのオブジェクト指向プログラミング言語などで記述された装置実行可能なプログラムにより実現でき、装置可読な記録媒体に格納して頒布または伝送して頒布することができる。これまで本発明を、特定の実施形態をもって説明してきたが、本発明は、実施形態に限定されるものではなく、他の実施形態、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用効果を奏する限り、本発明の範囲に含まれるものである。"