(57)【特許請求の範囲】
【請求項１】
第１言語の文及び第２言語の文について、それぞれの文に含まれる文字列の対応付けを行い翻訳モデルを生成する翻訳モデル生成装置であって、
前記第１言語の文及び前記第２言語の文のそれぞれについて、同一の文字列が前記文の異なる出現位置に存在する部分文字列の集合で、かつ、出現位置が同一の部分文字列の集合のうち最長の部分文字列を複数抽出する文字列抽出手段と、
前記第１言語の文及び前記第２言語の文のそれぞれについて、前記文字列抽出手段により抽出された部分文字列をノードに含み、かつ、親ノードに含まれる部分文字列が子ノードに含まれる部分文字列を包含するように有向グラフを生成する有向グラフ生成手段と、
前記第１言語の部分文字列と前記第２言語の部分文字列との対応付けの候補を特定し、当該候補に対応する第１言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第１言語の有向グラフのノードの階層関係と、当該候補に対応する第２言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第２言語の有向グラフのノードの階層関係との整合がとれていると判定した場合に、前記第１言語の文に対応する有向グラフに含まれるノードと、前記第２言語の文に対応する有向グラフに含まれるノードとの対応付けを行う対応付け手段と、
を備える翻訳モデル生成装置。
【請求項２】
前記文字列抽出手段は、前記第１言語の文及び前記第２言語の文の複数の組み合わせのそれぞれについて、前記第１言語の文及び前記第２言語の文から前記部分文字列を複数抽出し、
前記有効グラフ生成手段は、前記複数の組み合わせのそれぞれについて、前記第１言語の文に対応する有向グラフと前記第２言語の文に対応する有向グラフとを生成する
請求項１に記載の翻訳モデル生成装置。
【請求項３】
前記対応付け手段は、対応付け対象の前記第１言語及び前記第２言語の文に対応する有向グラフに、当該対象外の前記第１言語及び前記第２言語の文から抽出された部分文字列が含まれている場合に、当該部分文字列を、前記階層関係の判定対象として、前記第１言語の部分文字列と前記第２言語の部分文字列との対応付けの候補を特定する包含判定手段を有する
請求項２に記載の翻訳モデル生成装置。
【請求項４】
前記文字列抽出手段は、複数の前記第１言語の文を、当該第１言語の文に含まれない文字である特殊文字で連結するとともに、複数の前記第２言語の文を、当該第２言語の文に含まれない特殊文字で連結し、それぞれの連結された文字列から、同一の文字列が前記文の異なる出現位置に存在する部分文字列の集合で、かつ、出現位置が同一の部分文字列の集合のうち最長の部分文字列を極大部分文字列として抽出し、
前記有向グラフ生成手段は、前記文字列抽出手段により抽出され各言語の文に対応する極大部分文字列をノードに含み、かつ、親ノードに含まれる極大部分文字列が子ノードに含まれる極大部分文字列を包含するように有向グラフを生成する、
請求項１から３のいずれかに記載の翻訳モデル生成装置。
【請求項５】
コンピュータが、第１言語の文及び第２言語の文について、それぞれの文に含まれる文字列の対応付けを行い翻訳モデルを生成する方法であって、
前記第１言語の文及び前記第２言語の文のそれぞれについて、同一の文字列が前記文の異なる出現位置に存在する部分文字列の集合で、かつ、出現位置が同一の部分文字列の集合のうち最長の部分文字列を複数抽出する文字列抽出手順と、
前記第１言語の文及び前記第２言語の文のそれぞれについて、前記文字列抽出手順において抽出された各言語の文に対応する部分文字列をノードに含み、かつ、親ノードに含まれる部分文字列が子ノードに含まれる部分文字列を包含するように有向グラフを生成する有向グラフ生成手順と、
前記第１言語の部分文字列と前記第２言語の部分文字列との対応付けの候補を特定し、当該候補に対応する第１言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第１言語の有向グラフのノードの階層関係と、当該候補に対応する第２言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第２言語の有向グラフのノードの階層関係との整合がとれていると判定した場合に、前記第１言語の文に対応する有向グラフに含まれるノードと、前記第２言語の文に対応する有向グラフに含まれるノードとの対応付けを行う対応付け手順と、
を含む方法。
【請求項６】
第１言語の文及び第２言語の文について、それぞれの文に含まれる文字列の対応付けによる翻訳モデルの生成をコンピュータに実行させるプログラムであって、
前記第１言語の文及び前記第２言語の文のそれぞれについて、同一の文字列が前記文の異なる出現位置に存在する部分文字列の集合で、かつ、出現位置が同一の部分文字列の集合のうち最長の部分文字列を複数抽出する文字列抽出ステップと、
前記第１言語の文及び前記第２言語の文のそれぞれについて、前記文字列抽出ステップにおいて抽出された各言語の文に対応する部分文字列をノードに含み、かつ、親ノードに含まれる部分文字列が子ノードに含まれる部分文字列を包含するように有向グラフを生成する有向グラフ生成ステップと、
前記第１言語の部分文字列と前記第２言語の部分文字列との対応付けの候補を特定し、当該候補に対応する第１言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第１言語の有向グラフのノードの階層関係と、当該候補に対応する第２言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第２言語の有向グラフのノードの階層関係との整合がとれていると判定した場合に、前記第１言語の文に対応する有向グラフに含まれるノードと、前記第２言語の文に対応する有向グラフに含まれるノードとの対応付けを行う対応付けステップと、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、翻訳モデル生成装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、コンピュータを使用した機械翻訳が行われている。機械翻訳では、翻訳を行うための翻訳モデルが予め生成される。具体的には、翻訳モデルは、以下の手順で行われる。まず、第１言語の文章と、当該文章に対応する第２言語の文章とを形態素解析し、単語に分割する。続いて、単語単位で、第１言語の文章と、第２言語の文章とのアライメント（対応付け）を行う。単語単位でアライメントが行われた後、単語単位から、複数の単語から構成されるフレーズ単位に拡張してアライメントを行う。複数の文章それぞれにおいて上述した一連の処理を行うことで、フレーズ同士の対応関係を蓄積し、翻訳モデルが作成される。
【０００３】
ところで、機械翻訳の精度を向上させるために、精度の高い翻訳モデルの作成方法が要請されている。例えば、特許文献１に記載された方法は、フレーズのアライメントを行う際に、単語間の翻訳確率、辞書対応情報、及び構文構造情報に基づいて、フレーズのアライメントの評価が行われている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−１０２７９４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した翻訳モデルの生成方法では、形態素解析によって文章を単語に分割するため、例えば、日本語や中国語といった単語間を区切るための明確な条件がない言語について、適切に単語の分割が行われない場合がある。よって、上述した翻訳モデルの生成方法では、適切な単語の分割が行われないことを起因とした翻訳精度の低下が起こるという問題が発生する。
【０００６】
本発明は、言語に依存せずに翻訳精度を向上させることができる翻訳モデル生成装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
（１）第１言語の文及び第２言語の文について、それぞれの文に含まれる文字列の対応付けを行い翻訳モデルを生成する翻訳モデル生成装置であって、前記第１言語の文及び前記第２言語の文のそれぞれについて、同一の文字列が前記文の異なる出現位置に存在する部分文字列の集合で、かつ、出現位置が同一の部分文字列の集合のうち最長の部分文字列を複数抽出する文字列抽出手段と、前記第１言語の文及び前記第２言語の文のそれぞれについて、前記文字列抽出手段により抽出された部分文字列をノードに含み、かつ、親ノードに含まれる部分文字列が子ノードに含まれる部分文字列を包含するように有向グラフを生成する有向グラフ生成手段と、前記第１言語の部分文字列と前記第２言語の部分文字列との対応付けの候補を特定し、当該候補に対応する第１言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第１言語の有向グラフのノードの階層関係と、当該候補に対応する第２言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第２言語の有向グラフのノードの階層関係との整合がとれていると判定した場合に、前記第１言語の文に対応する有向グラフに含まれるノードと、前記第２言語の文に対応する有向グラフに含まれるノードとの対応付けを行う対応付け手段と、を備える翻訳モデル生成装置。
【０００８】
（２）前記文字列抽出手段は、前記第１言語の文及び前記第２言語の文の複数の組み合わせのそれぞれについて、前記第１言語の文及び前記第２言語の文から前記部分文字列を複数抽出し、前記有効グラフ生成手段は、前記複数の組み合わせのそれぞれについて、前記第１言語の文に対応する有向グラフと前記第２言語の文に対応する有向グラフとを生成する（１）に記載の翻訳モデル生成装置。 
【０００９】
（３）前記対応付け手段は、対応付け対象の前記第１言語及び前記第２言語の文に対応する有向グラフに、当該対象外の前記第１言語及び前記第２言語の文から抽出された部分文字列が含まれている場合に、当該部分文字列を、前記階層関係の判定対象として、前記第１言語の部分文字列と前記第２言語の部分文字列との対応付けの候補を特定する包含判定手段を有する（２）に記載の翻訳モデル生成装置。 
【００１０】
（４）前記文字列抽出手段は、前記組み合わせに含まれる複数の第１言語の文を、当該第１言語の文に含まれない文字である特殊文字で連結するとともに、前記組み合わせに含まれる複数の第２言語の文を、当該第２言語の文に含まれない特殊文字で連結し、それぞれの連結された文字列から、、同一の文字列が前記文の異なる出現位置に存在する部分文字列の集合で、かつ、出現位置が同一の部分文字列の集合のうち最長の部分文字列を極大部分文字列として抽出し、前記有向グラフ生成手段は、前記文字列抽出手段により抽出され各言語の文に対応する極大部分文字列をノードに含み、かつ、親ノードに含まれる極大部分文字列が子ノードに含まれる極大部分文字列を包含するように有向グラフを生成する、（１）から（３）のいずれかに記載の翻訳モデル生成装置。
【００１１】
（５）コンピュータが、第１言語の文及び第２言語の文について、それぞれの文に含まれる文字列の対応付けを行い翻訳モデルを生成する方法であって、前記第１言語の文及び前記第２言語の文のそれぞれについて、同一の文字列が前記文の異なる出現位置に存在する部分文字列の集合で、かつ、出現位置が同一の部分文字列の集合のうち最長の部分文字列を複数抽出する文字列抽出手順と、前記第１言語の文及び前記第２言語の文のそれぞれについて、前記文字列抽出手順において抽出された各言語の文に対応する部分文字列をノードに含み、かつ、親ノードに含まれる部分文字列が子ノードに含まれる部分文字列を包含するように有向グラフを生成する有向グラフ生成手順と、前記第１言語の部分文字列と前記第２言語の部分文字列との対応付けの候補を特定し、当該候補に対応する第１言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第１言語の有向グラフのノードの階層関係と、当該候補に対応する第２言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第２言語の有向グラフのノードの階層関係との整合がとれていると判定した場合に、前記第１言語の文に対応する有向グラフに含まれるノードと、前記第２言語の文に対応する有向グラフに含まれるノードとの対応付けを行う対応付け手順と、を含む方法。
【００１２】
（６）第１言語の文及び第２言語の文について、それぞれの文に含まれる文字列の対応付けによる翻訳モデルの生成をコンピュータに実行させるプログラムであって、前記第１言語の文及び前記第２言語の文のそれぞれについて、同一の文字列が前記文の異なる出現位置に存在する部分文字列の集合で、かつ、出現位置が同一の部分文字列の集合のうち最長の部分文字列を複数抽出する文字列抽出ステップと、前記第１言語の文及び前記第２言語の文のそれぞれについて、前記文字列抽出ステップにおいて抽出された各言語の文に対応する部分文字列をノードに含み、かつ、親ノードに含まれる部分文字列が子ノードに含まれる部分文字列を包含するように有向グラフを生成する有向グラフ生成ステップと、前記第１言語の部分文字列と前記第２言語の部分文字列との対応付けの候補を特定し、当該候補に対応する第１言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第１言語の有向グラフのノードの階層関係と、当該候補に対応する第２言語の有向グラフのノード及び既に対応付けが行われている部分文字列に対応する第２言語の有向グラフのノードの階層関係との整合がとれていると判定した場合に、前記第１言語の文に対応する有向グラフに含まれるノードと、前記第２言語の文に対応する有向グラフに含まれるノードとの対応付けを行う対応付けステップと、をコンピュータに実行させるプログラム。
【発明の効果】
【００１３】
本発明によれば、言語に依存せずに翻訳精度を向上させることができる翻訳モデル生成装置、方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００１４】
【図１】翻訳モデル生成サーバを示す図である。
【図２】接尾辞配列を示す図である。
【図３】接尾辞配列、ＢＷ変換列、最長共通接頭辞配列、及びこれらの配列の添え字を示す図である。
【図４】アライメントの整合性を説明する図（その１）である。
【図５】アライメントの整合性を説明する図（その２）である。
【図６】翻訳モデル生成サーバが実行する翻訳モデル生成処理の流れを示すフローチャートである。
【図７】図６に続くフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について、図を参照しながら説明する。
［翻訳モデル生成サーバ１の概要］
図１は、本実施形態に係る翻訳モデル生成装置としての翻訳モデル生成サーバ１を示す図である。
翻訳モデル生成サーバ１は、第１言語の文と、第１言語の翻訳文としての第２言語の文との入力を受け付ける。続いて、翻訳モデル生成サーバ１は、入力された第１言語の文を解析して部分文字列としての極大部分文字列を抽出するとともに、第２言語の文を解析して部分文字列としての極大部分文字列を抽出する。続いて、翻訳モデル生成サーバ１は、各言語の文において抽出された文字列のアライメント（対応付け）を行うことにより、アライメントされた結果を、第１言語と第２言語との翻訳モデルとして蓄積する。
【００１６】
［翻訳モデル生成サーバ１の構成］
続いて、翻訳モデル生成サーバ１の構成について説明する。
翻訳モデル生成サーバ１は、１又は複数の一般的にコンピュータによって構成される。一般的なコンピュータは、制御部１０と、記憶手段としての記憶部２０と、通信部と、入力部と、表示部と、これらの装置が接続されるバスラインとにより構成されている。制御部１０は、ＣＰＵ等によって構成され、後述の文受付部１１、文字列抽出手段としての文字列抽出部１２、有向グラフ生成手段としてのグラフ生成部１３、並びに集計手段及び対応付け手段としてのアライメント部１４として機能する。記憶部２０は、メモリ（ＲＡＭ、ＲＯＭ）、ハードディスク（ＨＤＤ）及び光ディスク（ＣＤ、ＤＶＤ等）等によって構成される。通信部は、各種有線及び無線ＬＡＮ装置から構成される。表示部は、液晶ディスプレイ、有機ＥＬディスプレイ等の各種ディスプレイにより構成される。入力部は、タッチパネルあるいはキーボード及びポインティング・デバイス（マウス・トラッキングボール等）により構成される。このような一般的なコンピュータにおいて、ＣＰＵは、翻訳モデル生成サーバ１を統括的に制御し、翻訳モデルを生成する処理のためのプログラム等、各種プログラムを適宜読み出して実行することにより、上述したハードウェアと協働し、本発明に係る各種機能を実現している。
【００１７】
文受付部１１は、入力部を介して、第１言語の文と、当該第１言語の対訳文である第２言語の文とを複数受け付ける。ここで、第１言語の文と第２言語の文との複数の組み合わせがｎ個あるとし、これらの組み合わせを、（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ）とする。なお、文受付部１１は、第１言語の文と第２言語の文との組み合わせを複数回受け付けてもよいし、当該組み合わせを一度に複数受け付けてもよい。文受付部１１は、入力部を介して受け付けた第１言語の文と第２言語の文との複数の組み合わせを記憶部２０に記憶させる。
【００１８】
文字列抽出部１２は、記憶部２０に記憶されている、第１言語に対応する複数の文と第２言語に対応する複数の文との組み合わせ（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ）のそれぞれについて、組み合わせに含まれる第１言語の文と、第２言語の文とのそれぞれを解析し、極大部分文字列を抽出する。この極大部分文字列は、互いに包含関係を有している。
【００１９】
具体的には、文字列抽出部１２は、各言語について、複数の文それぞれに出現しない特殊文字を用いて、これら複数の文を連結する。例えば、特殊文字を＄ｘ１，＄ｘ２，＄ｘ３，．．．，＄ｘｎとすると、文字列抽出部１２は、第１言語の複数の文のそれぞれの末尾に、これらの特殊文字を連結し、文字列ｘ１＄ｘ１ｘ２＄ｘ２ｘ３＄ｘ３，．．．ｘｎ＄ｘｎを生成する。なお、特殊文字は、上記のように文ごとに別の記号にすることのほか、１つの記号を用いてもよい。また、この特殊文字は、文を構成する文字と比較した場合に、辞書式順序で最も順序が小さい文字であるものとする。
また、文字列抽出部１２は、特殊文字を＄ｙ１，＄ｙ２，＄ｙ３，．．．，＄ｙｎとし、第２言語の複数の文のそれぞれの末尾に特殊文字を連結し、文字列ｙ１＄ｙ１ｙ２＄ｙ２ｙ３＄ｙ３，．．．ｙｎ＄ｙｎを生成する。このように、特殊文字で複数の文を連結することによって、後述する処理で生成される部分文字列のうち、出現場所が異なる部分文字列の数は、文書長よりも少ないものとなる。
【００２０】
続いて、文字列抽出部１２は、これら生成された文字列について、極大部分文字列を抽出する。文字列抽出部１２は、配列生成部１２１と、極大部分文字列抽出部１２２とから構成される。
【００２１】
以下に、これら生成された文字列の１つであるｘ１＄ｘ１を例とし、文字列抽出部１２による極大部分文字列の抽出について詳述する。ここで例として用いられる文字列ｘ１＄ｘ１は、「ａｂｃｄｅａｂｃａｂ＄」という文字列であるものとする。ここで、特殊文字＄ｘ１は、「＄」である。ここで、特殊文字＄ｘ１は、「＄」である。
【００２２】
配列生成部１２１は、文字列ｘ１＄ｘ１について、図２、図３に示すように、接尾辞配列ＳＡ、Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ変換（以下、ＢＷ変換という）列Ｂ及び最長共通接頭辞配列Ｌを生成する。なお、図３に示される最左列は、接尾辞配列ＳＡ、ＢＷ変換列Ｂ及び最長共通接頭辞配列Ｌの添え字（インデックス）である。
【００２３】
最初に、配列生成部１２１は、文字列ｘ１＄ｘ１を配列Ｔに格納する。この配列Ｔを、Ｔ［１，．．．，ｓ］と表す（ただし、文字列の長さはｓ）。また、この配列のｉ（ただし、１≦ｉ≦ｓ）番目の要素を、Ｔ［ｉ］と表す。
続いて、配列生成部１２１は、Ｓｉ＝Ｔ［ｉ，．．．，ｓ］を、配列Ｔに格納される文字列の接尾辞とする（図２（ａ）参照）。図２に示される配列において、例えばＳ３は、「ｃｄｅａｂｃａｂ＄」となる。続いて、配列生成部１２１は、配列Ｔに含まれる要素のそれぞれに対応する接尾辞（Ｓ１，Ｓ２，．．．Ｓｓ）を辞書式順序の小さい順に並べる（図２（ｂ）参照）。続いて、配列生成部１２１は、接尾辞を辞書式順序の小さい順に並べた場合の順序を添え字とした配列に、接尾辞の添え字を当該順序で格納する。この配列を配列Ｔに格納された文字列の接尾辞配列ＳＡ（Ｓｕｆｆｉｘ  Ａｒｒａｙ）という（図３参照）。
【００２４】
例えば、図２（ａ）に示される接尾辞を辞書式順序で並び替えをおこなった場合、Ｓ６は、図２（ｂ）に示すように３番目となる。よって、このＳＡ３に対応する接尾辞は、Ｓ６「ａｂｃａｂ＄」となる。
【００２５】
続いて、配列生成部１２１は、接尾辞配列ＳＡに格納される要素に対応する接尾辞を参照し、全ての接尾辞について、ＢＷ変換を行う。具体的には、配列生成部１２１は、接尾辞配列ＳＡに格納されている接尾辞の添え字を参照して接尾辞を特定する。配列生成部１２１は、この接尾辞をＢＷ変換することにより、Ｔ［ＳＡ［ｉ］−１］を得る。例えば、ＳＡ３に格納されている接尾辞の添え字は、「６」であることから、このＳ６「ａｂｃａｂ＄」をＢＷ変換することにより、Ｔ［６−１］に対応する文字「ｅ」が得られる。ここで、配列生成部１２１は、ＳＡ［ｉ］＝１の場合、Ｔ［ｓ］を得るものとする。続いて、配列生成部１２１は、このようにして変換された文字列を、図３に示すように接尾辞配列の添え字に関連付けて配列に格納する。この配列を、ＢＷ変換列Ｂという。
【００２６】
配列生成部１２１は、接尾辞配列ＳＡを参照し、先頭に格納されている添え字に対応する接尾辞と、次に格納されている添え字に対応する接尾辞とで、共通の接頭辞の長さを算出する。配列生成部１２１は、共通の接頭辞の長さの算出を、先頭に格納されている添え字から順に、全ての値で行う。
【００２７】
例えば、図３では、ＳＡ３に格納されている接尾辞の添え字は「６」であることから、ＳＡ３に対応する接尾辞は、Ｓ６「ａｂｃａｂ＄」である。他方、ＳＡ４に格納されている接尾辞の添え字は、対応する接尾辞は「１」であることから、ＳＡ４に対応する接尾辞は、Ｓ１「ａｂｃｄｅａｂｃａｂ＄」である。これら２つの接尾辞は、接頭辞「ａｂｃ」で共通するので、配列生成部１２１は、共通の接頭辞の長さを「３」と算出する。極大部分文字列抽出部１２２は、このようにして算出した値を、図３に示すように接尾辞配列の添え字に関連付けて配列に格納させる。この配列を、最長共通接頭辞配列Ｌという。なお、最長共通接頭辞配列Ｌの際に、共通の接尾辞でなおかつ特殊文字「＄」を含まない文字列の長さにすることで、文をまたぐ極大部分文字列を取らないようにしてもよい。
【００２８】
極大部分文字列抽出部１２２は、配列生成部１２１によって生成されたＢＷ変換列Ｂ及び最長共通接頭辞配列Ｌに基づいて極大部分文字列を抽出する。具体的には、極大部分文字列抽出部１２２は、最長共通接頭辞配列Ｌの先頭の添え字（ｉ＝１）から順に参照し、格納されている値が「１」以上の配列要素の添え字を特定する。続いて、極大部分文字列抽出部１２２は、当該添え字に対応する接尾辞配列ＳＡに格納されている接尾辞の添え字を参照して接尾辞を特定し、特定された接尾辞の先頭から、最長共通接頭辞配列Ｌに格納されている値を長さとして、部分文字列（接頭辞）を抽出する。
【００２９】
例えば、図３では、Ｌ２の値が「２」で、１以上の値が格納されているため、極大部分文字列抽出部１２２は、添え字ｉを「２」と特定する。この添え字「２」に対応する接尾辞配列は、ＳＡ２である。このＳＡ２に格納されている接尾辞の添え字は、「９」であることから、極大部分文字列抽出部１２２は、接尾辞Ｓ９「ａｂ＄」を特定する。極大部分文字列抽出部１２２は、特定された接尾辞の先頭から、最長共通接頭辞配列Ｌ２に格納されている値「２」を長さとして、部分文字列「ａｂ」を抽出する。
【００３０】
続いて、極大部分文字列抽出部１２２は、最長共通接頭辞配列Ｌを参照し、先に特定された添え字から１ずつ加算して、先に特定された値よりも小さい値が格納されている添え字を特定する。続いて、極大部分文字列抽出部１２２は、ＢＷ変換列Ｂを参照し、最初に特定された添え字から、次に特定された添え字までの間で、格納されている値が１つでも異なっているか否かを判定する。極大部分文字列抽出部１２２は、格納されている値が１つでも異なっていると判定した場合、抽出された部分文字列（接頭辞）を極大部分文字列とする。すなわち、極大部分文字列は、出現位置が同一の部分文字列の集合のうち、最長の文字列である部分文字列である。
【００３１】
例えば、図３では、極大部分文字列抽出部１２２は、先に特定された添え字「２」から１ずつ加算し、先に特定された値「２」よりも小さい値が格納されている添え字を、「４」と特定する。続いて、極大部分文字列抽出部１２２は、ＢＷ変換列Ｂにおいて、Ｂ２からＢ４の間で、格納されている値が１つでも異なっているか否かを判定する。Ｂ２の値が「ｃ」、Ｂ３の値が「ｅ」、Ｂ４の値が「＄」であることから、極大部分文字列抽出部１２２は、配列Ｂの各添え字に対応する要素の値が異なっていると判定する。そして、極大部分文字列抽出部１２２は、抽出された接頭辞「ａｂ」を極大部分文字列とする。
【００３２】
極大部分文字列抽出部１２２は、上述した極大部分文字列を抽出する処理を終えると、先に特定された添え字に１加算して、先に特定された添え字の次の添え字から、上述の処理を繰り返す。
【００３３】
例えば、図３において、極大部分文字列抽出部１２２は、Ｌ２に対応して接頭辞「ａｂ」を極大部分文字列として抽出した後、先に特定された添え字「２」に１を加算して、添え字を「３」とする。極大部分文字列抽出部１２２は、特定された接尾辞の先頭から、最長共通接頭辞配列Ｌ３に格納されている値「３」を長さとして、文字列「ａｂｃ」を抽出する。続いて、極大部分文字列抽出部１２２は、Ｌ３の値が「３」で、１以上の値が格納されているため、極大部分文字列抽出部１２２は、添え字ｉを「３」と特定する。極大部分文字列抽出部１２２は、この添え字「３」に対応する接尾辞配列ＳＡ３から、接尾辞の添え字として「６」を特定する。続いて、極大部分文字列抽出部１２２は、接尾辞の添え字「６」に対応する接尾辞Ｓ６「ａｂａｂｃ＄」を特定する。極大部分文字列抽出部１２２は、先に特定された添え字「３」から１ずつ加算し、先に特定された値「３」よりも小さい値が格納されている添え字を、「４」と特定する。続いて、極大部分文字列抽出部１２２は、ＢＷ変換列ＢにおけるＢ３とＢ４の間で、格納されている値が異なっていることから、抽出された接頭辞「ａｂｃ」を極大部分文字列とする。
【００３４】
極大部分文字列抽出部１２２は、添え字「３」から「１１」に対しても上記した極大部分文字列を抽出するための一連の処理を行い、極大部分文字列を抽出する。図３では、極大部分文字列抽出部１２２は、最終的に、極大部分文字列を「ａｂ」、「ａｂｃ」、「ｃ」として抽出する。なお、添え字「５」から「７」については、配列Ｂ５からＢ７までの値が共通していることから、接頭辞「ｂ」は、極大部分文字列となり得ない。すなわち、配列Ｂ５からＢ７までの値が共通している場合、この接頭辞の前の文字についても共通であるため、同一の出現位置において「極大」の部分文字列とはならない。ここで、抽出された文字列「ａｂｃ」は、「ａｂ」と「ｃ」とを包含している。なお、同一の出現位置とは、例えば、添え字「３」に対応する接頭辞「ａｂｃａｂ＄」（説明のために下線を付している）中の「ａｂｃ」と、添え字「６」に対応する接頭辞「ｂｃａｂ＄」中の「ｂ」、添え字「７」に対応する接頭辞「ｂｃｄｅａｂｃａｂ＄」中の「ｂｃ」が、出現している位置が同じであるという意味である。
【００３５】
グラフ生成部１３は、文受付部１１により受け付けた第１言語の複数の文と、第２言語の複数の文との組み合わせ（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ）のそれぞれに含まれる第１言語の文と第２言語の文との双方ついて、文字列抽出部１２により抽出された極大部分文字列に基づいて、有向グラフを生成する。具体的には、グラフ生成部１３は、各親ノードと子ノードとの間で、親ノードに含まれる極大部分文字列が子ノードに含まれる極大部分文字列を包含するように有向グラフを生成する。ここで、第１言語の文に対応する有向グラフをＧｘｉ（１≦ｉ≦ｎ）とし、第２言語の文に対応する有向グラフをＧｙｉ（１≦ｉ≦ｎ）とする。
【００３６】
アライメント部１４は、第１言語の文と、第２言語の文との組み合わせ（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ）のそれぞれについて、第１言語の文に対応する有向グラフＧｘｉと、第２言語の文に対応する有向グラフＧｙｉとの対比を行い、有向グラフＧｘｉに含まれる各ノードと、有向グラフＧｙｉに含まれる各ノードとのアライメントを行う。
【００３７】
具体的には、アライメント部１４は、第１言語の文と、第２言語の文との組み合わせ（例えば、（ｘ１，ｙ１））を１つ選択し、選択された組み合わせに対応する有向グラフに基づいて、アライメントを行う。なお、アライメント部１４は、複数の組み合わせ（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ）のそれぞれについて、少なくとも一回選択し、選択された組み合わせに対応する有向グラフに基づいてアライメントを行う。
【００３８】
以下に、選択された組み合わせに着目して、アライメントを行う処理について詳述する。
まず最初に、アライメント部１４は、選択された組み合わせ以外の組み合わせ（例えば、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ））について、アライメントを固定させる。続いて、アライメント部１４は、アライメントが固定されている組み合わせに対応する各有向グラフを参照し、各極大部分文字列間の対応状況について、各極大部分文字列間の対応ごとに集計する。
【００３９】
続いて、アライメント部１４は、集計結果に基づいて、集計値が最も高い極大部分文字列間の対応から順に、選択された組み合わせに対応する有向グラフに、当該極大部分文字列間の対応が含まれているか否かを判定する。アライメント部１４は、当該極大部分文字列間の対応が含まれていると判定した場合に、当該極大部分文字列間の対応を、アライメントの候補とし、選択された組み合わせに対応する有向グラフ（例えば、（Ｇｘ１，Ｇｙ１））を参照する。
【００４０】
続いて、アライメント部１４は、当該有向グラフにおいて、当該アライメントの候補によって極大部分文字列間のアライメントを行った場合に、当該アライメントの候補と、既にアライメントが行われている極大部分文字列間との整合が取れているか判定する。アライメント部１４は、整合が取れていると判定した場合、当該アライメントの候補について極大部分文字列間のアライメントを確定する。これにより、当該アライメントの候補に基づいてのアライメントが完了する。
【００４１】
ここで、本実施形態でいう整合とは、アライメントの候補に対応する第１言語の有向グラフのノード及び既にアライメントが行われている極大部分文字列に対応する第１言語の有向グラフのノードの階層関係と、アライメントの候補に対応する第２言語の有向グラフのノード及び既にアライメントが行われている極大部分文字列に対応する第２言語の有向グラフのノードの階層関係と、の整合が取れていることをいう。以下に、整合性について詳述する。
【００４２】
まず、既に関連付けられている極大部分文字列に対応する第１言語の有向グラフのノードを第１ノードとする。同様に、当該極大部分文字列に対応する第２言語の有向グラフのノードを第２ノードとする。この場合において、新たに関連付けられる候補とされた極大部分文字列に対応する第１言語のノードが、第１ノードに比べて上位（下位）であり、かつ、当該極大部分文字列に対応する第２言語のノードが上位（下位）である場合、整合が取れている状態である。他方、新たに関連付けられる候補とされた極大部分文字列に対応する第１言語のノードが、第１ノードに比べて上位（下位）であり、かつ、当該極大部分文字列に対応する第２言語のノードが下位（上位）である場合、整合が取れていない状態である。
【００４３】
例えば、グラフ生成部１３によって、図４に示すように、有向グラフＧ１と、有向グラフＧ２とが生成され、既に、有向グラフＧ１のノードＮＡ１と、有向グラフＧ２のノードＮＢ２とのアライメントが行われているものとする。
この場合において、アライメント部１４が、アライメントの候補として、有向グラフＧ１のノードＮＡ２と、有向グラフＧ２のノードＮＢ１とのアライメントを選択した場合、当該アライメントの候補と、ノードＮＡ１とノードＮＢ２とのアライメントとの整合が取れていないと判定する。すなわち、アライメントの候補に対応するノードＮＡ２は、既にアライメントが行われているノードＮＡ１の下位のノードである。また、アライメントの候補に対応するノードＮＢ１は、既にアライメントが行われているノードＮＢ２の上位のノードである。このような場合、２つのノードのアライメントの階層関係は矛盾するため、整合が取れていないとされる。
【００４４】
また、グラフ生成部１３によって、図５に示すように、有向グラフＧ１と、有向グラフＧ２とが生成され、既に、有向グラフＧ１のノードＮＡ１と、有向グラフＧ２のノードＮＢ１とのアライメントが行われているものとする。
この場合において、アライメント部１４は、アライメントの候補として、有向グラフＧ１のノードＮＡ２と、有向グラフＧ２のノードＮＢ２とのアライメントを選択した場合、当該アライメントの候補と、ノードＮＡ１とノードＮＢ１とのアライメントとの整合が取れていると判定する。すなわち、アライメントの候補に対応するノードＮＡ２は、既にアライメントが行われているノードＮＡ１の下位のノードである。同様に、アライメントの候補に対応するノードＮＢ２も、既にアライメントが行われているノードＮＢ１の下位のノードである。このような場合、２つのノードのアライメントの階層関係は矛盾しないため、整合が取れているとされる。
【００４５】
このように、アライメント部１４は、集計結果に含まれている極大部分文字列間の対応全てについて、集計値が最も高い極大部分文字列間の対応から順に、選択された組み合わせに含まれているか否か、及び整合が取れているか否かを判定し、選択された組み合わせに対応する極大部分文字列同士のアライメントを行う。
【００４６】
［動作］
次に、図６及び図７を参照して、翻訳モデル生成サーバ１の動作を説明する。
図６及び図７は、翻訳モデル生成サーバ１が実行する翻訳モデル生成処理の流れを示すフローチャートである。
【００４７】
文受付部１１は、入力部を介して、第１言語の文と、第２言語の文とを複数受け付ける（ステップＳ１）。ここで、第１言語の文と第２言語の文との複数の組み合わせがｎ個あるとし、これらの組み合わせを、（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ）とする。
【００４８】
文字列抽出部１２は、第１言語に対応する複数の文ｘ１，ｘ２，ｘ３，．．．，ｘｎについて、特殊文字を用いて複数の文を連結する。同様に、文字列抽出部１２は、第２言語に対応する複数の文ｙ１，ｙ２，ｙ３，．．．，ｙｎについて、特殊文字を用いて複数の文を連結する（ステップＳ２）。
【００４９】
文字列抽出部１２は、ステップＳ２において連結された文字列について、極大部分文字列を抽出する（ステップＳ３）。
【００５０】
グラフ生成部１３は、ステップＳ１において受け付けた第１言語の複数の文ｘ１，ｘ２，ｘ３，．．．，ｘｎと、第２言語の複数の文ｙ１，ｙ２，ｙ３，．．．，ｙｎとのそれぞれについて、ステップＳ３において抽出された極大部分文字列に基づいて、有向グラフを生成する（ステップＳ４）。グラフ生成部１３は、各親ノードと子ノードとの間で、親ノードの文字列が子ノードの文字列を包含するように有向グラフを生成する。
【００５１】
アライメント部１４は、第１言語の文と、第２言語の文との組み合わせ（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ）から、一の組み合わせを選択する（ステップＳ５）。ステップＳ５において、アライメント部１４は、第１言語の文と、第２言語の文との組み合わせのうち、一度も選択されていない組み合わせのいずれかを選択する。
【００５２】
アライメント部１４は、ステップＳ５において選択された組み合わせ以外の組み合わせについてアライメントを固定する（ステップＳ６）。
アライメント部１４は、アライメントを固定した組み合わせの有向グラフを参照して、各極大部分文字列間の対応状況について、各極大部分文字列の対応ごとに集計する（ステップＳ７）。
図７に移り、アライメント部１４は、ステップＳ７における集計結果を参照し、集計値が最も高い極大部分文字列間の対応から順に、アライメントの候補を選択する（ステップＳ８）。ここで、アライメント部１４は、アライメントの候補を選択する場合、まだ選択されていない対応からアライメントの候補を選択する。
【００５３】
アライメント部１４は、ステップＳ５において選択された組み合わせに対応する有向グラフに、ステップＳ８において選択されたアライメントの候補が含まれているか否かを判定する（ステップＳ９）。アライメント部１４は、この判定がＹＥＳの場合、ステップＳ１０に処理を移し、この判定がＮＯの場合、ステップＳ１２に処理を移す。
【００５４】
アライメント部１４は、ステップＳ８において選択されたアライメントの候補を用いて、選択された組み合わせの有向グラフにてアライメントを行った場合に、当該アライメントと、既にアライメントされている極大部分文字列との整合が取れているか否かを判定する（ステップＳ１０）。アライメント部１４は、この判定がＹＥＳの場合、ステップＳ１１に処理を移し、この判定がＮＯの場合、ステップＳ１２に処理を移す。
【００５５】
アライメント部１４は、ステップＳ１０において整合が取れていると判定した場合、選択された組み合わせの有向グラフにて、当該極大部分文字列間のアライメントを確定させる（ステップＳ１１）。
【００５６】
アライメント部１４は、アライメントの候補を全て選択したか否かを判定する（ステップＳ１２）。アライメント部１４は、この判定がＹＥＳの場合、ステップＳ１３に処理を移し、この判定がＮＯの場合、ステップＳ８に処理を移す。
【００５７】
アライメント部１４は、第１言語の文と、第２言語の文との組み合わせ（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、・・・（ｘｎ，ｙｎ）の全てについてアライメントが行われたか否かを判定する（ステップＳ１３）。アライメント部１４は、この判定がＹＥＳの場合、本フローチャートの処理を終了する。アライメント部１４は、この判定がＮＯの場合、図６のステップＳ５に処理を移す。
【００５８】
以上のように、本実施形態に係る翻訳モデル生成サーバ１は、文字列抽出部１２により、第１言語の文と第２言語の文との複数の組み合わせに含まれる第１言語の文と第２言語の文とから、互いに包含関係を有する部分文字列を複数抽出し、グラフ生成部１３により、複数の組み合わせのそれぞれに含まれる第１言語の文と第２言語の文との双方について、文字列抽出部１２により抽出され各言語の文に対応する部分文字列をノードに含み、かつ、親ノードに含まれる部分文字列が子ノードに含まれる部分文字列を包含するように有向グラフを生成し、アライメント部１４により、文字列抽出部１２により抽出された第１言語の部分文字列と、第２言語の部分文字列との対応状況について集計し、集計結果に基づいて、生成された有向グラフに含まれる各ノード間のアライメントを行う。
【００５９】
このように、翻訳モデル生成サーバ１は、互いに包含関係を有する部分文字列によって、アライメントを行うので、単語の区切りがはっきりしない言語についても、形態素解析を行うことなく、第１言語の文に含まれる文字列と、第２言語の文に含まれる文字列とのアライメントを行うができる。つまり、言語によっては形態素解析を行うことによる区切りミスで翻訳精度が低下することもあるが、翻訳モデル生成サーバ１では、翻訳精度の低下が見込まれる言語であっても、高精度の翻訳モデルを生成することが可能である。
【００６０】
また、翻訳モデル生成サーバ１によって生成される翻訳モデルは、有向グラフに基づいて生成される。このため、この翻訳モデルを用いて未知の文を翻訳する場合において、各言語の文に含まれるフレーズが翻訳モデルに含まれているときには、フレーズから翻訳を行うことができる。このように、翻訳モデル生成サーバ１は、各言語の文に含まれる単語から順に翻訳を行う場合に比べて、迅速に翻訳を行うことができる翻訳モデルを生成することができる。
【００６１】
また、翻訳モデル生成サーバ１は、アライメント部１４により、集計結果において相対的に集計値の多い対応状況から順に、当該対応状況に基づいて、第１言語の部分文字列と、第２言語の部分文字列とのアライメントを行う。
【００６２】
このようにすることで、翻訳モデル生成サーバ１は、統計上、よく対応する部分文字列間から優先的にアライメントを行うことができる。
【００６３】
また、翻訳モデル生成サーバ１は、アライメント部１４により、集計結果において相対的に集計値の多い対応状況から順に、当該対応状況に基づいて第１言語の部分文字列と第２言語の部分文字列とのアライメントの候補を決定し、当該候補に対応する第１言語の有向グラフのノード及び既にアライメントが行われている部分文字列に対応する第１言語の有向グラフのノードの階層関係と、当該候補に対応する第２言語の有向グラフのノード及び既にアライメントが行われている部分文字列に対応する第２言語の有向グラフのノードの階層関係との整合がとれていると判定した場合に、候補についてアライメントを確定させる。
【００６４】
このようにすることで、翻訳モデル生成サーバ１は、文字列の含有関係を壊すことなくアライメントを行うことができ、各部分文字列間のアライメントの精度を向上させることができる。
【００６５】
また、翻訳モデル生成サーバ１は、アライメント部１４により、文字列抽出手段は、組み合わせに含まれる複数の第１言語の文を、当該第１言語の文に含まれない文字である特殊文字で連結するとともに、組み合わせに含まれる複数の第２言語の文を、当該第２言語の文に含まれない特殊文字で連結し、それぞれの連結された文字列から、出現位置が同一の部分文字列の集合のうち、最長の文字列である極大部分文字列を抽出し、グラフ生成部１３により、文字列抽出手段により抽出され各言語の文に対応する極大部分文字列をノードに含み、かつ、親ノードに含まれる極大部分文字列が子ノードに含まれる極大部分文字列を包含するように有向グラフを生成する。
【００６６】
ここで、出現場所が異なる部分文字列の数は、文書長よりも少ないことから、翻訳モデル生成サーバ１は、全ての部分文字列を抽出する場合に比べて、多大なメモリを要することなく極大部分文字列を抽出することができる。
【００６７】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【００６８】
例えば、本実施形態では、文字列抽出部１２は、接尾辞配列ＳＡ、ＢＷ変換列Ｂ及び最長共通接頭辞配列Ｌを用いて極大部分文字列を抽出することとしたが、これに限らない。例えば、文字列抽出部１２は、順序付き木構造を有するＴｒｉｅ木により、全ての接尾辞から構成された接尾辞木を構築し、当該接尾辞木から極大部分文字列を抽出するようにしてもよい。また、文字列抽出部１２は、接尾辞配列ＳＡから直接極大部分文字列を抽出するようにしてもよい。
【００６９】
また、本実施形態では、アライメント部１４は、第１言語の文と第２言語の文との複数の組み合わせから１つの組み合わせを選択するとともに、選択された組み合わせ以外の組み合わせについてアライメントを固定させ、当該選択された組み合わせのアライメントを行うようにしたが、これに限らない。
【００７０】
例えば、アライメント部１４は、第１言語の文と第２言語の文との組み合わせを選択する場合において、一度に複数の組み合わせを選択するようにしてもよい。この場合において、アライメント部１４は、選択された組み合わせ以外の組み合わせについてアライメントを固定させて対応状況の集計を取り、この集計結果に基づいて、選択された複数の組み合わせのアライメントを行うようにしてもよい。
【００７１】
また、アライメント部１４は、第１言語の文と第２言語の文との組み合わせを選択する場合において、第１の組み合わせとして１つの組み合わせを選択するとともに、第２の組み合わせとして他の１つの組み合わせを選択するようにしてもよい。この場合において、アライメント部１４は、第２の組み合わせにおける極大部分文字列間の対応状況に基づいて第１の組み合わせのアライメントを行うようにしてもよい。
【００７２】
また、アライメント部１４は、第１言語の文と第２言語の文との組み合わせを選択する場合、全ての組み合わせをについて対応状況の集計を取り、この集計結果に基づいて、全ての組み合わせそれぞれのアライメントを行うようにしてもよい。
【００７３】
また、本実施形態では、翻訳モデル生成サーバ１は、１つのサーバとして実現される場合を例に挙げて説明したが、翻訳モデル生成サーバ１の機能を複数のサーバに分散して実装し、これらのサーバ全体が連携することによって翻訳モデル生成サーバ１の機能を実現することも可能である。
【符号の説明】
【００７４】
１  翻訳モデル生成サーバ
１０  制御部
１１  文受付部
１２  文字列抽出部
１２１  配列生成部
１２２  極大部分文字列抽出部
１３  グラフ生成部
１４  アライメント部
２０  記憶部
【図１】
0005600700.tif 000002
【図２】
0005600700.tif 000003
【図３】
0005600700.tif 000004
【図４】
0005600700.tif 000005
【図５】
0005600700.tif 000006
【図６】
0005600700.tif 000007
【図７】
0005600700.tif 000008