(57)【要約】【課題】分割した後の各部分の翻訳可能性が高くなるように文を分割して翻訳する機械翻訳装置を提供する。【解決手段】この方法は、入力文の先頭と最後とを含めて複数個のノードを定義するステップと、複数個のノードが定義された入力文を、予め定められた基準にしたがって複数個のノードのいずれかの組合せで１または複数個の部分に分割するステップ７２，７４，７６，７８，８０と、１または複数個の部分の各々の翻訳結果を結合して入力文に対する翻訳結果を生成するステップとを含み、予め定められた基準は、翻訳結果の得られない部分に含まれる単語数が小さい分割方法を優先すること、および翻訳結果の得られない部分に含まれる単語数が同じ複数の分割方法がある場合には、分割数の小さい分割方法を優先すること、という基準を含む。【選択図】　　　図５
2004110583.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムにおける機械翻訳方法であって、
入力文中に、入力文の先頭と最後とを含めて複数個のノードを定義するステップと、
前記複数個のノードが定義された入力文を、予め定められた基準にしたがって前記複数個のノードのいずれかの組合せで１または複数個の部分に分割するステップと、
前記１または複数個の部分の各々の翻訳結果を結合して前記入力文に対する翻訳結果を生成するステップとを含み、
前記予め定められた基準は、
翻訳結果の得られない部分に含まれる単語数が小さい分割方法を優先すること、および
翻訳結果の得られない部分に含まれる単語数が同じ複数の分割方法がある場合には、分割数の小さい分割方法を優先すること、
という基準を含む、機械翻訳方法。
【請求項２】
前記機械翻訳方法は、用例ベースの機械翻訳を用いる方法であって、
前記予め定められた基準はさらに、翻訳結果の得られない部分に含まれる単語数が同じ複数の分割方法があり、かつそれらの分割数が同じ場合には、前記１または複数個の部分の各々と、当該１または複数個の部分の各々の翻訳の基礎となる類似用例との間に定義される距離の合計の小さいものを優先すること、という基準を含む、請求項１に記載の方法。
【請求項３】
前記分割するステップは、前記予め定められた基準に適合するように定められる所定のコスト関数を最小とするような、前記入力文の前記先頭のノードと前記入力文の前記最後のノードとの間でのノードの経路を探索するステップを含む、請求項１または２に記載の方法。
【請求項４】
前記所定のコスト関数は、前記入力文のうち、分割によっても翻訳できない単語数と所定のコスト定数との積と、分割により翻訳可能となった部分の数との和により定義される、請求項３に記載の方法。
【請求項５】
前記所定のコスト定数を、前記複数個のノードの数以上となるように予め定義するステップをさらに含む、請求項４に記載の方法。
【請求項６】
前記複数個のノードは、前記入力文の単語の境界において定義される、請求項１〜５のいずれかに記載の方法。
【請求項７】
前記分割するステップは、
前記入力文の前記先頭のノードと前記最後のノードとの間で翻訳処理を試みるステップと、
先行するステップで試みられた翻訳処理が成功したか否かを判定し、翻訳処理が成功するまで、または隣接するノード間での翻訳処理が失敗したと判定されるまで、翻訳処理の対象の末尾を一ノードずつ前に移動して繰返し翻訳処理を試みるステップと、
翻訳処理が成功した、または隣接するノード間での翻訳処理が失敗したと判定されたことに応答して、それぞれ所定の値を前記コスト関数に加算して更新し、さらに次の翻訳処理の対象の先頭ノードを前記翻訳処理における対象の末尾のノードの次のノードに進めるステップと、
前記繰返し翻訳処理を試みるステップと前記加算するステップとを所定の終了条件が成立するまで実行するステップとを含む、請求項３から５のいずれかに記載の方法。
【請求項８】
前記所定の終了条件が成立するまで実行するステップは、
前記次のノードが前記最後のノードか否かを判定するステップと、
前記次のノードが前記最後のノードではないと判定されたことに応答して、前記繰返し翻訳処理を試みるステップと前記加算するステップとを再び実行するステップと、
前記次のノードが前記最後のノードと判定されたことに応答して処理を終了するステップとを含む、請求項７に記載の方法。
【請求項９】
さらに、前記進めるステップで更新された前記コスト関数の値が所定のしきい値より大きい場合には、当該分割方法を分割方法の候補から除外するステップを含む、請求項７または８に記載の方法。
【請求項１０】
コンピュータ上で実行されることにより、請求項１〜９のいずれかに記載の方法のすべてのステップをコンピュータが実行するように適合されたコンピュータプログラムコード手段を含む、コンピュータプログラム。
【請求項１１】
コンピュータ可読な媒体上に記録された、請求項１０に記載のコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は機械翻訳方法に関し、特に、入力文を複数個の部分に分割して部分翻訳を試みることにより翻訳成功率を向上させる機械翻訳方法およびそのためのコンピュータプログラムに関する。
【０００２】
【従来の技術】
出願人は、用例ベース翻訳の一つとして単語列編集距離を使った翻訳方式（ＤＰ−ｍａｔｃｈ　Ｄｒｉｖｅｎ　ｔｒａｎｓＤｕｃｅｒ、以下「Ｄ３」と呼ぶ）を提案した（後掲の非特許文献１を参照）　。本方式では対訳コーパスを直接利用することにより、人手による翻訳ルール、パターンの記述を不要とする。翻訳システム開発のコスト削減が可能となり、タスク移植性、多言語適用性の向上が期待できる。
【０００３】
旅行会話タスクにおける日英翻訳へ当方式の適用実験を行ない高い翻訳品質を得た。翻訳一対比較法（後掲の非特許文献２を参照）によるとＴＯＥＩＣ　７５０点の日本人と同等の翻訳品質のレベルである。
【０００４】
Ｄ３は、対訳コーパス、対訳辞書、類語辞書を用いて翻訳を行なう。入力文と類似する用例を基に次の手順により訳文を生成する。
（１）　用例検索
入力文と距離が最小の原文を持つ用例を対訳コーパスから検索する。与えられたしきい値未満の距離の用例が存在しなければ検索および翻訳処理は失敗（ＦＡＩＬ）となる。文同士の距離は次の式で定義している。
距離＝（２Σ置換単語間距離＋削除挿入単語数）／（入力文長＋用例原文長）
ここで単語間距離は類語辞書に基づき０と１との間の値をとる。文長は文の単語数を意味する。
（２）　翻訳パターン生成
用例原文の入力文と異なる箇所を変項とし、変項と用例訳文中の単語、変項と入力文中の単語の対応をとり翻訳パターンを生成する。対応を決める際に対訳辞書、類語辞書を参照する。
（３）　翻訳パターン選択
同じ距離のパターンが複数ある場合は一つ選択する。選択基準には変項の対応率、用例数、変項中の単語の出現頻度を用いる。
（４）　訳文生成
用例訳文中の変項対応箇所を対応する入力文中の単語の訳語で置き換える。この際対訳辞書を利用する。
【０００５】
【特許文献１】
特開平１０−３１２３８２号公報（第９欄段落００３８第４行目〜１１行目、図６）
【非特許文献１】
スミタ、Ｅ．（Ｓｕｍｉｔａ，　Ｅ．）「単語シーケンス間のＤＰマッチングを用いた用例ベースの機械翻訳（Ｅｘａｍｐｌｅ−Ｂａｓｅｄ　ｍａｃｈｉｎｅ　ｔｒａｎｓｌａｔｉｏｎ　ｕｓｉｎｇ　ＤＰ−ｍａｔｃｈｉｎｇ　ｂｅｔｗｅｅｎ　ｗｏｒｄ　ｓｅｑｕｅｎｃｅｓ）」第３９回ＡＣＬのＤＤＭＴワークショップ予稿集（Ｐｒｏｃ．　ｏｆ　ＤＤＭＴ　ｗｏｒｋｓｈｏｐ　ｏｆ　３９ｔｈ　ＡＣＬ）、２００１年
【非特許文献２】
菅谷文明ら「音声翻訳システムと人間との比較による音声翻訳能力評価手法の提案と比較実験」電子情報通信学会論文誌Ｄ−ＩＩ、Ｖｏｌ．　Ｊ８４−Ｄ−ＩＩ，　Ｎｏ．　１１、２００１年
【非特許文献３】
スミタ、Ｅ（Ｓｕｍｉｔａ，　Ｅ．）「話し言葉の翻訳に固有の問題に対する解決：ＡＴＲ−ＭＡＴＲＩＸのアプローチ（Ｓｏｌｕｔｉｏｎｓ　ｔｏ　Ｐｒｏｂｌｅｍｓ　Ｉｎｈｅｒｅｎｔ　ｉｎ　Ｓｐｏｋｅｎ−ｌａｎｇｕａｇｅ　Ｔｒａｎｓｌａｔｉｏｎ：　Ｔｈｅ　ＡＴＲ−ＭＡＴＲＩＸ　Ａｐｐｒｏａｃｈ）」ＭＴサミットＶＩＩ予稿集（Ｐｒｏｃ．　ｏｆ　ＭＴ　Ｓｕｍｍｉｔ　ＶＩＩ）、１９９９年
【非特許文献４】
タケザワ、Ｔら（Ｔａｋｅｚａｗａ　Ｔ．　ｅｔ　ａｌ．）「実世界における旅行会話の言語翻訳のための、広範囲のバイリンガルコーパスに向けて（Ｔｏｗａｒｄ　ａ　Ｂｒｏａｄ−ｃｏｖｅｒａｇｅ　Ｂｉｌｉｎｇｕａｌ　Ｃｏｒｐｕｓ　ｆｏｒ　Ｓｐｅｅｃｈ　Ｔｒａｎｓｌａｔｉｏｎ　ｏｆ　Ｔｒａｖｅｌ　Ｃｏｎｖｅｒｓａｔｉｏｎｓ　ｉｎ　ｔｈｅ　Ｒｅａｌ　Ｗｏｒｌｄ）」ＬＲＥＣ−２００２予稿集、２００２年
【非特許文献５】
大野晋、浜西正人、「類語新辞典」角川書店、１９８４年
【非特許文献６】
バーガー　Ａ．Ｌら（Ｂｅｒｇｅｒ　Ａ．Ｌ．　ｅｔ　ａｌ）「自然言語処理への最大エントロピーアプローチ（Ａ　Ｍａｘｉｍｕｍ　Ｅｎｔｒｏｐｙ　Ａｐｐｒｏａｃｈ　ｔｏ　Ｎａｔｕｒａｌ　Ｌａｎｇｕａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ）」計算言語学協会、１９９６年
【非特許文献７】
竹沢寿幸ら「発話単位の分割または接合による言語処理単位への変換手法」自然言語処理　Ｖｏｌ．　６　Ｎｏ．　２，　１９９９年
【非特許文献８】
中嶋秀治ら「音声認識過程での発話分割のための統計的言語モデル」情報処理学会論文誌　Ｖｏｌ．　４２　Ｎｏ．　１１、２００１年
【非特許文献９】
金淵培ら「日英機械翻訳のための日本語長文自動短文分割と主語の補完」情報処理学会論文誌　Ｖｏｌ．　３５　Ｎｏ．　６、１９９４年
【発明が解決しようとする課題】
旅行会話に関する基本文集（前掲の非特許文献４を参照）をテスト文と学習文とに分けて使用し実験を行なった。学習文つまり用例に使用した文数は１５２，１７２、テスト文は１，２５４文である。テスト文の平均文長は６．５語である。対訳辞書には旅行会話用に作成した辞書（前掲の非特許文献３を参照）、類語辞書には角川類語辞書（前掲の非特許文献５）を用いる。翻訳結果に対して日本語のできる英語ネイティブにより４段階の評価を与える（前掲の非特許文献３）。評価レベルを次に示す。
【０００６】
Ａ：問題なし
Ｂ：主要な情報が容易に復元できる
Ｃ：主要な情報がなんとか復元できる
Ｄ：主要な情報が復元できない
また用例検索に失敗し翻訳結果の得られない場合はＦＡＩＬと表記する。用例検索の距離のしきい値は１／３とする。
【０００７】
図１１に実験結果を示す。横軸は文長、縦軸は評価レベル別の文数である。文が長くなると翻訳品質が悪くなることが分かる。文長が１０以上になると特に劣化が大きい。
【０００８】
Ｄ３において翻訳結果が得られないのは、入力文との距離がしきい値未満の類似用例が見つからない場合である。特に入力文が長くなれば類似用例の存在しない可能性が大きくなる。距離と翻訳品質の間には明確な相関関係が存在する（非特許文献１）ため、むやみにしきい値を大きくするのは適当ではない。一方、入力文から部分を切り出せば類似用例が見つかり翻訳が成功する可能性がある。翻訳結果の得られない入力文への対策として、入力文を分割して翻訳することができれば、より多くの翻訳において正しい翻訳結果が得られると思われる。
【０００９】
翻訳の入力文を分割する従来技術の例として、特許文献１が存在する。この文献では、文をカンマ、特定の語などに基づく分割ルールにしたがって分割する。
【００１０】
しかしこの従来技術では、分割ルールが特定の言語に依存して定められるため、言語にあわせて文分割ルールを記述しなければならない。また、この分割ルールにしたがって文を分割した場合、確かに文が短くなるので翻訳ができる可能性は高くなる。しかし、単に文を短くするだけでは、分割した後の各部分が翻訳可能となるとは限らない。
【００１１】
それゆえに本発明の目的は、分割した後の各部分の翻訳可能性が高くなるように文を分割して翻訳する機械翻訳装置、方法、およびそのためのプログラムを提供することである。
【００１２】
本発明の他の目的は、特定の言語に制限されず、分割した後の各部分の翻訳可能性が高くなるように文を分割して翻訳する機械翻訳装置、方法、およびそのためのプログラムを提供することである。
【００１３】
【課題を解決するための手段】
本発明のある局面にかかる機械翻訳方法は、データ処理システムにおける機械翻訳方法であって、入力文中に、入力文の先頭と最後とを含めて複数個のノードを定義するステップと、複数個のノードが定義された入力文を、予め定められた基準にしたがって複数個のノードのいずれかの組合せで１または複数個の部分に分割するステップと、１または複数個の部分の各々の翻訳結果を結合して入力文に対する翻訳結果を生成するステップとを含み、予め定められた基準は、翻訳結果の得られない部分に含まれる単語数が小さい分割方法を優先すること、および翻訳結果の得られない部分に含まれる単語数が同じ複数の分割方法がある場合には、分割数の小さい分割方法を優先すること、という基準を含む。
【００１４】
好ましくは、この機械翻訳方法は、用例ベースの機械翻訳を用いる方法であって、予め定められた基準はさらに、翻訳結果の得られない部分に含まれる単語数が同じ複数の分割方法があり、かつそれらの分割数が同じ場合には、１または複数個の部分の各々と、当該１または複数個の部分の各々の翻訳の基礎となる類似用例との間に定義される距離の合計の小さいものを優先すること、という基準を含む。
【００１５】
さらに好ましくは、分割するステップは、予め定められた基準に適合するように定められる所定のコスト関数を最小とするような、入力文の先頭のノードと入力文の最後のノードとの間でのノードの経路を探索するステップを含む。
【００１６】
所定のコスト関数は、入力文のうち、分割によっても翻訳できない単語数と所定のコスト定数との積と、分割により翻訳可能となった部分の数との和により定義されるものであってもよい。
【００１７】
この方法は、所定のコスト定数を、複数個のノードの数以上となるように予め定義するステップをさらに含んでもよい。
【００１８】
複数個のノードは、入力文の単語の境界において定義されてもよい。
【００１９】
分割するステップは、入力文の先頭のノードと最後のノードとの間で翻訳処理を試みるステップと、先行するステップで試みられた翻訳処理が成功したか否かを判定し、翻訳処理が成功するまで、または隣接するノード間での翻訳処理が失敗したと判定されるまで、翻訳処理の対象の末尾を一ノードずつ前に移動して繰返し翻訳処理を試みるステップと、翻訳処理が成功した、または隣接するノード間での翻訳処理が失敗したと判定されたことに応答して、それぞれ所定の値をコスト関数に加算して更新し、さらに次の翻訳処理の対象の先頭ノードを翻訳処理における対象の末尾のノードの次のノードに進めるステップと、繰返し翻訳処理を試みるステップと加算するステップとを所定の終了条件が成立するまで実行するステップとを含んでもよい。
【００２０】
所定の終了条件が成立するまで実行するステップは、次のノードが最後のノードか否かを判定するステップと、次のノードが最後のノードではないと判定されたことに応答して繰返し翻訳処理を試みるステップと加算するステップとを再び実行するステップと、次のノードが最後のノードと判定されたことに応答して処理を終了するステップとを含んでもよい。
【００２１】
この方法は、さらに、進めるステップで更新されたコスト関数の値が所定のしきい値より大きい場合には、当該分割方法を分割方法の候補から除外するステップを含んでもよい。
【００２２】
本発明の他の局面にかかるコンピュータプログラムは、コンピュータ上で実行されることにより、上に述べたいずれかの方法のすべてのステップをコンピュータが実行するように適合されたコンピュータプログラムコード手段を含む。
【００２３】
本発明の他の局面にかかるコンピュータプログラムは、コンピュータ可読な媒体上に記録されたものであってもよい。
【００２４】
【発明の実施の形態】
―分割翻訳―
入力文を複数の部分に分割する、各々の部分の翻訳結果を連結して入力文全体の翻訳結果とする。分割の判定には次の基準を使う。
▲１▼　翻訳結果の得られない部分の単語数が小さい方が良い。
▲２▼　▲１▼が同じならば、分割数が小さい方が良い。
▲３▼　▲２▼が同じならば、部分＿類似用例間距離の合計が小さい方が良い。
【００２５】
このように分割方法は、分割部分の翻訳可能性に注目し、単語の連接情報や文法的知識は仮定していない。この基準による最良の分割翻訳を如何に見つけ出すかは探索問題となる。
【００２６】
―分割翻訳の例―
分割翻訳の例を示す。この例では入力文は２分割され、各部分の翻訳結果を連結した結果が出力される。
［入力文］
「はい合計百九十五ドルになりますカードでお支払いですね」
［分割結果］
「はい合計百九十五ドルになります／カードでお支払いですね」
［翻訳結果］
“ｉｔ’ｓ　ｏｎｅ　ｈｕｎｄｒｅｄ　ｎｉｎｅｔｙ　ｆｉｖｅ　ｄｏｌｌａｒｓ　ｉｎ　ｔｏｔａｌ，　ｗｉｌｌ　ｙｏｕ　ｂｅ　ｐａｙｉｎｇ　ｗｉｔｈ　ｙｏｕｒ　ｃｒｅｄｉｔ　ｃａｒｄ”
―ハードウェア構成―
以下に述べる本発明の各実施の形態は、コンピュータおよびコンピュータ上で動作するソフトウェアにより実現される。もちろん、以下に述べる機能の一部又は全部を、ソフトウェアでなくハードウェアで実現することも可能である。
【００２７】
図１に、本実施の形態で利用されるコンピュータシステム２０の外観図を、図２にコンピュータシステム２０のブロック図を、それぞれ示す。なおここに示すコンピュータシステム２０はあくまで一例であり、この他にも種々の構成が可能である。
【００２８】
図１を参照して、コンピュータシステム２０は、コンピュータ４０と、いずれもこのコンピュータ４０に接続されたモニタ４２、キーボード４６、およびマウス４８を含む。コンピュータ４０にはさらに、ＣＤ―ＲＯＭ（Ｃｏｍｐａｃｔ　Ｄｉｓｃ　Ｒｅａｄ−Ｏｎｌｙ　Ｍｅｍｏｒｙ）ドライブ５０と、ＦＤ（Ｆｌｅｘｉｂｌｅ　Ｄｉｓｋ）ドライブ５２とが内蔵されている。
【００２９】
図２を参照して、コンピュータシステム２０はさらに、コンピュータ４０に接続されるプリンタ４４を含むが、これは図１には示していない。またコンピュータ４０はさらに、ＣＤ―ＲＯＭドライブ５０およびＦＤドライブ５２に接続されたバス６６と、いずれもバス６６に接続された中央演算装置（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ：ＣＰＵ）５６、コンピュータ４０のブートアッププログラムなどを記憶したＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ　Ｍｅｍｏｒｙ）５８、ＣＰＵ５６が使用する作業エリアおよびＣＰＵ５６により実行されるプログラムの格納エリアを提供するＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）６０、および翻訳のための用例データベース、翻訳結果などを格納するハードディスク５４を含む。
【００３０】
以下に述べる実施の形態のシステムを実現するソフトウェアは、たとえば、ＣＤ―ＲＯＭ６２またはフレキシブルディスク６４のような記録媒体上に記録されて流通し、ＣＤ―ＲＯＭドライブ５０またはＦＤドライブ５２のような読取装置を介してコンピュータ４０に読込まれ、ハードディスク５４に格納される。ＣＰＵ５６がこのプログラムを実行する際には、ハードディスク５４からこのプログラムを読み出してＲＡＭ６０に格納し、図示しないプログラムカウンタによって指定されるアドレスから命令を読出して実行する。ＣＰＵ５６は、処理対象のデータをハードディスク５４から読出し、処理結果を同じくハードディスク５４に格納する。
【００３１】
コンピュータシステム２０の動作自体は周知であるので、ここではその詳細については繰り返さない。
【００３２】
なお、ソフトウェアの流通形態は上記したように記憶媒体に固定された形には限定されない。たとえば、ネットワークを通じて接続された他のコンピュータからデータを受取る形で流通することもあり得る。また、ソフトウェアの一部が予めハードディスク５４中に格納されており、ソフトウェアの残りの部分をネットワーク経由でハードディスク５４に取込んで実行時に統合するような形の流通形態もあり得る。
【００３３】
一般的に、現代のプログラムはコンピュータのオペレーティングシステム（ＯＳ）またはいわゆるサードパーティ等によってコンピュータ上で提供される汎用の機能を利用し、それらを所望の目的にしたがって組織化した形態で実行することにより前記した所望の目的を達成する。したがって、以下に述べる本実施の形態の各機能のうち、ＯＳまたはサードパーティが提供する汎用的な機能を含まず、それら汎用的な機能の実行順序の組合せだけを指定するプログラム（群）であっても、それらを利用して全体的として所望の目的を達成する制御構造を有するプログラム（群）である限り、それらが本発明の技術的範囲に含まれることは明らかである。
【００３４】
ただし、本発明をプログラムではなくハードウェア回路によって実現することも可能であることはもちろんである。
【００３５】
―データ構造―
以下、本実施例のうち、翻訳を行なう機能部分を除き、入力文を分割する機能について詳細に説明する。最初に、文分割処理のためのソフトウェアで使用されるデータの構造について説明する。なお、以下の処理では、前に述べた条件▲１▼、▲２▼の解を探しておいて、残った解を条件▲３▼で比較する、というやり方を採る。以下に示すのは条件▲１▼、▲２▼の探索方法である。
【００３６】
分割条件▲１▼▲２▼を満足する解を探すということは、次のコストが最小の分割を見つけることである。
・コスト＝翻訳もれ単語数×ＢｉｇＮｕｍｂｅｒ＋部分翻訳数
ここで、ＢｉｇＮｕｍｂｅｒは、予め定められた，文長より大きい数のことをいう。通常は１０００程度でよい。文長とは前述のとおり文に含まれる単語数をいう。
【００３７】
図３に、以下の処理で使用するトークンレコードの構造を示す。このトークンレコードは、図４に示すトークン配列の各項目を構成している。図３を参照して、各トークンレコードは、ｎｏｄｅフィールドと、ｃｏｓｔフィールドと、ｐａｔｈ＿ｌｉｓｔフィールドと、ｎｅｘｔフィールドとを含む。
【００３８】
ｎｏｄｅフィールドは、以下に説明するノードの番号（ノード番号）を格納する。たとえば入力文の語長をｎとして、ｎ＋１個のノードを「ノード０、語１、ノード１、語２、ノード２、語３、ノード３、…、語ｎ、ノードｎ」のように定義する。ここではノード０が先頭のノード、ノードｎが最後のノードである。各ノードの番号（０からｎまで）がノード番号である。
【００３９】
ｃｏｓｔフィールドは、ノード０からノードｎｏｄｅに進むまでの距離の合計を示す。ここにノード間の距離を次のように定義する。
・ノード間の単語列の翻訳が成功すればそのノード間は距離１
・隣接するノード間で翻訳が失敗すればそのノード間は距離ＢｉｇＮｕｍｂｅｒｐａｔｈ＿ｌｉｓｔはノード０からノードｎに進むまでの道筋（分割の仕方）を表わす。道筋は複数あり得るので、ｐａｔｈ＿ｌｉｓｔはいわゆるリスト形式として表わす。
【００４０】
ｎｅｘｔフィールドは、次に進む語数を表わす。この語数は、処理の最初には最終語までの語数で初期化されるが、その間での翻訳を試した後、より短い値で更新される。
【００４１】
図４に配列Ｓの構造を示す。配列Ｓは、図３に示したトークンの配列である。インデックスは０、１、…、文長である。インデックスは、各トークンに対応するノードのノード番号と一致する。各トークンのｎｏｄｅフィールドの値は、そのトークンが格納されている項目のインデックスと一致するので、トークンにｎｏｄｅフィールドを設けることは必ずしも必要ではない。しかし、アルゴリズム記述上でｎｏｄｅフィールドを設けると便利なので、このように各トークンにｎｏｄｅフィールドを設けている。
【００４２】
このようにデータを準備するのは、上に述べた▲１▼〜▲３▼の条件を充足する文の分割方法を求めることは、ノード０からノードｎへの最短経路を求める問題に帰着するためである。その解を求めるアルゴリズムは種々考えられるが、そのうちの一つを以下に示す。なお以下の説明では、トークンのフィールドを「トークン名．フィールド名」で表わすことがある。また以下の説明中で「ＮＩＬ」という表現はデータがないことを示す。
【００４３】
―プログラムの制御フロー―
図５に、本実施の形態にかかる文分割処理を実現するプログラムの制御のフローチャートを示す。図５を参照して、最初に初期化を行なう（７０）。具体的には、ある文分割方法を採用するか否かを判定する際に用いられる、その分割方法に伴うコストの大きさのしきい値を表わす変数にＢｉｇＮｕｍｂｅｒ×文長を代入し、Ｓ［０］にトークンの初期値として｛（０，０、｛｛｝｝、文長）｝を代入する。Ｓ［１］〜Ｓ［ｎ］までにはＮＩＬを代入する。
【００４４】
続いて、ｎｅｘｔフィールドの値が０になっていないトークンがあるか否かを判定する（７２）。そうしたトークンが存在していなければ処理を終了する。このとき、Ｓ［文長］にトークンがあればそれが解となり、そのトークンのｐａｔｈ＿ｌｉｓｔフィールドの内容が文分割の仕方を示す。
【００４５】
ｎｅｘｔフィールドの値が０となっているトークンがあれば、ステップ７４で次にどのトークンに処理を進めるかについての処理を行なう。具体的には、配列Ｓからｎｅｘｔ≠０、かつｃｏｓｔ最小、かつｎｏｄｅ最大のトークンを１個取出す。これが次に処理すべきノードに対応するトークンである。このトークンをｔｏｋｅｎ１とする。
【００４６】
続いてステップ７６で、ノードｔｏｋｅｎ１．ｎｏｄｅとノードｔｏｋｅｎ１．ｎｏｄｅ＋ｔｏｋｅｎ１．ｎｅｘｔの間の距離を計算する。図６に、ノード間の距離の計算処理の詳細を示す。ここでは、ノード間の単語列の翻訳を試みる事によりノード間の距離を計算する。
【００４７】
図６を参照して、まずノード間の単語列の翻訳を試みる（９０）。ｔｏｋｅｎ１．ｎｅｘｔが１より大きい場合には（ステップ９２の判定結果がＹＥＳ）、翻訳に成功した場合（ステップ９４の判定結果がＹＥＳ）に両ノード間の距離を１とし（９６）、変数ｎｅｘｔ＿ｃｏｓｔにｔｏｋｅｎ１．ｃｏｓｔに計算した距離（１）を加算した値を代入し、変数ｎｅｘｔ＿ｎｏｄｅにｔｏｋｅｎ１．ｎｏｄｅとｔｏｋｅｎ１．ｎｅｘｔとを加算した値を代入して（１０６）ノード間の距離の計算処理を終わる。翻訳に失敗した場合にはｔｏｋｅｎ１．ｎｅｘｔにｔｏｋｅｎ１．ｎｅｘｔ−１を代入して（９８）ステップ９０に制御を戻す。
【００４８】
再びステップ９２に戻り、ｔｏｋｅｎ１．ｎｅｘｔ＞１でない場合には、ｔｏｋｅｎ１．ｎｅｘｔ＝１となる。なぜなら、ｔｏｋｅｎ１．ｎｅｘｔの値はＢｉｇＮｕｍｂｅｒか１かのいずれだからである。この場合には、翻訳に成功すれば（ステップ１００の判定結果がＹＥＳ）両ノード間の距離を１とし（１０２）、失敗すれば（ステップ１００の判定結果がＮＯ）両ノード間の距離をＢｉｇＮｕｍｂｅｒとする（１０４）。いずれの場合にも、ステップ１０６で変数ｎｅｘｔ＿ｃｏｓｔにｔｏｋｅｎ１．ｃｏｓｔに計算した距離（１またはＢｉｇＮｕｍｂｅｒ）を加算した値を代入し、変数ｎｅｘｔ＿ｎｏｄｅにｔｏｋｅｎ１．ｎｏｄｅとｔｏｋｅｎ１．ｎｅｘｔとを加算した値を代入してノード間の距離の計算処理を終わる。これで図５のステップ７６の処理を終わる。
【００４９】
再び図５を参照して、ステップ７８において、ステップ７６で計算した距離を用いて、元のノードを次のように更新する。すなわち、元のノードＳ［ｔｏｋｅｎ１．ｎｏｄｅ］に（ｔｏｋｅｎ１．ｎｏｄｅ，ｔｏｋｅｎ１．ｃｏｓｔ，ｔｏｋｅｎ１．ｐａｔｈ＿ｌｉｓｔ，ｔｏｋｅｎ１．ｎｅｘｔ−１）なるトークンを代入する。
【００５０】
続いて、ステップ８０で、進んだ先のノードを以下のようにして更新する。詳細を図７に示す。図７を参照して、まずＳ［ｎｅｘｔ＿ｎｏｄｅ］にトークンがあるか否かを確かめ、あればそれをｔｏｋｅｎ２とする（１２０）。
【００５１】
続いてＳ［ｎｅｘｔ＿ｎｏｄｅ］＝ＮＩＬまたはｎｅｘｔ＿ｃｏｓｔ＜ｔｏｋｅｎ２．ｃｏｓｔが成立するか否かを判定する（１２２）。判定結果がＹＥＳの場合には制御はステップ１２４に、ＮＯの場合には制御はステップ１３０に、それぞれ進む。
【００５２】
ステップ１２４では、ｎｅｘｔ＿ｎｏｄｅ＜文長か否かについて判定する。ｎｅｘｔ＿ｎｏｄｅ＜文長であればステップ１２６でさらにｎｅｘｔ＿ｃｏｓｔ＜しきい値か否かを判定し、判定結果がＹＥＳであればステップ１２８でＳ［ｎｅｘｔ＿ｎｏｄｅ］に（ｎｅｘｔ＿ｎｏｄｅ，ｎｅｘｔ＿ｃｏｓｔ，新ｐａｔｈ＿ｌｉｓｔ，文長―ｎｅｘｔ＿ｎｏｄｅ）なるトークンを代入して処理を終了する。ステップ１２６でｎｅｘｔ＿ｃｏｓｔ＜しきい値でないと判定されれば何もせずこの処理を終了する。すなわち、この分割方法は分割候補から除外される。なおここで、新ｐａｔｈ＿ｌｉｓｔとは、ｔｏｋｅｎ１．ｐａｔｈ＿ｌｉｓｔの各道筋の末尾にｔｏｋｅｎ１．ｎｏｄｅからｎｅｘｔ＿ｎｏｄｅへのリンクを加えた道筋のリストである。
【００５３】
一方、ステップ１２４でｎｅｘｔ＿ｎｏｄｅ＜文長が成立しないと判定された場合、ステップ１３４でｎｅｘｔ＿ｎｏｄｅ＝文長か否かについて判定する。この判定結果がＮＯであればここでも何もせず処理を終了する。判定結果がＹＥＳであれば、しきい値を表わす変数にｎｅｘｔ＿ｃｏｓｔの値を代入（１３６）する。さらに、配列Ｓ中のトークンのうち、次の条件を満たす全トークンのｎｅｘｔフィールドを０にする（枝刈り）（１３８）。
・ｃｏｓｔ≧しきい値、または
・（ｎｏｄｅ＋ｎｅｘｔ＜文長、かつ、ｃｏｓｔ≧しきい値―１）
続いてステップ１４０で、Ｓ［ｎｅｘｔ＿ｎｏｄｅ］に（ｎｅｘｔ＿ｎｏｄｅ，ｎｅｘｔ＿ｃｏｓｔ，新ｐａｔｈ＿ｌｉｓｔ，文長―ｎｅｘｔ＿ｎｏｄｅ）なるトークンを代入し処理を終了する。
【００５４】
図７のステップ１２２に戻り、ステップ１２２での判定結果がＮＯの場合には、ステップ１３０でｎｅｘｔ＿ｃｏｓｔがｔｏｋｅｎ２．ｃｏｓｔと等しいか否かを判定する。両者が等しい場合には、Ｓ［ｎｅｘｔ＿ｎｏｄｅ］にｔｏｋｅｎ２のｐａｔｈ＿ｌｉｓｔに新ｐａｔｈ＿ｌｉｓｔを追加したトークンを代入し（ステップ１３２）処理を終了する。両者が異なる場合、すなわちｎｅｘｔ＿ｃｏｓｔ＞ｔｏｋｅｎ２．ｃｏｓｔの場合にはなにもしないで処理を終了する。以上で図５のステップ８０の処理を終了する。
【００５５】
再び図５に戻り、ステップ８０の後、制御はステップ７２に戻る。こうして、ステップ７２からステップ８０の処理を繰返し実行し、ステップ７２での判定結果がＮＯとなった時点で処理を終了する。
【００５６】
以上説明した処理が終了した時点で、Ｓ［文長］にトークンがあればそれが解となり、ノード０からノードｎまでの最短経路問題が解けたことになる。つまり、そのトークンのｐａｔｈ＿ｌｉｓｔフィールドの内容が前述した条件を充足する文分割の仕方のうちで最適な文分割の仕方を示す。
【００５７】
なお、本実施の形態では、ステップ１２６である分割方法を採用するか否かを判定する際に、その分割方法に伴うコストをしきい値と比較する。このしきい値の初期値としてどの程度の大きさの値を設定するかにより、枝刈りの速さが決まる。この値を小さくすれば、ある程度コストの小さい解だけが得られる。
【００５８】
―分割翻訳実験―
平均文長の長いテストデータを用いて分割翻訳実験を行なった。旅行会話に関するバイリンガル模擬会話の言語データベース（非特許文献４を参照）を実験対象として選んだ。テスト文数は３３０であり平均文長は１１．４語である。テスト文を入力とし分割を行わない従来の翻訳、今回提案した分割翻訳をそれぞれ実行し結果を分析した。翻訳結果の品質を図８に示す。
【００５９】
図８では評価レベル毎の文数、Ａ，ＡＢ，ＡＢＣの割合を分割翻訳無／有の場合で示している。分割翻訳無しに比べ有りでは翻訳成功率（ＡＢＣの割合）が１６．４％向上する。ＡＢの割合、Ａの割合もそれぞれ６．１％および１．２％向上する。分割無しで翻訳出力の得られなかった１２７文で見ると翻訳成功率は４２．５％である。
【００６０】
図９は文長別の翻訳成功文数を示すグラフである。分割無しの翻訳で評価レベルＡＢＣとなった文数、分割無しではＦＡＩＬだが分割翻訳によりＡＢＣとなった文数、分割翻訳の結果でもＤまたはＦＡＩＬとなった文数をグラフ中で区別している。分割翻訳によりＡＢＣとなった文が分割翻訳の効果である。特に文長９　以上で効果が見られる。
【００６１】
図１０は分割時距離と翻訳成功率との関係を示す。ここで分割時距離を次の式で定義する。入力文と用例との距離を分割翻訳の場合に一般化している。
分割時距離＝Σ（部分長　×　部分と類似用例との距離）／入力文長
類似用例の得られない部分では類似用例との距離は１とする。分割時距離と翻訳品質との相関は明瞭であり距離が大きくなると品質は悪くなる。
【００６２】
以上のように、本実施の形態では用例ベース翻訳において入力文の分割翻訳方式を提案し、その有効性を確認した。長い文に弱いというＤ３の短所の改善が見られ、全体として翻訳成功率が向上した。
【００６３】
一方で翻訳結果の信頼性の観点からは、悪い訳（評価Ｄ）を出すよりＦＡＩＬとした方が良いとの考え方もある。本実施の形態によれば、分割翻訳用に一般化した距離と品質との間に相関のあることが確認できるので、求められる信頼性に応じて分割翻訳のしきい値を設けるなどの方策が考えられる。
【図面の簡単な説明】
【図１】本発明の一実施の形態を実現するコンピュータシステムの外観を示す図である。
【図２】図１に示すコンピュータシステムのブロック図である。
【図３】トークンレコードの構造を示す図である。
【図４】トークンレコードの配列Ｓの構造を示す図である。
【図５】本発明の一実施の形態を実現するコンピュータプログラムの制御構造を示すフローチャートである。
【図６】ノード間の距離を計算する処理を示すフローチャートである。
【図７】進んだ先のノードの更新処理を示すフローチャートである。
【図８】本発明の一実施の形態にしたがって行なった翻訳実験の結果の品質を表形式で示す図である。
【図９】翻訳実験における文長別の翻訳成功文数を示すグラフである。
【図１０】分割時距離と翻訳成功率との関係を示すグラフである。
【図１１】従来技術による文長と翻訳品質との関係を示すグラフである。
【符号の説明】
２０　コンピュータシステム、４０　コンピュータ、５０　ＣＤ−ＲＯＭドライブ、５２　ＦＤドライブ、６２　ＣＤ−ＲＯＭ，６４　ＦＤ、５６　ＣＰＵ，５８　ＲＯＭ，６０　ＲＯＭ
【図１】
2004110583.tif 000003
【図２】
2004110583.tif 000004
【図３】
2004110583.tif 000005
【図４】
2004110583.tif 000006
【図５】
2004110583.tif 000007
【図６】
2004110583.tif 000008
【図７】
2004110583.tif 000009
【図８】
2004110583.tif 000010
【図９】
2004110583.tif 000011
【図１０】
2004110583.tif 000012
【図１１】
2004110583.tif 000013
【手続補正書】
【提出日】平成14年10月16日(2002.10.16)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００４８
【補正方法】変更
【補正の内容】
【００４８】
再びステップ９２に戻り、ｔｏｋｅｎ１．ｎｅｘｔ＞１でない場合には、ｔｏｋｅｎ１．ｎｅｘｔ＝１となる。この場合には、翻訳に成功すれば（ステップ１００の判定結果がＹＥＳ）両ノード間の距離を１とし（１０２）、失敗すれば（ステップ１００の判定結果がＮＯ）両ノード間の距離をＢｉｇＮｕｍｂｅｒとする（１０４）。いずれの場合にも、ステップ１０６で変数ｎｅｘｔ＿ｃｏｓｔにｔｏｋｅｎ１．ｃｏｓｔに計算した距離（１またはＢｉｇＮｕｍｂｅｒ）を加算した値を代入し、変数ｎｅｘｔ＿ｎｏｄｅにｔｏｋｅｎ１．ｎｏｄｅとｔｏｋｅｎ１．ｎｅｘｔとを加算した値を代入してノード間の距離の計算処理を終わる。これで図５のステップ７６の処理を終わる。