(57)【特許請求の範囲】
【請求項１】
複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置であって、
前記第１文書に含まれる前記複数の文の各単語に基づいて、値を示す終端ノード、各単語に対応する各中間ノード、及び前記文において隣接する単語間に対応する中間ノード間を結ぶエッジを含み、かつ、前記第１文書に含まれる前記複数の文を表わす系列二分決定グラフ（Sequence Binary Decision Diagram）を生成し、前記第２文書に含まれる前記複数の文の各単語に基づいて、前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフを生成するグラフ変換処理手段と、
前記グラフ変換処理手段によって生成され、又は前回更新された前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフと前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフとに基づいて、前記第１文書の文と前記第２文書の文とのペアのうち、編集距離が最小となる文のペアを計算する最小ペア計算手段と、
前記最小ペア計算手段によって計算された文のペアにおける前記第１文書の文を取り除くように、前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフを更新し、前記最小ペア計算手段によって計算された文のペアにおける前記第２文書の文を取り除くように、前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフを更新するグラフ更新手段と、
前記最小ペア計算手段による計算及び前記グラフ更新手段による更新を繰り返し、前記最小ペア計算手段によって繰り返し計算された文のペアの各々を、前記第１文書と前記第２文書との間での文の対応付けとして出力する対応付け出力手段と、
を含む文対応付け決定装置。
【請求項２】
前記最小ペア計算手段は、
前記第１文書に対する前記系列二分決定グラフの各ノードと、前記第２文書に対する前記系列二分決定グラフの各ノードとの各組み合わせに対するスコアを要素として格納するスコア行列、及び前記第１文書に対する前記系列二分決定グラフの各ノードと、前記第２文書に対する前記系列二分決定グラフの各ノードとの各組み合わせに対するスコア計算過程を示す情報を要素として格納するバックトラック行列を初期化する行列初期化手段と、
前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフの終端ノード及び前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフの終端ノードの組み合わせから順に、ノードの各組み合わせについて、前記組み合わせの前記第１文書に対する前記系列二分決定グラフのノードから終端ノードまでが表す系列の各々と、前記組み合わせの前記第２文書に対する前記系列二分決定グラフのノードから終端ノードまでが表す系列の各々とのペアの各々における編集距離のうち、最小の編集距離を、前記組み合わせに対するスコアとして前記スコア行列に格納し、前記最小の編集距離に対応する前記系列のペアを示すバックトラック情報を、前記組み合わせに対するスコア計算過程を示す情報として前記バックトラック行列に格納する行列計算手段と、
前記行列計算手段によって得られた前記バックトラック行列に基づいて、前記編集距離が最小となる文のペアを出力するスコア最小ペア出力手段と、
を含む請求項１記載の文対応付け決定装置。
【請求項３】
複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定方法であって、
グラフ変換処理手段によって、前記第１文書に含まれる前記複数の文の各単語に基づいて、値を示す終端ノード、各単語に対応する各中間ノード、及び前記文において隣接する単語間に対応する中間ノード間を結ぶエッジを含み、かつ、前記第１文書に含まれる前記複数の文を表わす系列二分決定グラフ（Sequence Binary Decision Diagram）を生成し、前記第２文書に含まれる前記複数の文の各単語に基づいて、前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフを生成し、
最小ペア計算手段によって、前記グラフ変換処理手段によって生成され、又は前回更新された前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフと前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフとに基づいて、前記第１文書の文と前記第２文書の文とのペアのうち、編集距離が最小となる文のペアを計算し、
グラフ更新手段によって、前記最小ペア計算手段によって計算された文のペアにおける前記第１文書の文を取り除くように、前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフを更新し、前記最小ペア計算手段によって計算された文のペアにおける前記第２文書の文を取り除くように、前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフを更新し、
対応付け出力手段によって、前記最小ペア計算手段による計算及び前記グラフ更新手段による更新を繰り返し、前記最小ペア計算手段によって繰り返し計算された文のペアの各々を、前記第１文書と前記第２文書との間での文の対応付けとして出力する
文対応付け決定方法。
【請求項４】
前記最小ペア計算手段による計算は、
行列初期化手段によって、前記第１文書に対する前記系列二分決定グラフの各ノードと、前記第２文書に対する前記系列二分決定グラフの各ノードとの各組み合わせに対するスコアを要素として格納するスコア行列、及び前記第１文書に対する前記系列二分決定グラフの各ノードと、前記第２文書に対する前記系列二分決定グラフの各ノードとの各組み合わせに対するスコア計算過程を示す情報を要素として格納するバックトラック行列を初期化し、
行列計算手段によって、前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフの終端ノード及び前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフの終端ノードの組み合わせから順に、ノードの各組み合わせについて、前記組み合わせの前記第１文書に対する前記系列二分決定グラフのノードから終端ノードまでが表す系列の各々と、前記組み合わせの前記第２文書に対する前記系列二分決定グラフのノードから終端ノードまでが表す系列の各々とのペアの各々における編集距離のうち、最小の編集距離を、前記組み合わせに対するスコアとして前記スコア行列に格納し、前記最小の編集距離に対応する前記系列のペアを示すバックトラック情報を、前記組み合わせに対するスコア計算過程を示す情報として前記バックトラック行列に格納し、
スコア最小ペア出力手段によって、前記行列計算手段によって得られた前記バックトラック行列に基づいて、前記編集距離が最小となる文のペアを出力することを含む請求項３記載の文対応付け決定方法。
【請求項５】
コンピュータを、請求項１又は２に記載の文対応付け決定装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文対応付け決定装置、方法、及びプログラムに係り、特に、２つの文書間の文の対応付けを決定する文対応付け決定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
既存の文関係の対応付けを決定する手法として、非特許文献１では、文の長さと文中に出現する単語が翻訳される確率に基づいて文の類似度を定め、スコアが高くなるマッチングを求める方法が示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Robert C. Moore, “Fast and Accurate Sentence Alignment of Bilingual Corpora”, in proceedings of AMTA’02, pp 135-144, 2002.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
既存の文アラインメント手法では、文の類似度として計算が容易なもののみしか用いられてこなかった。例えば文の編集距離は広く用いられる文の類似度の尺度であるが、計算にO(nm)の時間(n, m はそれぞれの文の長さ)がかかり、文の対応付けにかかる時間が膨大となる。そのため、編集距離を用いることでよい文アラインメントを求められる可能性があるにもかかわらず、これまで編集距離は文アラインメントでは利用されてこなかった。
【０００５】
本発明は、上記の事情を鑑みてなされたもので、計算量の増大を抑制して、文の対応付けを精度よく決定するこができる文対応付け決定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の目的を達成するために本発明に係る文対応付け決定装置は、複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置であって、前記第１文書に含まれる前記複数の文の各単語に基づいて、値を示す終端ノード、各単語に対応する各中間ノード、及び前記文において隣接する単語間に対応する中間ノード間を結ぶエッジを含み、かつ、前記第１文書に含まれる前記複数の文を表わす系列二分決定グラフ（Sequence Binary Decision Diagram）を生成し、前記第２文書に含まれる前記複数の文の各単語に基づいて、前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフを生成するグラフ変換処理手段と、前記グラフ変換処理手段によって生成され、又は前回更新された前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフと前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフとに基づいて、前記第１文書の文と前記第２文書の文とのペアのうち、編集距離が最小となる文のペアを計算する最小ペア計算手段と、前記最小ペア計算手段によって計算された文のペアにおける前記第１文書の文を取り除くように、前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフを更新し、前記最小ペア計算手段によって計算された文のペアにおける前記第２文書の文を取り除くように、前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフを更新するグラフ更新手段と、前記最小ペア計算手段による計算及び前記グラフ更新手段による更新を繰り返し、前記最小ペア計算手段によって繰り返し計算された文のペアの各々を、前記第１文書と前記第２文書との間での文の対応付けとして出力する対応付け出力手段と、を含んで構成されている。
【０００７】
本発明に係る文対応付け決定方法は、複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定方法であって、グラフ変換処理手段によって、前記第１文書に含まれる前記複数の文の各単語に基づいて、値を示す終端ノード、各単語に対応する各中間ノード、及び前記文において隣接する単語間に対応する中間ノード間を結ぶエッジを含み、かつ、前記第１文書に含まれる前記複数の文を表わす系列二分決定グラフ（Sequence Binary Decision Diagram）を生成し、前記第２文書に含まれる前記複数の文の各単語に基づいて、前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフを生成し、最小ペア計算手段によって、前記グラフ変換処理手段によって生成され、又は前回更新された前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフと前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフとに基づいて、前記第１文書の文と前記第２文書の文とのペアのうち、編集距離が最小となる文のペアを計算し、グラフ更新手段によって、前記最小ペア計算手段によって計算された文のペアにおける前記第１文書の文を取り除くように、前記第１文書に含まれる前記複数の文を表わす前記系列二分決定グラフを更新し、前記最小ペア計算手段によって計算された文のペアにおける前記第２文書の文を取り除くように、前記第２文書に含まれる前記複数の文を表わす前記系列二分決定グラフを更新し、対応付け出力手段によって、前記最小ペア計算手段による計算及び前記グラフ更新手段による更新を繰り返し、前記最小ペア計算手段によって繰り返し計算された文のペアの各々を、前記第１文書と前記第２文書との間での文の対応付けとして出力する。
【０００８】
本発明に係るプログラムは、コンピュータを、上記の文対応付け決定装置の各手段として機能させるためのプログラムである。
【発明の効果】
【０００９】
以上説明したように、本発明の文対応付け決定装置、方法、及びプログラムによれば、第１文書を表わす系列二分決定グラフ、及び第２文書を表わす系列二分決定グラフを生成し、系列二分決定グラフに基づいて第１文書の文と第２文書の文とのペアのうち編集距離が最小となる文のペアを計算すること、及び編集距離が最小となる文のペアを取り除くように系列二分決定グラフを更新することを繰り返し、繰り返し計算された文のペアの各々を、第１文書と第２文書との間での文の対応付けとして出力することにより、計算量の増大を抑制して、文の対応付けを精度よく決定するこができる、という効果が得られる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態に係る文対応付け決定装置の構成を示す概略図である。
【図２】ＳｅｑＢＤＤの例を示す図である。
【図３】スコア行列及びバックトラック行列の計算方法を説明するための図である。
【図４】スコア行列及びバックトラック行列の計算方法を説明するための図である。
【図５】バックトラック処理の方法を説明するための図である。
【図６】本発明の実施の形態に係る文対応付け決定装置における文対応付け決定処理ルーチンの内容を示すフローチャートである。
【図７】本発明の実施の形態に係る文対応付け決定装置における編集距離スコア最小ペアを計算する処理の内容を示すフローチャートである。
【図８】本発明の実施の形態に係る文対応付け決定装置におけるバックトラック処理の内容を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１２】
＜発明の概要＞
対応付けを行う対象である２つの文集合（それぞれＳL,ＳRとする）をそれぞれ、系列の集合を表わすためのデータ表現方法である系列二分決定グラフ（SeqBDD；Sequence Binary Decision Diagram）を用いて表現し（非特許文献2を参照）、それらのSeqBDD上での動的計画法を利用して、編集距離が最小の文のペアを順にもとめることで文のアラインメントを計算する。素朴に編集距離が最小の文のペアを求めるためには、ＳLとＳRの要素の可能な組合せの数だけ編集距離の計算を行わなければならないが、SeqBDDを用いることで計算回数を削減し、現実的な計算時間で編集距離に基づく文アラインメントを実行できる。
【００１３】
（非特許文献2）：Elsa Loekito, James Bailey, and Jian Pei, “A Binary Decision Diagram Based Approach for Mining Frequent Subsequences”, Knowledge and Information Systems, Volume 24 Issue 2, August 2010, Pages 235-268
【００１４】
＜システム構成＞
本発明の実施の形態に係る文対応付け決定装置１００は、対応する２つの文書が入力され、２つの文書間で文の対応付けを決定する。この文対応付け決定装置１００は、ＣＰＵと、ＲＡＭと、後述する文対応付け決定処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。図１に示すように、文対応付け決定装置１００は、文書ペア入力部１０と、演算部２０と、対応付け結果出力部３０を備えている。
【００１５】
文書ペア入力部１０は、対応付けを行う対象である２つの文書の入力を受け付ける。入力される２つの文書は、翻訳元言語の第１文書と、当該第１文書を翻訳した翻訳先言語の第２文書とである。なお、文書は文の集合とし、それぞれＳL,ＳRとして表現する。また、各文は単語が並んだ系列として表現されるものとする。例えば英語の文“This is a pen”は、単語 “This”,  “is”, “a”, “pen” の４つの単語からなる系列である。日本語の文であっても同様に単語に分けて系列とみなす。なお、以下では単語をa, b, cなどのアルファベットで表現し、文をアルファベットの列として表現する。
【００１６】
演算部２０は、ＳｅｑＢＤＤ変換処理部２１及び対応付け計算部２２を備えている。なお、ＳｅｑＢＤＤ変換処理部２１は、グラフ変換処理手段の一例であり、対応付け計算部２２は、最小ペア計算手段、行列初期化手段、行列計算手段、スコア最小ペア出力手段、及びグラフ更新手段の一例である。
【００１７】
ＳｅｑＢＤＤ変換処理部２１は、文書ペア入力部１０で受け付けた２つの文書の各々について、当該文書を表わす文の集合を、SeqBDDに変換する。SeqBDDとは系列の集合をグラフとして表現するデータ構造であり、本実施の形態では、SeqBDDは、値を示す終端ノード、各単語に対応する各中間ノード、及び文において隣接する単語間に対応する中間ノード間を結ぶエッジを含み、かつ、文書に含まれる文の集合を表わす系列二分決定グラフである。図２はSeqBDDの例である。図２の例では、２つのSeqBDDは系列の集合{abc, cbc}と{cbc, cc}をそれぞれ表している。SeqBDDの丸いノードは中間ノード、四角いノードは終端ノードである。また、各中間ノードを親とする２本のエッジは、実線で描かれたものを1枝、破線で描かれたものを0枝とよぶ。SeqBDDの、Tと書かれたエッジで指された中間ノードから、ラベル１が描かれた終端ノードまでのパスが、集合に含まれる１つの系列に対応する。例えば、図２左のSeqBDDではA→B→C→１というパスと、A⇒C→B→C→１という２つのパスが存在し、それぞれが系列{abc}と系列{cbc}に対応する。集合ＳL,ＳRに対応するSeqBDDをそれぞれＬ，Ｒと表わす。Ｌ［ｉ］，Ｒ［ｊ］をそれぞれのSeqBDDのｉ番目、ｊ番目のノードを表現するために用いる。
【００１８】
対応付け計算部２２は、ＳｅｑＢＤＤ変換処理部２１によって変換された２つのSeqBDDを用いて、以下に説明するように、文の対応付けを計算する。ここで文の対応付けとは、ＳLに含まれる各文が、ＳRのどの文に相当するかを見つけることをいう。
【００１９】
対応付け計算部２２は、２つのSeqBDDから編集距離スコアが最小となる系列のペアを選択する処理と、２つのSeqBDDから、編集距離スコア最小のペアに含まれる系列を取り除く処理とを、ｍｉｎ（ｎ，ｍ）回繰り返し実行する。ただし、入力された２つの文書のうちの一方の文書に含まれる文の数が、ｎであり、他方の文書に含まれる文の数が、ｍである。２つのSeqBDDから編集距離スコア最小のペアに含まれる系列を取り除く処理は、上記の非特許文献2に記載されているSeqBDDに対する演算を利用することで実現することができる。具体的には、一方の文書に対する文の集合を表わすSeqBDDから、編集距離スコア最小のペアの文を除いた文の集合を表わすSeqBDDになるように、中間ノード及びエッジを取り除く処理を行う。また、他方の文書に対する文の集合を表わすSeqBDDから、編集距離スコア最小のペアの文を除いた文の集合を表わすSeqBDDになるように、中間ノード及びエッジを取り除く処理を行う。
【００２０】
編集距離スコア最小の文のペアを求める方法について以下に説明する。編集距離スコア最小の文のペアは、２つのSeqBDD LとRのノード数の積の個数の要素をもつ２つの行列である、バックトラック行列及びスコア行列の各要素の値を、動的計画法によって計算することによって求めることができる。この処理にかかる時間はO(SIZE(L)＊SIZE(R))である。
【００２１】
まず、２つのSeqBDD LとRの各々について、ノードをトポロジカルソートし、下位にくるノードほど先に来るように並べ直す。次に、大きさSIZE(L) 行 SIZE(R) 列の、スコア行列及びバックトラック行列を生成し、スコア行列のすべての値、及びバックトラック行列のすべての値をゼロで初期化する。行列のi, j要素は、SeqBDD Lの i番目のノードと、SeqBDD Rのj番目のノードとのペアに対応している。生成されたバックトラック行列及びスコア行列は、メモリ（図示省略）に格納される。
【００２２】
次に、トポロジカルソートされたSeqBDD Lのすべての要素と、SeqBDD Rのすべての要素との各ペアについて、終端ノードのペアから上位ノードのペアまで順に、スコア行列の当該ペアに対応する要素の値を計算する処理と、バックトラック行列の当該ペアに対応する要素の値を計算する処理とを実行し、スコア行列とバックトラック行列の値を計算していく。スコア行列をV、バックトラック行列を Bとし、そのi, j番目の要素を V[i,j]とすると、V[i,j]の値は、以下の（１）式に従って計算され、更新される。
【００２３】
【数１】
0005959480.tif 000002
【００２４】
ここで del(v)、ins(v)、rewrite(u, v)は、編集距離スコア算出のために用いられるスコア関数であり、それぞれ語vを削除したときのスコア、語vを挿入したときのスコア、語uをvに書き換えた時のスコアを表わす。なお、語の書き換えスコアは、本実施の形態のように、文書ＳLとＳRとが異なる言語だった場合には、語uがvへ翻訳される確率等を利用して設定する。翻訳確率の算出方法については、従来既知の手法を用いればよいため、説明を省略する。L[i].oneは、SeqBDD Lのi番目のノードの１枝が指すノードの番号、L[i].zeroは０枝が指すノードの番号、L[i].vはi番目のノードが対応付けられている単語をそれぞれ表わす。
【００２５】
また、バックトラック行列の要素B[i, j]の値を、上記（１）式のどの値を用いてV[i,j]の値を更新したかに基づいて設定する。上記（１）式では５種類の候補から最大の値をとるものを１つ選択しているが、この５種類の候補のどれを選んだかによって、それぞれL0, R0, L1, R1, Pの５種類の値のいずれかをB[i, j]に設定する。具体的には、上記（１）式で、Ｖ［L[i].zero，ｊ］の値が選択された場合には、Ｌ０の値が設定され、上記（１）式で、Ｖ［ｉ，R[j].zero］の値が選択された場合には、Ｒ０の値が設定される。また、上記（１）式で、Ｖ［L[i].one，ｊ］＋del(L[i].v)の値が選択された場合には、Ｌ１の値が設定され、上記（１）式で、Ｖ［ｉ，R[j].one］＋ins(R[j].v)の値が選択された場合には、Ｒ１の値が設定される。また、また、上記（１）式で、Ｖ［L[i].one， R[j].one］＋rewrite(L[i].v，R[j].v)の値が選択された場合には、Ｐの値が設定される。
【００２６】
計算の例を、図３、４に示す。図３は、i = 1とし、 j = 1 から SIZE(R)まで変化させて、スコア行列の各値及びバックトラック行列の各値を計算したときの計算結果である。なお、このとき、del(u) = ins(v) = 1、rewrite(u, v) = 2 (if u ≠ v)、rewrite(u, u) = 0としている。各中間ノードの下に整数と記号が示されているが、それぞれスコア行列とバックトラック行列の対応する要素の値を表している。まず、「C」のラベルを持っているノードについては、V[0, 1] = V[0, 0] + ins(c) = 0 + 1 = 1としてスコア行列の値を求め、バックトラック行列の値は「R1」としている。同様にして、「B」、「C」のノードについても計算を進めている。図４はすべてのノードのペアについてスコア行列の値及びバックトラック行列の値を計算し終わったときの結果である。上記図４中の右上の値は、２つの系列の集合に含まれる系列のペアの編集距離の最小値を表している。この例では最小値は0となっている。
【００２７】
次に、計算したバックトラック行列の各値を用いてバックトラック処理を行い、編集距離スコアを最小とする系列のペアを取り出し、編集距離スコア最小の文のペアとして、出力する。
【００２８】
ここで、バックトラック処理は、スコアの計算時に作成したバックトラック行列を用いて、編集距離を最小とする系列のペアを復元する処理である。バックトラック処理の例を図５に示す。この例では、B[5, 4]を起点とし、黒い枠で囲んだ順にバックトラックを進めていく。最終的には、編集距離を最小とする系列のペアとして、文X = ‘cbc’、文Y = ‘cbc’が得られる。
【００２９】
そして、対応付け計算部２２は、編集距離スコアを最小とする系列のペアとして繰り返し得られた文のペアを、文書ペア入力部１０で受け付けた２つの文書間における最適な文の対応付けとして決定する。
【００３０】
対応付け結果出力部３０は、文対応付け決定装置１００によって得られた最適な文の対応付けを出力する。
【００３１】
＜文対応付け決定装置の作用＞
次に、本発明の実施の形態に係る文対応付け決定装置１００の作用について説明する。まず、文の対応付けの対象となる２つの文書が、文対応付け決定装置１００に入力されると、文対応付け決定装置１００によって、図６に示す文対応付け決定処理ルーチンが実行される。
【００３２】
まず、ステップＳ０１において、入力された２つの文書を受け付ける。
【００３３】
そして、ステップＳ０２において、上記ステップＳ０１で受け付けた２つの文書の各々について、ＳｅｑＢＤＤを構築する。
【００３４】
次のステップＳ０３では、上記ステップＳ０２で構築された２つの文書の各々のＳｅｑＢＤＤ、又は上記ステップＳ０４で前回更新された２つの文書の各々のＳｅｑＢＤＤに基づいて、編集距離スコア最小の文のペアを計算する。
【００３５】
ステップＳ０４では、上記ステップＳ０３で計算された編集距離スコア最小の文のペアを除いた２つの文書に対応する文の集合を表わすＳｅｑＢＤＤに更新する。
【００３６】
上記ステップＳ０３、ステップＳ０４の処理を、２つの文書の文の数のうち、小さい方の数と同じ回数だけ繰り返す。
【００３７】
そして、ステップＳ０５で、上記ステップＳ０３で繰り返し計算された編集距離スコア最小の文のペアを用いて、２つの文書間の文の対応付けを決定し、対応付け結果出力部３０により出力して、文対応付け決定処理ルーチンを終了する。
【００３８】
上記ステップＳ０３は、図７に示す処理ルーチンによって実現される。
【００３９】
ステップＳ１１において、２つの文書に対応するＳｅｑＢＤＤ  L, Rの各々について、各ノードをトポロジカルソートし、下位にくるノードほど先に来るように並べ直す。次に、ステップＳ１２において、SIZE(L)行、SIZE(R)列の、スコア行列とバックトラック行列を生成し、スコア行列のすべての値をゼロで初期化し、メモリ（図示省略）に格納する。
【００４０】
そして、トポロジカルソートされたＳｅｑＢＤＤ  Lのすべての要素ｉ＝１〜SIZE(L)と、トポロジカルソートされたＳｅｑＢＤＤ  Rのすべての要素ｊ＝１〜SIZE(R)とのペアの各々について、終端ノードのペア（ｉ＝１，ｊ＝１）から、最上位ノードのペア（ｉ＝SIZE(L)，ｊ＝SIZE(R)）までの順に、ステップＳ１３、Ｓ１４を繰り返し実行し、スコア行列とバックトラック行列の値を計算する。
【００４１】
ステップＳ１３では、２つの文書に対応するＳｅｑＢＤＤ  L, Rと、スコア行列と、予め求められた翻訳確率とに基づいて、スコア行列の要素V[i,j]の値を、上記（１）式に従って計算する。ステップＳ１４では、上記ステップＳ１３の計算結果に基づいて、５種類の候補から最小の値をとるものとしてどれを選んだかによって、L0, R0, L1, R1, Pの５種類の値のいずれかを、バックトラック行列の要素B[i, j]の値に設定する。
【００４２】
ステップＳ１５では、上記ステップＳ１４で繰り返し計算されたバックトラック行列に基づいて、起点から順にバックトラックを進めて、編集距離スコアを最小とする系列のペアを得る。そして、ステップＳ１６において、上記ステップＳ１５で得られた編集距離スコアを最小とする系列のペアを、編集距離スコアを最小とする文のペアとして出力し、処理ルーチンを終了する。
【００４３】
上記ステップＳ１５は、図８に示す処理ルーチンによって実現される。
【００４４】
ステップＳ２１において、上記ステップＳ１４で繰り返し計算されたバックトラック行列を入力として受け付け、ステップＳ２２で、変数ｉ，ｊをそれぞれSIZE(L)とSIZE(R)とで初期化し、また、バックトラック行列の要素B[i, j]の値を、Ｃの値に設定する。
【００４５】
そして、ステップＳ２３において、Ｃの値が、５種類の値のうちいずれであるかを判定する。ステップＳ２４で、上記ステップＳ２３での判定結果に応じて、出力する系列X, Yの更新および i, j の更新を行う。具体的には、Ｃの値が、Ｌ０である場合には、ｉの値を、Ｌ［i］．ｚｅｒｏの値に更新する。Ｃの値が、Ｌ１である場合には、Ｘの最後尾に、Ｌ［ｉ］．ｖの値（単語）を追加したものに、Ｘを更新すると共に、ｉの値を、Ｌ［i］．ｏｎｅの値に更新する。Ｃの値が、Ｒ０である場合には、ｊの値を、Ｒ［i］．ｚｅｒｏの値に更新する。Ｃの値が、Ｒ１である場合には、Ｙの最後尾に、Ｒ［ｊ］．ｖの値（単語）を追加したものに、Ｙを更新すると共に、ｊの値を、Ｒ［ｊ］．ｏｎｅの値に更新する。Ｃの値が、Ｐである場合には、Ｘの最後尾に、Ｌ［ｉ］．ｖの値（単語）を追加したものに、Ｘを更新し、Ｙの最後尾に、Ｒ［ｊ］．ｖの値（単語）を追加したものに、Ｙを更新すると共に、ｉの値を、Ｌ［i］．ｏｎｅの値に更新し、ｊの値を、Ｒ［i］．ｚｅｒｏの値に更新する。
【００４６】
そして、ステップＳ２５において、(i, j) = (1, 1)であるか否かを判定し、(i, j)が(1, 1)でない場合には、ステップＳ２６において、バックトラック行列の要素B[i, j]の値を、Ｃの値に設定して、上記ステップＳ２３へ戻る。一方、(i, j) = (1, 1)である場合には、ステップＳ２７において、XとYとを、編集距離スコアが最小となる系列のペアとして出力し、処理ルーチンを終了する。
【００４７】
以上説明したように、本実施の形態に係る文対応付け決定装置によれば、一方の文書を表わすＳｅｑＢＤＤ、及び他方の文書を表わすＳｅｑＢＤＤを生成し、ＳｅｑＢＤＤに基づいて、文のペアのうち編集距離スコアが最小となる系列のペアを計算すること、及び編集距離スコアが最小となる系列のペアを取り除くようにＳｅｑＢＤＤを更新することを繰り返し、繰り返し計算された系列のペアの各々を、２つの文書間での文の対応付けとして出力することにより、計算量の増大を抑制して、文の対応付けを精度よく決定するこができる。また、２つの文書中の文同士の対応付けを行う問題において、計算に時間がかかる編集距離を用いた場合でも高速な対応付けを可能とすることができる。
【００４８】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００４９】
例えば、入力される２つの文書は、翻訳元言語の文書と、当該文書を翻訳した翻訳先言語の文書とである場合を例に説明したが、これに限定されるものではない。同一言語の２つの文書が入力されて、同一言語の２つの文書間の文の対応付けを行うようにしてもよい。
【００５０】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００５１】
１０   文書ペア入力部
２０   演算部
２１   ＳｅｑＢＤＤ変換処理部
２２   対応付け計算部
３０   対応付け結果出力部
１００ 文対応付け決定装置
【図１】
0005959480.tif 000003
【図２】
0005959480.tif 000004
【図３】
0005959480.tif 000005
【図４】
0005959480.tif 000006
【図５】
0005959480.tif 000007
【図６】
0005959480.tif 000008
【図７】
0005959480.tif 000009
【図８】
0005959480.tif 000010