(57)【特許請求の範囲】
【請求項１】
複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置であって、
前記第１文書の複数の文の各々についての前記文が対応付けに利用されない度合いを表す文スコア、前記第２文書の複数の文の各々についての前記文が対応付けに利用されない度合いを表す文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対が対応付けられる度合いを表す対スコアに基づいて、前記第１文書のうちの連続するｉ番目からｊ番目までの文からなる第１部分文書と、前記第２文書のうちの連続するｋ番目からｌ番目までの文からなる第２部分文書とのペアを表す変数ｘｉｊｋｌの集合ＸＬに含まれる各変数ｘｉｊｋｌが表す前記第１部分文書と前記第２部分文書とのペアのうちの少なくとも１つのペアの各々について、前記ペアの前記第１部分文書と前記第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように文の対応付けを決定し、前記第１文書と前記第２文書との間での文の対応付けとする第１文対応付け決定部と、
前記第１文対応付け決定部によって決定された前記第１文書と前記第２文書との間での文の対応付けに基づいて、前記第１部分文書と前記第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、前記集合ＸＬに含まれない変数ｘｉｊｋｌの何れか１つを選択する選択部と、
予め定められた反復終了条件を満たすまで、前記選択部によって選択された前記変数ｘｉｊｋｌの前記集合ＸＬへの追加、前記第１文対応付け決定部による決定、及び前記選択部による選択を繰り返す反復判定部と、
前記第１文書の複数の文の各々についての前記文スコア、前記第２文書の複数の文の各々についての前記文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対スコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算される前記対応付けスコアを用いて求められる目的関数が最大となるように、前記集合ＸＬに含まれる変数ｘｉｊｋｌが表す前記第１部分文書と前記第２部分文書とのペアの各々から、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、対応付けられた前記第１部分文書と前記第２部分文書とのペアの各々について前記対応付けスコアを最適化するように決定した文の対応付けを、前記第１文書と前記第２文書との間での文の対応付けとして決定する第２文対応付け決定部と、
を含む文対応付け決定装置。
【請求項２】
前記選択部は、前記第１文対応付け決定部によって決定された前記第１文書と前記第２文書との間での文の対応付けに基づいて、前記第１部分文書と前記第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、前記集合ＸＬに含まれない変数ｘｉｊｋｌであって、前記変数ｘｉｊｋｌが表すペアについて最適化するように計算される前記対応付けスコアに基づいて計算される被約費用を最大とする変数ｘｉｊｋｌを１つ選択し、
前記反復判定部は、前記選択部によって選択された変数ｘｉｊｋｌの前記被約費用が負の値であるか否かを判定し、変数ｘｉｊｋｌの被約費用が負の値でない場合には、前記選択部によって選択された前記変数ｘｉｊｋｌを前記集合ＸＬへ追加して、前記第１文対応付け決定部による決定、及び前記選択部による選択を繰り返し、
前記変数ｘｉｊｋｌの被約費用が負の値である場合には、貪欲法に従って、前記第１文書の複数の文の各々についての前記文スコア、前記第２文書の複数の文の各々についての前記文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対スコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算される前記対応付けスコアを用いて求められる前記目的関数が最大となるように、前記第１部分文書と前記第２部分文書とのペアの各々から、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、
前記対応付けられる前記第１部分文書と前記第２部分文書とのペアを決定したときの前記目的関数の値と、前記第１文対応付け決定部において得られた前記ペアの各々について最適な対応付けスコアを用いて求められる前記目的関数の値との差分が、前記選択部によって選択された変数ｘｉｊｋｌの前記被約費用より大きい場合には、前記第１文対応付け決定部による決定、及び前記選択部による選択の繰り返しを終了し、前記差分が、前記選択部によって選択された変数ｘｉｊｋｌの前記被約費用以下である場合には、前記選択部によって選択された前記変数ｘｉｊｋｌを前記集合ＸＬへ追加して、前記第１文対応付け決定部による決定、及び前記選択部による選択を繰り返す請求項１記載の文対応付け決定装置。
【請求項３】
前記選択部は、前記第１文対応付け決定部によって決定された前記第１文書と前記第２文書との間での文の対応付けに基づいて得られる、前記第１部分文書の各文に対応する変数の値及び前記第２部分文書の各文に対応する変数の値と、前記第１文書の複数の文の各々についての前記文スコアと、前記第２文書の複数の文の各々についての前記文スコアと、前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対スコアとに基づいて、動的計画法に従って、前記第１文書の複数の文と前記第２文書の複数の文との各ペアについて、最適化するように前記ペアに対する編集操作スコアを算出し、各ペアについて前記編集操作スコアを算出した結果をバックトラッキングすることにより、前記第１部分文書と前記第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、前記集合ＸＬに含まれない変数ｘｉｊｋｌであって、前記被約費用が最大となる変数ｘｉｊｋｌを１つ選択する請求項２記載の文対応付け決定装置。
【請求項４】
第１文対応付け決定部と、選択部と、反復判定部と、第２文対応付け決定部と、を含む、複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置における、文対応付け決定方法であって、
前記第１文対応付け決定部が、前記第１文書の複数の文の各々についての前記文が対応付けに利用されない度合いを表す文スコア、前記第２文書の複数の文の各々についての前記文が対応付けに利用されない度合いを表す文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対が対応付けられる度合いを表す対スコアに基づいて、前記第１文書のうちの連続するｉ番目からｊ番目までの文からなる第１部分文書と、前記第２文書のうちの連続するｋ番目からｌ番目までの文からなる第２部分文書とのペアを表す変数ｘｉｊｋｌの集合ＸＬに含まれる各変数ｘｉｊｋｌが表す前記第１部分文書と前記第２部分文書とのペアのうちの少なくとも１つのペアの各々について、前記ペアの前記第１部分文書と前記第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように文の対応付けを決定し、前記第１文書と前記第２文書との間での文の対応付けし、
前記選択部が、前記第１文対応付け決定部によって決定された前記第１文書と前記第２文書との間での文の対応付けに基づいて、前記第１部分文書と前記第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、前記集合ＸＬに含まれない変数ｘｉｊｋｌの何れか１つを選択し、
前記第２文対応付け決定部が、前記反復判定部が、予め定められた反復終了条件を満たすまで、前記選択部によって選択された前記変数ｘｉｊｋｌの前記集合ＸＬへの追加、前記第１文対応付け決定部による決定、及び前記選択部による選択を繰り返し、
前記第１文書の複数の文の各々についての前記文スコア、前記第２文書の複数の文の各々についての前記文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対スコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算される前記対応付けスコアを用いて求められる目的関数が最大となるように、前記集合ＸＬに含まれる変数ｘｉｊｋｌが表す前記第１部分文書と前記第２部分文書とのペアの各々から、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、対応付けられた前記第１部分文書と前記第２部分文書とのペアの各々について前記対応付けスコアを最適化するように決定した文の対応付けを、前記第１文書と前記第２文書との間での文の対応付けとして決定する
文対応付け決定方法。
【請求項５】
コンピュータを、請求項１〜３の何れか１項記載の文対応付け決定装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文対応付け決定装置、方法、及びプログラムに係り、特に、２つの文書間の文の対応付けを決定する文対応付け決定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
既存の文関係の対応付けを決定する手法として、系列のＤＰマッチングに基づく方法が知られている（非特許文献１）。ＤＰマッチングは、二つの系列が与えられたときにその系列の要素間の対応関係を動的計画法によって求めるための方法である。また、交差を含む文の対応付けに利用できる方法も知られている（非特許文献２）。非特許文献２の方法は、整数計画法を用いることによって交差を含む文の対応付けを実現している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Moore, R.  C. “Fast and accurate sentence alignment of bilingual corpora”,in Proceedings of AMTA 2002, pages 135-144 (2002)
【非特許文献２】西野正彬、平尾努、永田昌明「集合パッキング問題に基づく文アラインメントのモデル化」言語処理学会第19会年次大会 発表論文集 pp. 932-935,2013
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献１記載の技術において、ＤＰマッチングに基づく方法は高速ではあるが、文間の対応付けにおいて文の出現順序の交差を許さないため、交差を含むような対応付けに利用できないという問題点がある。
【０００５】
また、非特許文献２記載の技術は、文の順序の交差を含むような文書対を正しく対応付けすることができる一方で、文書に含まれる文の数が増加すると、整数計画法の問題の規模が急激に大きくなり、高速な計算が行えないという問題点がある。
【０００６】
本発明では、上記問題点を解決するために成されたものであり、文の対応付けが交差している場合であっても、高速に文の対応付けを決定することができる文対応付け決定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、第１の発明に係る文対応付け決定装置は、複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置であって、前記第１文書の複数の文の各々についての前記文が対応付けに利用されない度合いを表す文スコア、前記第２文書の複数の文の各々についての前記文が対応付けに利用されない度合いを表す文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対が対応付けられる度合いを表す対スコアに基づいて、前記第１文書のうちの連続するｉ番目からｊ番目までの文からなる第１部分文書と、前記第２文書のうちの連続するｋ番目からｌ番目までの文からなる第２部分文書とのペアを表す変数ｘｉｊｋｌの集合ＸＬに含まれる各変数ｘｉｊｋｌが表す前記第１部分文書と前記第２部分文書とのペアのうちの少なくとも１つのペアの各々について、前記ペアの前記第１部分文書と前記第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように文の対応付けを決定し、前記第１文書と前記第２文書との間での文の対応付けとする第１文対応付け決定部と、前記第１文対応付け決定部によって決定された前記第１文書と前記第２文書との間での文の対応付けに基づいて、前記第１部分文書と前記第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、前記集合ＸＬに含まれない変数ｘｉｊｋｌの何れか１つを選択する選択部と、予め定められた反復終了条件を満たすまで、前記選択部によって選択された前記変数ｘｉｊｋｌの前記集合ＸＬへの追加、前記第１文対応付け決定部による決定、及び前記選択部による選択を繰り返す反復判定部と、前記第１文書の複数の文の各々についての前記文スコア、前記第２文書の複数の文の各々についての前記文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対スコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算される前記対応付けスコアを用いて求められる目的関数が最大となるように、前記集合ＸＬに含まれる変数ｘｉｊｋｌが表す前記第１部分文書と前記第２部分文書とのペアの各々から、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、対応付けられた前記第１部分文書と前記第２部分文書とのペアの各々について前記対応付けスコアを最適化するように決定した文の対応付けを、前記第１文書と前記第２文書との間での文の対応付けとして決定する第２文対応付け決定部と、を含んで構成されている。
【０００８】
第２の発明に係る文対応付け決定方法は、第１文対応付け決定部と、選択部と、反復判定部と、第２文対応付け決定部と、を含む、複数の文を含む第１文書と、複数の文を含む第２文書との間で、文の対応付けを決定する文対応付け決定装置における、文対応付け決定方法であって、前記第１文対応付け決定部が、前記第１文書の複数の文の各々についての前記文が対応付けに利用されない度合いを表す文スコア、前記第２文書の複数の文の各々についての前記文が対応付けに利用されない度合いを表す文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対が対応付けられる度合いを表す対スコアに基づいて、前記第１文書のうちの連続するｉ番目からｊ番目までの文からなる第１部分文書と、前記第２文書のうちの連続するｋ番目からｌ番目までの文からなる第２部分文書とのペアを表す変数ｘｉｊｋｌの集合ＸＬに含まれる各変数ｘｉｊｋｌが表す前記第１部分文書と前記第２部分文書とのペアのうちの少なくとも１つのペアの各々について、前記ペアの前記第１部分文書と前記第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように文の対応付けを決定し、前記第１文書と前記第２文書との間での文の対応付けし、前記選択部が、前記第１文対応付け決定部によって決定された前記第１文書と前記第２文書との間での文の対応付けに基づいて、前記第１部分文書と前記第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、前記集合ＸＬに含まれない変数ｘｉｊｋｌの何れか１つを選択し、前記反復判定部が、予め定められた反復終了条件を満たすまで、前記選択部によって選択された前記変数ｘｉｊｋｌの前記集合ＸＬへの追加、前記第１文対応付け決定部による決定、及び前記選択部による選択を繰り返し、前記第２文対応付け決定部が、前記第１文書の複数の文の各々についての前記文スコア、前記第２文書の複数の文の各々についての前記文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対スコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算される前記対応付けスコアを用いて求められる目的関数が最大となるように、前記集合ＸＬに含まれる変数ｘｉｊｋｌが表す前記第１部分文書と前記第２部分文書とのペアの各々から、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、対応付けられた前記第１部分文書と前記第２部分文書とのペアの各々について前記対応付けスコアを最適化するように決定した文の対応付けを、前記第１文書と前記第２文書との間での文の対応付けとして決定する。
【０００９】
第１及び第２の発明によれば、第１文対応付け決定部により、第１文書の複数の文の各々についての文スコア、第２文書の複数の文の各々についての文スコア、及び第１文書の複数の文と第２文書の複数の文との対の各々についての対スコアに基づいて、第１文書の第１部分文書と、第２文書の第２部分文書とのペアを表す変数ｘｉｊｋｌの集合ＸＬに含まれる各変数ｘｉｊｋｌが表す第１部分文書と第２部分文書とのペアのうちの少なくとも１つのペアの各々について、ペアの第１部分文書と第２部分文書との間で計算される対応付けスコアを最適化するように文の対応付けを決定し、第１文書と第２文書との間での文の対応付けし、選択部により、決定された第１文書と第２文書との間での文の対応付けに基づいて、第１部分文書と第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、集合ＸＬに含まれない変数ｘｉｊｋｌの何れか１つを選択し、反復判定部により、予め定められた反復終了条件を満たすまで、選択された変数ｘｉｊｋｌの集合ＸＬへの追加、決定、及び選択を繰り返し、第２対応付け決定部が、第１文書の複数の文の各々についての文スコア、第２文書の複数の文の各々についての文スコア、及び第１文書の複数の文と第２文書の複数の文との対の各々についての対スコアに基づいて、対応付けられる第１部分文書と第２部分文書とのペアの第１部分文書が、他のペアの第１部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの第２部分文書が、他のペアの第２部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの各々について最適化するように計算される対応付けスコアを用いて求められる目的関数が最大となるように、集合ＸＬに含まれる変数ｘｉｊｋｌが表す第１部分文書と第２部分文書とのペアの各々から、対応付けられる第１部分文書と第２部分文書とのペアを少なくとも１つ決定し、対応付けられた第１部分文書と第２部分文書とのペアの各々について対応付けスコアを最適化するように決定した文の対応付けを、第１文書と第２文書との間での文の対応付けとして決定する。
【００１０】
このように、対応付けられる第１部分文書と第２部分文書とのペアの第１部分文書が、他のペアの第１部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの第２部分文書が、他のペアの第２部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの各々について最適化するように計算される対応付けスコアを用いて求められる目的関数が最大となるように、集合ＸＬに含まれる変数ｘｉｊｋｌが表す第１部分文書と第２部分文書とのペアの各々から、対応付けられる第１部分文書と第２部分文書とのペアを少なくとも１つ決定し、対応付けられた第１部分文書と第２部分文書とのペアの各々について対応付けスコアを最適化するように決定した文の対応付けを、第１文書と第２文書との間での文の対応付けとして決定することにより、文の対応付けが交差している場合であっても、高速に文の対応付けを決定することができる。
【００１１】
また、第１の発明に係る文対応付け決定装置において、前記選択部は、前記第１文対応付け決定部によって決定された前記第１文書と前記第２文書との間での文の対応付けに基づいて、前記第１部分文書と前記第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、前記集合ＸＬに含まれない変数ｘｉｊｋｌであって、前記変数ｘｉｊｋｌが表すペアについて最適化するように計算される前記対応付けスコアに基づいて計算される被約費用を最大とする変数ｘｉｊｋｌを１つ選択し、前記反復判定部は、前記選択部によって選択された変数ｘｉｊｋｌの前記被約費用が負の値であるか否かを判定し、変数ｘｉｊｋｌの被約費用が負の値でない場合には、前記選択部によって選択された前記変数ｘｉｊｋｌを前記集合ＸＬへ追加して、前記第１文対応付け決定部による決定、及び前記選択部による選択を繰り返し、前記変数ｘｉｊｋｌの被約費用が負の値である場合には、貪欲法に従って、前記第１文書の複数の文の各々についての前記文スコア、前記第２文書の複数の文の各々についての前記文スコア、及び前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対スコアに基づいて、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第１部分文書が、他のペアの前記第１部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの前記第２部分文書が、他のペアの前記第２部分文書と重複せず、かつ、対応付けられる前記第１部分文書と前記第２部分文書とのペアの各々について最適化するように計算される前記対応付けスコアを用いて求められる前記目的関数が最大となるように、前記第１部分文書と前記第２部分文書とのペアの各々から、対応付けられる前記第１部分文書と前記第２部分文書とのペアを少なくとも１つ決定し、前記対応付けられる前記第１部分文書と前記第２部分文書とのペアを決定したときの前記目的関数の値と、前記第１文対応付け決定部において得られた前記ペアの各々について最適な対応付けスコアを用いて求められる前記目的関数の値との差分が、前記選択部によって選択された変数ｘｉｊｋｌの前記被約費用より大きい場合には、前記第１文対応付け決定部による決定、及び前記選択部による選択の繰り返しを終了し、前記差分が、前記選択部によって選択された変数ｘｉｊｋｌの前記被約費用以下である場合には、前記選択部によって選択された前記変数ｘｉｊｋｌを前記集合ＸＬへ追加して、前記第１文対応付け決定部による決定、及び前記選択部による選択を繰り返してもよい。
【００１２】
また、第１の発明に係る文対応付け決定装置は、前記選択部は、前記第１文対応付け決定部によって決定された前記第１文書と前記第２文書との間での文の対応付けに基づいて得られる、前記第１部分文書の各文に対応する変数の値及び前記第２部分文書の各文に対応する変数の値と、前記第１文書の複数の文の各々についての前記文スコアと、前記第２文書の複数の文の各々についての前記文スコアと、前記第１文書の複数の文と前記第２文書の複数の文との対の各々についての前記対スコアとに基づいて、動的計画法に従って、前記第１文書の複数の文と前記第２文書の複数の文との各ペアについて、最適化するように前記ペアに対する編集操作スコアを算出し、各ペアについて前記編集操作スコアを算出した結果をバックトラッキングすることにより、前記第１部分文書と前記第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、前記集合ＸＬに含まれない変数ｘｉｊｋｌであって、前記被約費用が最大となる変数ｘｉｊｋｌを１つ選択する。
【００１３】
また、本発明のプログラムは、コンピュータを、上記の文対応付け決定装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１４】
以上説明したように、本発明の文対応付け決定装置、方法、及びプログラムによれば、対応付けられる第１部分文書と第２部分文書とのペアの第１部分文書が、他のペアの第１部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの第２部分文書が、他のペアの第２部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの各々について最適化するように計算される対応付けスコアを用いて求められる目的関数が最大となるように、集合ＸＬに含まれる変数ｘｉｊｋｌが表す第１部分文書と第２部分文書とのペアの各々から、対応付けられる第１部分文書と第２部分文書とのペアを少なくとも１つ決定し、対応付けられた第１部分文書と第２部分文書とのペアの各々について対応付けスコアを最適化するように決定した文の対応付けを、第１文書と第２文書との間での文の対応付けとして決定することにより、文の対応付けが交差している場合であっても、高速に文の対応付けを決定することができる。
【図面の簡単な説明】
【００１５】
【図１】日本語と英語との文書の対応付けの例を示す図である。
【図２】本発明の実施の形態に係る文対応付け決定装置の機能的構成を示すブロック図である。
【図３】本発明の実施の形態に係る文対応付け決定装置における文対応付け決定処理ルーチンを示すフローチャート図である。
【図４】本発明の実施の形態に係る文対応付け決定装置における最適マッチング計算処理ルーチンを示すフローチャート図である。
【図５】本発明の実施の形態に係る文対応付け決定装置におけるアイテム選択処理ルーチンを示すフローチャート図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１７】
＜本発明の原理＞
まず、本発明の原理について説明する。本発明は、二つの異なる文書が与えられたときに、それらの間に含まれる文の間の対応関係を求めるものである。文同士の対応関係を求めることは、統計的機械翻訳において必要とされる対訳データを生成するために不可欠な処理である。また、そのほかにも、ある文書の違法なコピーを発見する問題なども、文の対応関係を求めることによって解くことができる。日本語と英語との文書の対応付けの例を図１に示す。図１は５文の英文からなる文書Ａと、４文の日本語の文からなる文書Ｂとの文対応付けの例である。線で結ばれた文同士が対応付けられている。
【００１８】
また、本発明においては、非特許文献２の方法と同様に、文対応付けを整数計画法の問題として定式化して解く。この際に、列生成法（非特許文献３：Marco E. Lubbecke,  Jacques Desrosiers, “Selected Topics in Column Generation”,Operations Research,Vol. 53, No.6, pp.1007-1023 (2005)）を用いることによって、高速に整数計画法の問題を解く。
【００１９】
本実施の形態においては、翻訳元言語の文書と当該文書を翻訳した翻訳先言語の文書との対応付けを行う。ここでは、翻訳元言語の文書の集合をＥとし、翻訳先言語の文書の集合をＦとする。集合Ｅに含まれる各文をｅｉと表し、１≦ｉ≦｜Ｅ｜とする。また、｜Ｅ｜は、集合Ｅに含まれる文の総数とする。同様に、集合Ｆに含まれる各文をｆｋ（１≦ｋ≦｜Ｆ｜）とし、｜Ｆ｜は、集合Ｆに含まれる文の総数とする。なお、以下では、ｅｉ，ｊで、集合Ｅの連続するｉ番目からｊ番目までの文からなる文の集まり（部分文書）を表すとする。集合Ｆについても同様に表現する。
【００２０】
ここで、集合Ｅ及び集合Ｆの各々に含まれる文毎に、当該文が対応付けに利用されない度合いを表す文スコアが与えられ、集合Ｅに含まれる文の各々と、集合Ｆに含まれる文の各々の対毎に、当該文の対が対応付けされる度合いを表す対スコアが与えられている。なお、文ｅｉの文スコアをｗ（ｅｉ）、文ｆｋの文スコアをｗ（ｆｋ）、文の対について与えられる対スコアをｗ（ｅｉ，ｆｋ）と表す（ｅｉ∈Ｅ、ｆｋ∈Ｆ）。また、部分文書ｅｉ，ｊと部分文書ｆｋ，ｌの対応付けを行ったときの当該部分文書のペアの対応付けスコアをｗｉｊ，ｋｌと表す。また、部分文書のペアの対応付けスコアｗｉｊ，ｋｌは、下記（１）式に従って、再帰的に計算することができるため、任意のｗｉｊ，ｋｌについては、ｗｉｉ，ｋｋから順に再帰的に計算することで求めることができる。なお、翻訳元言語の文書における部分文書を第１部分文書とし、翻訳先言語の文書における部分文書を第２部分文書とする。
【００２１】
【数１】
0006019538.tif 000002
【００２２】
翻訳元言語の文書と当該文書を翻訳した翻訳先言語の文書との対応付けは、下記（２）式の整数計画問題を解き、最適マッチング計算を行うことによって実現可能である。
【００２３】
【数２】
0006019538.tif 000003
【００２４】
ここで、ｘｉｊｋｌは、対応付けが行われた第１部分文書ｅｉ，ｊと第２部分文書ｆk，lとのペア（ｅｉ，…，ｅｊ，ｆｋ，…，ｆｌ）を表すバイナリ変数である。最終的に得られた対応付けにおいて部分文書のペア（ｅｉ，…，ｅｊ，ｆｋ，…，ｆｌ）が含まれているときにｘｉｊｋｌは１をとり、そうでないときに０をとる。λはペアを加えることに対するコストであり、ｗｉｊ，ｋｌに対して大きいλを設定することで、できるだけ大きい文の集まり同士で対応が取られ易くする。この問題を、整数計画問題ソルバーを用いて解くことによって文の対応付けを求めることができるが、変数ｘｉｊｋｌの個数は｜Ｅ｜（｜Ｅ｜−１）｜Ｆ｜（｜Ｆ｜−１）／４となり、小さな｜Ｅ｜、｜Ｆ｜に対しても多数の変数を用意する必要があるため、問題を解くことが困難になる。
【００２５】
そこで、本発明においては、この問題を、列生成法を用いて解く。列生成法は、最適解でｘｉｊｋｌ＝１となるような変数の数はごく少数であることに着目し、変数の数を減らした制約つき主問題を繰り返し解くことによって所望の解を求める最適化手法である。具体的な制約つき主問題は下記（３）式に示す。
【００２６】
【数３】
0006019538.tif 000004
【００２７】
ここでＸＬは制約つき主問題で利用される変数の集合であり、可能な全ての変数ｘｉｊｋｌの集合の部分集合となっている。なお、上記（３）式に示す制約つき主問題を解く際に、必要となるｗｉｊ，ｋｌのみ上記（１）式に従って求めるものとする。
【００２８】
＜本発明の実施の形態に係る文対応付け決定装置の構成＞
次に、本発明の実施の形態に係る文対応付け装置の構成について説明する。図２に示すように、本発明の実施の形態に係る文対応付け決定装置１００は、ＣＰＵと、ＲＡＭと、後述する文対応付け決定処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この文対応付け決定装置１００は、機能的には図２に示すように入力部１０と、演算部２０と、対応付け結果出力部５０とを備えている。
【００２９】
入力部１０は、対応付けを行う対象である２つの文書の入力を受け付ける。入力される２つの文書は、翻訳元である英語の文書と、当該英語の文書を翻訳した日本語の文書とである。また、入力部１０は、入力部１０において受け付けた英語の文書及び日本語の文書に含まれる各文の各々に与えられる文スコア、及び英語の文書に含まれる文と日本語の文書に含まれる文との対の各々に与えられる対スコアを受け付け、メモリ（図示省略）に記憶する。なお、翻訳元である英語の文書が第１文書であり、当該英語の文書を翻訳した日本語の文書が第２文書の一例である。
【００３０】
演算部２０は、メモリ（図示省略）に記憶されている英語の文書の集合Ｅに含まれる文の各々の文スコアと、日本語の文書の集合Ｆに含まれる文の各々の文スコアと、文の対の各々の対スコアとを用いて、上記（３）式に示す目的関数が最大となるような部分文書同士の対応付けを決定する。
【００３１】
演算部２０は、第１文対応付け決定部３２と、選択部３４と、反復判定部３６と、第２文対応付け決定部３８と、を備えている。
【００３２】
整数線形計画問題処理装置２００は、文対応付け決定装置１００の外部にある、整数計画問題及び線形計画問題を解くための装置であり、演算部２０から呼び出されて使われる。整数線形計画問題処理装置２００として、市販の任意の整数計画問題ソルバー及び線形計画問題ソルバーを利用すればよい。
【００３３】
以下に、演算部２０による最適マッチング計算について説明する。
【００３４】
まず、第１文対応付け決定部３２により、整数線形計画問題処理装置２００において、上記（３）式の最適化問題を解くことによって行われる。
【００３５】
始めに、変数の集合
【００３６】
【数４】
0006019538.tif 000005
【００３７】
を用意し、ＸＬに初期アイテムを追加する。初期アイテムとして集合Ｅに含まれる全ての文と、集合Ｆに含まれる全ての文からなるペアｘ１｜Ｅ｜１｜Ｆ｜を加える。次に、メモリに記憶されている集合Ｅに含まれる文の各々の文スコアと、集合Ｆに含まれる文の各々の文スコア、及び英語の複数の文と日本語の複数の文との対の各々についての対スコアに基づいて、変数ｘｉｊｋｌの集合ＸＬに含まれる各変数ｘｉｊｋｌが表す第１部分文書と第２部分文書とのペアのうちの少なくとも１つのペアの各々について、ペアの第１部分文書と第２部分文書との間で文の対応付けに応じて計算される対応付けスコアを最適化するように文の対応付けを決定し、第１文書と第２文書との間での文の対応付けとする。具体的には、上記（３）式に従って、制約つき主問題を解く。制約つき主問題は線形計画問題であるから、線形計画問題ソルバーを用いることによって主問題を最大化することができる。
【００３８】
次に、選択部３４により、第１文対応付け決定部３２によって決定された英語の文書と日本語の文書との間での文の対応付けに基づいて、第１部分文書と第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、集合ＸＬに含まれない変数ｘｉｊｋｌであって、変数ｘｉｊｋｌが表すペアについて最適化するように計算される対応付けスコアに基づいて計算される被約費用を最大とするような可能なアイテム
【００３９】
【数５】
0006019538.tif 000006
【００４０】
を１つ選択する。ここでアイテムｘｉｊｋｌに対する被約費用を〜ｃｉｊ，ｋｌとすると、
【００４１】
【数６】
0006019538.tif 000007
【００４２】
として計算できる量とする。
【００４３】
ｕｍ、ｖｎは制約つき主問題の双対問題の解における、ｍ文目（１≦ｍ≦｜Ｅ｜）に対応する変数とｎ文目（１≦ｎ≦｜Ｆ｜）に対応する変数の値であり、これらの値は、制約つき主問題の最適解が求まると容易に計算できる。被約費用を最大とするアイテムを選ぶ問題をＳｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズム（非特許文献４：Temple F. Smith and Michael S. Waterman, “Identification of Common Molocular Subsequences”,Journalof Molecular Biology No. 147, pp. 195-197 (1981)）を用いて解く。
【００４４】
Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムは、系列間の編集操作に対するコストが与えられたときに、２つの系列の任意の部分系列のペアのうち、編集操作の編集操作スコア〜ｃｊｌを最大とするものを求めることができる、動的計画法アルゴリズムである。具体的には、まず、予めメモリ（図示省略）に記憶されているスコア表、及びバックトラック表を初期化する。次に、下記（４）式の漸化式
【００４５】
【数７】
0006019538.tif 000008
【００４６】
に基づいて、動的計画法に従って、すべてのｊ，ｌの組合せについて、最適化するように編集操作スコア〜ｃｊｌを求めると共に、スコア表、及びバックトラック表のセルに格納したのちに、スコア表のセルに格納されている編集操作スコア〜ｃｊｌの最大値を選択し、バックトラック表を用いて、バックトラッキングすることによって被約費用最大となるｘｉｊｋｌを求める。
【００４７】
次に、反復判定部３６により、選択部３４において選択されたｘｉｊｋｌの被約費用が負の値であるか否か判定する。もし被約費用が負の値でない場合には、ＸＬに、選択部３４において選択されたｘｉｊｋｌを追加し、第１文対応付け決定部３２及び選択部３４の処理を繰り返し行う。一方、被約費用が負である場合、貪欲法に従って、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムを用いて整数実行可能解を求める。具体的な手順は以下のとおりである。
【００４８】
１．全てのｘｉｊｋｌから、被約費用を最大とするｘｉｊｋｌをＳｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムを用いて求める。
２．選ばれなかった文からなる集合（ｅ１，…，ｅｉ−１，ｆ１，…，ｆｋ−１）、（ｅｊ＋１，…，ｅ｜Ｅ｜，ｆｌ＋１，…，ｆ｜Ｆ｜）のそれぞれについてＳｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムを実行して、それぞれについて被約費用を最大とする文のまとまりを得る。
３．被約費用を最大とする文のまとまりを取り除いた文の集合について、上記２の手順を繰り返し実行する。
【００４９】
次に、上記１〜３の手順により繰り返し求められた被約費用を最大とするｘｉｊｋｌの各々を１として、上記（３）式の目的関数の値を計算し、実行可能解の目的関数値とする。
【００５０】
そして、選択されたアイテムの被約費用〜ｃｉｊｋｌについて、実行可能解の目的関数値と、第１文対応付け決定部３２で求められた目的関数値とに基づいて、下記（５）式の条件を満たすか否かを判定する。選択されたアイテムの被約費用〜ｃｉｊｋｌが下記（５）式の条件を満たさないならば（被約費用以下の場合）、選択部３４により選択したアイテムｘｉｊｋｌを集合ＸＬに追加して、第１文対応付け決定部３２及び選択部３４の処理を繰り返し行う。
【００５１】
【数８】
0006019538.tif 000009
【００５２】
反復判定部３６は、選択されたアイテムの被約費用〜ｃｉｊｋｌが上記（５）式の条件を満たす場合には、選択部３４により選択したアイテムｘｉｊｋｌを集合ＸＬに追加せずに、第１文対応付け決定部３２及び選択部３４の処理の繰り返しを終了する。なお上記（５）式の条件が反復終了条件の一例である。
【００５３】
第２文対応付け決定部３８は、集合ＸＬを用いて、制約付き主問題にｘｉｊｋｌが０または１をとるという制約を加えて、メモリに記憶されている集合Ｅに含まれる文の各々の文スコアと、集合Ｆに含まれる文の各々の文スコアと、英語の複数の文と日本語の複数の文との対の各々についての対スコアと、最終的に得られた変数の集合ＸＬとに基づいて、下記（６）式に従って、制約つき主問題を整数計画問題として解く。
【００５４】
【数９】
0006019538.tif 000010
【００５５】
上記（６）式の最適化問題（整数計画問題）を解くことによって、対応付けられる第１部分文書と第２部分文書とのペアの第１部分文書が、他のペアの第１部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの第２部分文書が、他のペアの第２部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの各々について最適化するように計算される対応付けスコアを用いて求められる目的関数が最大となるように、集合ＸＬに含まれる変数ｘｉｊｋｌが表す第１部分文書と第２部分文書とのペアの各々から、対応付けられる第１部分文書と第２部分文書とのペアを少なくとも１つ決定し、対応付けられた第１部分文書と第２部分文書とのペアの各々について対応付けスコアを最適化するように決定した文の対応付けを、第１文書と第２文書との間での文の対応付けとして決定し、対応付け結果出力部５０へ出力する。
【００５６】
＜本発明の実施の形態に係る文対応付け決定装置の作用＞
次に、本発明の実施の形態に係る文対応付け決定装置１００の作用について説明する。入力部１０において、対応付けを行う対象である英語の文書、及び当該英語を翻訳した日本語の文書と、英語の文書及び日本語の文書に含まれる各文の各々に与えられる文スコアと、英語の文書に含まれる文と日本語の文書に含まれる文との対の各々に与えられる対スコアとを受け付けると、文対応付け決定装置１００は、図３に示す文対応付け決定処理ルーチンを実行する。
【００５７】
まず、ステップＳ１００では、メモリに記憶されている、入力部１０において受け付けた英語の文書及び日本語の文書に含まれる各文の各々に与えられる文スコア、及び英語の文書に含まれる文と日本語の文書に含まれる文との対の各々に与えられる対スコアを読み込む。
【００５８】
次に、ステップＳ１０２では、入力部１０において受け付けた英語の文書と、日本語の文書と、ステップＳ１００において取得した英語の文書及び日本語の文書に含まれる各文の各々に与えられる文スコアと、英語の文書に含まれる文と日本語の文書に含まれる文との対の各々に与えられる対スコアとに基づいて、最適マッチング計算を行う。
【００５９】
次に、ステップＳ１０４では、ステップＳ１０２において取得した最適マッチング計算において決定した文の対応付けを、英語の文書と日本語の文書との間での文の対応付けとして決定し、対応付け結果出力部５０に出力して文対応付け決定処理ルーチンを終了する。
【００６０】
上記ステップＳ１０２は、図４に示す最適マッチング計算処理ルーチンによって実現される。
【００６１】
図４のステップＳ２００は、変数の集合ＸＬ（集合ＸＬの初期状態は空集合である）に、入力部１０において受け付けた英語の文書の集合Ｅに含まれる全ての文と、日本語の文書の集合Ｆに含まれる全ての文とからなるペアｘ１｜Ｅ｜１｜Ｆ｜を初期アイテムとして加える。
【００６２】
次に、ステップＳ２０２では、ステップＳ１００において取得した英語の文書及び日本語の文書に含まれる各文の各々に与えられる文スコアと、英語の文書に含まれる文と日本語の文書に含まれる文との対の各々に与えられる対スコアとに基づいて、整数線形計画問題処理装置２００を用いて、上記（３）式に従って、制約つき主問題を解く。
【００６３】
次に、ステップＳ２０４では、ステップＳ２０２における制約つき主問題の解に基づいて、第１部分文書と第２部分文書とのペアを表す変数ｘｉｊｋｌのうち、集合ＸＬに含まれない変数ｘｉｊｋｌであって、被約費用を最大とするアイテムｘｉｊｋｌを選択する。
【００６４】
次に、ステップＳ２０６では、ステップＳ２０４において選択したアイテムｘｉｊｋｌの被約費用が負であるか否かを判定する。選択したアイテムの被約費用が負である場合には、ステップＳ２１０へ移行し、選択したアイテムの被約費用が０以上である場合には、ステップＳ２０８へ移行する。
【００６５】
次に、ステップＳ２０８では、ステップＳ２０４において選択したアイテムｘｉｊｋｌを変数の集合ＸＬに追加してステップＳ２０２へ移行する。
【００６６】
ステップＳ２１０では、貪欲法に従って、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムを用いて整数実行可能解の目的関数値を求める。
【００６７】
次に、ステップＳ２１２では、ステップＳ２０２において取得した目的関数値と、ステップＳ２１０において取得した整数実行可能解の目的関数値とに基づいて、ステップＳ２０４において選択したアイテムｘｉｊｋｌの被約費用が上記（５）式の条件を満たすか否かを判定する。選択したアイテムの被約費用が上記（５）式の条件を満たす場合にはステップＳ２１４へ移行し、選択したアイテムの被約費用が上記（５）式の条件を満たさない場合には、ステップＳ２０８へ移行する。
【００６８】
次に、ステップＳ２１４では、ステップＳ１００において取得した、英語の文書及び日本語の文書に含まれる各文の各々に与えられる文スコアと、英語の文書に含まれる文と日本語の文書に含まれる文との対の各々に与えられる対スコアと、最終的に得られた変数の集合ＸLとに基づいて、整数線形計画問題処理装置２００を用いて、上記（６）式に従って、制約つき主問題を解いて、最適マッチング計算処理ルーチンを終了する。
【００６９】
上記ステップＳ２０４は、図５に示すアイテム選択処理ルーチンによって実現される。
【００７０】
図５のステップＳ３００は、予めメモリ（図示省略）に記憶されているスコア表及びバックトラック表を初期化する。
【００７１】
次に、ステップＳ３０２では、ステップＳ１００において取得した、英語の文書及び日本語の文書に含まれる各文の各々に与えられる文スコアと、英語の文書に含まれる文と日本語の文書に含まれる文との対の各々に与えられる対スコアと、ステップＳ２０２における制約つき主問題の解に基づいて得られる英語の文書の各文に対応する変数及び日本語の文書の各文に対応する変数の値とに基づいて、上記（４）式に従って、すべてのｊ，ｌの組み合わせについて、動的計画法に従って、最適化するように編集操作スコア〜ｃｊｌを計算し、計算結果を、スコア表、及びバックトラック表のセルに格納する。
【００７２】
次に、ステップＳ３０４では、ステップＳ３０２において取得した、スコア表に基づいて、編集操作スコア〜ｃｊ，ｌの最大値を選択し、バックトラック表に基づいて、選択された最大値のセルから、バックトラッキングすることによって、被約費用が最大となるｘｉｊｋｌを求める。
【００７３】
次に、ステップＳ３０６では、ステップＳ３０４において取得したアイテムｘｉｊｋｌに対する被約費用を算出し、ステップＳ３０４において取得したアイテムｘｉｊｋｌと、当該アイテムに対する被約費用とを出力し、アイテム選択処理ルーチンを終了する。
【００７４】
以上説明したように、本発明の実施の形態に係る文対応付け決定装置によれば、対応付けられる第１部分文書と第２部分文書とのペアの第１部分文書が、他のペアの第１部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの第２部分文書が、他のペアの第２部分文書と重複せず、かつ、対応付けられる第１部分文書と第２部分文書とのペアの各々について最適化するように計算される対応付けスコアを用いて求められる目的関数が最大となるように、集合ＸＬに含まれる変数ｘｉｊｋｌが表す第１部分文書と第２部分文書とのペアの各々から、対応付けられる第１部分文書と第２部分文書とのペアを少なくとも１つ決定し、対応付けられた第１部分文書と第２部分文書とのペアの各々について対応付けスコアを最適化するように決定した文の対応付けを、英語の文書と日本語の文書との間での文の対応付けとして決定することにより、文の対応付けが交差している場合であっても、高速に文の対応付けを決定することができる
【００７５】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７６】
また、本実施の形態においては、選択した被約費用が負である場合には、貪欲法で実行可能解を求める処理に移行（上記ステップＳ２１０）する場合について説明したが、これに限定されるものではない。例えば、選択した被約費用が負である場合には、上記ステップＳ２１４の処理へ移行してもよい。この場合、上記ステップＳ２１０で求まる解は必ずしも最適解である保証はないが、ステップＳ２００において、初期解としてｘ１｜Ｅ｜１｜Ｆ｜を加えているため、少なくともｘ１｜Ｅ｜１｜Ｆ｜＝１で他の変数がすべて０になるような実行可能解を見つけることができる。
【００７７】
また、各文についての文スコア、文の対の各々についての対スコアが入力される場合を例に説明したが、これに限定されるものではなく、従来既知の手法を用いて、各文についての文スコア、文の対の各々についての対スコアを算出してもよい。
【００７８】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【００７９】
１０   入力部
２０   演算部
３２   第１文対応付け決定部
３４   選択部
３６   反復判定部
３８   第２文対応付け決定部
５０   対応付け結果出力部
１００ 文対応付け決定装置
２００ 整数線形計画問題処理装置
【図１】
0006019538.tif 000011
【図２】
0006019538.tif 000012
【図３】
0006019538.tif 000013
【図４】
0006019538.tif 000014
【図５】
0006019538.tif 000015