(57)【要約】【課題】自然言語文の構造を容易に変換することができる自然言語解析装置を提供する。【解決手段】記憶手段に、自然言語の構造に含まれる任意の変換対象構造を当該変換対象構造とは異なる構造に変換するための変換規則群を記憶し、入力文字列の形態素列から、複数の統語構造木を含む統語森を求め、前記統語森から、前記変換対象構造を少なくとも１つ含む前記統語構造木を含む複数の部分構造を求め、各部分構造内の前記変換対象構造に含まれる形態素の数、構造変換後の統語森に含まれる前記統語構造木の数、及び適用される変換規則の数のうちの少なくとも１つに基づいて、前記複数の部分構造のなかから、前記変換規則群を適用して構造変換するための第１の部分構造を選択し、前記変換規則群のうち、前記第１の部分構造に含まれる各変換対象構造を変換するための各変換規則を用いて、当該第１の部分構造の構造を変換する。【選択図】      図１
2006012088.tif 000002
【特許請求の範囲】
【請求項１】
自然言語の構造を変換する自然言語解析装置であって、
自然言語の構造に含まれる任意の変換対象構造を当該変換対象構造とは異なる構造に変換するための変換規則群を記憶する記憶手段と、
入力文字列の形態素列から、複数の統語構造木を含む統語森を求める構文解析手段と、
前記統語森から、前記変換対象構造を少なくとも１つ含む前記統語構造木を含む複数の部分構造を求める手段と、
各部分構造内の前記変換対象構造に含まれる形態素の数、構造変換後の統語森に含まれる前記統語構造木の数、及び適用される変換規則の数のうちの少なくとも１つに基づいて、前記複数の部分構造のなかから、前記変換規則群を適用して構造変換するための第１の部分構造を選択する選択手段と、
前記変換規則群のうち、前記第１の部分構造に含まれる各変換対象構造を変換するための各変換規則を用いて、当該第１の部分構造の構造を変換する構造変換手段と、
を具備したことを特徴とする自然言語解析装置。
【請求項２】
前記選択手段は、前記複数の部分構造のなかで前記部分構造内の前記変換対象構造に含まれる形態素の数が最も多い部分構造である前記第１の部分構造を選択することを特徴とする請求項１記載の自然言語解析装置。
【請求項３】
前記選択手段は、前記複数の部分構造のなかで前記部分構造内の前記変換対象構造に含まれる形態素の数が最も多く、かつ構造変換後の統語森に含まれる前記統語構造木の数が最も少ない部分構造である前記第１の部分構造を選択することを特徴とする請求項１記載の自然言語解析装置。
【請求項４】
前記選択手段は、前記複数の部分構造のなかで前記部分構造内の前記変換対象構造に含まれる形態素の数が最も多く、かつ構造変換後の統語森に含まれる前記統語構造木の数が最も少なく、かつ適用される変換規則の数が最も多い部分構造である前記第１の部分構造を選択することを特徴とする請求項１記載の自然言語解析装置。
【請求項５】
自然言語の構造に含まれる任意の変換対象構造を当該変換対象構造とは異なる構造に変換するための変換規則群を用いて、自然言語の構造を変換するための自然言語解析方法であって、
入力文字列の形態素列から、複数の統語構造木を含む統語森を求める第１のステップと、
前記統語森から、前記変換対象構造を少なくとも１つ含む前記統語構造木を含む複数の部分構造を求める第２のステップと、
各部分構造内の前記変換対象構造に含まれる形態素の数、構造変換後の統語森に含まれる前記統語構造木の数、及び適用される変換規則の数のうちの少なくとも１つに基づいて、前記複数の部分構造のなかから、前記変換規則群を適用して構造変換するための第１の部分構造を選択する第３のステップと、
前記変換規則群のうち、前記第１の部分構造に含まれる各変換対象構造を変換するための各変換規則を用いて、当該第１の部分構造の構造を変換する第４のステップと、
を有することを特徴とする自然言語解析方法。
【請求項６】
前記第３のステップは、前記複数の部分構造のなかで前記部分構造内の前記変換対象構造に含まれる形態素の数が最も多い部分構造である前記第１の部分構造を選択することを特徴とする請求項５記載の自然言語解析方法。
【請求項７】
前記第３のステップは、前記複数の部分構造のなかで前記部分構造内の前記変換対象構造に含まれる形態素の数が最も多く、かつ構造変換後の統語森に含まれる前記統語構造木の数が最も少ない部分構造である前記第１の部分構造を選択することを特徴とする請求項５記載の自然言語解析方法。
【請求項８】
前記第３のステップは、前記複数の部分構造のなかで前記部分構造内の前記変換対象構造に含まれる形態素の数が最も多く、かつ構造変換後の統語森に含まれる前記統語構造木の数が最も少なく、かつ適用される変換規則の数が最も多い部分構造である前記第１の部分構造を選択することを特徴とする請求項５記載の自然言語解析方法。
【請求項９】
自然言語の構造を変換するためにコンピュータに、
自然言語の構造に含まれる任意の変換対象構造を当該変換対象構造とは異なる構造に変換するための変換規則群を記憶手段に記憶するステップと、
入力文字列の形態素列から、複数の統語構造木を含む統語森を求めるステップと、
前記統語森から、前記変換対象構造を少なくとも１つ含む前記統語構造木を含む複数の部分構造を求めるステップと、
各部分構造内の前記変換対象構造に含まれる形態素の数、構造変換後の統語森に含まれる前記統語構造木の数、及び適用される変換規則の数のうちの少なくとも１つに基づいて、前記複数の部分構造のなかから、前記変換規則群を適用して構造変換するための第１の部分構造を選択するステップと、
前記変換規則群のうち、前記第１の部分構造に含まれる各変換対象構造を変換するための各変換規則を用いて、当該第１の部分構造の構造を変換するステップと、
を含む処理を実行させるコンピュータ読出し可能な自然言語解析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械翻訳システムや、質問応答システムなど、日本語や英語などの自然言語を解析する自然言語解析装置に関する。
【背景技術】
【０００２】
近年、自然言語処理技術の進展に伴い、例えば日本語で書かれた文章から英語など他の言語による文章へと翻訳する機械翻訳システムや、あるいは、単語或いは文による利用者からの入力を受け取って、関連する情報を適宜検索して利用者に提供する情報検索システムなどが、広く使われるようになってきている。
【０００３】
また、自然言語で書かれた文章の要旨を短くまとめた抄録や要約を自動生成する自動要約システムや、あるいは自然言語による文によって機器操作をしたり、あるいは各種のサービスを受けたりするための自然言語インタフェースシステムへの期待が高まっている。
【０００４】
そして、音声処理技術の進展に伴い、利用者が発声した文章を自動で文字に変換することで、音声による自然言語文字列の入力を可能にする音声ディクテーションシステムや、電子データとして得られた文章やシステムからの出力メッセージである自然言語文字列を、音声出力に変換する音声合成システムが、徐々に使われるようになってきている。
【０００５】
この様な、自然言語処理技術ならびに音声処理技術の進展に伴って、例えば、人に依頼するときと同じように、喋ることによって、システムを操作したり様々なサービスの提供を受けたりする為の音声対話インタフェースへの期待が高まっている。
【０００６】
この音声対話インタフェースが実現できれば、例えば自動車を運転中の利用者や、家庭で例えば料理を行なっている最中の利用者などが、手を離さずに様々な機器を操作できるようにするハンズフリーなインタフェースが実現されたり、あるいは老人や子供や、あるいは体が不自由な人など機器を操作することが困難な利用者が、安全に利用可能なバリアフリーインタフェースが実現されたりするなど、大きな効果が期待される。さらに、音声による自然言語入力を文字列に変換する音声認識技術と、第１の言語による入力文を第２の言語による文に変換する翻訳技術と、自然言語文字列を音声に変換する音声合成技術とを組み合わせることによって、例えば日本語の音声入力を、例えば英語の音声出力へと翻訳する音声通訳システムへの期待も高まっている。
【０００７】
上述した様な自然言語処理技術の応用システムを実現する為の従来の手法としては、表層的な浅い処理に基づく方法と、入力された自然言語文の内部構造を解析して行なわれる深い処理に基づく方法が存在する。前者の表層的な浅い処理に基づく手法では、前述のような高度な自然言語処理において、実用レベルの性能は実現できない。従って、以下、入力された自然言語文に対し、後者の深い処理を行う自然言語処理を議論の主要対象とする。この深い処理では、入力された自然言語文に対して、例えば文法規則を使った構文解析処理などを行って、よりきめの細かい分析が行なえるのである。
【０００８】
従来、上述した機械翻訳システムや、情報検索システムや、自動抄録システムや、自然言語インタフェースシステムにおいては、まず、入力された自然言語の文に対し構文解析処理を行い、統語的な構造である構文木構造が抽出される。次に、構文木構造に対して、予め用意した変換規則に基づく構造変換処理が行なわれ、入力された自然言語の内容を表す内部表現へと変換がなされる。最後に、内部表現に基づいて、それぞれの応用システムに応じた処理が行なわれる。
【０００９】
即ち、機械翻訳システムにおいては、上述の内部表現に基づく生成処理が行なわれ、対象言語の文字列が生成され出力される。また、情報検索システムにおいては、上述の内部表現に基づいて、データベース等への検索命令が生成され、その検索結果が利用者に提供される。また、自動抄録システムにおいては、１つ以上の入力文に対する上述の内部表現に基づいて、それぞれの重要性や、論理的な関係などが解析され、取捨選択の上、再構成されて、自然言語文章として再構成されて、利用者に提示される。また、自然言語インタフェースシステムにおいては、上述の内部表現に基づいて、制御対象システムに対するコマンドなどが生成され、伝達され、また制御対象システムから利用者へのメッセージは適宜自然言語文字列として利用者に提示される。
【００１０】
前述の音声処理技術を応用したシステムでは、音声入力を認識して自然言語の文字列を得た後、上述の自然言語処理技術の応用システムと同様の処理が行なわれ、この結果得られる自然言語の文字列に基づいて、音声合成処理を施すことによって、音声出力が利用者に提供される。即ち、例えば、音声対話インタフェースシステムにおいては、利用者から入力された音声は、音声認識システムによって自然言語の文字列に変換され、前述の自然言語インタフェースシステムに提供される。そして、この自然言語インタフェースシステムで得られる自然言語文字列が、適宜音声合成システムによって自然言語音声として利用者に提示される。
【００１１】
音声通訳システムでは、利用者からの第１の言語による入力音声は、音声認識システムによって自然言語の文字列に変換され、前述の機械翻訳システムに提供される。そして、機械翻訳システムから得られる第２の言語による自然言語文字列が、適宜音声合成システムによって第２の言語による自然言語音声として出力される。
【００１２】
構文解析処理において、１つの構文木候補（統語構造木）を返す、従来の構文解析では、処理の途中で必然的に生じる曖昧性を取り除く為に、多くの仮定を設定する必要がある。このため、処理の途上で設定した仮定が誤りであった場合に、後戻り処理を行なう必要がでて、処理効率が悪くなるという問題があった。また、すべての可能な仮定を設定してそれぞれについて検証して最適な結果を探索する全解探索を行なうことは、処理量が膨大となり、非現実的であるため、一般に最適解の統語構造木を得られないという問題があった。
【００１３】
ところで、解析では、複数の候補を圧縮して表現する圧縮統語森構造に対し、一度の解析処理で全ての統語構造を効率よく探し出す手法として「Ｇｅｎｅｒａｌｉｚｅｄ  ＬＲ  Ｐａｒｓｉｎｇ／一般化ＬＲアルゴリズム」などが提案され、利用されている（例えば非特許文献１や２を参照）。
【００１４】
しかし、翻訳処理で広く利用されているトランスファは、１つの解釈候補である統語構造木のみを扱うことはできるが、直接この統語森構造を扱うことは出来ない。このため、統語森構造に含まれる各統語構造木を１つづつ仮定して処理する必要があり、上述の過程における全ての問題が同様に生じていた。
【００１５】
また、上述の手法は、曖昧性を持つ複数の解析結果を探索し、圧縮した１つの表現である圧縮統語森として出力する方法は示しているものの、このようにして得られた複数の解釈候補の統語構造木の中から、より最適解の統語構造木を選び出す方法を提供するものではない。
【非特許文献１】The Generalized LR Parsing Algorithm/M.Tomita編,Generalized LR Parsing, Chapter 1, pp1-16, Kluwer Academic Publishers,ISBN0-7923-9201-9, 1991
【非特許文献２】1.2.8節、自然言語処理-基礎と応用-、田中穂積監修、社団法人電子情報通信学会刊、ISBN4-88552-160-2、1999年
【発明の開示】
【発明が解決しようとする課題】
【００１６】
このように、従来は、入力された自然言語文から得られる複数の統語構造木を含む統語森から最適な統語構造木を容易に求めることができず、しかも構造変換は曖昧性の無い木構造に対してのみ適用できるものであったために、曖昧性を持つ自然言語文の構造を変換することができないという問題点があった。
【００１７】
そこで、本発明は上記問題点に鑑み、曖昧性を持つ自然言語文の構造を変換することができる自然言語解析装置を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明は、（１）記憶手段に、自然言語の構造に含まれる任意の変換対象構造を当該変換対象構造とは異なる構造に変換するための変換規則群を記憶し、（２）入力文字列の形態素列から、複数の統語構造木を含む統語森を求め、（３）前記統語森から、前記変換対象構造を少なくとも１つ含む前記統語構造木を含む複数の部分構造を求め、（４）各部分構造内の前記変換対象構造に含まれる形態素の数、各部分構造に含まれる前記統語構造木の数（構造変換後の統語森に含まれる前記統語構造木の数）、及び各部分構造に含まれる前記変換対象構造の数（適用される変換規則の数）のうちの少なくとも１つに基づいて、前記複数の部分構造のなかから、前記変換規則群を適用して構造変換するための第１の部分構造を選択し（５）前記変換規則群のうち、前記第１の部分構造に含まれる各変換対象構造を変換するための各変換規則を用いて、当該第１の部分構造の構造を変換する。
【発明の効果】
【００１９】
本発明によれば、曖昧性を持つ自然言語文の構造を変換することができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の実施形態について図面を参照して説明する。
【００２１】
まず、本実施形態に係る自然言語解析装置の概要を説明する。すなわち、本実施形態に係る自然言語解析装置は、入力された自然言語文から得られる複数の統語構造木（構文木構造）それぞれについて構造変換を行うのではなく、複数の統語構造木を含む圧縮統語森構造（統語森）に対し、適用可能な変換規則を用いて構造変換（トランスファ処理）を行うことによって、最適解の統語構造木の構造変換結果を効率よく得るというものである。
【００２２】
例えば自然言語文から図４４に示すような５つの統語構造木を含む統語森が得られたとする。尚、統語構造木の数え方については、後で図６を用いて説明する。
【００２３】
図４４は統語構造木を模式的に示したもので、当該自然言語文の形態素列の各形態素（表層）はａ〜ｆで示し、これら複数の形態素間の文法規則に基づく意味的な階層構造に含まれる各ノードをＩ〜Ｌ、Ｘ、Ｙ、Ｓで示している。各ノードは、当該ノードの支配下にある１または複数の形態素からなる語に相当する。
【００２４】
また自然言語文の構造を変換するための変換規則の例を図４５に示す。一般に変換規則は、変換対象構造が記述されたマッチングパターンと、当該変換対象構造とは異なる構造から記述されたターゲットパターンを含む。図４５は、変換規則を模式的に示したもので、例えば、１番目の変換規則は、図４４の「ノードＫと表層ｆを子ノードとしてもつノードＹ」という変換対象構造を、「ノードＫと表層ｕを子ノードとしてもつノードＹ」という構造に変換するための変換規則を示している。同様に、２番目の変換規則は、図４４の「表層ｄ、ｅ、ｆを子ノードとしてもつノードＬ」という変換対象構造を、「表層ｖ、ｆ、ｄを子ノードとしてもつノードＬ」という構造に変換するための変換規則を示している。また、３番目の変換規則は、図４４の「表層ａとノードＪを子ノードとしてもつノードＸ」という変換対象構造を、「表層ｔとノードＪを子ノードとしてもつノードＸ」という構造に変換するための変換規則を示している。
【００２５】
ここでは、図４４の統語森に、図４５の３つの変換規則のいずれかを適用する場合を例にとり、本実施形態の自然言語解析装置の処理動作の概要を説明する。すなわち、まず、統語森に１つまたは複数の変換規則を適用すると仮定した場合に、統語森に含まれる複数の統語構造木のうちのどの統語構造木が構造変換されるのかを調べる。
【００２６】
図４６は、図４４の統語森に１番目の変換規則を適用すると仮定した場合を示している。この場合、統語森中の５つの統語構造木のうち、変換対象構造「ノードＫと表層ｆを子ノードとしてもつノードＹ」を含む２つの統語構造木が構造変換される。
【００２７】
図４７は、図４４の統語森に２番目の変換規則を適用すると仮定した場合を示している。この場合、統語森中の５つの統語構造木のうち、変換対象構造「表層ｄ、ｅ、ｆを子ノードとしてもつノードＬ」を含む４つの統語構造木が構造変換される。
【００２８】
図４８は、図４４の統語森に３番目の変換規則を適用すると仮定した場合を示している。この場合、統語森中の５つの統語構造木のうち、変換対象構造「表層ａとノードＪを子ノードとしてもつノードＸ」を含む１つの統語構造木のみが構造変換される。
【００２９】
図４９は、図４４の統語森に２番目と３番目の変換規則を適用すると仮定した場合を示している。この場合、統語森中の５つの統語構造木のうち、２番目の変換規則の変換対象構造と３番目の変換対象構造とを含む１つの統語構造木のみが構造変換される。
【００３０】
図４６〜図４９に示す４つの構造は、図４４に示した統語森に、変換規則を適用すると仮定した場合に構造変換される（１つまたは複数の）統語構造木を含む当該統語森の部分構造である。各部分構造には、上記３つの変換規則群の３つの変換対象構造のうちの少なくとも１つの変換対象構造を含む統語構造木が少なくとも１つ含まれている。
【００３１】
次に、図４６〜図４９に示す４つの部分構造のなかから、最適解の統語構造木を含む最適解の部分構造を選択する。ここで、最適解の部分構造とは、上記４つの部分構造のうち、次の３つの条件のうちの少なくとも１つを満たす部分構造である。
【００３２】
（条件１）部分構造内の変換対象構造に含まれる形態素（表層）の数が最も多いこと。（条件２）構造変換後の統語森に含まれる統語構造木の数が最も少ないこと。（条件３）適用された変換規則の数が最も多いこと。
【００３３】
ここでは、例えば、条件１を満たす部分構造が１つのみであるときには、これを最適解の部分構造として選択する。条件１を満たす部分構造が複数ある場合には、この中で条件２を満たす部分構造が１つのみであるときに、これを最適解として選択する。条件１及び条件２を満たす部分構造が複数ある場合には、これらの中で条件３を満たす部分構造を最適解として選択する。
【００３４】
図４６に示す部分構造では、当該部分構造内で変換対象構造に含まれる形態素（表層）の数は４つであり（図４６では丸で囲まれた表層）、構造変換後の統語森に含まれる統語構造木の数は２つであり、適用された変換規則の数は１つである。
【００３５】
図４７に示す部分構造では、当該部分構造内で変換対象構造に含まれる形態素（表層）の数は３つであり（図４７では丸で囲まれた表層）、構造変換後の統語森に含まれる統語構造木の数は４つであり、適用された変換規則の数は１つである。
【００３６】
図４８に示す部分構造では、当該部分構造内で変換対象構造に含まれる形態素（表層）の数は３つであり（図４８では丸で囲まれた表層）、変換後の統語構造に含まれる統語構造木の数は１つであり、適用された変換規則の数は１つである。
【００３７】
図４９に示す部分構造では、当該部分構造内で変換対象構造に含まれる形態素（表層）の数は６つであり（図４９では丸で囲まれた表層）、構造変換後の統語森に含まれる統語構造木の数は１つであり、適用された変換規則の数は２つである。
【００３８】
部分構造内で変換対象構造に含まれる形態素（表層）の数が最も多いのは、図４９の部分構造であるから、当該部分構造が最適解である。なお、当該部分構造に含まれる統語構造木の数は１つのみであるから、当該統語構造木が図４４の統語森から得られる最適解の統語構造木であると云える。
【００３９】
このようにして選択された最適解の部分構造（最適割当）に含まれる変換対象構造を変換するための変換規則（ここでは、図４５の２番目と３番目の変換規則）を用いて、当該最適解の部分構造の構造を変換する。すなわち、図４９の部分構造中の変換対象構造「表層ｄ、ｅ、ｆを子ノードとしてもつノードＬ」は、図５０に示すように、「表層ｖ、ｆ、ｄを子ノードとしてもつノードＬ」という構造に変換する。さらに、図４９の部分構造中の変換対象構造「表層ａとノードＪを子ノードとしてもつノードＸ」は、図５０に示すように、「表層ｔとノードＪを子ノードとしてもつノードＸ」という構造に変換する。
【００４０】
このように、本実施形態によれば、自然言語の構造を変換する際には、まず、自然言語文から得られる統語森から、変換対象構造を少なくとも１つもつ統語構造木を少なくとも１つ含む複数の部分構造を求め、そのなかから実際に変換規則を適用して構造変換する部分構造を１つ選択する。そして、選択された部分構造に含まれる各変換対象構造を変換するための変換規則を用いて、当該部分構造の構造を変換する。
【００４１】
以下、本実施形態に係る自然言語解析装置について、詳細に説明する。
【００４２】
（自然言語解析装置の構成）
図１は、本発明の一実施形態にかかる自然言語解析装置１００の構成例と、自然言語解析装置１００を用いた機械翻訳装置１０１の構成例を示したものである。機械翻訳装置１０１では、第１の言語を第２の言語へ翻訳するが、ここでは、一例として、第１の言語が日本語、第２の言語が英語の場合を例にとり説明する。
【００４３】
図１において、自然言語解析装置１００は、構文解析部２、変換規則記憶部３、割当候補抽出部４、割当候補評価部５、構造絞込部６、構造変換部７を含む。更に、機械翻訳装置１０１は、形態素解析部１、訳文生成部８を含む。
【００４４】
形態素解析部１は、日本語の入力文字列Ｓを受け取り、形態素解析を行なって、形態素列Ｍを出力する。ここで行なわれる形態素解析処理は、公知公用の自然言語解析処理を用いればよく、また、本願発明の要旨ではないので、その詳細な説明は省略する。
【００４５】
例えば、入力文字列Ｓとして図５（ａ）に示すような「リムジンって空港バスのことですか」が入力された場合は、形態素解析部１で形態素解析を行った結果、図５（ｂ）に示すような「リムジン・って・空港・バス・の・こと・ですか」という形態素列Ｍが出力される。
【００４６】
構文解析部２は、形態素解析部１から出力された形態素列Ｍを受け取り、（例えば構文解析部２に）予め記憶された文法規則、語彙辞書を参照して構文解析処理を行なう。
【００４７】
語彙辞書は、第１の言語の各単語について、その品詞などを示したものである。
【００４８】
図２は、文法規則の一例を示したもので、図３は、語彙辞書の一例であって、上記形態素列Ｍ「リムジン・って・空港・バス・の・こと・ですか」に含まれる各形態素に対する品詞名を示している。
【００４９】
図２の文法規則では、文（Ｓ）は前置詞句（ＰＰ）と文（Ｓ）からなり、文（Ｓ）は名詞句（ＮＰ）と動詞句（ＶＰ）からなり、前置詞句（ＰＰ）は名詞句（ＮＰ）と付属語（Ｆ）からなることを示している。同様に、名詞句（ＮＰ）は名詞句（ＮＰ）、付属語（Ｆ）、名詞句（ＮＰ）からなる場合と、名詞（Ｎ）と名詞句（ＮＰ）からなる場合と、名詞（Ｎ）のみからなる場合があることを示している。さらに、動詞句（ＶＰ）は動詞（Ｖ）からなることも示している。
【００５０】
構文解析部２における構文解析処理は、図２に示すような文法規則に基づいて行なわれる。構文解析部２では、形態素列Ｍの統語的な内部構造を表現する少なくとも１つの統語構造木が得られる。１つの統語構造木は、形態素列に含まれる各形態素間の関係を表した意味的な階層構造である。構文解析処理の結果、例えば、各形態素間であり得る係り受け関係の違いなどの曖昧性から複数の統語構造木が得られる。少なくとも１つの統語構造木が存在する場合に、これらを包含して表現された解析済圧縮統語構造Ｆを出力する。ここで行なわれる構文解析処理は、例えば、前述のＧｅｎｅｒａｌｉｚｅｄ  ＬＲ  Ｐａｒｓｉｎｇ（一般化ＬＲアルゴリズム）などを用いて行なうことができ、またその解析結果として得られる圧縮共有統語森構造（Ｐａｃｋｅｄ  Ｓｈａｒｅｄ  Ｓｙｎｔａｘ  Ｆｏｒｅｓｔ）が、そのまま本装置での解析済圧縮統語構造の表現手段として利用可能である。従って、以下の説明では、この圧縮共有統語森構造を、構文解析部２の出力である解析済圧縮統語構造Ｆとする。解析済圧縮統語構造Ｆは、形態素列を構文解析した結果得られる１つまたは複数の統語構造木を１つの階層構造により表したものであると云える。
【００５１】
図６は、構文解析部２から出力される解析済圧縮統語構造（簡単に統語森とも呼ぶ）Ｆの一例を示したもので、上記形態素列Ｍ「リムジン・って・空港・バス・の・こと・ですか」に対し構文解析処理を行った結果得られる解析済圧縮統語構造（以下、図６に示す解析済み圧縮統語構造を統語森Ａと呼ぶ）である。図６に示すように、統語森構造の葉（葉ノード）は、形態素列Ｍに含まれる形態素（トークンとも呼ぶ）であり、この上位に、文法規則に基づく構文解析処理によって得られた複数の統語構造木を圧縮して表現した圧縮共有統語森構造が示されている。
【００５２】
統語森上の各ノードは、当該ノードの支配下にある語の品詞を示す記号（文（Ｓ）、前置詞句（ＰＰ）、名詞句（ＮＰ）、動詞句（ＶＰ）、名詞（Ｎ）、付属語（Ｆ）、動詞（Ｖ）など）と当該統語森上での当該ノードの識別子（ここでは番号）とを有し、ここでは、各ノードのもつ品詞を示す記号及び番号とをラベルと呼ぶ。
【００５３】
例えば、統語森上の葉ノードとして表される「リムジン」という形態素は名詞（Ｎ）であるから、この唯一の親ノードのラベルは「Ｎ１」であり、「って」という形態素は付属語（Ｆ）であるから、この唯一の親ノードのラベルは「Ｆ２」であり、「ですか」という形態素は動詞（Ｖ）であるから、この唯一の親ノードのラベルは「Ｖ７」となっている。
【００５４】
文法上、名詞句（ＮＰ）と付属語（Ｆ）とで前置詞句（ＰＰ）となるから、ラベル「ＮＰ８」のノードとラベル「Ｆ２」のノードを子ノードとしてもつノードは前置詞句（ＰＰ）であり、そのラベルは、「ＰＰ１４」となっている。
【００５５】
また、ラベル「ＮＰ１５」のノード（以下、簡単にノード「ＮＰ１５」と呼ぶ）は、ノード「ＮＰ８」とノード「Ｆ２」とノード「ＮＰ１２」を支配する。ノード「ＮＰ１２」は、同時にノード「ＮＰ１６」からも支配されており、ノード「ＮＰ１５」とノード「ＮＰ１６」に共有されていることが表現されている。
【００５６】
ノード「ＮＰ１７」は「ｃ１７ａ」と「ｃ１７ｂ」というラベルのノードを持ち、図６ではこれら２つのノードは四角で囲まれた黒丸にそれぞれ対応している。これは、統語森Ａ上のノード「ＮＰ１７」以下に２つの部分構造（ノード「ｃ１７ａ」以下の部分構造とノード「ｃ１７ｂ」以下の部分構造）があることを示している。ノード「ＮＰ１５」のように、当該ノード以下に１つのみの部分構造がある場合には、四角を省略して、唯１つの黒丸で示している。
【００５７】
ノード「ＮＰ１５」の黒丸、ノード「ＮＰ１７」がもつ２つのノードにそれぞれ対応する黒丸などを候補ノードと呼ぶ。そして、１または複数の候補ノードをもつノードを通常ノードと呼ぶ。通常ノードは図６では、ラベルが内部に付された円で示している。通常ノードは、１つまたは複数の候補ノードをもっていると云える。
【００５８】
統語森Ａのノード「ＮＰ１７」以下の構造には、候補ノード「ｃ１７ａ」以下で表現される統語森Ａの部分的な構造、すなわち、部分森構造（１つ又は複数の（部分的な）統語構造木を含む構造）と、候補ノード「ｃ１７ｂ」以下で表現される部分森構造を含み、両者を圧縮して表現したものとなっている。なお、図６では、候補ノード「ｃ１７ａ」、「ｃ１７ｂ」以下の部分森構造には、それぞれ１つの部分統語構造木のみが含まれている。
【００５９】
ここでは、１つの通常ノードに対して候補ノードが１つしかない場合には、図６の四角は省略して記載する。つまり、例えばノード「ＮＰ８」はノード「Ｎ１」に接続する１つの候補ノードのみをもつから、候補ノード「ＮＰ８」を表す黒丸の周りの四角は記載されない。また、全てのノードは、後に説明する処理に利用する為に、属性情報として必須フラグと不要フラグをもつ。
【００６０】
構文解析部２では、出力される統語森Ｆ（のルートノード以下の構造）に含まれる統語構造木の数や、複数の候補ノードをもつ通常ノード以下の構造に含まれる統語構造木の数も合わせて出力する。例えば、統語森Ｆ上の任意のノードについて、このノード以下の構造に複数の統語構造木が含まれている場合には、当該ノードは当該ノード以下の構造に含まれる統語構造木の数を示す属性情報Ｐを有するものとする。
【００６１】
統語森Ａのルートノードであるノード「Ｓ２１」は３つの候補ノードをもつから、各候補ノード以下の構造に含まれる統語構造木の数の合計が、当該ルートノードに含まれる統語構造木の数となる。
【００６２】
すなわち、図６の統語森Ａのノード「ＮＰ１７」以下は、２つの（部分的な）統語構造木を含むことから、ノード「ＮＰ１７」は「Ｐ＝２」という属性情報をもつ。また、ノード「Ｓ２０」以下は、２つの（部分的な）統語構造木を含むことから、ノード「Ｓ２０」は「Ｐ＝２」という属性情報をもつ。
【００６３】
さらに、統語森Ａのルートノードであるノード「Ｓ２１」のもつ３つの候補ノードのうちの１つである候補ノード「ｃ２１ａ」以下の構造には、ノード「ＮＰ１７」が含まれているから、候補ノード「ｃ２１ａ」以下の構造には、２つの統語構造木が含まれている。また、ルートノード「Ｓ２１」の候補ノード「ｃ２１ｂ」以下の構造には、ノード「ＮＰ１７」が含まれているから、候補ノード「ｃ２１ａ」以下の構造には１つの統語構造木が含まれている。ルートノード「Ｓ２１」の候補ノード「ｃ２１ｃ」以下の構造には、ノード「Ｓ２０」が含まれているから、候補ノード「ｃ２１ｃ」以下の構造には、２つの統語構造木が含まれている。従って、統語森Ａに含まれる統語構造木の数は全部で５（＝２＋１＋２）であり、ルートノード「Ｓ２１」は「Ｐ＝５」という属性情報をもつ。
【００６４】
図７〜図１１は、それぞれ、統語森Ａに含まれる５つの統語構造の候補、すなわち統語構造木Ａ１〜Ａ５を示したものである。
【００６５】
図７に示す統語構造木Ａ１は、ルートノード「Ｓ２１」のもつ候補ノード「ｃ２１ａ」以下の構造であり、「こと」と「ですか」の間で、名詞句と動詞句とに区切られ、当該名詞句は名詞句「リムジン」と付属語「って」と名詞句「エアポート・バス・の・こと」とからなる構造をもつことがわかる。
【００６６】
図８に示す統語構造木Ａ２は、ルートノード「Ｓ２１」のもつ候補ノード「ｃ２１ａ」以下の構造であり、「こと」と「ですか」の間で、名詞句と動詞句とに区切られ、当該名詞句は名詞句「リムジン・って・エアポート・バス」と付属語「の」と名詞句「こと」とからなる構造をもつことがわかる。
【００６７】
図９に示す統語構造木Ａ３は、ルートノード「Ｓ２１」のもつ候補ノード「ｃ２１ｂ」以下の構造であり、「の」と「こと」の間で、前置詞句と文とに区切られ、当該前置詞句は名詞句「リムジン・って・エアポート・バス」と付属語「の」とからなる構造をもち、当該文は名詞句「こと」と動詞句「ですか」とからなる構造をもつことがわかる。
【００６８】
図１０に示す統語構造木Ａ４は、ルートノード「Ｓ２１」のもつ候補ノード「ｃ２１ｃ」以下の構造であり、「って」と「エアポート」の間で、前置詞句と文とに区切られ、当該前置詞句は名詞句「リムジン」と付属語「って」とからなる構造をもち、当該文は前置詞句「エアポート・バス・の」と文「こと・ですか」とからなる構造をもつことがわかる。
【００６９】
図１１に示す統語構造木Ａ５は、ルートノード「Ｓ２１」のもつ候補ノード「ｃ２１ｃ」以下の構造であり、「って」と「エアポート」の間で、前置詞句と文とに区切られ、当該前置詞句は名詞句「リムジン」と付属語「って」とからなる構造をもち、当該文は名詞句「エアポート・バス・の・こと」と動詞句「ですか」とからなる構造をもつことがわかる。
【００７０】
図１の説明に戻り、変換規則記憶部３は、構文解析部２から出力される図６に示したような統語森Ｆの構造を変換する為の規則が記憶されている。ここでは、第１の言語（例えば日本語）から第２の言語（英語）への機械翻訳を行う場合を例にとり説明しているので、変換規則記憶部３には、日本語（の統語森Ｆ）の構造を英語の構造に変換するための変換規則が予め記憶されている。
【００７１】
図４は、変換規則記憶部３に記憶されている変換規則の例（＃１〜＃３）を示したものである。変換規則は、「ＭＰ＝」に続くマッチングパターン部と、「ＴＰ＝」に続くターゲットパターン部とから構成される。マッチングパターン部には、その変換規則を適用する（統語森上の）部分構造（すなわち、変換対象構造）が記述されている。例えば、図４の変換規則＃１では、マッチングパターン部が「［Ｓ＿ａ［ＮＰ＿ｂ，“って”，Ｓ＿ｃ［ＮＰ＿ｄ，“の”，“こと”，“ですか”］］］」であることから、この規則を適用する為には、統語森Ｆの中に、まず、１つの名詞句ノードＮＰ＿ｄと、表層が“の”と、“こと”と、“ですか”である３つの葉ノードによって構成される文ノードＳ＿ｃがあることと、さらに、別の名詞句ノードＮＰ＿ｂと、表層が“って”である葉ノードと、上記文ノードＳ＿ｃから構成される別の文ノードＳ＿ａが、部分構造として含まれていることが、この変換規則を適用可能な条件として表現されていることになる。
【００７２】
本実施形態で用いる変換規則は、マッチングパターンが指定しているのが、あくまで統語森の部分的な構造である点と、指定されている部分構造についても、部分構造の構成要素の並びと、このならび全体を支配する部分構造のルートなどを指定しているのみで、部分構造の内部構造の詳細を指定していないことに特徴がある。なお、マッチングパターン中の大文字で表現された記号は変数部を表し、ある変換規則をある統語森に適用した際に、対応する部分を変数に代入して後に利用できるようにしている。以降、この変数を、変数トリガーと呼ぶこととする。
【００７３】
マッチングパターン中のダブルクオーテーションマークで囲まれた文字列は、変換規則を適用する統語森に含まれるべき葉ノードの表層文字列を表現し指定するようにしている。以後この表層ノードに対応する文字列を表層トリガーと呼ぶこととする。また、以降、前述の変数トリガーと、この表層トリガーを総称して、ＭＰトリガーと呼ぶこととする。
【００７４】
一方、変換規則のターゲットパターン部には、構造変換方法が記述されている。例えば、図４の変換規則＃１のターゲットパターン部を例にとり説明する。変換規則＃１のターゲットパターン部は、「［ＤＥＮＯＴＥ（ｔｙｐｅ＝ｑｕｅｓｔｉｏｎ）［ｓｂｊＮＰ＿ｂ，ｏｂｊ／ＮＰ＿ｄ］］」であることから、マッチングパターン部で指定された部分構造は、“ＤＥＮＯＴＥ（ｔｙｐｅ＝ｑｕｅｓｔｉｏｎ）”で表現されるノードで置換し、かつマッチングパターン中の変数ＮＰ＿ｂおよび変数ＮＰ＿ｄに割り当てられた変換対象の部分構造を、それぞれ“ｓｂｊ（主語）”および“ｏｂｊ（目的語）”という関係で、この順に“ＤＥＮＯＴＥ（ｔｙｐｅ＝ｑｕｅｓｔｉｏｎ）”で表現されるノードの子ノードとして接続してなる構造に変換することが表現されている。
【００７５】
図１の割当候補抽出部４は、構文解析部２から出力される統語森Ｆを受け取る。そして、変換規則記憶部３で記憶されている変換規則のなかから、当該統語森に対し適用可能な変換規則を収集し、この収集された各変換規則中の変数を割り当てることが可能な割当候補を全て洗い出し、割当候補セットＱとして出力する。この割当候補抽出部４の処理動作の詳細は後述する。
【００７６】
図１２は、図６の統語森Ａに対して、図４の変換規則＃１を適用する際の１つの割当候補である割当候補Ａ１を示したものである。ここでは、変換規則＃１のマッチングパターン中の変数Ｓ＿ａが統語森Ａのノード「Ｓ２１」に割り当てられ、変数ＮＰ＿ｂがノード「ＮＰ８」に割り当てられ、変数Ｓ＿ｃがノード「Ｓ２０」に割り当てられ、変数ＮＰ＿ｄがノード「ＮＰ１２」に割り当てられる。なお、図１２において、上記各変数が割り当てられたノード、マッチングパターン中の表層トリガーである、“って”、“の”、“こと”、および“ですか”に対応する葉ノードには、斜線を入れて表している。
【００７７】
割当候補抽出部４では、変換規則＃１のマッチングパターン中の括弧付きの入れ子構造に従った形で、入れ子内の全ての変数トリガーならびに表層トリガーがその出現順に（かつ隙間無く）並ぶ構造を統語森から探索するようになっている。すなわち、図１２に示すように、ノード「Ｓ２１」以下の内部構造中のノード「ＮＰ８」と、葉ノード「って」と、ノード「Ｓ２０」とが、その内部構造の詳細を問わずに、ノード「Ｓ２１」の支配する、スパン全体を隙間無く、出現順に被覆していることがわかる。また、ノード「Ｓ２０」以下の内部構造である、ノード「ＮＰ１２」と、葉ノード「の」と、「こと」と、「ですか」も、その内部構造の詳細を問わずにノード「Ｓ２０」の支配するスパン全体を、隙間無く、出現順に被覆していることがわかる。
【００７８】
図１３は、図６の統語森Ａに対して、図４の変換規則＃２を適用する際の１つ目の割当候補である割当候補Ａ２ａを示したものである。ここでは、変換規則＃２のマッチングパターン中の変数ＮＰ＿ｅが統語森Ａのノード「ＮＰ１６」に割り当てられ、変数ＮＰ＿ｆがノード「ＮＰ１２」に割り当てられ、表層トリガーである“の”、および“こと”も図１３に示したとおりに割り当てられている。すなわち、図１３では、変換規則＃２が、統語森Ａの部分的な構造、すなわち、ノード「ＮＰ１６」以下の当該ノード「ＮＰ１６」が支配する部分森構造に対して適用されている。図１３において、上記各変数が割り当てられたノード、マッチングパターン中の表層トリガーに対応する葉ノードには、斜線を入れて表している。
【００７９】
図１４は、図６の統語森Ａに対して、図４の変換規則＃２を適用する際の、もう１つの割当候補である割当候補Ａ２ｂを示したものである。ここでは、変換規則＃２のマッチングパターン中の変数ＮＰ＿ｅが統語森Ａのノード「ＮＰ１７」に割り当てられ、変数ＮＰ＿ｆがノード「ＮＰ１５」に割り当てられ、また表層トリガーである“の”、および“こと”も図１４に示したとおりに割り当てられている。すなわち、図１４では、変換規則＃２が統語森Ａのノード「ＮＰ１７」以下の部分森構造に対して適用されている。図１４において、上記各変数が割り当てられたノード、マッチングパターン中の表層トリガーに対応する葉ノードには、斜線を入れて表している。
【００８０】
図１の割当候補評価部５は、割当候補抽出部４で得られる割当候補セットＱの各要素（各割当候補）を評価し、割当候補セットＱの要素のうちの１つであって、実際に適用すべき最適な割当候補である最適割当ｑを選択し、出力する。この割当候補評価部５の処理動作の詳細は後述する。
【００８１】
図１の構造絞込み部６は、割当候補評価部５によって選定された最適割当ｑに基づいて、統語森Ｆから不要な部分構造を削除した絞込済圧縮統語構造Ｇを出力する。なお、この構造絞込み部６の処理動作の詳細は後述する。
【００８２】
図１の構造変換部７は、絞込済圧縮統語構造Ｇを受け取り、変換規則記憶部３に記憶されている変換規則を参照して、実際の圧縮統語構造の構造変換処理を行なうことによって、変換済統語意味構造Ｈを出力する。
【００８３】
なお、ここで行なわれる構造変換処理は、従来の、１つの統語構造木に対する構造変換処理であるトランスファ処理を、複数の統語構造木を内包する統語森に対して適用するものであるが、前述の構造絞込部６の働きによって、構造変換部７では、変換規則を通常のトランスファ処理と同様の方法で適用するだけで、統語森をトランスファできるようになっている。
【００８４】
構造変換部７で構造変換処理を行った後、複数の候補（複数の統語構造木）が残っている場合には、例えば確率情報や、共起頻度情報などの従来技術を併用するなどして、候補を１つに絞込む。このための手法は、複数候補を扱う従来の自然言語解析処理と同様の処理であり、また、本願発明の要旨ではないので説明は省略する。
【００８５】
図１の訳文生成部８は、変換済統語意味構造Ｈを受け取り、翻訳対象言語（第２の言語であって、ここでは例えば英語）の語彙辞書や生成文法規則などを参照して第２の言語による翻訳結果文字列Ｔを生成し、出力する。ここでの処理も従来の機械翻訳システムにおける対象言語の生成処理と同様の処理であり、本願発明の要旨ではないので説明は省略する。
【００８６】
（自然言語解析装置の処理動作）
次に、図１の自然言語解析装置１００を含む機械翻訳装置１０１の処理動作について説明する。
【００８７】
図１５は、機械翻訳装置１０１の全体の処理動作を示す処理Ａのフローチャートであり、まず、図１５を参照して機械翻訳装置１０１の処理の流れを説明した後に、割当候補抽出部４、割当候補評価部５、構造絞込部６の動作について詳しく説明する。
【００８８】
まず、図１５を参照して、機械翻訳装置１０１の処理動作について説明する。
【００８９】
機械翻訳装置１０１には文字列Ｓが入力される。形態素解析部１は、入力文字列Ｓを受け取ると（ステップＳ１）、形態素解析を行って形態素列Ｍを得る（ステップＳ２）。
【００９０】
形態素解析部１で得られた形態素列Ｍは構文解析部２に入力する。構文解析部２は、形態素列Ｍに対し構文解析を行い、解析済圧縮統語構造Ｆ（統語森Ｆ）を出力する（ステップＳ３）。
【００９１】
なお、構文解析部２で形態素列Ｍが受理されなかった場合（ステップＳ４のＹｅｓ）には、ここで処理を終了し、ステップＳ１へ戻り、新たな文字列の入力を待つ。また、構文解析部２で形態素列Ｍが受理された場合（ステップＳ４のＮｏ）には、ステップＳ５へ進む。  割当候補抽出部４は、構文解析部２で出力された統語森Ｆを基に、後述する処理Ｂを行い、割当候補セットＱを得る（ステップＳ５）。割当候補セットＱが空の場合には、ステップＳ１２へ進み、空でない場合にはステップＳ７へ進む（ステップＳ６）。
【００９２】
ステップＳ７では、割当候補評価部５において、割当候補セットＱを基に、後述する処理Ｄを行って、最適割当ｑを出力する。
【００９３】
構造絞込部６は、最適割当ｑを基に後述する処理Ｇを行い、統語森Ｆから不要な部分構造を排除して得られる絞込済圧縮統語構造Ｇを出力する（ステップＳ８）。そして、構造変換部７は、最適割当ｑに従って、絞込済圧縮統語構造Ｇに対して、少なくとも１つの変換規則を適用して、変換済統語意味構造Ｈを出力する（ステップＳ９）。
【００９４】
訳文生成部８において、変換済統語意味構造Ｈに基づいて、翻訳結果である第２の言語の文字列Ｔを生成する（ステップＳ１０）。
【００９５】
一方、ステップＳ１２では、構造変換部７において、統語森Ｆから１つの統語構造木が選択された後、従来と同様のトランスファ処理を行い、この結果得られる変換済統語意味構造Ｈに基づいて、訳文生成部８において第２の言語の文字列Ｔを生成する。ステップＳ１２の翻訳処理動作は、従来と同様である。
【００９６】
ステップＳ１０あるいはステップＳ１２で生成された第２の言語の文字列Ｔが出力される（ステップＳ１１）。
【００９７】
なお、入力文字列Ｓから得られた形態素列Ｍが構文解析部２に受理されない場合もあり得るので、この場合を考慮しステップＳ４を設けたが、ステップＳ４はなくてもよい。また、ステップＳ６、ステップＳ１２は、構文解析の結果得られた統語森Ｆに対して適用可能な変換規則の割当候補が見つからなかった場合の処理であるが、本発明の要旨ではないので説明は省略する。
【００９８】
次に、割当候補抽出部４の処理動作（図１５のステップＳ５の処理動作）について、図１６、図１７に示すフローチャートを参照して説明する。割当候補抽出部４は、図１６の処理Ｂを行う。なお、処理Ｂは図１７の処理Ｃを含む。
【００９９】
まず、処理Ｂについて、図１６に示すフローチャートを参照して説明する。割当候補抽出部４は、解析済圧縮統語構造Ｆ（統語森Ｆ）を受け取ると（ステップＳ２１）、変換規則記憶部３に記憶されている変換規則の中から、統語森Ｆの葉ノードと一致する表層トリガーを持つ全ての変換規則の集合Ｒを得る（ステップＳ２２）。また、初期設定として、割当候補セットＱを空に設定する（ステップＳ２３）。
【０１００】
変換規則の集合Ｒが空である場合には、ステップＳ２９へ進み、空でない場合には、ステップＳ２５へ進む（ステップＳ２４）。
【０１０１】
ステップＳ２５では、変換規則の集合Ｒの要素である変換規則を１つずつ取出し、これを変換規則ｒとする。ステップＳ２６では、変換規則ｒを用いて処理Ｃを行う。ステップＳ２７では、変換規則ｒが集合Ｒの最後の要素でないときには、ステップＳ２８へ進み、集合Ｒから次の変換規則ｒを取り出し、ステップＳ２６へ進む。このように、変換規則の集合Ｒの全要素について処理Ｃを行うまで、ステップＳ２６〜ステップＳ２８を繰り返す。
【０１０２】
ステップＳ２７で変換規則の集合Ｒの全要素について処理Ｃを行った後はステップＳ２９へ進み、割当候補セットＱを出力する。
【０１０３】
ステップＳ２６の処理Ｃについて、図１７に示すフローチャートを参照して説明する。
【０１０４】
まず、変換規則ｒのマッチングパターンＭＰを得る（ステップＳ３１）。そして、ＭＰ中の全ての表層トリガーの集合Ｔｓを得る（ステップＳ３２）。また、ＭＰ中の全ての変数トリガーの集合Ｔｖを得る（ステップＳ３３）。
【０１０５】
表層トリガーの集合Ｔｓの各要素（各表層トリガー）ｔｓについて、当該表層トリガーｔｓに一致する統語森Ｆ中の葉ノードのラベルの集合Ｎ（ｔｓ）を求める（ステップＳ３４）。また、変数トリガーの集合Ｔｖの各要素（各変数トリガー）ｔｖについて、当該変数トリガーｔｖを割り当てる統語森Ｆ中のノードのラベルの集合Ｎ（ｔｖ）を求める（ステップＳ３５）。
【０１０６】
変換規則ｒのマッチングパターンＭＰ中のＭＰトリガーの集合Ｔを求める（ステップＳ３６）。なお、集合Ｔは、集合Ｔｓと集合Ｔｖの和集合である。
【０１０７】
ＭＰトリガーの集合Ｔの要素である各表層トリガー及び各変数トリガーに対応する、各表層トリガーに一致する葉ノードのラベルの集合Ｎ（ｔｓ）の要素と、各変数トリガーを割り当てるノードのラベルの集合Ｎ（ｔｖ）の要素の組合せのうち、可能な組合せの集合Ｘを求める（ステップＳ３７）。
【０１０８】
集合Ｘが空である場合（ステップＳ３８のＹｅｓ）、すなわち、統語森Ｆに変換規則ｒを適用した場合に、各ＭＰトリガーを割り当てることの可能なノードの組合せが存在しない場合には、処理Ｃを終了する。集合Ｘが空でない場合（ステップＳ３８のＮｏ）にはステップＳ３９へ進み、集合Ｘから要素（ノードの組合せ）を１つ取り出し、それをｘとする（ステップＳ３９）。
【０１０９】
次に、ノードの組合せｘが次の条件を満足するかを検査する（ステップＳ４０）。
【０１１０】
（条件）ノードの組合せｘに含まれる各ノードが、統語森Ｆの中で、ＭＰ中で指定されている表層トリガー及び変数トリガーの順序と同じ順序で隙間無く出現し、しかも、ノードの組合せｘに含まれる各ノードが、ＭＰ中で指定されている表層トリガー及び変数トリガー間の階層関係と同じ階層関係をもつ。
【０１１１】
ノードの組合せｘが上記条件を満足するものでないときには（ステップＳ４１のＮｏ）、ステップＳ４３へ進む。ノードの組合せｘが上記条件を満足する場合には（ステップＳ４１のＹｅｓ）、ステップＳ４２へ進み、ｘを割当候補セットＱの要素に追加する。上記ステップＳ４０〜ステップＳ４１を集合Ｘの全要素について行う（ステップＳ４３、ステップＳ４４）。
【０１１２】
次に、割当候補評価部５の処理動作（図１５のステップＳ７の処理動作）について、図１８〜図２２に示すフローチャートを参照して説明する。割当候補評価部５は、処理Ｄを行う。なお、図１８の処理Ｄには、図１９〜図２０の処理Ｅを含み、処理Ｅは、図２１〜図２２の処理Ｆを含む。
【０１１３】
まず、処理Ｄについて、図１８に示すフローチャートを参照して説明する。割当候補評価部５は、割当候補セットＱを受け取ると（ステップＳ５１）、割当候補セットＱの要素（割当候補）を１つ取り出し、これをｐとする（ステップＳ５２）。割当候補ｐに対し、処理Ｅを行って、割当候補ｐの評価値を求める（ステップＳ５３）。後述するように、処理Ｅにより、割当候補ｐに対し、評価値として評価値ＣＲ１〜ＣＲ４が得られる。
【０１１４】
割当候補セットＱから要素を１つずつ取出して、割当候補セットＱの全ての要素に対し評価値を求める（ステップＳ５３〜ステップＳ５５）。割当候補セットＱの全ての要素に対し評価値を求めたら（ステップＳ５４のＹｅｓ）、割当候補セットＱの要素のうち最も評価値の高い要素を最適割当ｑとして選択する（ステップＳ５６）。
【０１１５】
すなわち、後述する処理Ｅにより求めた評価値ＣＲ１が「Ｙｅｓ」である割当候補のなかから、評価値ＣＲ２、評価値ＰＣＲ３、評価値ＣＲ４のうちの少なくとも１つを用いて、最適割当ｑを選択する。
【０１１６】
ステップＳ５３の処理Ｅについて、図１９、図２０に示すフローチャートを参照して説明する。図１８のステップＳ５２で得られた割当候補ｐを受け取ると（ステップＳ６１）、まず、統語森Ｆ中の各ノードのもつ必須フラグ及び不要フラグをクリアする（ステップＳ６２）。ここでは、説明の簡単のため、必須フラグ／不要フラグ（例えば必須フラグビット／不要フラグビット）が「１」のときの状態を「ＯＮ」と呼び、「０」のときの状態を「ＯＦＦ」と呼ぶ。フラグをクリアするとは、フラグを「ＯＦＦ」にするということである。
【０１１７】
さて、割当候補ｐを受け取ると、当該割当候補ｐで各ＭＰトリガーｔを割り当てた統語森Ｆ中のノードの必須フラグをＯＮにする（ステップＳ６３）。そして、後述する処理Ｆを行って、統語森Ｆの各ノードの必須フラグ、不要フラグを更新する（ステップＳ６４）。
【０１１８】
処理Ｆは、統語森Ｆの各ノードについて、必須フラグおよび不要フラグの値をチェックするための処理である。割当候補ｐの割当方法に従って、統語森Ｆに変換規則を適用した場合に、統語森Ｆ中で必須となるノードは必須フラグがＯＮとなり、不要となるノードは不要フラグがＯＮとなる。割当候補ｐが統語森Ｆに適用可能な場合には、統語森Ｆの各ノードの必須フラグと不要フラグは、多くてもいずれか一方のみがＯＮである。統語森Ｆには、必須フラグと不要フラグがともにＯＮであるノードが存在する場合には、割当候補ｐは統語森Ｆに適用不可能となる。必須フラグと不要フラグがともにＯＮであるノードをここでは矛盾ノードと呼ぶ。
【０１１９】
統語森Ｆに変換規則を適用した場合に、当該変換規則に含まれる変数トリガーや表層トリガー（これらをまとめてＭＰトリガーと呼ぶ）の１つの割当方法を示したものが割当候補である。この割当方法が統語森Ｆに適しているか否かを判定するために、本実施形態では矛盾ノードの有無を調べている。
【０１２０】
統語森Ｆに、ある変換規則を適用可能な場合に、当該変換規則の各ＭＰトリガーの（統語森中のノードへの）割当方法を示す割当候補にとって、当該変換規則の各ＭＰトリガーが割当られている各ノードと、当該ノードからみた親ノードや子ノードは必須のノード（必須フラグがＯＮであるノード）であり、さらに、必須フラグがＯＮであるノードの親ノードや子ノードも必須のノード（必須フラグがＯＮであるノード）である。
【０１２１】
従って、例えば、統語森Ｆに複数（例えば２つ）の変換規則を適用可能な場合に、各変換規則の各ＭＰトリガーの（統語森中のノードへの）割当方法を示す割当候補において、一方の変換規則を適用した場合に不要となるノードが、他方の変換規則を適用した場合に必須となるようなノードが上記矛盾ノードである。
【０１２２】
ステップＳ６４で処理Ｆを行った後、統語森Ｆ中のノードの中に、必須フラグと不要フラグがともにＯＮであるような矛盾ノードが存在する場合には（ステップＳ６５のＹｅｓ）、ステップＳ７１へ進む。矛盾ノードがない場合（ステップＳ６５のＮｏ）にはステップＳ６６へ進む。
【０１２３】
ステップＳ６６では、統語森Ｆ中のノードにフラグが変更されたノードがある場合（ステップＳ６６のＹｅｓ）には、ステップＳ６４へ戻る。統語森Ｆ中のノードにフラグが変更されたノードがない場合（ステップＳ６６のＮｏ）には、ステップＳ６７へ進む。
【０１２４】
ステップＳ６７では、割当候補ｐの適用可否を示す評価値ＣＲ１を「ＹＥＳ」とし、ステップＳ６８へ進む。また、ステップＳ６５において、統語森Ｆ中に矛盾ノードがある場合にはステップＳ７１において、割当候補ｐの適用可否を示す評価値ＣＲ１を「ＮＯ」とする。
【０１２５】
ステップＳ６８では、統語森Ｆにもともとある葉ノードの数をＬ０とする。ステップＳ６９では、割当候補ｐで各ＭＰトリガーを割り当てた統語森Ｆ中のノードが被覆する部分森構造の葉ノードの数をＬｔとする。そして、ステップＳ７０では、ＬｔをＬ０で除して、評価値ＣＲ２（＝Ｌｔ／Ｌ０）を求める。すなわち、評価値ＣＲ２は、割当候補ｐの被覆範囲の広さに対する評価値である。
【０１２６】
次に、図２０のステップＳ７２へ進み、統語森Ｆに含まれる統語構造木の数をＰ０とすし、ステップＳ７３へ進む。ステップＳ７３では、統語森Ｆから不要フラグがＯＮであるノードを削除した場合に、残存する統語構造木の数をＰｔとする。そして、ステップＳ７４では、Ｐ０をＰｔで除して、評価値ＣＲ３（＝Ｐ０／Ｐｔ）を求める。すなわち、評価値ＣＲ３は、割当候補ｐによる構造絞込の程度に対する評価値である。
【０１２７】
次に、ステップＳ７５では、割当候補ｐで適用されている変換規則の数を評価値ＣＲ４とする。
【０１２８】
以上で、割当候補ｐの適用可否を示す評価値ＣＲ１が「ＹＥＳ」の場合には、割当候補ｐに対しては、さらに評価値ＣＲ２〜ＣＲ４が求まり、ステップＳ７６では、これら評価値ＣＲ２〜ＣＲ４を出力する。なお、割当候補ｐの適用可否を示す評価値ＣＲ１が「ＮＯ」の場合には、割当候補ｐに対し評価値ＣＲ２〜ＣＲ４は求めない。
【０１２９】
最後に、ステップＳ７７では、割当候補ｐの評価値ＣＲ１を出力する。
【０１３０】
次に、図１９のステップＳ６４の処理Ｆについて、図２１〜図２２に示すフローチャートを参照して説明する。まず、統語森Ｆのノードｎを受け取る（ステップＳ８１）。当該ノードｎが、通常ノードの場合には（ステップＳ８２のＹｅｓ）、ステップＳ８３へ進む。
【０１３１】
ステップＳ８３において、ノードｎの必須フラグがＯＦＦである場合には、ステップＳ８４へ進む。ノードｎの全ての親ノードの必須フラグがＯＮである場合（ステップＳ８４のＹｅｓ）、あるいは、ノードｎの全ての親ノードの必須フラグがＯＮではないが、ノードｎの子ノードのなかに、必須フラグがＯＮである子ノードがある場合には（ステップＳ８５のＹｅｓ）、ステップＳ８６へ進み、当該ノードｎの必須フラグをＯＮに変更する。
【０１３２】
一方、ステップＳ８３でノードｎの必須フラグがＯＮである場合には、さらに、不要フラグを調べ、不要フラグがＯＮである場合には（ステップＳ８７のＹｅｓ）、当該ノードｎは矛盾ノードあるから（従って、前述の評価値ＣＲ１は「ＮＯ」となる）、ここで、当該ノードｎに対する処理Ｆを終了する。
【０１３３】
ノードｎの必須フラグはＯＮであり（ステップＳ８３のＹｅｓ）、不要フラグがＯＦＦである場合には（ステップＳ８７のＮｏ）、ステップＳ８８へ進み、当該ノードｎの不要フラグをＯＮにする必要があるか否かを調べる。すなわち、ノードｎの全ての親候補ノードの不要フラグがＯＮである場合（ステップＳ８８のＹｅｓ）、あるいは、ノードｎの全ての子候補ノードの不要フラグがＯＮである場合（ステップＳ８９のＹｅｓ）には、共にステップＳ９０へ進み、ノードｎの不要フラグをＯＮにする。ノードｎが、不要フラグがＯＦＦである親候補ノードをもち（ステップＳ８８のＮｏ）、更に、ノードｎが、不要フラグがＯＦＦである子候補ノードをもつ場合（ステップＳ８９のＮｏ）には、不要フラグをＯＦＦのままにして、当該ノードｎに対する処理Ｆを終了する。
【０１３４】
ノードｎが、複数の候補ノードをもつ通常ノードの１候補ノードである場合には（ステップＳ８２のＮｏ）、図２２のステップＳ９１へ進む。
【０１３５】
ステップＳ９１において、ノードｎの必須フラグがＯＮである場合（ステップＳ９１のＹｅｓ）には、ステップＳ９７へ進む。
【０１３６】
ステップＳ９１において、ノードｎの必須フラグがＯＦＦである場合（ステップＳ９１のＮｏ）にはステップＳ９２へ進み、まず、ノードｎの必須フラグをＯＮにする必要があるか否かを調べる。すなわち、ノードｎが、必須フラグがＯＮである通常ノードの唯一の親候補ノードである場合（ステップＳ９２のＹｅｓ）、あるいは、ノードｎが、必須フラグがＯＮである通常ノードの唯一の子候補ノードである場合（ステップＳ９３のＹｅｓ）には、ノードｎの必須フラグをＯＮにする（ステップＳ９４）。
【０１３７】
一方、ノードｎが、必須フラグがＯＮである通常ノードの唯一の親候補ノードでもなく（ステップＳ９２のＮｏ）、更に、必須フラグがＯＮである通常ノードの唯一の子候補ノードでもない場合には（ステップＳ９３のＮｏ）、当該ノードｎの不要フラグをＯＮにするか否かを調べる。すなわち、ノードｎの子ノードのうち、必須フラグがＯＮである子候補ノードに、ノードｎ以外の親候補ノードがあり、かつ当該親候補ノードの必須フラグがＯＮである場合には（ステップＳ９５のＹｅｓ）、ノードｎの不要フラグをＯＮにする（ステップＳ９６）。そうでない場合（ステップＳ９５のＮｏ）には、ステップＳ９５からステップＳ９７へ進む。
【０１３８】
ステップＳ９７において、ノードｎの不要フラグが既にＯＮとなっている場合（ステップＳ９７のＹｅｓ）には、ここで、ノードｎに対する処理Ｆを終了する。一方、ノードｎの不要フラグがＯＦＦである場合（ステップＳ９７のＮｏ）には、更に、ノードｎの不要フラグをＯＮにする必要があるか否かを調べる。すなわち、ノードｎの親ノード（通常ノード）の不要フラグがＯＮである場合（ステップＳ９８のＹｅｓ）、あるいは、ノードｎの子ノード（通常ノード）に不要フラグがＯＮの子ノードがある場合（ステップＳ９９のＹｅｓ）、あるいは、ノードｎの兄弟ノードに必須フラグがＯＮのノードがある場合（ステップＳ１００のＹｅｓ）、ステップＳ９６へ進み、ノードｎの不要フラグをＯＮに変更する。一方、ノードｎの親ノード（通常ノード）の不要フラグがＯＦＦであり（ステップＳ９８のＮｏ）、かつ、ノードｎの子ノード（通常ノード）に不要フラグがＯＮであるような子ノードがなく（ステップＳ９９のＮｏ）、かつ、ノードｎの全ての兄弟ノードの必須フラグはＯＦＦである（ステップＳ１００のＮｏ）場合には、ノードｎの不要フラグはＯＦＦのままにして、当該ノードｎに対する処理Ｆを終了する。
【０１３９】
図１９のステップＳ６４では、統語森Ｆの各ノードｎについて、上記図２１、図２２に示した処理Ｆを行って、各ノードｎの必須フラグ及び不要フラグの更新を行う。そして、この結果、統語森Ｆに矛盾ノード（必須フラグと不要フラグがともにＯＮであるようなノード）が存在しない場合（ステップＳ６５のＹｅｓ）には、統語森Ｆ上の各ノードｎの必須フラグ及び不要フラグがステップＳ６４の処理Ｆにより変更されなくなるまで、処理Ｆを繰り返す（ステップＳ６５、ステップＳ６６）。
【０１４０】
そして、矛盾ノードが存在する場合（ステップＳ６５のＹｅｓ）には、ステップＳ６１で受け取った割当候補ｐに対する適用可否を示す評価値ＣＲ１の値をステップＳ７１で「ＮＯ」とすることにより、図１８のステップＳ５６において選択候補から除外するものの、矛盾ノードが存在しない場合（ステップＳ６５のＮｏ）には、評価着度ＣＲ１の値を「ＹＥＳ」として（ステップＳ６７）、さらに、割当候補ｐの統語森Ｆ上の被覆範囲の広さに対する評価値ＣＲ２（ステップＳ７０）、割当候補ｐによる構造絞込の程度に対する評価値ＣＲ３（ステップＳ７４）、割当候補ｐで利用された変換規則の数に対する評価値ＣＲ４（ステップＳ７５）を求めて、図１８のステップＳ５６において選択候補とする。これらステップＳ６５での選択については、後で詳しく述べる。
【０１４１】
なお、ここでは、評価値ＣＲ２は、割当候補ｐで統語森上に割当てられた各変換規則の（マッチングパターン部に記述されている）変換対象構造に含まれる形態素の数が多いほど高い値を示すような評価値である。評価値ＣＲ３は、割当候補ｐで統語森上に割当照られた変換規則で構造変換される当該統語森中の統語構造木の数が多いほど高い値を示すようになっている。また、評価値ＣＲ４は、割当候補ｐで統語森上に割当てられている（変換規則のマッチングパターン部に記述されている）変換対象構造の数を示している。
【０１４２】
ステップＳ５６で割当候補セットＱから最適割当ｑを選択する方法について説明する。割当候補セットＱに含まれる割当候補のなかから、評価値ＣＲ１が「ＮＯ」である割当候補は取り除く。そして、評価値ＣＲ１が「ＹＥＳ」である割当候補群の中で評価値ＣＲ２の値が最も高い割当候補を選択する。評価値ＣＲ２の値が最も高い割当候補が複数ある場合には、これら中で、評価値ＣＲ３の値が最も高い割当候補を選択する。この選択した中に評価値ＣＲ３の値が最も高い割当候補が複数ある場合には、更に、これらの中で、評価値ＣＲ４の値が最も高い割当候補を選択する。もし、評価値ＣＲ４の値が最も高い割当候補が複数ある場合には、各割当候補に対して異なる評価基準を用いたり、あるいは重み付け評価等を行う。このようにして、割当候補セットＱのなかから１つの割当候補を選択して、これを最適割当ｑとする。
【０１４３】
次に、構造絞込部６の処理動作（図１５のステップＳ８の処理動作）について、図２３に示すフローチャートを参照して説明する。構造絞込部６は、処理Ｇを行う。なお、処理Ｇは処理Ｆを含む。
【０１４４】
図１８のステップＳ５６でられた最適割当ｑと、統語森Ｆとを受け取ると（ステップＳ１１１，ステップＳ１１２）、まず、統語森Ｆ中の各ノードのもつ必須フラグ及び不要フラグをクリアする（ＯＦＦにする）（ステップＳ１１３）。そして、割当候補ｑで各ＭＰトリガーｔを割り当てた統語森Ｆ中のノードの必須フラグをＯＮにする（ステップＳ１１４）。この後、前述の処理Ｆ（図２１、２２参照）を行って、統語森Ｆの各ノードの必須フラグ、不要フラグを更新する（ステップＳ１１５）。統語森Ｆ中のノードにフラグが変更されたノードがなくなるまで、処理Ｆを行う（ステップＳ１１６、ステップＳ１１５）。処理Ｆを行った結果、統語森Ｆ中のノードにフラグが変更されたノードがない場合には（ステップＳ１１６のＮｏ）、ステップＳ１１７へ進む。
【０１４５】
ステップＳ１１７〜ステップＳ１１９では、統語森Ｆから、不要部分を削除して、絞込済圧縮統語構造Ｇを求める処理を行う。すなわち、まず、統語森Ｆ中から、不要フラグがＯＮであるノードの集合Ｄを求める（ステップＳ１１７）。そして、統語森Ｆから、集合Ｄの各要素（不要フラグがＯＮであるノード）に接続された全アーク（アークは、統語森Ｆのノード間を結ぶ線に対応する）を削除する（ステップＳ１１８）。さらに、統語森Ｆから、集合Ｄの各要素を削除する（ステップＳ１１９）。この結果、絞込済圧縮統語構造Ｇが求まる。
【０１４６】
絞込済圧縮統語構造Ｇは、統語森にもともと含まれていた全統語構造木のうち、最適割当ｑで用いた各変換規則の変換対象構造をそれぞれ有する統語構造木のみが含まれている統語森Ｆの部分構造である。
【０１４７】
（具体的な説明）
次に、機械翻訳装置１０１の処理動作について、より具体的に説明する。
【０１４８】
（第１の具体的例）
ここでは、図２４を参照して、入力文字列Ｓとして、「リムジンって空港バスのことですか」が入力された場合について、図１５のフローチャートに従って説明する。
【０１４９】
なお、ここでは、図２に示した文法規則や、図４に示した変換規則を用いる場合について説明する。
【０１５０】
（ステップＳ１）機械翻訳装置１０１に、図２４（ａ）に示すような文字列Ｓ「リムジンって空港バスのことですか」が入力されて、機械翻訳装置１０１の動作が開始する。
【０１５１】
（ステップＳ２）形態素解析部１は、入力文字列Ｓに対し形態素解析を行って、図２４（ｂ）に示すような形態素列Ｍ「リムジン・って・空港・バス・の・こと・ですか」を得る。
【０１５２】
（ステップＳ３）構文解析部２は形態素列Ｍを解析して、図６に示したような統語森Ａを得る（図２４（ｃ））。
【０１５３】
（ステップＳ４、ステップＳ５）上記入力文字列Ｓは構文解析部２によって受理されるため（ステップＳ４）、ステップＳ５へ進み、割当候補抽出部４において、統語森Ａを基に図１６の処理Ｂを行う。ステップＳ５では、次の（ｓｔ１）〜（ｓｔ２）に示す処理を行う。
【０１５４】
（ｓｔ１）処理ＢのステップＳ２２では、統語森Ａの葉ノードと一致する表層トリガーを持つ全ての変換規則の集合Ｒを求める。ここでは、図４の変換規則＃１〜＃３のうち、表層がマッチする、変換規則＃１と変換規則＃２が集合Ｒの要素である。
【０１５５】
（ｓｔ２）次に、処理ＢのステップＳ２３〜ステップＳ２９の処理により、割当候補セットＱの要素を求める。ここでは、統語森Ａに変換規則＃１を適用した場合に得られる図１２の割当候補Ａ１と、統語森Ａに変換規則＃２の規則を適用した場合に得られる図１３の割当候補Ａ２ａ及び図１４の割当候補Ａ２ｂが、割当候補セットＱの要素として得られる。
【０１５６】
（ステップＳ６、ステップＳ７）得られた割当候補セットＱには、上記３つの要素が含まれているため（ステップＳ６）、ステップＳ７へ進む。ステップＳ７では、割当候補評価部５にて、処理Ｄ（及び処理Ｄに含まれる処理Ｅ、処理Ｆ）を行うことにより、割当候補セットＱの各要素について評価値を求めて、割当候補セットＱの要素のなかから最適割当ｑを選択する。
【０１５７】
ステップＳ７では、次の（ｓｔ１１）〜（ｓｔ２０）に示す処理を行う。
【０１５８】
（ｓｔ１１）図２５は、図１２の割当候補Ａ１に対する評価処理手順を示している。処理Ｄから呼び出される図１９の処理ＥのステップＳ６３では、統語森Ｆ中のノードのうち、割当候補Ａ１上で各ＭＰトリガーｔが割り当てられているノードについてこのノードの必須フラグをＯＮにする。図２５では、ステップＳ６３で必須フラグがＯＮとなるノードには、二重丸を付して示している。すなわち、割当候補Ａ１でＭＰトリガーに割り当てられているノードは、ノード「Ｓ２１」、ノード「ＮＰ１２」、葉ノード「の」、葉ノード「こと」、および葉ノード「ですか」）であり、これらの必須フラグがステップＳ６３でＯＮとなる。
【０１５９】
（ｓｔ１２）図１９の処理ＥのステップＳ６４では、統語森Ａの各ノードについて図２１〜図２２に示した処理Ｆを行うことにより、統語森Ｆの各ノードの必須フラグ、不要フラグを更新する。図２５では、処理Ｆを実施した場合の必須フラグおよび不要フラグの伝播の様子を示している。図２５では、ステップＳ６４で必須フラグがＯＮとなるノードには○印を付し、不要フラグがＯＮとなるノードには×印を付して表している。また、点線矢印により、ＯＮである各フラグが処理Ｆによって伝播する様子を示している。なお、図２５に示したフラグの伝播処理の順序は一例であって、必ずしもこの順序に限定されるものではなく、統語森Ｆ中の各ノードの評価順序により異なるものである。
【０１６０】
（ｓｔ１３）処理Ｆを行った結果、割当候補Ａ１では図２５に示したように、必須フラグと不要フラグがともにＯＮであるような矛盾ノードは存在しない（図１９のステップＳ６５）。従って、割当候補Ａ１は統語森Ａに対し適用可能であるから、図１９のステップＳ６７において、割当候補Ａ１の適用可否を示す評価値ＣＲ１は「ＹＥＳ」となる。
【０１６１】
（ｓｔ１４）統語森Ａにもともとある葉ノードの数Ｌ０は「７」である（図１９のステップＳ６８）。また、この適応割当Ａ１はノード「Ｓ２１」をルートとする構造に適応されているが、これは統語森Ａの構造全体にかかるものであるため、割当候補Ａ１で各ＭＰトリガーを割り当てた統語森Ａ中のノードが被覆する部分森構造の葉ノードの数Ｌｔは、統語森Ａのもつ全はノードの数「７」である（図１９のステップＳ６９）。従って、割当候補Ａ１の被覆範囲の広さに対する評価値ＣＲ２は、「７／７＝１．０」と算出される（図１９のステップＳ７０）。
【０１６２】
（ｓｔ１５）統語森Ａが本来内包している統語木構造の数Ｐ０は、前述したように「５」である（図２０のステップＳ７２）。統語森Ａから、不要フラグがＯＮであるノード及びそれに付随するアーク（図２５では細い実線で示した部分）を削除する。すると残存したノードのうち、ノード「Ｓ２０」が２つの候補ノード「ｃ２０ａ」、「ｃ２０ｂ」をもち、ノード「Ｓ２０」以下に２つの構造が存在するから、残存する統語構造木の数Ｐｔは「２」である（図２０のステップＳ７３）。よって、割当候補Ａ１の構造絞込の程度を表す評価値ＣＲ３は「５／２＝２．５」と算出される（図２０のステップＳ７４）。
【０１６３】
（ｓｔ１６）割当候補Ａ１で適用されている変換規則は、変換規則＃１のみであるため、評価値ＣＲ４は「１」となる（図２０のステップＳ７５）。
【０１６４】
（ｓｔ１７）以上の処理によって、１つ目の割当候補Ａ１に対して、評価値Ａ１（ＣＲ１＝ＹＥＳ、ＣＲ２＝１．０、ＣＲ３＝２．５、ＣＲ４＝１）が得られる。
【０１６５】
（ｓｔ１８）次に、割当候補セットＱの２つ目の要素である割当候補Ａ２ａについて、評価値ＣＲ１〜ＣＲ４を算出する。図２６は、図１３の割当候補Ａ２ａに対する評価処理手順を示している。割当候補Ａ２ａについても上記（ｓｔ１１）〜（ｓｔ１７）と同様にして、評価値Ａ２ａ（ＣＲ１＝ＹＥＳ、ＣＲ２＝．０．５７＝４／７、ＣＲ３＝２．５＝５／２、ＣＲ４＝１）が得られる。
【０１６６】
（ｓｔ１９）さらに、割当候補セットＱの３つ目の要素である割当候補Ａ２ｂについて、評価値ＣＲ１〜ＣＲ４を算出する。図２７は、図１４の割当候補Ａ２ｂに対する評価処理手順を示している。割当候補Ａ２ｂについても上記（ｓｔ１１）〜（ｓｔ１７）と同様にして、評価値Ａ２ｂ（ＣＲ１＝ＹＥＳ、ＣＲ２＝０．８６＝６／７、ＣＲ３＝５．０＝５／１、ＣＲ４＝１）が得られる。
【０１６７】
（ｓｔ２０）以上で、３つの割当候補に対する評価が完了し、図１８の処理ＤのステップＳ５６で、各割当候補に対し求めた評価値を比較する。３つの割当候補の評価値ＣＲ１はどれも「ＹＥＳ」であるから、これら３つの割当候補の評価値ＣＲ２を比較して、最も高い評価値の割当候補を選択する。ここでは、割当候補Ａ１が最も評価値が高いので、割当候補Ａ１が最適割当として選択される。なお、最適割当Ａ１は、変換規則＃１を適用したものである（図２４（ｄ））。
【０１６８】
（ステップＳ８）次に、構造絞込部６は、処理Ｇを行って、割当候補Ａ１を適用した統語森Ａから、不要フラグがＯＮである不要ノード、すなわち、図２５において、通常ノード「ＮＰ１７」、「ＮＰ１５」、「ＰＰ１８」、候補ノード「ｃ１７ａ」、「ｃ１７ｂ」、「ｃ２１ａ」、「ｃ２１ｂ」と、これらに関連する全てのアークを削除し、図２８に示すような絞込済圧縮統語構造Ａ１を求める。
【０１６９】
（ステップＳ９）構造変換部７は、図２３に示した絞込済圧縮統語構造Ａ１に対して、変換規則＃１を最適割当Ａ１に従って適用し、図２９に示すように、変換済統語意味構造Ａ１を求める（図２４（ｅ））。
【０１７０】
（ステップＳ１０）訳文生成部８は、図１９に示したような変換後統語意味構造Ａ１に基づいて、第２の言語の文字列を生成する。すなわち、図２４（ｆ）に示すような、翻訳結果文字列Ｔ＝“Does a limousine denote an airport bus?”が得られる。
【０１７１】
第１の具体例では、複数の統語構造木を内包する統語森に対して、適切に構造変換処理がなされることを示した。さらに、図２９にも示したように、構造変換前の絞込済圧縮統語構造には、ノード「Ｓ２０」の部分で未解決の曖昧性が残っているにもかかわらず（２通りの部分構造が含まれている）、適切な構造変換処理がなされているのである。
【０１７２】
（第２の具体例）
次に、統語森Ｆに対し複数の変換規則を同時に適応する場合について、図３０を参照して、図１５のフローチャートに従って具体的に説明する。なお、ここでは、図２に示した文法規則や、図４に示した変換規則を用いる場合について説明する。
【０１７３】
（ステップＳ１）機械翻訳装置１０１に、図３０（ａ）に示すような文字列Ｓ「リムジンとは空港バスのことです」が入力されて、機械翻訳装置１０１の動作が開始する。
【０１７４】
（ステップＳ２）形態素解析部１は、入力文字列Ｓに対し形態素解析を行って、図３０（ｂ）に示すような形態素列Ｍ「リムジン・とは・空港・バス・の・こと・です」を得る。
【０１７５】
（ステップＳ３）構文解析部２は図３０（ｂ）に示す形態素列Ｍを解析して、図３１に示すような統語森Ｂを得る（図３０（ｃ））。なお、図３０（ｂ）に示す形態素列は、前述の第１の具体例で用いた形態素列と同一であるため、得られる統語森Ｂも、葉ノードの表層を除いて、図６の統語森Ａと同一の構造をもっている。よって、統語森Ｂには５つの統語構造木が含まれている。
【０１７６】
（ステップＳ４、ステップＳ５）上記入力文字列Ｓは構文解析部２によって受理されるため（ステップＳ４）、ステップＳ５へ進み、割当候補抽出部４において、統語森Ｂを基に図１６の処理Ｂを行う。
【０１７７】
ステップＳ５では、次の（ｓｔ１０１）〜（ｓｔ１０２）に示す処理を行う。
【０１７８】
（ｓｔ１０１）処理ＢのステップＳ２２では、統語森Ｂの葉ノードと一致する表層トリガーを持つ全ての変換規則の集合Ｒを求める。ここでは、図４の変換規則＃１〜＃３のうち、表層がマッチする、変換規則＃２と変換規則＃３が集合Ｒの要素である。
【０１７９】
（ｓｔ１０２）次に、処理ＢのステップＳ２３〜ステップＳ２９の処理により、割当候補セットＱの要素を求める。ここでは、統語森Ｂに変換規則＃２を適用した場合に得られる図３２の割当候補Ｂ２ａ及び図３３の割当候補Ｂ２ｂと、統語森Ｂに変換規則＃３の規則を適用した場合に得られる図３４の割当候補Ｂ３と、統語森Ｂに変換規則＃２及び＃３の規則を適用した場合に得られる図３５の割当候補Ｂ２ｂ＆Ｂ３及び図３６の割当候補Ｂ２ｂ＆Ｂ３との５つが、割当候補セットＱの要素として得られる。
【０１８０】
（ステップＳ６、ステップＳ７）得られた割当候補セットＱには、上記５つの要素が含まれているため（ステップＳ６）、ステップＳ７へ進む。ステップＳ７では、割当候補評価部５にて、処理Ｄ（及び処理Ｄに含まれる処理Ｅ、処理Ｆ）を行うことにより、割当候補セットＱの各要素について評価値を求めて、割当候補セットＱの要素のなかから最適割当ｑを選択する。ステップＳ７では、次の（ｓｔ１１１）〜（ｓｔ１３０）に示す処理を行う。
【０１８１】
（ｓｔ１１１）図３２、図３３に示した割当候補Ｂ２ａ、割当候補Ｂ２ｂは、それぞれ、前述の図１３、図１４の割当候補Ａ２ａ、割当候補Ａ２ｂと構造的に同一である為、それぞれ図２６、図２７を用いて説明した割当候補Ａ２ａおよび割当候補Ａ２ｂの評価処理と同様の処理がなされて、図３７、図３８にそれぞれ示したとおり、割当候補Ｂ２ａからは評価値Ｂ２ａ（ＣＲ１＝ＹＥＳ、ＣＲ２＝０．５７、ＣＲ３＝２．５、ＣＲ４＝１）、割当候補Ｂ２ｂからは評価値Ｂ２ｂ（ＣＲ１＝ＹＥＳ、ＣＲ２＝０．８６、ＣＲ３＝５．０、ＣＲ４＝１）が得られる。
【０１８２】
（ｓｔ１１２）図３９は、図３４に示した割当候補Ｂ３に対する評価処理手順を説明するためのものである。処理Ｄから呼び出される図１９の処理ＥのステップＳ６３では、統語森Ｂ中のノードのうち、割当候補Ｂ３上で変換規則＃３の各ＭＰトリガーｔが割り当てられているノードについて、このノードの必須フラグをＯＮにする。図３９では、ステップＳ６３で必須フラグがＯＮとなるノードには、二重丸を付して示している。すなわち、割当候補Ｂ３でＭＰトリガーに割り当てられているノードは、ノード「Ｓ４２」、ノード「Ｓ４１」、「ＮＰ３５」、「ＮＰ２９」、葉ノード「とは」及び葉ノード「です」であり、これらの必須フラグがステップＳ６３でＯＮとなる。
【０１８３】
（ｓｔ１１３）図１９の処理ＥのステップＳ６４では、統語森Ｂの各ノードについて図２１〜図２２に示した処理Ｆを行うことにより、統語森Ｂの各ノードの必須フラグ、不要フラグを更新する。図３９では、処理Ｆを実施した場合の必須フラグおよび不要フラグの伝播の様子を示している。図３９では、ステップＳ６４で必須フラグがＯＮとなるノードには○印を付し、不要フラグがＯＮとなるノードには×印を付して表している。また、点線矢印により、ＯＮである各フラグが処理Ｆによって伝播する様子を示している。なお、図３９に示したフラグの伝播処理の順序は、一例であって、必ずしもこの順序に限定されるものではなく、統語森Ｂ中の各ノードの評価順序による異なるものである。
【０１８４】
（ｓｔ１１４）処理Ｆを行った結果、割当候補Ｂ３では図３９に示したように、必須フラグと不要フラグがともにＯＮである矛盾ノードは存在しない（図１９のステップＳ６５）。従って、割当候補Ｂ３は統語森Ｂに対し適用可能であるから、図１９のステップＳ６７において、割当候補Ｂ３の適用可否を示す評価値ＣＲ１は「ＹＥＳ」となる。
【０１８５】
（ｓｔ１１５）統語森Ｂにもともとある葉ノードの数Ｌ０は「７」である（図１９のステップＳ６８）。また、この適応割当Ｂ３はノード「Ｓ４２」をルートとする構造に適応されているが、これは統語森Ｂの構造全体にかかるものであるため、割当候補Ｂ３で各ＭＰトリガーを割り当てた統語森Ｂ中のノードが被覆する部分森構造の葉ノードの数Ｌｔは、統語森Ｂのもつ全はノードの数「７」である（図１９のステップＳ６９）。従って、割当候補Ｂ３の被覆範囲の広さに対する評価値ＣＲ２は、「７／７＝１．０」と算出される（図１９のステップＳ７０）。
【０１８６】
（ｓｔ１１６）統語森Ｂが本来内包している統語木構造の数Ｐ０は、前述したように「５」である（図２０のステップＳ７２）。統語森Ｂから、不要フラグがＯＮであるノード及びこのノードに付随するアーク（図３９では細い実線で示した部分）を削除する。すると残存する統語構造木の数Ｐｔは「１」である（図２０のステップＳ７３）。よって、割当候補Ａ１の構造絞込の程度を表す評価値ＣＲ３は「５／１＝５．０」と算出される（図２０のステップＳ７４）。
【０１８７】
（ｓｔ１１７）割当候補Ｂ３で適用されている変換規則は、変換規則＃３のみであるため、評価値ＣＲ４は「１」となる（図２０のステップＳ７５）。
【０１８８】
（ｓｔ１１８）以上の処理によって、割当候補Ｂ３に対して、評価値Ｂ３（ＣＲ１＝ＹＥＳ、ＣＲ２＝１．０、ＣＲ３＝５．０、ＣＲ４＝１）が得られる。
【０１８９】
（ｓｔ１１９）図４０は、図３５に示した割当候補Ｂ２ａ＆Ｂ３に対する評価処理手順を説明するためのものである。処理Ｄから呼び出される図１９の処理ＥのステップＳ６３では、統語森Ｂ中のノードのうち、割当候補Ｂ２ａ＆Ｂ３上で変換規則＃２及び＃３の各ＭＰトリガーｔが割り当てられているノードについて必須フラグをＯＮにする。図４０では、ステップＳ６３で必須フラグがＯＮとなるノードには、二重丸を付して示している。すなわち、割当候補Ｂ２ａ＆Ｂ３でＭＰトリガーに割り当てられているノードは、ノード「ＮＰ３５」、「ＮＰ３３」、「Ｓ４２」、「ＮＰ２９」、「Ｓ４１」、「ＮＰ３５」、葉ノード「とは」、「の」、「こと」及び「です」であり、これらの必須フラグがステップＳ６３でＯＮとなる。
【０１９０】
（ｓｔ１２０）図１９の処理ＥのステップＳ６４では、統語森Ｂの各ノードについて図２１〜図２２に示した処理Ｆを行うことにより、統語森Ｂの各ノードの必須フラグ、不要フラグを更新する。図４０では、処理Ｆを実施した場合の必須フラグおよび不要フラグの伝播の様子を示している。図４０では、ステップＳ６４で必須フラグがＯＮとなるノードには○印を付し、不要フラグがＯＮとなるノードには×印を付して表している。また、点線矢印により、ＯＮである各フラグが処理Ｆによって伝播する様子を示している。なお、図４０に示したフラグの伝播処理の順序は一例であって、必ずしもこの順序に限定されるものではなく、統語森Ｂ中の各ノードの評価順序により異なるものである。
【０１９１】
（ｓｔ１２１）処理Ｆを行った結果、割当候補Ｂ２ａ＆Ｂ３では図４０に示したように、必須フラグと不要フラグがともにＯＮである矛盾ノードは存在しない（図１９のステップＳ６５）。従って、割当候補Ｂ２ａ＆Ｂ３は統語森Ｂに対し適用可能であるから、図１９のステップＳ６７において、割当候補Ｂ２ａ＆Ｂ３の適用可否を示す評価値ＣＲ１は「ＹＥＳ」となる。
【０１９２】
（ｓｔ１２２）統語森Ｂにもともとある葉ノードの数Ｌ０は「７」である（図１９のステップＳ６８）。また、この適応割当Ｂ２ａ＆Ｂ３はノード「Ｓ４２」をルートとする構造に適応されているが、これは統語森Ｂの構造全体にかかるものであるため、割当候補Ｂ２ａ＆Ｂ３で各ＭＰトリガーを割り当てた統語森Ｂ中のノードが被覆する部分森構造の葉ノードの数Ｌｔは、統語森Ｂのもつ全はノードの数「７」である（図１９のステップＳ６９）。従って、割当候補Ｂ２ａ＆Ｂ３の被覆範囲の広さに対する評価値ＣＲ２は、「７／７＝１．０」と算出される（図１９のステップＳ７０）。
【０１９３】
（ｓｔ１２３）統語森Ｂが本来内包している統語木構造の数Ｐ０は、前述したように「５」である（図２０のステップＳ７２）。統語森Ｂから、不要フラグがＯＮであるノード及びそれに付随するアーク（図４０では細い実線で示した部分）を削除する。すると、候補ノードは存在しないので、残存する統語構造木の数Ｐｔは「１」である（図２０のステップＳ７３）。よって、割当候補Ｂ２ａ＆Ｂ３の構造絞込の程度を表す評価値ＣＲ３は「５／１＝５．０」と算出される（図２０のステップＳ７４）。
【０１９４】
（ｓｔ１２４）割当候補Ｂ２ａ＆Ｂ３で適用されている変換規則は、変換規則＃２及び＃３の２つであるため、評価値ＣＲ４は「２」となる（図２０のステップＳ７５）。
【０１９５】
（ｓｔ１２５）以上の処理によって、割当候補Ｂ２ａ＆Ｂ３に対して、評価値Ｂ２ａ＆Ｂ３（ＣＲ１＝ＹＥＳ、ＣＲ２＝１．０、ＣＲ３＝５．０、ＣＲ４＝２）が得られる。
【０１９６】
（ｓｔ１２６）図４１は、図３６に示した割当候補Ｂ２ｂ＆Ｂ３に対する評価処理手順を説明するためのものである。処理Ｄから呼び出される図１９の処理ＥのステップＳ６３では、統語森Ｂ中のノードのうち、割当候補Ｂ２ｂ＆Ｂ３上で変換規則＃２及び＃３の各ＭＰトリガーｔが割り当てられているノードについて必須フラグをＯＮにする。図４１では、ステップＳ６３で必須フラグがＯＮとなるノードには、二重丸を付して示している。すなわち、割当候補Ｂ２ｂ＆Ｂ３でＭＰトリガーに割り当てられているノードは、ノード「ＮＰ３８」、「ＮＰ３４」、「Ｓ４２」、「ＮＰ２９」、「Ｓ４１」、「ＮＰ３５」、葉ノード「とは」、「の」、「こと」及び「です」であり、これらの必須フラグがステップＳ６３でＯＮとなる。
【０１９７】
（ｓｔ１２７）図１９の処理ＥのステップＳ６４では、統語森Ｂの各ノードについて図２１〜図２２に示した処理Ｆを行うことにより、統語森Ｂの各ノードの必須フラグ、不要フラグを更新する。図４１では、処理Ｆを実施した場合の必須フラグおよび不要フラグの伝播の様子を示している。図４１では、ステップＳ６４で必須フラグがＯＮとなるノードには○印を付し、不要フラグがＯＮとなるノードには×印を付して表している。また、点線矢印により、ＯＮである各フラグが処理Ｆによって伝播する様子を示している。なお、図４１に示したフラグの伝播処理の順序は一例であって、必ずしもこの順序に限定されるものではなく、統語森Ｂ中の各ノードの評価順序により異なるものである。
【０１９８】
（ｓｔ１２８）処理Ｆを行った結果、割当候補Ｂ２ｂ＆Ｂ３では図４１に示したように、ノード「ＮＰ３４」、あるいはノード「ＮＰ３５」、あるいはノード「Ｓ４２」の候補ノードが矛盾ノードとなる（図１９のステップＳ６５）。従って、割当候補Ｂ２ｂ＆Ｂ３は統語森Ｂに対し実際には適用不可能な変換規則の割当方法であることが判明する。従って、図１９のステップＳ６７において、割当候補Ｂ２ｂ＆Ｂ３の適用可否を示す評価値ＣＲ１は「ＮＯ」となる。
【０１９９】
ここで、圧縮された候補ノード「ｃ４２ａ」が、矛盾ノードとなる過程について説明する。まず、処理ＥのステップＳ６２で統語森Ｂの各ノードの必須フラグ及び不要フラグがクリアされる。そして、ステップＳ６３で当該割当候補Ｂ２ｂ＆Ｂ３での必須ノード（ＮＰ２９、ＮＰ３４、ＮＰ３５、ＮＰ３８、ＮＰ４１、Ｓ４２「とは」、「の」、「こと」、「です」）の必須フラグをＯＮとする。
【０２００】
ステップＳ６４では、統語森Ｂ中の各ノードに対して、図２１〜図２２の処理Ｆが施されるが、この処理の中で、候補ノード「ｃ４２ａ」については、図２１のステップＳ８１、ステップＳ８２、図２２のステップＳ９１、ステップＳ９２と進む。ステップＳ９２では、候補ノード「ｃ４２ａ」が、既に必須フラグがＯＮとなっている通常ノード「ＮＰ３８」の唯一の親候補ノードであることから、ステップＳ９２へ進み、候補ノード「ｃ４２ａ」の必須フラグをＯＮにする。
【０２０１】
同様に、候補ノード「ｃ４２ｃ」についても、図２１のステップＳ８１、ステップＳ８２、図２２のステップＳ９１、ステップＳ９２と進む。ステップＳ９２では、候補ノード「ｃ４２ｃ」が、既に必須フラグがＯＮとなっている通常ノード「Ｓ４１」の唯一の親候補ノードであることから、ステップＳ９４へ進み、候補ノード「ｃ４２ｃ」の必須フラグをＯＮにする。
【０２０２】
次に、必須フラグがＯＮとなった候補ノード「ｃ４２ａ」についての処理において、図２１のステップＳ８１、ステップＳ８２、図２２のステップＳ９１と進む。ステップＳ９１で、候補ノード「ｃ４２ａ」の必須フラグがＯＮであることからステップＳ９７へ進む。ステップＳ９７では、候補ノード「ｃ４２ａ」の不要フラグがＯＦＦであることから、ステップＳ９８へ進み、さらに、ステップＳ９９、ステップＳ１００へと進む。ステップＳ１００において、候補ノード「ｃ４２ａ」の兄弟ノードである候補ノード「ｃ４２ｃ」の必須フラグがＯＮであることから、ステップＳ９６へ進み、候補ノード「ｃ４２ａ」の不要フラグがＯＮとなる。
【０２０３】
以上の処理によって、候補ノード「ｃ４２ａ」は、必須フラグと不要フラグの両方がＯＮとなる矛盾ノードとなることがわかる。同様の処理によって、候補ノード「ｃ４２ｃ」も矛盾ノードとなる。
【０２０４】
（ｓｔ１２９）以上の処理によって、割当候補Ｂ２ｂ＆Ｂ３に対して、評価値Ｂ２ｂ＆Ｂ３（ＣＲ１＝ＮＯ、ＣＲ２＝ｎｕｌｌ、ＣＲ３＝ｎｕｌｌ、ＣＲ４＝２）が得られる。なお、図４１では、複数のノードに矛盾ノードが発生する様子を示したが、実際の処理では矛盾ノードが１つ発見された時点で評価処理を終了する。
【０２０５】
（ｓｔ１３０）以上で、５つの割当候補に対する評価が完了し、図１８の処理ＤのステップＳ５６で、各割当候補に対し求めた評価値を比較する。５つの割当候補のうち評価値ＣＲ１が「ＹＥＳ」である割当候補Ｂ２ａ、Ｂ３ｂ、Ｂ３、Ｂ２ｂ＆Ｂ３のうち、評価値ＣＲ２が最も高い「１．０」である割当候補はＢ３、Ｂ２ａ＆Ｂ３であり、これら２つの割当候補の評価値ＣＲ３はともに「５．０」である。そこで、これら２つの割当候補のうち、評価値ＣＲ４の値が高い方、すなわち、割当候補Ｂ２ａ＆Ｂ３が最適割当として選択される。なお、最適割当Ｂ２ａ＆Ｂ３Ａ１は、変換規則＃２及び＃３を適用したものである（図３０（ｄ））。
【０２０６】
（ステップＳ８）次に、構造絞込部６は、処理Ｇを行って、割当候補Ｂ２ａ＆Ｂ３を適用した統語森Ｂから、図４０の不要フラグがＯＮである不要ノードと、これらに関連する全てのアークを削除し、図４２に示すような絞込済圧縮統語構造Ｂ２ａ＆Ｂ３を求める。
【０２０７】
（ステップＳ９）構造変換部７は、図４２に示した絞込済圧縮統語構造Ｂ２ａ＆Ｂ３に対して、変換規則＃２及び＃３を最適割当Ｂ２ａ＆Ｂ３に従って適用し、図４３に示すように、変換済統語意味構造Ｂ２ａ＆Ｂ３を求める（図３０（ｅ））。
【０２０８】
（ステップＳ１０）訳文生成部８は、図４３に示したような変換後統語意味構造Ｂ２ａ＆Ｂ３に基づいて、第２の言語の文字列を生成する。すなわち、図３０（ｆ）に示すような、翻訳結果文字列Ｔ＝”Ａ  ｌｉｍｏｕｓｉｎｅ  ｄｅｎｏｔｅ  ａｎ  ａｉｒｐｏｒｔ  ｂｕｓ．”が得られる。
【０２０９】
以上説明したように、上記実施形態によれば、自然言語の構造を変換する際には、まず、自然言語文から得られる統語森から、変換規則による変換対象構造を少なくとも１つもつ統語構造木を少なくとも１つ含む複数の部分構造を求め、このなかから実際に変換規則を適用して構造変換する部分構造を１つ選択する。このようにして統語森中の曖昧性のある複数の候補のなかから最適解となり得る統語構造木を絞り込む。この後、選択された部分構造に含まれる各変換対象構造を変換するための変換規則を用いて、当該部分構造の構造を変換することにより、自然言語文の構造を容易に変換することができる。
【０２１０】
複数の解釈候補（統語構造木）を含む統語森構造に対するトランスファ処理が可能となる。また、入力文に対する複数の解釈候補をまとめて取り扱うことで、従来のように、後戻りの必要が無く、しかも過度の仮定を設定すること無しに、解釈候補の絞込が行えるので、容易に最適解（唯一の統語構造木）を得ることが可能となる。
【０２１１】
また、上記実施形態に記載した手法は、コンピュータに実行させることの出来るプログラムとして、磁気ディスク（フロッピーディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、半導体メモリなどの記録媒体を用いてコンピュータにプログラムを読み込み、ＣＰＵ部で実行させれば、本発明の音声インタフェース装置を実現することが出来ることになる。
【０２１２】
すなわち、コンピュータのハードディスク、半導体メモリなどの所定の記憶手段に、自然言語の構造に含まれる任意の変換対象構造を当該変換対象構造とは異なる構造に変換するための変換規則群を記憶させ、ＣＰＵ等の演算手段に、入力文字列の形態素列から、複数の統語構造木を含む統語森を求めるステップと、統語森から、（各変換規則の）変換対象構造を少なくとも１つ含む統語構造木を含む複数の部分構造を求めるステップ、各部分構造内の変換対象構造に含まれる形態素の数、各部分構造に含まれる統語構造木の数、及び各部分構造に含まれる変換対象構造の数のうちの少なくとも１つに基づいて、上記複数の部分構造のなかから、上記記憶手段に記憶された変換規則群を適用して構造変換するための第１の部分構造を選択するステップと、前記変換規則群のうち、上記第１の部分構造に含まれる各変換対象構造を変換するための各変換規則を用いて、当該第１の部分構造の構造を変換するステップとを含むプログラムを実行させることにより、当該コンピュータは上記実施形態に係る自然言語解析装置として機能する。
【０２１３】
さらに、本発明を実施する際の記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮ（ローカルエリアネットワーク）や、インターネット等により伝送されたプログラムやデータをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０２１４】
また、記憶媒体は１つに限らず、複数の記憶媒体から本発明を実施することも可能であり、媒体の構成は何れの構成であっても良い。
【０２１５】
なお、上記構文解析部２で行なわれる解析処理は、例えばチャートパージングなど別の方法を用いても良い。自然言語解析装置１００には、文字列が入力されるのではなく、直接形態素列を受け取ったり、あるいはラティスなど構造をもつデータを受け付けるようにしても良い。第１の言語及び第２の言語は、上記実施形態の場合に限定されるものではない。また、変換規則に、優先度や適応順序に関する制御を追加しても良い。自然言語解析装置１００は、例えば、音声認識結果や手書き文字認識結果や画像文字認識結果として得られる文字列が入力される場合も上記実施形態の説明と全く同様である。
【０２１６】
各割当候補に対する評価処理において、各割当候補について異なる評価基準を用いたり、あるいは重み付け評価を行なったり、異なる順序での評価を行なったりしても良い。また、確率文法併用や、単語や単語クラスの共起情報などの頻度情報や、意味情報を併用しても良い。また、音声や文字認識結果が自然言語解析装置１００に入力される場合には、認識スコアを利用してもよい。
【０２１７】
本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０２１８】
【図１】本発明の実施形態に係る自然言語解析装置及び自然言語解析装置を含む機械翻訳装置の構成例を示した図。
【図２】文法規則の例を示した図。
【図３】語彙辞書の例を示した図。
【図４】変換規則の例を示した図。
【図５】入力文字列の一例と当該入力文字列の形態素例の一例を示した図。
【図６】統語森の一例（統語森Ａ）を示した図。
【図７】図６の統語森Ａに含まれる５つの統語構造のうちの１つである統語構造木Ａ１を示した図。
【図８】図６の統語森Ａに含まれる５つの統語構造のうちの１つである統語構造木Ａ２を示した図。
【図９】図６の統語森Ａに含まれる５つの統語構造のうちの１つである統語構造木Ａ３を示した図。
【図１０】図６の統語森Ａに含まれる５つの統語構造のうちの１つである統語構造木Ａ４を示した図。
【図１１】図６の統語森Ａに含まれる５つの統語構造のうちの１つである統語構造木Ａ５を示した図。
【図１２】図６の統語森に図４の変換規則＃１を適用する際の１割当方法である割当候補Ａ１を示した図。
【図１３】図６の統語森に図４の変換規則＃２を適用する際の１割当方法である割当候補Ａ２ａを示した図。
【図１４】図６の統語森に図４の変換規則＃２を適用する際の１割当方法である割当候補Ａ２ｂを示した図。
【図１５】図１の機械翻訳装置の全体の処理動作を示すフローチャート。
【図１６】割当候補抽出部の処理動作（処理Ｂ）について説明するためのフローチャート。
【図１７】割当候補抽出部の処理動作（処理Ｂに含まれる処理Ｃ）について説明するためのフローチャート。
【図１８】割当候補評価部の処理動作（処理Ｄ）について説明するためのフローチャート。
【図１９】割当候補評価部の処理動作（処理Ｄに含まれる処理Ｅ）について説明するためのフローチャート。
【図２０】割当候補評価部の処理動作（処理Ｄに含まれる処理Ｅ）について説明するためのフローチャート。
【図２１】割当候補評価部の処理動作（処理Ｅに含まれる処理Ｆ）について説明するためのフローチャート。
【図２２】割当候補評価部、構造絞込部の処理動作（処理Ｅ、処理Ｇに含まれる処理Ｆ）について説明するためのフローチャート。
【図２３】構造絞込部の処理動作（処理Ｇ）について説明するためのフローチャート。
【図２４】図１の機械翻訳装置の処理動作の第１のを具体例を説明するための図。
【図２５】割当候補評価部における割当候補Ａ１に対する評価処理動作を説明するための図で、特に、処理Ｆで各ノードのフラグが更新される様子の一例を示した図。
【図２６】割当候補評価部における割当候補Ａ２ａに対する評価処理動作を説明するための図で、特に、処理Ｆで各ノードのフラグが更新される様子の一例を示した図。
【図２７】割当候補評価部における割当候補Ａ２ｂに対する評価処理動作を説明するための図で、特に、処理Ｆで各ノードのフラグが更新される様子の一例を示した図。
【図２８】絞込済圧縮統語構造の一例を示したもので、最適割当として割当候補Ａ１が選択された場合に、当該最適割当に基づき、得られる絞込済圧縮統語構造Ａ１を示す図。
【図２９】絞込済圧縮統語構造Ａ１に対して、変換規則＃１を最適割当Ａ１に従って適用した結果得られる変換済統語意味構造Ａ１を示す図。
【図３０】図１の機械翻訳装置の処理動作の第２の具体例を説明するための図。
【図３１】第２の具体例にかかる統語森Ｂを示した図。
【図３２】統語森Ｂに図４の変換規則＃２を適用する際の１割当方法である割当候補Ｂ２ａを示した図。
【図３３】統語森Ｂに図４の変換規則＃２を適用する際の１割当方法である割当候補Ｂ２ｂを示した図。
【図３４】統語森Ｂに図４の変換規則＃３を適用する際の１割当方法である割当候補Ｂ３を示した図。
【図３５】統語森Ｂに図４の変換規則＃２及び＃３を適用する際の１割当方法である割当候補Ｂ２ａ＆Ｂ３を示した図。
【図３６】統語森Ｂに図４の変換規則＃２及び＃３を適用する際の１割当方法である割当候補Ｂ２ｂ＆Ｂ３を示した図。
【図３７】割当候補評価部における割当候補Ｂ２ａに対する評価処理動作を説明するための図。
【図３８】割当候補評価部における割当候補Ｂ２ｂに対する評価処理動作を説明するための図。
【図３９】割当候補評価部における割当候補Ｂ３に対する評価処理動作を説明するための図で、特に、処理Ｆで各ノードのフラグが更新される様子の一例を示した図。
【図４０】割当候補評価部における割当候補Ｂ２ａ＆Ｂ３に対する評価処理動作を説明するための図で、特に、処理Ｆで各ノードのフラグが更新される様子の一例を示した図。
【図４１】割当候補評価部における割当候補Ｂ２ｂ＆Ｂ３に対する評価処理動作を説明するための図で、特に、処理Ｆで各ノードのフラグが更新される様子の一例を示した図。
【図４２】第２の具体例に係る絞込済圧縮統語構造の例を示したもので、最適割当として割当候補Ｂ２ａ＆Ｂ３が選択された場合に、当該最適割当に基づき、得られる絞込済圧縮統語構造Ｂ２ａ＆Ｂ３を示す図。
【図４３】絞込済圧縮統語構造Ｂ２ａ＆Ｂ３に対して、変換規則＃２、＃３を最適割当Ｂ２ａ＆Ｂ３に従って適用した結果得られる変換済統語意味構造Ｂ２ａ＆Ｂ３を示す図。
【図４４】自然言語解析装置の処理動作を概略を説明するための図で、統語森を模式的に示した図。
【図４５】自然言語解析装置の処理動作を概略を説明するための図で、変換規則を模式的に示した図。
【図４６】自然言語解析装置の処理動作を概略を説明するための図で、図４４の統語森に図４５の１番目の変換規則を適用すると仮定した場合に得られる部分構造を示している。
【図４７】自然言語解析装置の処理動作を概略を説明するための図で、図４４の統語森に図４５の２番目の変換規則を適用すると仮定した場合に得られる部分構造を示している。
【図４８】自然言語解析装置の処理動作を概略を説明するための図で、図４４の統語森に図４５の３番目の変換規則を適用すると仮定した場合に得られる部分構造を示している。
【図４９】自然言語解析装置の処理動作を概略を説明するための図で、図４４の統語森に図４５の２番目と３番目の変換規則を適用すると仮定した場合に得られる部分構造を示している。
【図５０】自然言語解析装置の処理動作を概略を説明するための図で、図４９の部分構造を構造変換した結果を示した図。
【符号の説明】
【０２１９】
１…形態素解析部、２…構文解析部、３…変換規則記憶部、４…割当候補抽出部、５…割当候補評価部、６…構造絞込部、７…構造変換部、８…訳文生成部、１００…自然言語解析装置、１０１…機械翻訳装置。
【図１】
2006012088.tif 000003
【図２】
2006012088.tif 000004
【図３】
2006012088.tif 000005
【図４】
2006012088.tif 000006
【図５】
2006012088.tif 000007
【図６】
2006012088.tif 000008
【図７】
2006012088.tif 000009
【図８】
2006012088.tif 000010
【図９】
2006012088.tif 000011
【図１０】
2006012088.tif 000012
【図１１】
2006012088.tif 000013
【図１２】
2006012088.tif 000014
【図１３】
2006012088.tif 000015
【図１４】
2006012088.tif 000016
【図１５】
2006012088.tif 000017
【図１６】
2006012088.tif 000018
【図１７】
2006012088.tif 000019
【図１８】
2006012088.tif 000020
【図１９】
2006012088.tif 000021
【図２０】
2006012088.tif 000022
【図２１】
2006012088.tif 000023
【図２２】
2006012088.tif 000024
【図２３】
2006012088.tif 000025
【図２４】
2006012088.tif 000026
【図２５】
2006012088.tif 000027
【図２６】
2006012088.tif 000028
【図２７】
2006012088.tif 000029
【図２８】
2006012088.tif 000030
【図２９】
2006012088.tif 000031
【図３０】
2006012088.tif 000032
【図３１】
2006012088.tif 000033
【図３２】
2006012088.tif 000034
【図３３】
2006012088.tif 000035
【図３４】
2006012088.tif 000036
【図３５】
2006012088.tif 000037
【図３６】
2006012088.tif 000038
【図３７】
2006012088.tif 000039
【図３８】
2006012088.tif 000040
【図３９】
2006012088.tif 000041
【図４０】
2006012088.tif 000042
【図４１】
2006012088.tif 000043
【図４２】
2006012088.tif 000044
【図４３】
2006012088.tif 000045
【図４４】
2006012088.tif 000046
【図４５】
2006012088.tif 000047
【図４６】
2006012088.tif 000048
【図４７】
2006012088.tif 000049
【図４８】
2006012088.tif 000050
【図４９】
2006012088.tif 000051
【図５０】
2006012088.tif 000052