(57)【要約】【課題】文の対応付けが交叉している場合であっても、文の対応付けを精度よく決定するこができるようにする。【解決手段】部分文書ペアスコア計算処理部２１によって、２つの文書の部分文書の全てのペアの各々について、部分文書間の文の対応付けを、対応付けスコアを最適化するように決定する。文対応付け計算部２２によって、整数線形計画問題を解くことによって、対応付けられる部分文書のペアを決定し、対応付けられた部分文書のペアの各々について決定した文の対応付けを、２つの文書間での文の対応付けとして決定する。【選択図】図１
2014154102.tif 000002
【特許請求の範囲】
【請求項１】
複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置であって、
前記第１文書のうちの連続する１つ以上の文からなる第１部分文書を各々作成すると共に、前記第２文書のうちの連続する１つ以上の文からなる第２部分文書を各々作成し、前記第１部分文書と前記第２部分文書との全てのペアの各々について、前記ペアの前記第１部分文書と前記第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように前記ペアの文の対応付けを決定する部分文書ペアスコア計算手段と、
前記部分文書ペアスコア計算手段によって最適化するように計算された前記ペアの各々の対応付けスコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算された前記対応付けスコアの総和が最大となるように、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、対応付けられた前記第１部分文書と前記第２部分文書とのペアの各々について前記決定した文の対応付けを、前記第１文書と前記第２文書との間での文の対応付けとして決定する文対応付け決定手段と、
を含む文対応付け決定装置。
【請求項２】
前記文対応付け決定手段は、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算された前記対応付けスコアから所定値を減算した値の総和が最大となるように、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定する請求項１記載の文対応付け決定装置。
【請求項３】
前記文対応付け決定手段は、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算された前記対応付けスコアの総和が最大となるように、線形計画問題を解くことによって、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定する請求項１又は２記載の文対応付け決定装置。
【請求項４】
複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置における文対応付け決定方法であって、
部分文書ペアスコア計算手段によって、前記第１文書のうちの連続する１つ以上の文からなる第１部分文書を各々作成すると共に、前記第２文書のうちの連続する１つ以上の文からなる第２部分文書を各々作成し、前記第１部分文書と前記第２部分文書との全てのペアの各々について、前記ペアの前記第１部分文書と前記第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように前記ペアの文の対応付けを決定し、
文対応付け決定手段によって、前記部分文書ペアスコア計算手段によって最適化するように計算された前記ペアの各々の対応付けスコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算された前記対応付けスコアの総和が最大となるように、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、対応付けられた前記第１部分文書と前記第２部分文書とのペアの各々について前記決定した文の対応付けを、前記第１文書と前記第２文書との間での文の対応付けとして決定する
文対応付け決定方法。
【請求項５】
前記文対応付け決定手段によって、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定することは、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算された前記対応付けスコアから所定値を減算した値の総和が最大となるように、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定する請求項４記載の文対応付け決定方法。
【請求項６】
前記文対応付け決定手段によって、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定することは、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算された前記対応付けスコアの総和が最大となるように、線形計画問題を解くことによって、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定する請求項４又は５記載の文対応付け決定方法。
【請求項７】
コンピュータを、請求項１〜請求項３の何れか１項記載の文対応付け決定装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文対応付け決定装置、方法、及びプログラムに係り、特に、２つの文書間の文の対応付けを決定する文対応付け決定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
既存の文関係の対応付けを決定する手法として、非特許文献１では系列のＤＰマッチングに基づく方法が示されている。ＤＰマッチングは、二つの系列が与えられたときにその系列の要素間の対応関係を動的計画法によって高速に求めるための方法である。また、文の対応付けでは利用されていないが、類似の問題である単語同士の対応付けを求める問題は離散最適化の問題の一種である割当問題として定式化して解くことができ、文同士の対応付け問題も同様に解くことができる（非特許文献２）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Robert C. Moore, “Fast and Accurate Sentence Alignment of Bilingual Corpora”, in proceedings of AMTA’02, pp 135-144, 2002.
【非特許文献２】Evgenv Matusov, Richard Zens, and Hermann Ney, “Symmetric Word Alignments for Statistical Machine Translation” In Proceedings of the 20th international conference on Computational Linguistics, page 219. Association for Computational Linguistics.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
既存のＤＰマッチングによる方法では，可能な文間の対応付けにおいて順序の反転を許さないという制約がある。すなわち、いま、2つの文書をＦ，Ｅとし、それぞれがｍ個の文ｆ１，ｆ２，．．．，ｆｍとｎ個の文ｅ１，ｅ２，．．．，ｅｎからなるとする。文の対応付けを求める問題は、これらの文における、スコアを最大にする対応付けの集合Ａ＝｛（ｆρ（１），ｅη（１）），（ｆρ（２），ｅη（２）），．．．，（ｆρ（Ｇ），ｅη（Ｇ））｝を見つけることに対応する。ここでＧは対応付けの個数を表し、Ｇ≦ｍ、ｎである。また、ρ（ｉ）はｉ番目の対応付けにおけるｆの添字、η（ｉ）はｅの添字をそれぞれ表す。ＤＰマッチングを用いる方法には、交叉を許す対応付けを見つけることができないという問題がある。ここで、対応付けが交叉するとは、Ａにおいて（ｆｉ，ｅｊ）という対応付けがなされている場合に、ｉ’＜ｉかつｊ’＞ｊであるような対応付け（ｆｉ’，ｅｊ’）もＡに含まれていることを指す。この制約は、ＥがＦの対訳であるような場合には妥当であることが多いが、例えば文書中の段落の順番が入れ替わっているような場合には、正しい対応付けを得られない可能性が高い。
【０００５】
割当問題として文の対応付けを行った場合にはこのような問題は発生しないが、一方で文書内での前後のつながりを考慮せずに対応を行うことになるため、よい対応付けを得ることができないという問題がある．
【０００６】
本発明は、上記の事情を鑑みてなされたもので、文の対応付けが交叉している場合であっても、文の対応付けを精度よく決定するこができる文対応付け決定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記の目的を達成するために本発明に係る文対応付け決定装置は、複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置であって、前記第１文書のうちの連続する１つ以上の文からなる第１部分文書を各々作成すると共に、前記第２文書のうちの連続する１つ以上の文からなる第２部分文書を各々作成し、前記第１部分文書と前記第２部分文書との全てのペアの各々について、前記ペアの前記第１部分文書と前記第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように前記ペアの文の対応付けを決定する部分文書ペアスコア計算手段と、前記部分文書ペアスコア計算手段によって最適化するように計算された前記ペアの各々の対応付けスコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算された前記対応付けスコアの総和が最大となるように、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、対応付けられた前記第１部分文書と前記第２部分文書とのペアの各々について前記決定した文の対応付けを、前記第１文書と前記第２文書との間での文の対応付けとして決定する文対応付け決定手段と、含んで構成されている。
【０００８】
本発明に係る文対応付け決定方法は、複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置における文対応付け決定方法であって、部分文書ペアスコア計算手段によって、前記第１文書のうちの連続する１つ以上の文からなる第１部分文書を各々作成すると共に、前記第２文書のうちの連続する１つ以上の文からなる第２部分文書を各々作成し、前記第１部分文書と前記第２部分文書との全てのペアの各々について、前記ペアの前記第１部分文書と前記第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように前記ペアの文の対応付けを決定し、文対応付け決定手段によって、前記部分文書ペアスコア計算手段によって最適化するように計算された前記ペアの各々の対応付けスコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算された前記対応付けスコアの総和が最大となるように、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、対応付けられた前記第１部分文書と前記第２部分文書とのペアの各々について前記決定した文の対応付けを、前記第１文書と前記第２文書との間での文の対応付けとして決定する。
【０００９】
本発明に係るプログラムは、コンピュータを、上記の文対応付け決定装置の各手段として機能させるためのプログラムである。
【発明の効果】
【００１０】
以上説明したように、本発明の文対応付け決定装置、方法、及びプログラムによれば、
部分文書のペアの各々について、部分文書間で対応付けスコアを最適化するように文の対応付けを決定し、対応付けられるペアの部分文書が、他のペアの部分文書と重複せず、かつ、対応付けられる部分文書のペアの最適な対応付けスコアの総和が最大となるように、対応付けられる部分文書のペアを決定し、対応付けられた部分文書のペアについて決定された文の対応付けを、文書間の文の対応付けとして決定することにより、文の対応付けが交叉している場合であっても、文の対応付けを精度よく決定することができる、という効果が得られる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態に係る文対応付け決定装置の構成を示す概略図である。
【図２】本発明の実施の形態に係る文対応付け決定装置における文対応付け決定処理ルーチンの内容を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１３】
＜システム構成＞
本発明の実施の形態に係る文対応付け決定装置１００は、対応する２つの文書が入力され、２つの文書間で文の対応付けを決定する。この文対応付け決定装置１００は、ＣＰＵと、ＲＡＭと、後述する文対応付け決定処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。図１に示すように、文対応付け決定装置１００は、文書入力部１０と、演算部２０と、対応付け結果出力部３０を備えている。
【００１４】
文書入力部１０は、対応付けを行う対象である２つの文書の入力を受け付ける。入力される２つの文書は、翻訳元言語の文書と、当該文書を翻訳した翻訳先言語の文書とである。
【００１５】
演算部２０は、部分文書ペアスコア計算処理部２１及び対応付け計算部２２を備えている。
【００１６】
部分文書ペアスコア計算処理部２１は、文書入力部１０で受け付けた２つの文書について、それぞれに含まれる、すべての連続する１文以上のまとまり（部分文書とよぶ）を全て作成し、部分文書同士のすべてのペアについて、以下のように、スコアを計算する。
【００１７】
ここで、２つの文書をＦ、Ｅとし、それぞれがｍ個の文ｆ１，ｆ２，．．．，ｆｍとｎ個の文ｅ１，ｅ２，．．．，ｅｎからなるとする。なお、以下ではｆｉ,ｊで、Ｆのｉ番目の文からｊ番目の文からなる文の集まり（部分文書）を表すとする。Ｅについても同様に表現する。
【００１８】
部分文書のペアとは、２つの文の集まりｆｉ，ｊとｅｋ，ｌのペアのこととする。ｆｉ，ｊが（ｎ＋１）ｎ／２通り、ｅｋ，ｌが（ｍ＋１）ｍ／２通りあることから、可能なペアの総数は、（ｎ＋１）（ｍ＋１）ｎｍ／４通りである。
【００１９】
部分文書のペアのスコアは、その部分文書同士で、上記の手法でＤＰマッチングを行うことによって計算する。ＤＰマッチングでは文同士のペアに対するスコアｓｃｏｒｅ（ｆｉ，ｅｊ）をもとにして、部分文書間のＤＰマッチングによる最適なスコアを計算する。ｓｃｏｒｅ（ｆｉ，ｅｊ）としては、たとえば、非特許文献１に記載されているものを利用することができ、以下の（１）式で表わされる。
【００２０】
【数１】
2014154102.tif 000003
【００２１】
また、ＤＰマッチングによって、以下の（２）式に従って、ｆｉ，ｊとｅｋ，ｌのペアについての最適なスコアｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）を計算するとともに、部分文書内での最適な文同士の対応付けを得ることができる。計算された最適なスコアｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）をメモリ（図示省略）に記憶しておく。なお、スコアｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）が、対応付けスコアの一例である。部分文集合fi，jとek，lのマッチングスコアｓｃｏｒｅ（ｆｉｊ，ｅｋ，ｌ）は、以下の（２）式のような再帰式で求めることができる．
【００２２】
【数２】
2014154102.tif 000004
【００２３】
ここで、score(fj)、score(el)はそれぞれの文が対応づけられなかったときのスコアを表す。ｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）はDPマッチングを用いて効率的に求めることができる。すなわち、
【００２４】
【数３】
2014154102.tif 000005
【００２５】
として順番に解を求めていくことで、以前に計算した結果を再利用してスコアを求めることができる。
【００２６】
対応付け計算部２２は、部分文書ペアスコア計算処理部２１で計算した全てのペアのスコアを用いて、スコアを最大とする部分文書の対応付けを計算する。整数線形計画問題処理装置１５０は、文対応付け決定装置１００の外部にある、整数線形計画問題を解くための装置であり、対応付け計算部２２から呼び出されて使われる。整数線形計画問題処理装置１５０として、市販の任意の整数線形計画法のソルバーを利用できる。
【００２７】
以下に、対応付け計算部２２による最適マッチング計算について説明する。この計算は、整数線形計画問題処理装置１５０において、以下の最適化問題を解くことによって行われる。
【００２８】
【数４】
2014154102.tif 000006
【００２９】
ただし、ｗijklは、対応付けが行われた文の集まりのペア（ｆi,j，ｅk,l）を表すバイナリ変数，ｆi,j，ｅk,lは文それぞれの集まりを表すバイナリ変数である．最終的に得られた対応付けにおいて文の集まりのペア（ｆi,j，ｅk,l）が含まれているときにｗijklは1をとり、そうでないときに0をとる。λはペアを加えることに対するコストであり、ｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）に対して大きいλを設定することで、できるだけ大きい文の集まり同士で対応がとられ易くする。なお、λ＝０としてもよい。
【００３０】
上記の最適化問題（整数線形計画問題）を解くことによって、対応付けられる第１部分文書と第２部分文書とのペアの第１部分文書が、対応付けられる他のペアの第１部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの第２部分文書が、対応付けられる他のペアの第２部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの対応付けスコアｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）からλを減算した値の総和が最大となるように、対応付けられる第１部分文書と第２部分文書とのペアが少なくとも１つ決定される。
【００３１】
そして、対応付け計算部２２は、対応付けられた第１部分文書と第２部分文書とのペアの各々について部分文書ペアスコア計算処理部２１で決定した文の対応付けを、文書入力部１０で受け付けた２つの文書における最適な文の対応付けとして決定する。
【００３２】
対応付け結果出力部３０は、文対応付け決定装置１００によって得られた最適な文の対応付けを出力する。
【００３３】
＜文対応付け決定装置の作用＞
次に、本発明の実施の形態に係る文対応付け決定装置１００の作用について説明する。まず、文の対応付けの対象となる２つの文書が、文対応付け決定装置１００に入力されると、文対応付け決定装置１００によって、図２に示す文対応付け決定処理ルーチンが実行される。
【００３４】
まず、ステップＳ０１において、入力された２つの文書を受け付ける。
【００３５】
そして、ステップＳ０２において、上記ステップＳ０１で受け付けた２つの文書の各々について、すべての部分文書を生成するとともに、２つの文書の各々の部分文書で形成されるすべてのペアの各々について、当該ペアの部分文書間のＤＰマッチングを行って、当該ペアについての最適なスコアｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）を計算する。
【００３６】
次のステップＳ０３では、上記ステップＳ０２で計算されたすべてのペアの各々の最適なスコアｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）に基づいて、整数線形計画問題処理装置１５０を用いて、上記（３）式に示す最適化問題（整数線形計画問題）を解くことによって、２つの文書間の部分文書の対応付けを決定する。
【００３７】
ステップＳ０４では、上記ステップＳ０３で対応付けられた部分文書のペアの各々について、上記ステップＳ０２で決定された当該ペアの部分文書間の文の対応付けを用いて、２つの文書間の文の対応付けを決定し、対応付け結果出力部３０により出力して、文対応付け決定処理ルーチンを終了する。
【００３８】
以上説明したように、本実施の形態に係る文対応付け決定装置によれば、２つの文書における部分文書の全てのペアについて、部分文書ｆｉ，ｊ、ｅｋ，ｌ間でスコアｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）を最適化するように文の対応付けを決定し、対応付けられるペアの部分文書が、対応付けられる他のペアの部分文書と重複せず、かつ、対応付けられる部分文書のペアの最適なスコアｓｃｏｒｅ（ｆｉ，ｊ，ｅｋ，ｌ）からλを減算した値の総和が最大となるように、対応付けられる部分文書のペアを決定し、対応付けられた部分文書のペアについて最適化するよう決定された文の対応付けを、２つの文書間の文の対応付けとして決定することにより、文書間で文の対応付けが交叉している場合であっても、文の対応付けを精度よく決定するこができる。
【００３９】
また、いくつかの連続する文のまとまりである部分文書を構成要素とする割当問題として、文の対応付け問題を定式化して解く。このように部分文書を構成要素として解くことによって、一つの文を構成要素とする割当問題として解く際に考慮できなかった、文の前後のつながりを考慮した対応付けを行うことができる。また、ＤＰマッチングによる方法では不可能だった、文の交叉があるような場合でも対応付けを行うことが可能となる。
【００４０】
また、２つの文書中の文同士の対応付けを行う問題において、対応する文のまとまり（例えば、段落）の位置が文書間で交叉しているような場合にも、適切な対応付けを行うことが可能となり、結果として文書間の文の対応付けの精度を向上させることができる。
【００４１】
また、本実施の形態で説明した文の対応付けを、対訳データを生成する際に利用することにより、対訳データにおける文の対応付けを精度よく行うことができ、統計的機械翻訳の精度向上等の効果が見込める。また、本実施の形態で説明した文の対応付けを、ある文書の違法なコピーを発見する問題などにも適用することができる。
【００４２】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００４３】
例えば、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００４４】
１０   文書入力部
２０   演算部
２１   部分文書ペアスコア計算処理部
２２   計算部
３０   対応付け結果出力部
１００ 文対応付け決定装置
１５０ 整数線形計画問題処理装置
【図１】
2014154102.tif 000007
【図２】
2014154102.tif 000008