(57)【特許請求の範囲】
【請求項１】
入力文の１以上の単語から成る各部分を部分解析し、前記入力文全体の構文解析を実行する主構文解析部と、
該主構文解析部の構文解析が不能であると前記各部分の部分解析結果を組み合わせて出力する解析救済部とを備える構文解析装置であって、
前記解析救済部は、
前記二以上の各部分の１以上の部分解析結果をそれぞれ組み合わせて複数の組合体を生成する組合処理部と、
前記複数の組合体に対しそれぞれ１つの単語から成る一対の部分に対応する二つの部分解析結果の組合体を選択する第１のフィルタと、
該選択された組合体に対し品詞が同一の単語を含む組合体が存在すると該品詞同一の組合体を出力し、品詞同一の組合体が存在しないと該選択された組合体を出力する第２のフィルタと、
前記出力する組合体が存在しないと部分解析結果の無い単語に対し解析無しを示す結果といずれかの部分解析結果とを組み合わせた組合体を出力する追加部と、
を含むことを特徴とする構文解析装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、構文解析を行った結果、文全体の構文解析結果が得られなかった場合でも、何らかの解析結果を出力する構文解析装置に関する。
【０００２】
【従来の技術】
機械翻訳といった自然言語処理においては、構文解析を行いこの構文解析結果に基づいて翻訳処理が行われる。例えば、特開平５−２９００８２号公報等に示されている従来技術では、パターンによる構文解析を行っている。
【０００３】
【発明が解決しようとする課題】
翻訳処理等の自然言語処理では、構文解析の失敗により解が出ないことよりも、よい結果でなくとも何らかの解が現れる方が望ましい場合が少なからず存在する。上記従来の技術においても、パターンによる構文解析が失敗した場合は文法による解析を行うようになっている。しかしながら、パターン解析部の結果を全く使用しないため、処理に無駄があり、パターンによる品質の向上の恩恵は受けられない。更に、文法による解析が失敗した場合には、後の処理が全く行えず、部分的は得られるであろう結果さえも失われることになるという問題があった。
【０００４】
【課題を解決するための手段】
本発明は、前述の課題を解決するため次の構成を採用する。
〈構成１〉
入力文の１以上の単語から成る各部分を部分解析し、前記入力文全体の構文解析を実行する主構文解析部と、該主構文解析部の構文解析が不能であると前記各部分の部分解析結果を組み合わせて出力する解析救済部とを備える構文解析装置であって、前記解析救済部は、前記二以上の各部分の１以上の部分解析結果をそれぞれ組み合わせて複数の組合体を生成する組合処理部と、前記複数の組合体に対しそれぞれ１つの単語から成る一対の部分に対応する二つの部分解析結果の組合体を選択する第１のフィルタと、該選択された組合体に対し品詞が同一の単語を含む組合体が存在すると該品詞同一の組合体を出力し、品詞同一の組合体が存在しないと該選択された組合体を出力する第２のフィルタと、前記出力する組合体が存在しないと部分解析結果の無い単語に対し解析無しを示す結果といずれかの部分解析結果とを組み合わせた組合体を出力する追加部とを含むことを特徴とする構文解析装置。
【００１２】
【発明の実施の形態】
以下、本発明の実施の形態を具体例を用いて詳細に説明する。
《具体例》
図１は本発明の構文解析方法の具体例を示す説明図であるが、これに先立ち、本発明の構文解析装置を説明する。
【００１３】
〈構成〉
図２は、本発明の構文解析装置の具体例を示す構成図である。
図の装置は、パーソナルコンピュータ等で実現され、入力部１、主構文解析部２、解析救済部３、出力部４を備えている。
入力部１は、構文解析を行うための対象となる文を入力するための機能部であり、文を直接入力するためのキーボードや装置外部から文のデータを入力するためのインタフェース等からなる。主構文解析部２は、入力部１にて入力された文を構文解析する機能部であり、構文解析が成功した場合は、そのまま出力部４に出力し、構文解析が失敗した場合は、部分的に解析された結果を解析救済部３に出力するよう構成されている。尚、主構文解析部２における構文解析処理については公知のものが適用可能である。解析救済部３は、主構文解析部２にて解析に失敗した文、即ち、文全体を覆う解析結果が得られなかった場合、部分的に解析された結果、即ち、部分解析結果を合成して文全体を覆う構文解析結果を作成する機能を有している。また、解析救済部３は、第１のフィルタ３１、第２のフィルタ３２、木追加装置３３を備えている。
【００１４】
第１のフィルタ３１は、部分解析結果の合成結果に対して、部分解析結果のみを用いて合成される組合せ、即ち、主構文解析部２から出力された部分解析結果のみから組み合わせた合成結果を優先してフィルタリングする機能部である。第２のフィルタ３２は、部分解析結果の品詞が同じであった場合、これを合成して新たな部分解析結果として出力する機能を有している。木追加装置３３は、部分解析結果がない場合は、空の部分解析結果を設定する機能部である。
尚、上記主構文解析部２および解析救済部３は、それぞれの機能に対応したソフトウェアとこれを実行するＣＰＵ等のハードウェアからその構成が実現されている。
【００１５】
出力部４は、構文解析結果をユーザの用途に応じて出力または他の装置への入力とする機能部である。
【００１６】
〈動作〉
先ず、例文“I shall eat the radish salad”が入力部１より入力されたとする。この場合、主構文解析部２による構文解析が成功する。
図３は、主構文解析成功例の説明図である。
このように解析が成功した場合、その出力は、図３（ａ）のようになる。尚、これは構文解析を木構造で表した場合である。このように、構文解析を木構造で表すと、文全体は単一の木として表現される。以下、部分木はその詳細を略し、図３（ｂ）で示すように三角形で表すことにする。
【００１７】
次に、主構文解析部２が構文解析に失敗した例を説明する。
今度は、例文“I shall the radish salad”を入力部１より入力したとする。この例では主構文解析部２で解析が失敗し、そのため、例文の部分解析結果を解析救済部３に出力する。
図４は、部分解析結果を示す説明図である。
この場合、出力は、図示のように、解析に成功した範囲を示すインデックス値と、その部分の解析結果を表現する木の集合として与えられる。図中、［０，１］や［１，２］がインデックス値であり、例えば［０，１］は、文の０番目の区切り（＝文頭）から１番目の区切り（＝“Ｉ”と“ｓｈａｌｌ”との間）までの解析結果、即ち“Ｉ”の解析結果を表している。また、三角形の数は、それぞれの部分解析結果を示しており、“Ｉ”の場合は３個、“ｓｈａｌｌ”の場合は２個の解析結果があることを示している。尚、それぞれの解析結果とは、例えば“Ｉ”の場合、
▲１▼名詞（英語のアルファベットの９番目を意味する“Ｉ”）
▲２▼代名詞（日本語の私を意味する“Ｉ”）
▲３▼記号（化学記号のヨウ素を意味する“Ｉ”）
といった解析結果を意味している。また、“ｓｈａｌｌ”の場合、例えば、▲１▼助動詞、▲２▼動詞といった解析結果を意味している。
【００１８】
次に、このような部分解析結果を用いた解析救済部３の動作を図１を用いて説明する。
図１は、部分解析結果を格納する三角行列を示している。先ず、主構文解析部２の部分解析結果をこの三角行列に並べる。ここで、（１０１）は、文頭から“Ｉ”と“ｓｈａｌｌ”まで（つまり“Ｉ”）を示し、（１０２）は“ｒａｄｉｓｈ”と“ｓａｌａｄ”の間から文末まで（つまり“ｓａｌａｄ”）を示し、（１０３）は  文頭から“ｓｈａｌｌ”と“ｔｈｅ”の間まで（つまり“Ｉ  ｓｈａｌｌ”）を示している。他の欄も同様である。各欄にある三角形は、図４で示したように、部分解析結果（の数）を示している。
【００１９】
解析救済部３は、図１に示す行列の（１０５）、つまり文頭から文末までを示す欄を埋めることで解析の救済を行う。このために行列上の（１０１）から（１０２）、（１０３）から（１０４）の方向に順に（１０５）までの行列の各要素に対して、要素が空である場合、例えば（１０３）のような場合に木を合成し、この合成結果を解析が成功したものとみなして行列の要素に追加する。要素が空でない場合、例えば（１０４）のような場合は、その部分については合成を行わず、既存の木を使用する。ある一つの欄に入る木の合成は次のように行う。
【００２０】
図５は、解析救済部３の動作を示す説明図である。
図５は、図１における“Ｉ”と“ｓｈａｌｌ”の部分の合成処理を示すものである。
先ず、空欄に対応する範囲に対してそれを構成する二つの範囲の組合せを列挙する。図５に示す場合、空欄（２０３）に対応する範囲は“Ｉ  ｓｈａｌｌ”であり、この場合は、“Ｉ”（２０１）、“ｓｈａｌｌ”（２０２）の組合せとなる。そのそれぞれの組合せに対して以下の合成を行い、その全ての結果を空欄（２０３）に書き込む。
【００２１】
先ず、（２０１）、（２０２）から木（２０４）、（２０５）を取出す。尚、これら（２０４）および（２０５）の、Ａ，Ｂ，Ｃおよびａ，ｂは、木の識別のために便宜上付与したものであり、それぞれ図４で示した部分解析結果と同様のものである。
次に、これらの木に対し、全ての組合せ（図５の場合３×２＝６通り）で、二つの木をつなぎ（２０６）、それぞれ一つの木とする（２０７）。尚、この合成は文法等を使用せず無条件に行う。
そして、第１のフィルタ３１〜木追加装置３３により、余分な木の削除および不足した木の追加を行う（２０８）〜（２１３）。
【００２２】
［第１のフィルタ３１の処理］
●部分木数の最小化（２０８）
先ず、主構文解析部２の出力の全ての木に対して、“主構文解析部２の結果を一つ使っている”という意味でそれぞれ“１”と印を付ける。次に、解析救済部３において合成された木の二つの部分木についている印を見てその合計値を合成された木に印を付ける。そして、この数を比べて最小のもの（複数存在する場合もある）を残して他のものを削除する。
主構文解析部２の出力として各単語に対する解析結果が単語毎に少なくとも一つずつはあるとしているため、合成の時に付ける印は最低が“２”、最大が合成対象の範囲の単語数となる。
このように、部分木数の最小化は図４で与えられた木を使用する数を最小とする組合せを選択する。これは、主構文解析部２で解析された結果の木の方が、解析救済部３で合成された木よりも構文解析結果として質が良いためである。即ち、主構文解析部２で解析された木の数が少ない→主構文解析部２で解析された範囲が広く、合成の回数が少ない→構文解析結果の質がよい。となる。尚、この処理では、部分木がどのような言語学的内容を持つかは一切考慮しない。
【００２３】
図５の場合、６個の合成木［Ａ，ａ］［Ｂ，ａ］［Ｃ，ａ］［Ａ，ｂ］［Ｂ，ｂ］［Ｃ，ｂ］の合成値は、それぞれ“２”であるため、全て最小のものとなり、削除される合成木がなく、そのままの合成木が出力される（２０９）。
【００２４】
［第２のフィルタ３２の処理］
●同品詞ペアの優先処理（２１０）
第２のフィルタ３２の機能は、「同品詞ペアの合成木が存在する場合は、この合成木を残して全ての合成木を削除する。但し、同品詞ペアがない場合は全ての合成木を残す」である。このため、図５の例では、６個の合成木［Ａ，ａ］［Ｂ，ａ］［Ｃ，ａ］［Ａ，ｂ］［Ｂ，ｂ］［Ｃ，ｂ］は全て同品詞のペアではないため、同品詞ペアの合成木が存在せず、そのままの合成木が出力される（２１１）。
このように、同品詞ペアの優先処理を設けるのは、二つの部分木が同じ品詞である場合、熟語等のひとかたまりの語であることが多いためである。例えば、本例でいえば、主構文解析部２において、“radish salad”といった名詞句を解析できなかった場合では、この第２のフィルタ３２の処理（名詞＋名詞）によって救済されることになる。
尚、この処理においては、部分木がどのように生成されたか、つまり主構文解析部２で出力した木なのか解析救済部３で生成した木なのかは一切考慮しない。
【００２５】
［木追加装置３３の処理］
●最低要素数の確保処理（２１２）
木追加装置３３の処理は、その入力の候補数を調べ、その結果が、
１個以上ある→処理せず。入力をそのまま出力する。
０個である→内容が空の木を一つ作成し、それを出力する。
である。従って、図５の場合は入力が６個あるため、この処理は行われず、入力された木をそのまま出力する（２１３）。
このように、木追加装置３３の処理を設けるのは、入力等に何らかのエラーがあって部分木が存在せず、そのため合成処理が行えない状態になるのを防ぐためである。
【００２６】
以上のような第１のフィルタ３１〜木追加装置３３の処理を行うと、図１の行列の各値は次のようになる。尚、図１の行列の上からｉ番目、左からｊ番目（□のないところも数える）を［ｉ，ｊ］で示すとする。例えば、図１の（１０１）は［１，１］、（１０２）は［５，５］となる。
以下、［１，１］（１０１）から［５，５］（１０２）、［１，２］（１０３）から［４，５］（１０４）、…、［１，５］（１０５）の順にボトムアップに処理を行う場合について説明する。
【００２７】
［１，１］（１０１）：
既に入っているので何もしない。
［２，２］：
既に入っているので何もしない。
［３，３］：
既に入っているので何もしない。
［４，４］：
既に入っているので何もしない。
［５，５］（１０２）：
既に入っているので何もしない。
［１，２］（１０３）：
［１，１］と［２，２］を合成。６個木ができる（図５参照）。
［２，３］：
［２，２］と［３，３］を合成。６個木ができる。
［３，４］：
既に入っているので何もしない。
［４，５］（１０４）：
既に入っているので何もしない。
［１，３］：
［１，１］と［２，３］（［Ｉ］と［ｓｈａｌｌ  ｔｈｅ］）、［１，２］と［３，３］（［Ｉ  ｓｈａｌｌ］と［ｔｈｅ］）を合成。３６個木ができる。
［２，４］：
［２，２］と［３，４］、［２，３］と［４，４］を合成。４個木ができる。尚、第１のフィルタ３１によって［２，３］と［４，４］の木は消える。即ち、［２，２］と［３，４］の合成木の合計値はそれぞれの合成木で“２”であるが、［２，３］と［４，４］の場合は、合計値が“３”となるため削除される。
【００２８】
［３，５］：
既に入っているので何もしない。
［１，４］：
［１，１］と［２，４］、［１，２］と［３，４］、［１，３］と［４，４］を合成。１２個木ができる。尚、第１のフィルタ３１によって［１，２］と［３，４］以外の木は消える。
［２，５］：
［２，２］と［３，５］、［２，３］と［４，５］、［２，４］と［５，５］を合成。６個木ができる。第１のフィルタ３１によって［２，２］と［３，５］以外の木は消える。
［１，５］（１０５）：
［１，１］と［２，５］、［１，２］と［３，５］、［１，３］と［４，５］、［１，４］と［５，５］を合成。３６個木ができる。第１のフィルタ３１によって［１，１］と［２，５］、［１，２］と［３，５］以外の木は消える。
【００２９】
最終的には、“Ｉ”の木を［△Ｉ１，  △Ｉ２，  △Ｉ３］、“ｓｈａｌｌ”の木を［△Ｓ１，  △Ｓ２］、“ｔｈｅ  ｒａｄｉｓｈ  ｓａｌａｄ”の木を［△Ｒ１，  △Ｒ２，  △Ｒ３］とすると、“ｔｈｅ”，“ｒａｄｉｓｈ”，“ｓａｌａｄ”，“ｔｈｅ  ｒａｄｉｓｈ”，“ｒａｄｉｓｈ  ｓａｌａｄ”は途中で結果として捨てられ、次のような木が生成される。
【００３０】
図６は、最終的に生成された木の説明図である。
このように、“I shall the radish salad”の場合、最終的に３６個の解となる。即ち、“I”と“shall”が先に結びつくのが１８個、“shall”と“the radish salad”が先に結びつくのが１８個である。
これらは全て主構文解析部２の出力の部分木を三つ含むものとなる。それ以外の候補は、途中第１のフィルタ３１で削除されるか、予め入っている木のため生成されないかとなる。
【００３１】
以上、ボトムアップで処理を行う場合について説明したが、トップダウンで処理を行うこともできる。以下、トップダウンで処理を行う場合について説明する。
0003995186.tif 000002
0003995186.tif 000003
【００３２】
以上説明したトップダウンで処理を行う場合の例は合成の回数が７回であり、ボトムアップする場合の処理と変化がないが、以下の場合は合成の回数が少なくなる。
例えば、図１の行列、［１，１］［１，２］［１，３］［１，４］［２，２］［３，３］［４，４］［５，５］［２，５］［３，５］［４，５］に１つ以上の木が存在し、その他の行列［２，３］［３，４］［２，４］［１，５］は木が存在しない場合であれば、ボトムアップで処理を行うと木が存在しない個所、つまり４マス分全ての合成が必要であるが、トップダウンの場合、右上隅［１，５］の１マスだけを合成すればよい。
【００３３】
〈効果〉
以上のように具体例によれば、主構文解析部２で、ある文に対する構文解析結果が得られなかった場合は、解析救済部３が、主構文解析部２の部分解析結果を合成してその文全体を覆う構文解析結果を作成するようにしたので、何らかの原因により主構文解析が失敗した場合でも、必ず構文解析結果を出力することができる。従って、構文解析できないことによる翻訳処理不能状態を回避することができる。
例えば、英語等で綴りに若干の誤りがあった等で、構文解析ができなかった場合でも、何らかの翻訳結果を出すことができる。このことは、即時性を要求されるような場面、例えば、インターネット上での英語のチャットの場面で翻訳を行う、といったことを考えた場合、翻訳結果が出ないよりも何らかの翻訳結果が出た方が望ましく、このような場合にも非常に大きな効果を有するものである。
【００３４】
また、構文解析失敗時の対応処理が集約できることにより、主構文解析部２は解析が失敗したときのための対処を簡素化あるいは不要とすることができる。即ち、主構文解析部２は構文解析が失敗した場合は、その部分解析結果を出力するだけでよく、他の処理は考慮する必要がない。
更に、解析救済部３は主構文解析部２の構文解析が失敗した場合に限り使用されるため、構文解析成功時では余分な処理を行う必要がなく、この場合の解析救済部３を設けたことによる構文解析効率の低下は全くない。
【００３５】
また、上記具体例では、第１のフィルタ３１を設けたので、解の爆発（膨大な量の解が生成されること）を防止することができる。そのため、合成時に無駄な処理を行うことなく、処理の高速化に寄与することができる。
更に、上記具体例では、第２のフィルタ３２を設けたので、例えば、複数の名詞からなる名詞句も的確に抽出することができ、構文解析の精度を向上させることができる。
また、上記具体例では、木追加装置３３を設けたので、合成処理にエラーが発生せず、確実に文全体を覆う解析結果を出力することができる。
【００３６】
《利用形態》
上記具体例では、構文解析の対象文として英文を例に挙げたが、特定の言語に限定されるものではなく、任意の言語に適用可能である。
上記具体例では、英文のように入力がリストとして表現できるものを扱う例を示したが、例えば日本語文に対しても、語間の連接情報を付与することにより入力として有向非循環グラフを扱うことが可能である。
上記具体例では、構文解析として木構造で表現したが、部分解析結果を合成することが可能でありさえすれば、部分あるいは文全体の解析結果の表現は、例えば素性構造等、木以外に任意のものが使用可能である。
本発明は、主構文解析部２での構文解析がパターン解析だけでなく、どのような構文解析であっても、主構文解析部２から出力される部分解析結果の集合内に、文全体を覆う組合せが一つ以上存在することが保証される限り、任意の主構文解析に適用可能である。
【００３７】
上記具体例では、第１のフィルタ３１、第２のフィルタ３２および木追加装置３３をそれぞれ一つずつ設けたが、これらの個数は任意の数に増減が可能であり、また、その処理順序も任意の順序に変更可能である。例えば、主構文解析部２の出力から各単語分の部分木しかない場合（図１において、（１０１）〜（１０２）上にしか木がない場合）、第１のフィルタ３１は削除することが可能である。即ち、この場合、範囲が決まればその中で主構文解析部２の出力した部分木の個数は、語数に一致する筈だからである。このような場合は、第１のフィルタ３１を削除することで不要な処理を行わないため、処理の高速化を図ることができる。また、主構文解析部２の出力で品詞情報が付かないことが分かっている場合は、第２のフィルタ３２を削除することが可能である。この場合も不要な処理を行わないことによる処理の高速化を図ることができる。
【００３８】
本発明では、出力部４に接続される後段側の装置の動作に合わせて任意の処理を行うフィルタを付加してもよい。例えば、後段側の装置が“文”という品詞情報が付与されている解析結果に対して処理する場合は、解析救済部３で得られた解析結果に対して“文”という品詞情報を付与するフィルタを設けてもよい。
また、上記具体例において、例えば、第１のフィルタ３１の出力結果に対して第２のフィルタ３２で削除されたくない合成木がある場合、この合成木に対して何らかの識別子を付与し、後段側のフィルタリングで削除しないよう構成してもよい。
【００３９】
上記具体例では、第１のフィルタ３１〜木追加装置３３の処理内容は、合成処理毎に固定としたが、装置全体の負荷のかかり方や、どのあたりの合成を行っているか（合成処理が文全体に近いのか単語レベルに近いのか）、また、文章内でのその文の役割は、見出し／概略／説明等のどの部分なのか（但し、この場合は、役割を判定する手段が必要）といったことを加味して処理内容を変えるよう構成してもよい。負荷によって出力を変える場合は、“負荷を下げる”と“精度を上げる”のどちらを取るかを現在の負荷によって（合成毎に）異なる結果を出力することになる。
例えば、装置全体の負荷が大きい場合は、第１のフィルタ３１で、特定の部分解析結果を使用する部分木の優先度を高くするといった処理により、出力される木の数を少なくし、以後の処理の負荷を下げるといった動作が可能である。一方、余力のある場合は木を減らす量を少なくすることで、妥当性の少しでも高い木が削られる可能性を下げることができる。
【００４０】
上記具体例では、解析救済部３において、図５に示したように、合成した後にフィルタリングを行うようにしたが、合成処理とフィルタリングを同時に行うようにしてもよい。即ち、合成しながらその時点で最も部分木の値の小さいものを残していく、といった処理を行うよう構成してもよい。このようにすれば、その時点での組み合せ爆発を防止することができる。
【図面の簡単な説明】
【図１】本発明の構文解析方法の具体例を示す説明図である。
【図２】本発明の構文解析装置の具体例を示す構成図である。
【図３】主構文解析成功例の説明図である。
【図４】部分解析結果を示す説明図である。
【図５】解析救済部の動作を示す説明図である。
【図６】最終的に生成された木の説明図である。
【符号の説明】
２  主構文解析部
３  解析救済部
３１  第１のフィルタ
３２  第２のフィルタ
３３  木追加装置
【図１】
0003995186.tif 000004
【図２】
0003995186.tif 000005
【図３】
0003995186.tif 000006
【図４】
0003995186.tif 000007
【図５】
0003995186.tif 000008
【図６】
0003995186.tif 000009