(57)【特許請求の範囲】
【請求項１】
原語文書に含まれる複数の原語文と、前記原語文書の訳語文書に含まれる複数の訳語文との対応関係を付けるための対訳文書文対応付けシステムであって、
前記原語文の数と前記訳語文の数とを比較し、前記原語文の数が前記訳語文の数と等しい場合、各前記原語文及び各前記訳語文を文並びに従って一対一に対応させたそれぞれの対応組を順に設定してなる各初期パスを求め、前記原語文の数が前記訳語文の数より大きい場合、各前記原語文及び各前記訳語文を文並びに従って一対一及び二対一のいずれかに対応させたそれぞれの対応組を順に設定してなる各初期パスを求め、前記原語文の数が前記訳語文の数より小さい場合、各前記原語文及び各前記訳語文を文並びに従って一対一及び一対二のいずれかに対応させたそれぞれの対応組を順に設定してなる各初期パスを求め、引き続き、前記原語文と前記訳語文との対応数を順次増加させる毎に、他の対応組からなる他のパスを順次求める組合せ管理手段と、
前記初期パス及び前記他のパス毎に、各前記対応組に対応して、前記原語文及び前記訳語文の対応度を示すそれぞれの評価値を文の評価要素に基づき算出し、該算出した各評価値を順次、加算してパス毎の評価値の総和を求める評価値計算手段と、
各前記いずれかの初期パスを求めた場合のパス毎の前記評価値の総和の最大値を暫定解として該当する前記初期のパスに対応させて保持し、且つ、前記評価値の設定評価値を保持し、前記他のパスに対して計算済みの前記評価値を取り込んでその途中和を計算し、未計算の対応組の前記評価値が計算される前に、該未計算の前記対応組の数を調べて該数と前記設定評価値とを積算し、該積算値を前記途中和に加算してその加算結果が前記暫定解より小さいと判定すると前記他のパスの計算を中止させ、前記他のパスの前記評価値の総和が前記暫定解より大きいと判定すると、前記暫定解を更新し、更に、前記他のパスにおいて対応組の原語文と訳語文との前記対応数が最大対応付け文数になると、前記組合せ管理手段に該最大対応付け文数以上の対応組に関する他のパスの生成を終止させると共に、現在の暫定解に対応するパスを文の対応付けの解とする計算結果管理手段と
を備えることを特徴とする対訳文書文対応付けシステム。
【請求項２】
前記設定評価値は、前記組合せが取り得る最大評価値及び前記組合せの平均及び分散から計算される評価基準値のいずれかであることを特徴とする請求項１記載の対訳文書対応付けシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、英語−日本語などの原文と訳文で構成される対訳文書における文の対応付けを行う対訳文書対応付けシステムに関する。
【０００２】
【従来の技術】
英語−日本語といった原文と訳文とで構成される対訳文書中の各文の対応付けを、対訳辞書を用いて行うシステムがある。例えば、このようなシステムに関する文献として、
対訳辞書および統計情報を用いた二言語対訳テキスト照合  宇津呂  武仁  松本  裕治  Ｖｏｌ．１２  Ｎｏ．５  ｓｅｐ．１９９５があった。
【０００３】
この文献では、対訳文書の文の対応付けを対訳辞書を利用してダイナミックプログラミング（ＤＰ）で行う方法を述べている。このような対応付けをダイナミックプログラミングを用いて行うには、先ず、原文および訳文を１文毎に区切り、その文の形態解析を行って単語毎に分割する。そして、それらの単語の中から自立語を取り出し、対訳辞書を用いて、それぞれの文の中の自立語がどの程度対応しているかで評価する。例えば、評価する方法として以下のような式を用いる。
【０００４】
ｈ（ｘ，ｙ）＝２×ｆｍ（ｘ，ｙ）／（ｆｊ（ｘ）＋ｆｊ（ｙ））
ここで、
ｘは原文中の文（複数文の場合もある）
ｙは訳文中の文（複数文の場合もある）
ｈ（ｘ，ｙ）は評価関数
ｆｍ（ｘ，ｙ）は、ｘ，ｙの中で対応のついた自立語の数
ｆｊ（ｘ）は、ｘ中の自立語の数
ｆｊ（ｙ）は、ｙ中の自立語の数
である。
【０００５】
このような評価関数を用いることによって、対応する文同士の評価関数の値は大きくなり、対応していない文同士の評価関数は小さくなる。これを文の先頭から調べていき、評価関数の和が最も大きくなるような組み合わせを対応付け問題の解とする。
【０００６】
【発明が解決しようとする課題】
しかしながら、上記のように、評価関数を用いて対応付けを行うには、対訳辞書を引いたり、文字列のマッチング処理を行うため、評価値を算出するには時間がかかる。更に、ＤＰを用いた方法は、原文の文数×訳文の文数に比例した時間がかかり、実行速度に問題があった。それは文の対応のほとんどが１文対１文の対応であり、１文対２文、２文対１文まで含めるとほとんど１００パーセントに近い確率で当てはまるにもかかわらず、１文対３文、３文対１文や１文対４文、４文対１文になるまでの可能性を考慮して、考えられる全ての組の評価値を計算しているからである。
【０００７】
このような問題に対処するためには、１文対３文、３文対１文などを計算しないといった方法が容易に考えられる。しかしながら、上記のような確率値は対訳文書の分野等によっては変化する恐れがあり、場合によっては、１文対３文といた対応が最適解であることも考えられる。ところが、このような方法は、１文対３文の対応があった場合にこれを見つけられないため、場合によっては対応付けの精度が低くなってしまうという問題があった。
【０００８】
このような点から、対応付けの精度を低下させることなく処理を高速化することのできる対訳文書対応付けシステムの実現が望まれていた。
【０００９】
【課題を解決するための手段】
本発明は、前述の課題を解決するため次の構成を採用する。
〈構成〉
本発明は、原語文書に含まれる複数の原語文と、原語文書の訳語文書に含まれる複数の訳語文との対応関係を付けるための対訳文書文対応付けシステムであって、原語文の数と訳語文の数とを比較し、原語文の数が訳語文の数と等しい場合、各原語文及び各訳語文を文並びに従って一対一に対応させたそれぞれの対応組を順に設定してなる各初期パスを求め、原語文の数が訳語文の数より大きい場合、各原語文及び各訳語文を文並びに従って一対一及び二対一のいずれかに対応させたそれぞれの対応組を順に設定してなる各初期パスを求め、原語文の数が訳語文の数より小さい場合、各原語文及び各訳語文を文並びに従って一対一及び一対二のいずれかに対応させたそれぞれの対応組を順に設定してなる各初期パスを求め、引き続き、原語文と訳語文との対応数を順次増加させる毎に、他の対応組からなる他のパスを順次求める組合せ管理手段と、初期パス及び他のパス毎に、各対応組に対応して、原語文及び訳語文の対応度を示すそれぞれの評価値を文の評価要素に基づき算出し、該算出した各評価値を順次、加算してパス毎の評価値の総和を求める評価値計算手段と、各いずれかの初期パスを求めた場合のパス毎の評価値の総和の最大値を暫定解として該当する初期のパスに対応させて保持し、且つ、評価値の設定評価値を保持し、他のパスに対して計算済みの評価値を取り込んでその途中和を計算し、未計算の対応組の評価値が計算される前に、該未計算の対応組の数を調べて該数と設定評価値とを積算し、該積算値を途中和に加算してその加算結果が暫定解より小さいと判定すると他のパスの計算を中止させ、他のパスの評価値の総和が暫定解より大きいと判定すると、暫定解を更新し、更に、他のパスにおいて対応組の原語文と訳語文との対応数が最大対応付け文数になると、組合せ管理手段に該最大対応付け文数以上の対応組に関する他のパスの生成を終止させると共に、現在の暫定解に対応するパスを文の対応付けの解とする計算結果管理手段と
を備えることを特徴とする。
【００１０】
この設定評価値は、組合せが取り得る最大評価値及び組合せの平均及び分散から計算される評価基準値のいずれかである。
【００１２】
【発明の実施の形態】
本発明は、１文対１文や１文対２文等、可能性の高いものから優先的に計算し、暫定解を利用して正解の可能性を絞ることにより、ＤＰで使用する評価値の計算量を減らすようにしたものである。
【００１３】
以下、本発明の実施の形態を具体例を用いて詳細に説明する。
【００１４】
《具体例１》
〈構成〉
図１は本発明の対訳文書対応付けシステムの具体例１を示す構成図である。
図のシステムは、原文ファイル１０１、訳文ファイル１０２、文分割手段１０３、形態素解析手段１０４、組み合わせ管理手段１０５、評価値計算手段１０６、計算結果管理手段１０７、対応タグ付き原文ファイル１０８、対応タグ付き訳文ファイル１０９、対訳辞書１１０からなる。
【００１５】
原文ファイル１０１は、複数の原文からなる文書ファイルであり、例えば英語の文書ファイルである。訳文ファイル１０２は、複数の訳文からなる文書ファイルであり、例えば日本語の文書ファイルである。
【００１６】
文分割手段１０３は、原文ファイル１０１および訳文ファイル１０２の文書ファイルを１文毎に分割する機能を有している。例えば、英文であればピリオド、日本文ならば句点等で分割を行うよう構成されている。
【００１７】
形態素解析手段１０４は、文分割手段１０３で分割された英文や日本文に対して形態素解析を行い、単語毎に分割する機能を有している。尚、これら文分割手段１０３および形態素解析手段１０４は既知の構成を用いることができる。
【００１８】
組み合わせ管理手段１０５は、原文と訳文との対応組の組み合わせを求めると共に、文分割手段１０３や形態素解析手段１０４の結果に基づき、原文と訳文の原文ファイル１０１および訳文ファイル１０２中の文数から、原文と訳文との対応付けの最適解の可能性が高い組み合わせを求める機能を有している。
【００１９】
評価値計算手段１０６は、原文と訳文とが対応している程、高い値となる評価値を求めると共に、暫定解として、組み合わせ管理手段１０５で求めた可能性の高い組み合わせの評価値の和を求める機能を有している。具体的には、従来技術の項で説明した評価関数の式に基づいて評価値を計算する構成、あるいは他の手段により評価値を計算する構成であってもよい。
【００２０】
計算結果管理手段１０７は、評価値計算手段１０６で計算したＤＰの評価値を格納するテーブル（図示せず）を備え、組み合わせ管理手段１０５で求めた原文と訳文との組み合わせ（パス）の評価値の計算を、組み合わせの先頭の文から順次計算するよう評価値計算手段１０６に指示し、得られた評価値を前記のテーブルに格納する機能を有している。そして、これらのテーブルの評価値に基づき、任意の組み合わせで、最後まで計算しても暫定解を上回る値にならないと判定できた場合は、その時点で評価値の計算を中止させる機能を有している。
【００２１】
対応タグ付き原文ファイル１０８および対応タグ付き訳文ファイル１０９は、それぞれ原文ファイル１０１と訳文ファイル１０２に文の対応を示すためのタグを付与したものである。
【００２２】
対訳辞書１１０は、対応付けするための原文の単語を引くと訳文の語が複数あるような辞書である。例えば、原文が英語、訳文が日本語の場合英和辞典に相当する。
【００２３】
上記の対訳文書対応付けシステムは、マイクロコンピュータ等で構成され、原文ファイル１０１、訳文ファイル１０２、対応タグ付き原文ファイル１０８、対応タグ付き訳文ファイル１０９、対訳辞書１１０は、ハードディスク装置等の外部記憶装置あるいは半導体メモリに設けられている。また、文分割手段１０３〜計算結果管理手段１０７は、それぞれの手段に対応したプログラムとこれを実行するためのプロセッサや主記憶装置等で構成されている。
【００２４】
〈動作〉
図２は、本具体例の動作を示すフローチャートである。
先ず、文分割手段１０３によって、原文ファイル１０１と訳文ファイル１０２の文区切りを行う（ステップＳ１００）。ここで、原文の文数をｍ、訳文の文数をｎとする。また、組み合わせ管理手段１０５において、文の対応組を徐々に増やしていくための変数ｉに２をセットする。
【００２５】
次に、原文の文数と訳文の文数とが等しいか、即ち、ｍ＝ｎかをチェックする（ステップＳ１０１）。ここで、等しければ評価値を計算する文の組み合わせを（１，１）のみとし（ステップＳ１０３）、ステップＳ１０６に移行する。一方、ステップＳ１０１において、等しくなければ、ｍ＞ｎであるかを判定する（ステップＳ１０２）。
【００２６】
ステップＳ１０２において、ｍ＜ｎであれば、計算する対応組を（１，１）、（２，１）として（ステップＳ１０４）、ステップＳ１０６に移行し、ｍ＞ｎであれば計算する対応組を（１，１）、（１，２）として（ステップＳ１０５）、ステップＳ１０６に移行する。
【００２７】
ステップＳ１０６では、評価値計算手段１０６によって、対応組の評価関数を計算し、計算結果を計算結果管理手段１０７に送る。これにより、計算結果管理手段１０７は、最も点数の高いパスを暫定解とする（ステップＳ１０７）。尚、パスとは、先頭文から最後の文までどのようなルート（原文と訳文の対応組）を通って対応付けられているいるかを一意に示すものである。
【００２８】
次いで、計算結果管理手段１０７は、計算する対応組を（１，１）、（１，２）、（２，１）とし（ステップＳ１０８）、未計算の枝があるかを調べる（ステップＳ１０９）。尚、枝とは、パスの１要素であり、パス中のある地点（英文５文目、和文４文目等）から、次の原文と訳文との対応組がどのようなものであるかを示すものである。
【００２９】
ステップＳ１０９において、未計算の枝があった場合は、その枝の評価値を計算し、この計算値を計算結果管理手段１０７内のＤＰのテーブルに保持する（ステップＳ１１０）。次に、この計算値によって、上述した暫定解よりも評価値の合計値の高い解が得られるかを判定し（ステップＳ１１１）、高い解が得られた場合は、その解を暫定解として更新する（ステップＳ１１２）。
【００３０】
一方、ステップＳ１１１において、暫定解より高い解が得られるかが不明であった場合は、そのパスが最適解になり得ないかを判定する（ステップＳ１１３）。このステップＳ１１３において、明らかに暫定解より評価値が大きくならないことが判明した場合は、そのノードにマークを付け、それより先の枝の計算は保留し（ステップＳ１１４）、ステップＳ１０９に戻る。即ち、そのパスとしての計算を中止する。また、ステップＳ１１３において、最適解となり得ないかが不明であった場合は、そのままステップＳ１０９に戻る。
【００３１】
このようなステップＳ１０９〜ステップＳ１１４の処理を繰り返すことにより、対応組（１，１）、（１，２）、（２，１）におけるパスの暫定解が求められ、また、その処理中で暫定解より大きい値にならないと分かったパスは、それ以上の枝の計算が保留される。尚、ステップＳ１１４において、計算が中止ではなく保留となっているのは、後述するステップＳ１１５以降でｉの値をインクリメントした場合に、そのノードより先も計算する場合があるからである。
【００３２】
ステップＳ１０９において、未計算の枝がなくなった場合は、ステップＳ１１５に移行し、文の対応組を徐々に増やしていくための変数ｉの値をインクリメントする。即ち、ｉの値を３とする。
【００３３】
次に、ｉの値が予め定めた最大対応付け文数より大きいかを調べる（ステップＳ１１６）。この最大対応付け文数とは、１文と何文の対応まで調べるかを示すもので、最大対応付け文数が４であれば、１文対４文、４文対１文の対応まで調べることを意味する。このステップＳ１１６において、ｉ≦最大対応付け文数であれば、計算結果管理手段１０７において、計算する対応組に、（１，ｉ）、（ｉ，１）を追加し（ステップＳ１１７）、ステップＳ１０９に戻る。
【００３４】
一方、ステップＳ１１６において、ｉ＞最大対応付け文数であれば、現在の暫定解を最適解、最適解のパスを文の対応付けの解とし（ステップＳ１１８）、対応付け処理を終了する。
【００３５】
以上の処理を、更に具体的な一例を用いて説明する。
【００３６】
図３は、英文９文、和文７文からなるファイルの対応を取るためのパスの説明図である。
【００３７】
図において、Ｅ１〜Ｅ９はそれぞれ英文の１文目から９文目を表しており、Ｊ１〜Ｊ７はそれぞれ和文の１文目から７文目までを表している。また、丸付きの番号は枝の評価値を計算する順番を表している。例えば、１番の枝は英文の１文目と和文の１文目の対応を評価する。２番の枝は英文の１文目から２文目までと、和文の１文目の対応を評価する、…、２７番目の枝は英文の９文目と和文の７文目の対応を評価する、という意味である。
【００３８】
先ず、図２のフローチャートにおけるステップＳ１００〜ステップＳ１０７の処理を説明する。
【００３９】
この例では英文の数の方が多いので、最初に（１，１）、（２，１）の組み合わせを計算する。対応の組み合わせをこの２通りに限定するとゴール（図の右上）まで到達し得るパスは図３に示すように狭い範囲となる。
【００４０】
図示の枝にふられた番号順に計算し（必ずしもこの通りに計算しなくともよい）、２７番まで計算し終わったら、ＤＰによって、最も評価値の和の高いパスを調べ、その評価値の和を暫定解とする。ここでは、２−５−９−１４−１９−２３−２６が暫定解となったとする。
【００４１】
次に、ステップＳ１０８〜ステップＳ１１４の処理を説明する。
ステップＳ１０８において、（１，２）の組み合わせを追加すると、図３のパスは次のようになる。
【００４２】
図４は、（１，２）の組み合わせを追加した場合のパスの説明図である。
例えば、図中の３１番を計算した時点で、２−３１−１２−１９−２３−２６のパスの方が暫定解よりも高い評価値を得たとすると、その時に暫定解を更新し、そのパスを記憶しておく（ステップＳ１１１〜ステップＳ１１２）。
【００４３】
次に、３６番を計算した時点で、どのようなパスを通っても暫定解よりよい解が得られないと分かったら（この方法については後述する）、３６番の枝の終点（ゴール側）にマーク付けし、そこから先の枝の評価を保留する（ステップＳ１１３〜ステップＳ１１４）。図４の例では、４０、４１、４４、４５の枝の計算をせずに済む。
【００４４】
上記のステップＳ１１３の判断処理は次のように行う。各枝の評価値の最大値は１、暫定解が４．８、２−６−３６の枝の和が１．２であるとすると、そのパスを通る解は４．２以上にはならない。即ち、暫定解より大きくならないため、そのパスの評価値を計算する意味がないことになる。従って、そのパスとしての計算は中止する。
【００４５】
ステップＳ１１５〜ステップＳ１１８の処理では、最大対応付け文数までの対応について計算するためのものである。その際、上記の対応組を（１，１）、（１，２）、（２，１）とした場合と同様に、１文対３文といった計算で、最適解になり得ない枝の計算はせずに済む。
【００４６】
〈効果〉
以上のように、具体例１によれば、原文と訳文との対応の可能性の高い解を暫定解とし、評価値の計算処理において、暫定解より高い値にならないと分かった時点で、そのパスとしての計算を中止するようにしたので、ＤＰにおける計算量を削減でき、処理時間の短縮化を図ることができる。また、１文対３文といった計算も考慮しているため、文書の内容等で精度が低下することもない。
【００４７】
更に、任意の組み合わせで、それまでの暫定解よりも評価値の和の高い値が見つかった場合は、見つかった値を新たな暫定解とするようにしたので、処理を行うに従ってより正しい暫定解が得られ、従って、処理の高速化と精度向上の効果を同時に得ることができる。
【００４８】
特に、本具体例では、最適解のパスが最初に求めた暫定解のパスと一致するか、あるいは近傍にある場合、従来技術と比較して省略できる評価値の計算個所が多くなり、効果が顕著となる。
【００４９】
《具体例２》
具体例２は、複数の枝（原文と訳文との対応組）の評価値が一定の割合で含まれるような値を各枝の基準値として設定し、そのパスが最適解になるか否かの判定を、この基準値を用いて行うようにしたものである。
【００５０】
〈構成〉
図５は、具体例２の対訳文書対応付けシステムの構成図である。
図示のシステムは、原文ファイル１０１、訳文ファイル１０２、文分割手段１０３、形態素解析手段１０４、組み合わせ管理手段１０５、評価値計算手段１０６、計算結果管理手段１０７、対応タグ付き原文ファイル１０８、対応タグ付き訳文ファイル１０９、対訳辞書１１０、基準値計算手段１１１からなる。ここで、原文ファイル１０１〜対訳辞書１１０は、具体例１の構成と同様であるため、その説明を省略する。
【００５１】
基準値計算手段１１１は、各枝の平均、分散などを計算し、一定の割合の枝の評価値がその値を超えないような一定の値、例えば、９５％の枝がこの基準値内にあるような値を導き出す機能を有している。図５中に破線で示す式は、基準値の求め方の一例を示すものである。例えば、枝の値が正規分布をなし、平均をμ、分散をＤとしたときに図示の式において、ｐ＝０．９５となるようなｘを基準値とするよう構成されている。
【００５２】
計算結果管理手段１０７は、基準値計算手段１１１で求めた基準値を用いて暫定解よりも高くなり得ないパスを判断するよう構成されている。つまり、評価値を計算していない枝は高々基準値であると見なしてそのパスの評価値を計算する。
【００５３】
〈動作〉
図６は、具体例２の動作を示すフローチャートである。
図２に示した具体例１と異なる部分は、ステップＳ２０８において、基準値計算手段１１１で基準値を求めている部分と、ステップＳ２１４において、計算結果管理手段１０７が最適解になる見込みがあるかどうかを判定する時に、ステップＳ２０８で求めた基準値を使うことである。
【００５４】
具体例２におけるステップＳ２００〜Ｓ２０７は、具体例１のステップＳ１００〜Ｓ１０７の処理と同様である。次に、ステップＳ２０８では、例えば図５中の式に基づき、枝の平均、分散から評価基準値を計算する。これ以降のステップＳ２０９〜Ｓ２１３の処理は、具体例１のステップＳ１０８〜Ｓ１１２の処理と同様である。
【００５５】
ステップＳ２１４では、上述したように最適解になる見込みがあるか否かを判断する場合に、まだ、計算していない枝の評価値を高々基準値であるとして計算し、これに基づき判断を行うことである。即ち、具体例１では、まだ、計算していない枝の評価値を１として、つまり評価値を最高値としてそのパスの評価値を計算した。これに対し、具体例２では、ほとんどの枝がこの基準値内にあるような値、例えば０．７といったような値であるとしてそのパスの評価値を計算する。
【００５６】
このような基準値を用いることにより、最適解が見つかるという保証は必ずしもできなくなるが、具体例１よりも更に評価値を計算する枝を少なくすることができる。
【００５７】
尚、最適解が見つかるという保証は必ずしもできなくなるという理由は次の点からである。即ち、基準値は、０．７といった最高値ではない値であるため、まだ計算していない枝の評価値を基準値で計算した場合よりも、実際にその枝の評価値を計算した場合の方がそのパスの評価値が大きくなってしまう可能性がある。しかしながら、適切な基準値を設定することで、実際の処理ではこのような可能性はほとんどあり得ないと考えられる。
【００５８】
また、文の対応付け問題は、最適解が１００％正しいとは限らないので、後で人手により対応が正しいかどうかをチェックすることが必要であることを考えると、時間をかけて最適解を見つけるよりも、短時間でそれなりの解を見つける方が利用価値の高い場合もある。
【００５９】
具体例２におけるそれ以降のステップＳ２１５〜Ｓ２１９の処理は、具体例１におけるステップＳ１１４〜Ｓ１１８と同様であるため、ここでの説明は省略する。
【００６０】
以上の処理を更に具体的な一例を用いて説明する。ここで、具体例２においても、対象となるファイルは英文９文、和文７文からなるとする。また、これらの文の対応を取るためのパスの説明図として、具体例１における図３および図４を用いて説明する。
【００６１】
先ず、図６のフローチャートにおけるステップＳ２００〜ステップＳ２０７の処理を説明する。
【００６２】
この例では英文の数の方が多いので、最初に（１，１）、（２，１）の組み合わせを計算する。対応の組み合わせをこの２通りに限定するとゴール（図の右上）まで到達し得るパスは図３に示すように狭い範囲となる。
【００６３】
図示の枝にふられた番号順に計算し（必ずしもこの通りに計算しなくともよい）、２７番まで計算し終わったら、ＤＰによって、最も評価値の和の高いパスを調べ、その評価値の和を暫定解とする。ここでは、２−５−９−１４−１９−２３−２６が暫定解となったとする。以上は、具体例１と同様である。
【００６４】
次に、ステップＳ２０８では、枝の基準値を計算する。ここでは、基準値が０．７になったとする。
【００６５】
次に、ステップＳ２０９〜Ｓ２１５の処理を説明する。
ステップＳ２０９において、（１，２）の組み合わせを追加すると、図３のパスは図４のようになる。
【００６６】
例えば、図中の３１番を計算した時点で、２−３１−１２−１９−２３−２６のパスの方が暫定解よりも高い評価値を得たとすると、その時に暫定解を更新し、そのパスを記憶しておく（ステップＳ２１２〜ステップＳ２１３）。
【００６７】
次に、３６番を計算した時点で、どのようなパスを通っても暫定解よりよい解が得られないと分かったら（この方法については後述する）、３６番の枝の終点（ゴール側）にマーク付けし、そこから先の枝の評価を保留する。図４の例では、４０、４１、４４、４５の枝の計算をせずに済む。
【００６８】
上記の判断方法は次のように行う。各枝の評価値の基準値は０．７、暫定解が４．８、２−６−３６の枝の和が２．２であるとすると、そのパスを通る解は４．３以上にはならない。即ち、暫定解より大きくならないため、そのパスの評価値を計算する意味がないことになる。従って、そのパスとしての計算は中止する。
【００６９】
ここで、具体例１との比較を行うと次のようになる。即ち、具体例１では、各枝の評価値の最大値である１を用いているため、暫定解が４．８、２−６−３６の枝の和が２．２であるとすると、そのパスを通る解は最大５．２となり、この時点では最適解とはなり得ないと判定することができない。これに対し、具体例２では、この時点で計算を中止することができるため、具体例１よりも評価値を計算する枝を少なくすることができる。
【００７０】
ステップＳ２１６〜ステップＳ２１９の処理では、最大対応付け文数までの対応について計算するためのものである。その際、上記の対応組を（１，１）、（１，２）、（２，１）とした場合と同様に、１文対３文といった計算で、最適解になり得ない枝の計算はせずに済む。
【００７１】
〈効果〉
以上のように、具体例２によれば、原文と訳文との対応の可能性の高い解を暫定解とし、評価値の計算処理において、暫定解より高い値にならないと分かった時点で、そのパスとしての計算を中止するようにしたので、具体例１と同様に、ＤＰにおける計算量を削減でき、処理時間の短縮化を図ることができ、また、精度の低下もない。
【００７２】
更に、具体例２では、予め、基準値を用意し、この基準値を用いて最適解とはなり得ないパスかを判定するようにしたので、具体例１よりも更に評価値を求める枝を少なくすることができ、処理時間の短縮化を図ることができる。
【００７３】
尚、上記具体例１、２では、英文と和文との対応付けの場合を示したが、対訳辞書を替えることによって、あらゆる言語同士の対応付けにも利用することができる。また、枝の評価値を計算していく順番も、図示の順番に限定されるものではなく、ある程度順番を変えてもよい。
【００７４】
また、具体例１、２において、ｍ＞２ｎのような場合にも、最初に計算する対応組を変更することで容易に対処することができる。このような場合は、１文対１文、２文対１文、３文対１文を最初に計算する。
【００７５】
上記具体例２において、基準値は、枝の評価値の平均や分散等により予めその値を決めておいたが、最初に暫定解を見つけるまでの枝の値（図３に示す枝の値＝図６におけるステップＳ２０６までの処理の値）で計算してもよい。こうすれば、対応付け処理と同時に基準値のための計算も行うことができる。
【図面の簡単な説明】
【図１】本発明の対訳文書対応付けシステムの具体例１を示す構成図である。
【図２】本発明の対訳文書対応付けシステムの具体例１の動作を示すフローチャートである。
【図３】本発明の対訳文書対応付けシステムにおける英文９文、和文７文からなるファイルの対応を取るためのパスの説明図である。
【図４】本発明の対訳文書対応付けシステムにおける（１，２）の組み合わせを追加した場合のパスの説明図である。
【図５】本発明の対訳文書対応付けシステムの具体例２を示す構成図である。
【図６】本発明の対訳文書対応付けシステムの具体例２の動作を示すフローチャートである。
【符号の説明】
１０１  原文ファイル
１０２  訳文ファイル
１０５  組み合わせ管理手段
１０６  評価値計算手段
１０７  計算結果管理手段
１１１  基準値計算手段
【図１】
0003778705.tif 000002
【図２】
0003778705.tif 000003
【図３】
0003778705.tif 000004
【図４】
0003778705.tif 000005
【図５】
0003778705.tif 000006
【図６】
0003778705.tif 000007