局所対応抽出装置及び局所対応抽出方法
【課題】本発明は、事前にインデックス化されてない任意の文字列の間で代表的な局所対応を網羅的に抽出する局所対応抽出装置を提供することを目的とする。
【解決手段】任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出装置において、遷移元セルに対応する第二行列のセルがいずれかの局所対応に属することを示し、かつ、第一行列生成部によって算出された最大のスコアが所定値よりも大きい場合、算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、算出対象のセルに対応する二つの文字が局所対応の終点となることを記憶することを特徴とする。
【解決手段】任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出装置において、遷移元セルに対応する第二行列のセルがいずれかの局所対応に属することを示し、かつ、第一行列生成部によって算出された最大のスコアが所定値よりも大きい場合、算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、算出対象のセルに対応する二つの文字が局所対応の終点となることを記憶することを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二つの文書間で類似する文字列対である局所対応を抽出する局所対応抽出装置に関し、特に、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法を用いて局所対応を抽出する局所対応抽出装置に関する。
【背景技術】
【０００２】
長い文書間では、文書全体が互いに類似することは稀であり、部分的な類似個所が存在する。例えば、書籍間の類似性を考える。書籍間での類似個所は一つではなく、複数ある場合も多い。数個の文字からなる単語が書籍間で一致する場合まで考慮すると、書籍間での類似個所の数は膨大になる。二つの文書間での類似箇所（類似文字列対）のことを局所対応という。この局所対応を数え上げることができれば、二つの文書全体を読まなくても、局所対応の周辺を読むだけで二つの文書間の類似性の根拠を把握できる。
【０００３】
例えば、特許審査等の審査業務において、審査対象となる出願と特許文献や非特許文献との間で内容の同一性及び類似性を判定しなければならない。判定対象となる文書間で局所対応を数え上げることができれば、文書全体を読まずとも局所対応の周辺のみを読むことによって対象文書間の同一性及び類似性が判定でき、審査業務を促進できる。
【０００４】
概念検索では、文字列が入力された場合、入力された文字列と類似する文書を類似度順にランキングして提示する。この場合、ユーザは、入力した文字列に適合しそうな文書を上から順に調べていくことができる。しかし、ユーザは、ランキングの根拠が解りにくいため、入力した文字列と提示された文書との適合性を判定するために、提示された文書自体を読まなければならならない場合が多い。文書が長ければ読解時間も長くなる。
【０００５】
一方、全文検索では、入力された文字列と一致する文字列の周辺部を提示することによって、文書全体を読む作業を軽減する。
【０００６】
そこで、概念検索においても、入力された文字列と入力された文字列に適合する文書との間で類似箇所（局所対応）が抽出され、抽出された局所対応が提示されることによって、文書全体を読まずに文書の適合性を判定できる。
【０００７】
また、特許出願の請求項と明細書との間で局所対応を抽出すれば、請求項に関連する実施例を即座に探すこともできる。
【０００８】
局所対応を抽出する従来技術として、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法（非特許文献１）がある。Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法は、動的計画法によってスコアが最大の局所対応を効率良く探索する。ここで、スコアとは、部分文字列間の類似度のことである。
【０００９】
局所対応を抽出するために生成されたスコア行列から、スコアが所定値以上の局所対応を抽出することによって、より多くの局所対応を網羅的に抽出できる。しかしながら、この方法では、単純にスコアのみで局所対応か否かを判断するため、既に抽出された局所対応の周辺の意味のない文字も含む局所対応が大量に抽出されてしまう。このため、局所対応の中でも代表的なもののみを取捨選択する必要がある。つまり、代表性と網羅性双方を満足させる必要がある。
【００１０】
特許文献１には、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法の局所対応の抽出精度を出来るだけ低減させずに、局処対応の抽出の効率を高める方法が記載されている。具体的には、完全に一致する文字列対を抽出し、抽出した文字列対の中である一定のギャップ以内にある文列対を連結する。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００２−１９１３７１号公報
【非特許文献】
【００１２】
【非特許文献１】“Ａｌｇｏｒｉｔｈｍｓ ｏｎ Ｓｔｒｉｎｇｓ，Ｔｒｅｅｓ， ａｎｄ Ｓｅｑｕｅｎｃｅｓ”（ｐｐ．２３２−２３４），Ｇｕｓｆｉｅｌｄ，Ｄ．，Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，１９９７
【発明の概要】
【発明が解決しようとする課題】
【００１３】
ただし、特許文献１に記載された方法で、完全に一致する文字列対を抽出するためには、接尾辞配列等のインデックスを事前に作成しなければならない。また、特許文献１に記載された方法の局所対応の抽出精度もＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法に劣る。遺伝子配列の検索に用いられるＢＬＡＳＴ、ＦＡＳＴＡといったソフトウェアも、特許文献１に記載された方法と同じく、精度を犠牲にして高速化を図るものであり、インデックスが事前に作成されていなければならない。
【００１４】
したがって、インデックス化されていないデータについては局所対応が抽出しにくいという問題がある。
【００１５】
事前にインデックス化されていない任意の長い文字列の間で局所対応を抽出する場合、代表的な局所対応を網羅的に抽出することは困難である。また、局所対応の網羅性を重視すると代表性を損い、代表性を重視すると網羅性を損なうものであった。
【００１６】
このため、本発明は、事前にインデックス化されてない任意の文字列の間で代表的な局所対応を網羅的に抽出する局所対応抽出装置を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の代表的な一例を示せば、任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出装置において、前記局所対応抽出部は、前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とし、前記行の文字列を構成する文字及び前記列の文字列を構成する文字に対応するセルに、当該セルに対応する二つの文字の類似度を示すスコアを登録して、第一行列を生成する第一行列生成部と、前記第一行列のセルに対応するセルによって構成される第二行列のセルのうち前記第一行列生成部によってスコアが算出されたセルに対応するセルに、当該セルに対応する二つの文字が属する局所対応の識別子を登録して、前記第二行列を生成する第二行列生成部と、を有し、前記第一行列のセルに登録されるスコアは、当該セルに対応する二つの文字の類似度が大きいほど大きい値を示し、前記第一行列生成部は、前記スコアの算出対象のセルに隣接するセルのうちすでにスコアが算出されたセルから当該算出対象のセルまでのパスに予め設定された値に基づいて前記算出対象のセルのスコアを算出し、前記算出されたスコアのうち最大のスコアを前記算出対象のセルのスコアとして登録し、前記最大のスコアを算出したパスのセルを遷移元セルとして記憶し、前記第二行列生成部は、前記遷移元セルに対応する前記第二行列のセルがどの局所対応にも属しないことを示し、かつ、前記第一行列生成部によって算出された最大のスコアが所定値である場合、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶し、前記遷移元セルに対応する前記第二行列のセルがいずれかの局所対応に属することを示し、かつ、前記第一行列生成部によって算出された最大のスコアが前記所定値よりも大きい場合、前記算出対象のセルに対応する前記第二行列のセルに、前記遷移元セルに対応する前記第二行列のセルに登録された局所対応の識別子を登録し、さらに、前記算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、前記算出対象のセルに対応する二つの文字が前記局所対応の終点となることを記憶することを特徴とする。
【発明の効果】
【００１８】
本発明によれば、事前にインデックス化されてない任意の文字列の間で代表的な局所対応を網羅的に抽出できる。
【図面の簡単な説明】
【００１９】
【図１】本発明の第１の実施形態の局所対応抽出システムの構成の説明図である。
【図２】本発明の第１の実施形態のディスプレイに表示される局所対応表示画面２０の説明図である。
【図３】本発明の第１の実施形態の変形例の局所対応表示画面の説明図である。
【図４】本発明の第１の実施形態の変形例の要約バーチャートを追加した局所対応表示画面の説明図である。
【図５】本発明の第１の実施形態の二つの文字列間におけるスコアの説明図である。
【図６】本発明の第１の実施形態のスコア行列の説明図である。
【図７】本発明の第１の実施形態のスコア算出方法の説明図である。
【図８】本発明の第１の実施形態の初期化処理の説明図である。
【図９】本発明の第１の実施形態の局所対応収集処理の説明図である。
【図１０】本発明の第１の実施形態の始点行列の説明図である。
【図１１】本発明の第１の実施形態の局所対応抽出処理のフローチャートである。
【図１２】二つの文字列間に本発明の第１の実施形態の局所対応処理を実行し、局所対応が抽出されない場合の説明図である。
【図１３】酷似する二つの文書に第１の実施形態の局所対応処理を実行することによって抽出された局所対応の表示例である。
【図１４】本発明の第２の実施形態の局所対応収集処理の説明図である。
【図１５】本発明の第２の実施形態の局所対応処理を実行することによって抽出された局所対応の表示例である。
【発明を実施するための形態】
【００２０】
本発明の第１の実施形態を図１〜図１１を用いて説明する。
【００２１】
図１は、本発明の第１の実施形態の局所対応抽出システムの構成の説明図である。
【００２２】
抽出対象となる二つの文字列（文書）間で類似する文字列対を局所対応という。
【００２３】
局所対応抽出システムは、二つの文字列間で局所対応を抽出し、抽出した局所対応を表示するシステムである。局所対応抽出システムは、クライアント１０、及び、クライアント１０にネットワーク１１を介してアクセス可能な検索サーバ１２を備える。
【００２４】
検索サーバ１２は、局所対応の抽出の対象となる対象文字列（対象文書）をクライアント１０にネットワーク１１を介して送信する計算機である。
【００２５】
対象文字列がキーボード・マウス１０３を介してクライアント１０に直接入力される場合には、局所対応抽出システムはネットワーク１１及び検索サーバ１２を備えなくてもよい。
【００２６】
クライアント１０は、ＣＰＵ１０１、メモリ１０２、キーボード・マウス１０３、ディスプレイ１０４、局所対応抽出部１０５、局所対応表示制御部１０６、及びデータ通信部１０７を備える。
【００２７】
ＣＰＵ１０１は、局所対応抽出部１０５及び局所対応表示制御部１０６を構成する各種プログラムを実行する。メモリ１０２は、ＣＰＵ１０１が実行するプログラム、及び当該プログラムを実行するために必要なデータを一時的に記憶する。
【００２８】
キーボード・マウス１０３は、ユーザからの入力を受け付ける入力部である。ディスプレイ１０４は、局所対応抽出部１０５によって抽出された局所対応を局所対応表示制御部１０６の制御下で表示する表示部である。
【００２９】
局所対応抽出部１０５は、対象文字列から局所対応を抽出する。局所対応表示制御部１０６は、局所対応抽出部１０５によって抽出された局所対応をディスプレイ１０４に表示するための制御を行う。
【００３０】
データ通信部１０７は、ネットワーク１１を介してデータを通信するインターフェースであり、例えば、ＴＣＰ／ＩＰプロトコルによって通信可能なＬＡＮカードである。
【００３１】
局所対応抽出システムの全体的な処理の概略を説明する。
【００３２】
まず、クライアント１０が対象文字列を取得する。クライアント１０が対象文字列を取得する方法には種々の方法がある。例えば、クライアント１０が検索サーバ１２から対象文字列を取得する方法、及び、ユーザがキーボード・マウス１０３を操作して対象文字列をクライアント１０に入力する方法などがある。
【００３３】
クライアント１０が検索サーバ１２から対象文字列を取得する場合、まず、クライアント１０は、取得する対象文字列の文書番号を検索サーバ１２に送信する。そして、検索サーバ１２は、文書番号を受信した場合、受信した文書番号に対応する文書の文字列を対象文字列としてクライアント１０に送信する。
【００３４】
次に、局所対応抽出部１０５は、クライアント１０が取得した対象文字列から局所対応を抽出する。なお、局所対応抽出部１０５が局所対応を抽出するための具体的な処理については図５〜図１０で詳細を説明する。
【００３５】
そして、局所対応表示制御部１０６は、局所対応抽出部１０５によって抽出された局所対応をディスプレイ１０４に表示する。なお、ディスプレイ１０４に表示される局所対応については図２〜図４で詳細を説明する。
【００３６】
なお、図６で詳述するが、局所対応抽出部１０５は、対象文字列から局所対応を抽出する場合、対象文字列の文字列情報のみを用いるので、対象文字列がインデックス化されてなくてもよい。このため、本実施形態の対象文字列は、検索サーバ１２で検索された文書であってもよいし、ユーザによって直接入力された文字列であってもよい。
【００３７】
図２は、本発明の第１の実施形態のディスプレイ１０４に表示される局所対応表示画面２０の説明図である。
【００３８】
局所対応表示画面２０は、局所対応表示制御部１０６の制御下でディスプレイ１０４に表示される。
【００３９】
局所対応表示画面２０は、抽出ボタン２０１、一致スコア入力ボックス２０２、不一致スコア入力ボックス２０３、読み飛ばしスコア入力ボックス２０４、ギャップ入力ボックス２０５、スコア閾値入力エリア２０６、文書番号入力エリア２０７、２０８、テキストエリア２０９、２１０、及び、局所対応表示エリア２１１を含む。
【００４０】
まず、テキストエリア２０９及び２１０について説明する。テキストエリア２０９及び２１０には、対象文字列が表示される。
【００４１】
テキストエリア２０９及び２１０は、ユーザのキーボード・マウス１０３を介した文字入力を受け付ける。このため、ユーザは、テキストエリア２０９及び２１０に表示される文字列をキーボード・マウス１０３を用いて自由に編集できる。
【００４２】
また、クライアント１０が対象文字列を検索サーバ１２から取得する場合、ユーザは、文書番号入力エリア２０７及び２０８に取得を所望する対象文字列の文書番号を入力する。そして、それぞれの文書番号入力エリア２０７及び２０８に改行が入力されると、クライアント１０は、文書番号入力エリア２０７及び２０８に入力された文書番号を検索サーバ１２に送信する。
【００４３】
検索サーバ１２は、文書番号を受信した場合、受信した文書番号に対応する文書を検索し、検索した文書をクライアント１０に送信する。クライアント１０は、検索サーバ１２から送信された文書を受信した場合、受信した文書に対応する文書番号が入力された文書番号入力エリア２０７及び２０８の下方に位置するテキストエリア２０９及び２１０に、受信した文書の文字列を表示する。
【００４４】
なお、局所対応表示制御部１０６は、局所対応表示画面２０をディスプレイ１０４に表示する場合、文書番号入力エリア２０７及び２０８に前回入力された文書番号を検索サーバ１２に送信するようにしてもよい。
【００４５】
そして、ユーザが抽出ボタン２０１を操作した場合、局所対応表示制御部１０６は、テキストエリア２０９及び２１０に表示された対象文字列を局所対応抽出部１０５に入力する。そして、局所対応抽出部１０５は、入力された対象文字列から局所対応を抽出し、抽出した局所対応を局所対応表示制御部１０６に入力する。
【００４６】
局所対応表示制御部１０６は、入力された局所対応を局所対応表示エリア２１１に表示する。
【００４７】
なお、一致スコア入力ボックス２０２、不一致スコア入力ボックス２０３、読み飛ばしスコア入力ボックス２０４、ギャップ入力ボックス２０５、及びスコア閾値入力エリア２０６には、局所対応抽出部１０５が局所対応を抽出する場合に用いられるパラメータが入力される。これらのパラメータについては、図６〜図１０で詳細を説明する。
【００４８】
なお、局所対応表示制御部１０６は、局所対応表示画面２０をディスプレイ１０４に表示させる場合に対象文字列が決まっていれば、抽出ボタン２０１の操作を自動化してもよい。
【００４９】
次に、局所対応抽出部１０５によって抽出された局所対応を表示する局所対応表示エリア２１１について説明する。
【００５０】
局所対応表示エリア２１１は、対象文字列となる二つの文字列を二次元の行列によって表現する。具体的には、局所対応表示エリア２１１の横軸がテキストエリア２０９に入力された文字列に対応し、局所対応表示エリア２１１の縦軸がテキストエリア２１０に入力された文字列に対応する。横軸においては、先頭の文字が左端に位置し、末尾の文字が右端に位置する。縦軸においては、先頭の文字が上端に位置し、末尾の文字が下端に位置する。
【００５１】
なお、図２では、局所対応表示エリア２１１の上方の表示領域２１５に横軸に対応する文字列を表示し、また、局所対応表示エリア２１１の左側の表示領域２１６に縦軸に対応する文字列を表示するが、これらの表示領域２１４、２１５には文字列が表示されなくてもよい。例えば、横軸及び縦軸に対応する文字列の文字数が所定数以上である場合には、局所対応表示制御部１０６は、表示領域２１４、２１５には文字列を表示しない。
【００５２】
局所対応表示エリア２１１の縦軸に対応する文字列と横軸に対応する文字列との間の局所対応を矩形によって表示する。図２では、二つの局所対応が抽出されており、この抽出された局所対応を二つの矩形２１２Ａ及び２１２Ｂ（以下、総称して２１２という）によって表示する。
【００５３】
矩形２１２の縦辺の位置及び長さは、局所対応表示エリア２１１の縦軸が示す文字列の局所対応の範囲に対応し、矩形２１２の横辺の位置及び長さは、局所対応表示エリア２１１の横軸が示す文字列の局所対応の範囲に対応する
具体的には、矩形２１２Ａは、局所対応表示エリア２１１の横軸が示す文字列の一部の「特許を検索」と、縦軸が示す文字列の一部の「特許検索」との間の局所対応である。矩形２１２Ｂは、局所対応表示エリア２１１の横軸が示す文字列の一部の「精度向上」と、縦軸が示す文字列の一部の「精度の向上」との間の局所対応である。
【００５４】
ユーザは、マウスポインタ２１４によって特定の矩形２１２を指すことによって、局所対応表示エリア２１１に表示された複数の矩形２１２（局所対応）の中から特定の矩形２１２を選択できる。なお、局所対応表示制御部１０６は、ユーザによって選択された矩形２１２を、選択されていることをユーザに把握可能な態様で表示する。具体的には、局所対応表示制御部１０６は、ユーザによって選択された矩形２１２をハイライト（例えば、グレーの塗りつぶし等）で表示する。
【００５５】
また、局所対応表示制御部１０６は、テキストエリア２０９及び２１０に表示された文字列のうち、ユーザによって選択された矩形２１２に対応する部分文字列を、当該部分文字列に対応する矩形２１２が選択されていることをユーザに把握可能な態様で表示する。具体的には、局所対応表示制御部１０６は、当該部分文字列をハイライト（例えば、反転表示等）で表示する。
【００５６】
これによって、ユーザは、局所対応表示エリア２１１に表示される矩形２１２を選択しながら、テキストエリア２０９及び２１０に表示される文字列のうち選択した矩形２１２に対応する文字列を即座に探すことができ、テキストエリア２０９及び２１０から探した文字列周辺を比較しながら読むことができる。
【００５７】
また、局所対応の文字列が長い場合には、矩形２１２の面積は大きくなるので、ユーザは一目で重要な局所対応を判別できる。通常、ユーザは、局所対応表示エリア２１１に表示された大きな矩形を探し、当該矩形をマウスポインタ２１４によって差すことによって当該矩形を選択し、当該矩形に対応する文字列をテキストエリア２０９及び２１０から探し、当該文字列の周辺も含めて読む。
【００５８】
なお、テキストエリア２０９及び２１０に表示される文字列の文字数が所定数よりも大きい場合、局所対応表示制御部１０６は、選択された矩形２１２に対応する部分文字列がテキストエリア２０９及び２１０の最上部に位置するように、自動スクロールして表示する。なお、当該所定数は、例えば、テキストエリア２０９及び２１０にスクロールなしで表示可能な文字数よりも大きい値に設定される。
【００５９】
テキストエリア２０９及び２１０に入力される文字列が長くなると、局所対応表示エリア２１１に表示される矩形２１２も相対的に小さく表示されるため、ユーザは、面積の小さい矩形２１２を判別しにくくなる。このため、図３に示すように、局所対応表示エリア２１１の一部を拡大表示するズームエリア３０３を追加する変形例も考えられる。
【００６０】
図３は、本発明の第１の実施形態の変形例の局所対応表示画面３０の説明図である。
【００６１】
図３に示す局所対応表示画面３０の構成のうち、図２に示す局所対応表示画面２０の構成と同じ構成は、同じ符号を付与し、説明を省略する。
【００６２】
図３に示す局所対応表示エリア２１１は、テキストエリア２０９及び２１０に表示される対象文字列の行列の全体を表示するエリアである。
【００６３】
当該局所対応表示エリア２１１内には、ユーザがマウスによって操作可能なスコープ３０２が表示される。スコープ３０２内に位置する範囲が、ズームエリア３０３に拡大表示される。なお、スコープ３０２が移動すると、局所対応表示制御部１０６は、ズームエリア３０３の表示内容を移動したスコープ３０２に対応する表示内容に更新する。
【００６４】
図４は、本発明の第１の実施形態の変形例の局所対応表示画面４０の説明図である。
【００６５】
図４に示す局所対応表示画面４０は、図２又は図３に示す局所対応表示エリア２１１に要約バーチャート４１及び４２が追加された画面である。
【００６６】
ユーザは、局所対応表示エリア２１１に表示される矩形２１２がどの部分に集中しているかを即座に把握したい場合がある。ユーザは、局所対応表示エリア２１１を探すことによって、矩形２１２が局所対応表示エリア２１１のどの部分に集中しているかをある程度把握できる。しかしながら、この方法は一覧性に欠ける。
【００６７】
そこで、局所対応表示制御部１０６は、局所対応表示エリア２１１に表示される矩形２１２の横方向の分布を集約し、縦方向の分布度を示す要約バーチャート４１を生成し、また、局所対応表示エリア２１１に表示される矩形２１２の横方向の分布を示す要約バーチャート４２を生成して、生成した要約バーチャート４１及び４２を表示する。
【００６８】
要約バーチャート４１は、局所対応表示エリア２１１に表示される矩形２１２を横方向に射影した結果のバーチャートで、縦方向の文字列中での局所対応の分布を示す。一方、要約バーチャート４２は、横方向の文字列中での局所対応の分布を示す。例えば、矩形２１２Ｃは、要約バーチャート４１の４１１及び４１２の部分に射影される。なお、局所対応の最大スコアが大きいほど濃い色で表示することで、ユーザにとって重要な局所対応を注視しやすくすることもできる。なお、スコアは類似度を意味し、具体的なスコアの算出法は後述する。
【００６９】
一方の文字列中の部分文字列が、他方の文字列中の複数の部分と対応がとれる場合も多い。例えば、図４では、縦方向の文字列中の「精度」は横方向で３か所出現している。このため、縦方向の「精度」に対応する要約バーチャート４１の部分４１２は他と比べて色が濃く表示される。
【００７０】
このように、局所対応表示エリア２１１に表示される矩形２１２を行方向及び列方向に射影した場合、当該行方向及び列方向に位置する局所対応のスコアの総和に比例して要約バーチャート４１及び４２の色を濃く表示すれば、ユーザは、要約バーチャート４１及び４２を見るだけで、スコアが大きい局所対応が存在する部分や、多くの局所対応が存在する部分をすぐに見つけることができる。要約バーチャート４１及び４２中でマウスをクリックすると、局所対応表示エリア２１１でも対応する部分が頭出しされて表示される。
【００７１】
以下に、要約バーチャート生成処理について説明する。要約バーチャート生成処理は、局所対応表示制御部１０６によって実行される。
【００７２】
なお、局所対応表示制御部１０６による要約バーチャート生成処理は、局所対応抽出部１０５によって抽出された局所対応が局所対応表示制御部１０６に入力された後に実行される。
【００７３】
ここで、局所対応は始点と終点とを有し、始点は局所対応表示エリア２１１に表示される矩形２１２の左上点の座標（ｂｒ，ｂｃ）に相当し、終点は矩形２１２の右下点の座標（ｅｒ，ｅｃ）に相当する。また、局所対応のスコアをＳとし、局所対応表示エリア２１１に表示されるすべての矩形２１２（局所対応）の中で最大のスコアの局所対応のスコアをＳｍａｘという。
【００７４】
まず、局所対応表示制御部１０６は、各局所対応の透明度を、各局所対応のスコアＳ及び最大スコアＳｍａｘに基づいて決定する。透明度は０〜２５５で示され、透明度が０であれば完全な透明で、透明度が２５５であれば完全な不透明である。
【００７５】
各局所対応の透明度は、当該局所対応のスコアＳが大きければ大きいほど不透明であるように決定される。これによって、要約バーチャート４１及び４２ではスコアＳの大きい局所対応ほど濃い色で表示されるようになり、ユーザが注視しやすくなる。
【００７６】
具体的には、最大スコアＳｍａｘの局所対応の透明度Ｔｍａｘが予め設定されていれば、局所対応表示制御部１０６は、各局所対応の透明度Ｔを透明度Ｔｍａｘに基づいて等比配分することによって決定する。換言すれば、局所対応表示制御部１０６は、透明度ＴをＴｍａｘ＊（Ｓ／Ｓｍａｘ）を計算することによって決定する。
【００７７】
次に、局所対応表示制御部１０６は、要約バーチャート４１において、矩形２１２の始点のｙ座標ｂｃから終点のｙ座標ｅｃまでの範囲を当該矩形２１２の局所対応の透明度Ｔで塗りつぶす。また、局所対応表示制御部１０６は、要約バーチャート４２において、矩形２１２の始点のｘ座標ｂｒから終点のｘ座標ｅｒまでの範囲を当該矩形２１２の局所対応の透明度Ｔで塗りつぶす。局所対応表示制御部１０６は、当該処理をすべての局所対応に対して実行する。ここで、局所対応表示制御部１０６は、要約バーチャート４１及び４２で局所対応が重複する箇所については重複する局所対応の透明度Ｔを加算し、加算した透明度で塗りつぶすので、当該個所の色を濃く表示する。
【００７８】
なお、以上の処理では、各局所対応の透明度Ｔは各局所対応のスコアに比例した値である。このため、要約バーチャート４１及び４２で色が濃い箇所は、当該個所に対応する局所対応のスコアが大きいか、又は、当該個所で局所対応が重複しているかである。いずれの場合であっても、要約バーチャート４１及び４２で色が濃い箇所には、ユーザにとって重要な局所対応が存在することを意味する。しかし、ユーザは、スコアが大きい局所対応は局所対応表示エリア２１１で矩形２１２の面積が大きくなるため、ユーザはスコアが大きい局所対応を見つけやすいが、縦方向及び横方向に重複する局所対応は局所対応表示エリア２１１で見つけにくいという観点で、局所対応が重複する箇所のみを知りたい場合もある。
【００７９】
このため、局所対応表示制御部１０６は、局所対応の透明度Ｔを当該局所対応のスコアＳを用いて決定するのではなく、すべての局所対応の透明度Ｔを所定値に設定し、局所対応が縦方向又は横方向に重複する場合、重複する局所対応の透明度Ｔを加算し、加算した透明度で塗りつぶしてもよい。
【００８０】
これによって、要約バーチャート４１及び４２の色の濃さは、スコアに依存せず、重複する局所対応の数に依存するので、ユーザは、縦方向及び横方向に重複する局所対応は局所対応表示エリア２１１で見つけやすくなる。
【００８１】
次に、局所対応抽出部１０５が局所対応を抽出する処理について説明する。
【００８２】
局所対応の抽出では、前述したように、代表的な局所対応のみを網羅的に抽出することが課題となる。本発明では、既存のＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法に、始点一致による枝刈りを組み込むことによって、前述の課題を解決する。
【００８３】
図５は、本発明の第１の実施形態の二つの文字列間におけるスコアの説明図である。
【００８４】
文字列Ａ「特許の検索精度の向上」と文字列Ｂ「特許検索の精度の向上」との間の各文字が対応付けられる。この各文字単位の対応をアラインメントという。アラインメントには、対応する文字同士が一致する一致アラインメント、及び、対応する文字同士が一致しない不一致アラインメントがある。図５では、「を」と「の」とのアラインメント５０が不一致アラインメントであり、その他のアラインメントは一致アラインメントである。
【００８５】
文字列Ａ及び文字列Ｂのすべての文字でアラインメントがあるわけではない。図５では、文字列Ａの「の」（５１）及び文字列Ｂの「の」（５２）はいずれの文字にも対応付けられていない。このアラインメントがない文字は当該文字が読み飛ばされたことを意味し、これを以下読み飛ばしという。
【００８６】
一致アラインメント、不一致アラインメント、及び読み飛ばしには、予め所定値が設定されている。図５では、一致アラインメントには＋２点、不一致アラインメントには−２点、読み飛ばしには−１点が設定されているとする。この場合、文字列Ａと文字列Ｂとの間でこれらの値を合計した値（スコア）は１２点になり、このスコアが文字列Ａと文字列Ｂとの類似度となる。
【００８７】
また、局所対応は、対象文字列中でスコアが局所的に大きくなる部分文字列対であり、局所対応抽出部１０５によって抽出される。局所対応抽出部１０５は、一致アラインメント、不一致アラインメント、及び読み飛ばしに設定された値次第で、異なる局所対応を抽出する。
【００８８】
なお、ユーザは、図２に示す一致スコア入力ボックス２０２、不一致スコア入力ボックス２０３、及び読み飛ばしスコア入力ボックス２０４を介して、一致アラインメント、不一致アラインメント、及び読み飛ばしの値に所望の値を設定できる。
【００８９】
また、不一致アラインメントの値は、不一致アラインメントの文字の種類によって異なるものであってもよい。例えば、不一致アラインメントの文字の種類が助詞である場合の値は、不一致アラインメントの文字の種類が助詞以外である場合の値よりも低く設定されてもよい。
【００９０】
また、文字列において出現回数の多い部分文字列はユーザにとって重要である可能性が高いため、局所対応抽出部１０５が出現回数を把握できるように、スコアに出現回数を含ませてもよい。これによって、局所対応抽出部１０５は、出現回数が所定値以上である部分文字列のスコアに１以上の所定値を乗算することによって、出現回数が所定値未満の部分文字列よりもスコアを大きくできる。
【００９１】
本実施形態では、局所対応抽出部１０５が対象文字列のスコアを算出して、局所対応を抽出するために、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法を用いる。Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法は動的計画法によって効率良くスコアを算出する方法である。
【００９２】
以下に、本実施形態のスコア算出方法について図６を用いて説明する。
【００９３】
図６は、本発明の第１の実施形態のスコア行列の説明図である。
【００９４】
局所対応抽出部１０５は、二つの対象文字列のうち一方の対象文字列を行に配置し、他方の対象文字列を列に配置する。そして、局所対応抽出部１０５は、行列のセルのスコアを左上のセルから順番に計算して、計算したスコアをセルに登録して、スコア行列を生成する。
【００９５】
なお、行列のセルは、当該セルに対応する行の文字と当該セルに対応する列の文字とに対応する。また、各セルに登録されるスコアは、当該セルまでのスコアの合計値である。
【００９６】
ここで、スコアの算出方法について、図７を用いて説明する。
【００９７】
図７は、本発明の第１の実施形態のスコア算出方法の説明図である。
【００９８】
あるセルのスコアを算出する場合、局所対応抽出部１０５は、算出対象のセルに隣接し、かつすでにスコアが算出されたセルから算出対象のセルまでの各パスごとのスコアを算出し、算出したスコアのうち最大のスコアを算出対象のセルに登録する。
【００９９】
以下、図７のセル７３のスコアを算出する場合について具体的に説明する。
【０１００】
セル７３に隣接し、かつすでにスコアが算出されたセルは、セル７０、７１、および７２である。セル７３の真上に位置するセル７１からのパスを第１パス７４とし、セル７３の左上に位置するセル７０からのパスを第２パス７５とし、セル７３の左に位置するセル７２からのパスを第３パス７６とする。
【０１０１】
まず、第１パス７４を経由した場合のセル７３のスコアについて説明する。
【０１０２】
算出対象のセル７３の真上に位置するセル７１に対応する文字は「検」（７０２）及び「許」（７０３）であり、セル７３に対応する文字は「検」（７０２）及び「検」（７０４）である。当該セル７１で「検」（７０４）が読み飛ばされたことになる。つまり、「検」（７０２）は変化せず、真上のセルから算出対象のセルまでのパスは、行の文字は変化せずに、列の文字が変化することになり、当該列の「検」（７０４）が読み飛ばされたこと（読み飛ばし）を意味する。
【０１０３】
ここで、読み飛ばしには「−１」が予め設定されているので、第１パス７４を経由した場合のセル７３のスコアは、セル７１のスコアの値「２」に、第１パス７４に設定された値（読み飛ばしに設定された値）「−１」を加算し、「１」と算出される。
【０１０４】
次に、第３パス７６を経由した場合のセル７３のスコアについて説明する。
【０１０５】
算出対象のセル７３の左に位置するセル７２に対応する文字は「を」（７０１）及び「検」（７０４）であり、セル７３に対応する文字は「検」（７０２）及び「検」（７０４）である。当該セル７０の段階で「検」（７０２）が読み飛ばされたことになる。つまり、左のセルから算出対象のセルまでのパスは、列の文字は変化せずに、行の文字が変化することになり、当該行の「検」（７０２）が読み飛ばされたこと（読み飛ばし）を意味する。
【０１０６】
ここで、読み飛ばしには「−１」が予め設定されているので、第３パス７６を経由した場合のセル７３のスコアは、セル７２のスコアの値「２」に、第３パス７６に設定された値（読み飛ばしに設定された値）「−１」を加算し、「１」と算出される。
【０１０７】
次に、第２パス７５を経由した場合のセル７３のスコアについて説明する。
【０１０８】
左上に位置するセル７０に対応する文字は「を」（７０１）及び「許」（７０３）であり、セル７３に対応する文字は「検」（７０２）及び「検」（７０４）である。この場合、左上に位置するセル７０に対応する行の文字及び列の文字と、セル７３に対応する行の文字及び列の文字とが異なるので読み飛ばしではない。第２パス７５は、セル７３に対応する行の文字と列の文字とが一致する場合、一致アラインメントを意味し、セル７３に対応する行の文字と列の文字とが一致しない場合、不一致アラインメントを意味する。なお、図７では、セル７３に対応する行の文字「検」（７０４）と列の文字（７０２）とは一致するので、第２パス７５は一致アラインメントを意味する。
【０１０９】
ここで、一致アラインメントには「２」が予め設定され、不一致アラインメントには「−２」が予め設定されている。第２パス７５を経由した場合のセル７３のスコアは、セル７０のスコアの値「３」に、一致アラインメントに設定された値「２」を加算し、「５」と算出される。
【０１１０】
以上のように、第１パス７４〜第３パス７６を経由した場合のセル７３のスコアが算出される。そして、算出されたスコアから最大のスコアのパスが選択され、当該最大のスコアがセル７３に登録される。図７では、第２パス７５を経由した場合のスコア「５」が最大となるので、セル７３にはスコア「５」が登録される。
【０１１１】
以上のように、局所対応抽出部１０５は、図６に示す左上端のセルから順に横方向にスコアを登録する。そして、局所対応抽出部１０５は、一行のすべてのセルにスコアを登録した場合、次の行の左端のセルから順にスコアを登録する。このため、算出対象のセルの左のセル、左上のセル、及び左のセルのスコアは必ず登録されていることになる。
【０１１２】
また、局所対応抽出部１０５は、初期化処理として、行に対応する対象文字列（図６に示す「精度向上の特許を検索」）の先頭文字の前に列を一列挿入し、列に対応する対象文字列（図６に示す「特許検索の精度の向上」）の先頭文字の前に行を一列挿入する。この挿入された行及び列は初期行列という。そして、局所対応抽出部１０５は、初期行列のセルにスコア「０」を予め登録する。
【０１１３】
ここで、従来のＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法を用いた局所対応抽出処理の問題点について説明する。
【０１１４】
図７で説明したスコア算出方法によって図６に示すスコア行列が生成された後、スコア行列のセルから最大のスコアが登録されたセルが選択される。当該選択されたセルまでのパスを逆順に辿ることによって、最大のスコアの局所対応が抽出される。
【０１１５】
図６では、最大のスコアは「７」であり、最大のスコアが登録されたセルはセル６０及び６１である。セル６０からパスを逆順に辿ることによって、対象文字列（「精度向上の特許を検索」）からは「特許を検索」が抽出され、セル６１からパスを逆順に辿ることによって、対象文字列（「特許検索の精度の向上」）からは「特許検索」が抽出される。なお、「特許を検索」及び「特許検索」が局所対応である。
【０１１６】
この場合、スコア行列の中で最大スコアの局所対応しか抽出できず、最大スコアよりも低い局所対応は抽出できない。例えば、図６において、仮に、「特許を検索」及び「特許検索」のスコアが「７」で、「精度向上」及び「精度の向上」のスコアが「６」であるとすると、「精度向上」及び「精度の向上」は局所対応として抽出されない。したがって、スコア行列生成後に最大のスコアが登録されたセルからパスを逆順に辿る方法では、代表的な局所対応しか抽出できず、局所対応を網羅的に抽出できない。
【０１１７】
このため、スコアが所定値以上のセルを抽出し、抽出したセルからパスを逆順に辿ることによって、局所対応を抽出する方法が考えられる。しかしながら、この方法では、網羅的に局所対応を抽出できるが、局所対応を重複して抽出してしまい、抽出される局所対応が冗長となってしまう。
【０１１８】
図６で、抽出するセルのスコアの所定値が「６」に設定された場合、セル６２及び６３が抽出される。この場合、セル６２からパスを逆順に辿ることによって抽出される局所対応は、「特許を検索」と「特許検索の」である。この「特許検索の」は、本来「特許を検索」と対応する局所対応として抽出されるべき文字列「特許検索」の末尾に「の」を追加しただけの文字列であり、本来の局所対応「特許検索」のバリエーションにすぎない。
【０１１９】
本来の局所対応として抽出される文字列の最後の文字は、スコアが最大となるセルに対応する文字である。一致のアラインメントであればスコアを加算し、不一致のアラインメント及び読み飛ばしであればスコアが減少するように設定されている場合、二つの対象文字列の各文字が一致していればスコアは増加し、その他の場合スコアは減少するためであり、スコアが減少せずスコアが最大となる文字が最後の文字が本来の局所対応として抽出される文字列の最後の文字となる。
【０１２０】
前述した方法では、スコアが最大となるセルの周辺のセルに対応する文字が局所対応の最後の文字として抽出されてしまう場合があり、この局所対応は本来の局所対応のバリエーションにすぎず、抽出された局所対応は冗長化してしまう。
【０１２１】
本実施形態では、局所対応抽出部１０５は、スコア行列を生成する際に算出したスコアが、当該算出したスコアのセルが属する局所対応内における最大スコアよりも大きい場合、当該算出したスコアのセルを局所対応の終点として登録する。なお、算出したスコアのセルが属する局所対応を構成するセルは、当該算出したスコアに至るまでのパスの始点と同じ始点からのすべてのパスが経由するセルである。この処理を、始点一致による枝刈りという。
【０１２２】
これによって、本来の局所対応のバリエーションを抽出せず、冗長化しない局所対応を網羅的に抽出できる。
【０１２３】
なお、対象文字列が長くなり、スコア行列のサイズが大きくなると、スコア行列を生成してから始点一致による枝刈りを実行すると、始点が同じパスを探索するための計算量が増大してしまう。このため、本実施形態では、局所対応抽出処理をスコア行列の生成と同時に実行するので、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法による局所対応抽出処理とほぼ同じ計算量で局所対応を抽出できる。
【０１２４】
図８〜図１１を用いて本実施形態の局所対応抽出処理を説明する。
【０１２５】
図８は、本発明の第１の実施形態の初期化処理の説明図である。
【０１２６】
初期化処理は、局所対応抽出部１０５によって実行される。
【０１２７】
まず、局所対応抽出部１０５は、二つの対象文字列を登録し、一致スコア、不一致スコア、及び読み飛ばしスコアを設定する（Ｓ８０１）。
【０１２８】
具体的には、二つの対象文字列は、配列Ｘ［ｌ．．ｌｘ］及び配列Ｙ［ｌ．．ｌｙ］によって表現される。便宜上、各対象文字列の先頭文字は各配列の要素１に登録される。また、各対象文字列の長さは１ｘ及び１ｙである。
【０１２９】
また、局所対応抽出部１０５は、図２に示す一致スコア入力ボックス２０２、不一致スコア入力ボックス２０３、及び読み飛ばしスコア入力ボックス２０４に入力された値を、一致スコア（Ｍａｔｃｈ）、不一致スコア（Ｕｎｍａｔｃｈ）、及び読み飛ばしスコア（Ｓｋｉｐ）に設定する。
【０１３０】
次に、局所対応抽出部１０５は、スコア行列を初期化する（Ｓ８０２）。スコア行列は、図６で説明した行列であり、Ｍ［０．．ｌｘ］［０．．ｌｙ］で表現される。［０．．ｌｘ］が配列Ｘによって表現される対象文字列に相当し、［０．．ｌｙ］が配列Ｘによって表現される対象文字列に相当する。
【０１３１】
また、配列Ｘのｉ番目の文字Ｘ［ｉ］及び配列Ｙのｊ番目の文字Ｙ［ｊ］に対応するセルはＭ［ｉ］［ｊ］である。スコア行列の各セルには図６と同じく、そのセルへ至るパスのスコア合計値が登録される。また、局所対応抽出部１０５は、スコア行列の０行目のセル及び０行目の列にスコア「０」を登録する。
【０１３２】
次に、局所対応抽出部１０５は、局所対応を初期化する（Ｓ８０３）。局所対応は、始点配列Ｂ、終点配列Ｅ、スコア配列Ｓの三つの配列によって表現される。局所対応の一意な識別子であるＩＤは、これらの配列のインデックスに相当する。
【０１３３】
始点配列Ｂには、各局所対応の始点の座標が登録され、終点座標Ｅには、各局所対応の終点の座標が登録される。ここで、座標とは、スコア行列のインデックス対のことである。例えば、配列Ｘのi番目の文字Ｘ［ｉ］及び配列Ｙのｊ番目の文字Ｙ［ｊ］が始点である場合、始点の座標は（ｉ，ｊ）である
。
【０１３４】
スコア配列Ｓには、各局所対応のスコアが登録される。スコア配列Ｓには、初期値として０が登録される。
【０１３５】
ＩＤがｉである局所対応の始点座標はＢ［ｉ］であり、終点座標はＥ［ｉ］であり、当該局所対応のスコアはＳ［ｉ］である。
【０１３６】
本実施形態では、局所対応に関する情報として、始点情報、終点情報、及びスコア情報が記憶されるが、局所対応のパス情報（アラインメント）も記憶してもよい。
【０１３７】
図９は、本発明の第１の実施形態の局所対応収集処理の説明図である。
【０１３８】
局所対応抽出部１０５は、図８に示す初期化処理を実行した後、局所対応収集処理を実行する。
【０１３９】
まず、局所対応抽出部１０５は、局所対応のＩＤが登録される変数ａを０に初期化する（Ｓ９０１）。
【０１４０】
局所対応のＩＤは、前述したように、局所対応の始点配列Ｂ、終点配列Ｅ、スコア配列Ｓのインデックスに相当する。Ｓ９０１では、局所対応が未抽出であるため、局所対応抽出部１０５は、局所対応のＩＤを０に初期化する。
【０１４１】
次に、局所対応抽出部１０５は、図１０に示す始点行列を初期化する（Ｓ９０２）。始点行列のセルはスコア行列のセルと対応しており、始点行列のセルには、当該セルが属する局所対応のＩＤが登録される。
【０１４２】
Ｓ９０２では、局所対応抽出部１０５は、始点行列のすべてのセルに初期値「−１」を登録する。始点行列の局所対応のＩＤが「−１」であることは、当該セルはいずれの局所対応にも属さないことを意味する。
【０１４３】
ここで、始点行列について、図１０を用いて説明する。図１０は、本発明の第１の実施形態の始点行列の説明図である。
【０１４４】
始点行列の各セルの座標は図６に示すスコア行列の座標と同じであり、各セルにはセルが属する局所対応のＩＤが登録される。なお、前述したように各セルには初期値として「−１」が登録されるため、「−１」が登録されているセルは、いずれの局所対応にも属さない。
【０１４５】
次に、局所対応抽出部１０５は、処理対象となるスコア行列の行を選択する（Ｓ９０３）。
【０１４６】
具体的には、局所対応抽出部１０５は、スコア行列の行のうち対象文字列の先頭の文字列に対応する行（配列Ｙの最初のインデックスに対応する行）を処理対象の行として選択し、当該処理対象の行にＳ９０４〜Ｓ９０６を実行する。局所対応抽出部１０５は、Ｓ９０４〜Ｓ９０６の処理を実行すると、選択した行の次の行（下の行）を処理対象の行として選択する。局所対応抽出部１０５は、Ｓ９０４〜Ｓ９０６がすべての行に実行されるまで繰り返す。
【０１４７】
次に、局所対応抽出部１０５は、処理対象の行に含まれる列から処理対象の列を選択する（Ｓ９０４）。
【０１４８】
具体的には、局所対応抽出部１０５は、処理対象の行に含まれる列のうち対象文字列の先頭の文字列に対応する列（配列Ｘの最初のインデックスに対応する行）を処理対象の列として選択し、当該処理対象の列にＳ９０５〜Ｓ９０６を実行する。局所対応抽出部１０５は、Ｓ９０５〜Ｓ９０６の処理を実行すると、選択した列の次の列（右の列）を処理対象の列として選択する。局所対応抽出部１０５は、Ｓ９０５〜Ｓ９０６が処理対象の行に含まれるすべての列に実行されるまで繰り返す。
【０１４９】
Ｓ９０３及びＳ９０４によって、スコア行列のセルからＳ９０５及び９０６の実行対象となるセル（以下、処理対象のセルという）が決まり、スコア行列のすべてのセルに対してＳ９０５及び９０６が実行される。
【０１５０】
次に、局所対応抽出部１０５は、処理対象のセルのスコアを算出する（Ｓ９０５）。
【０１５１】
具体的には、局所対応抽出部１０５は、図９のＳ９０５の１〜４に示すパスのスコアを算出し、算出したスコアから最大のスコア（Ｓｍａｘ）を選択して、選択した最大のスコアを処理対象のセル（Ｍ［ｒ］［ｃ］）に登録する。この場合、局所対応抽出部１０５は、パスの遷移元のセルの座標を（ｒ１、ｃ１）として記憶する。
【０１５２】
以下に、図９のＳ９０５の１〜４に示すパスについて説明する。
【０１５３】
Ｓ９０５の１は、スコアの最大値がマイナスの値にならないようにするためのものであり、スコアが「０」に設定されている。
【０１５４】
Ｓ９０５の２は、処理対象のセル（ｒ、ｃ）の真上に位置するセル（ｒ−１、ｃ）からの遷移で、縦方向の文字の読み飛ばしに相当する。この場合の処理対象のセルのスコアは、遷移元のセル（ｒ−１、ｃ）のスコア（Ｍ［ｒ−１］、［ｃ］）に読み飛ばしスコア（Ｓｋｉｐ）を加算することによって算出される。
【０１５５】
Ｓ９０５の３は、処理対象のセル（ｒ、ｃ）の左に位置するセル（ｒ、ｃ−１）からの遷移で、横方向の文字の読み飛ばしに相当する。この場合の処理対象のセルのスコアは、遷移元のセル（ｒ、ｃ−１）のスコア（Ｍ［ｒ］、［ｃ−１］）に読み飛ばしスコア（Ｓｋｉｐ）を加算することによって算出される。
【０１５６】
Ｓ９０５の４は、処理対象のセル（ｒ、ｃ）の左上に位置するセル（ｒ−１、ｃ−１）からの遷移で、処理対象のセルに対応する二つの文字（配列Ｘ［ｒ］と配列Ｙ［ｃ］）が一致するか否かで算出するスコアが異なる。
【０１５７】
処理対象のセルに対応する二つの文字が一致する場合の処理対象のセルのスコアは、遷移元の遷移元のセル（ｒ−１、ｃ−１）のスコア（Ｍ［ｒ−１］、［ｃ−１］）に一致スコア（Ｍａｔｃｈ）を加算することによって算出される。
【０１５８】
一方、処理対象のセルに対応する二つの文字が一致しない場合の処理対象のセルのスコアは、遷移元の遷移元のセル（ｒ−１、ｃ−１）のスコア（Ｍ［ｒ−１］、［ｃ−１］）に不一致スコア（Ｕｎｍａｔｃｈ）を加算することによって算出される。
【０１５９】
Ｓ９０５によってスコア行列のセルにスコアが登録されるので、Ｓ９０５をスコア行列生成処理という。
【０１６０】
次に、局所対応抽出部１０５は、Ｓ９０５で算出された処理対象のセルの最大のスコアＳｍａｘに基づいて、当該処理対象のセルの座標を局所対応の終点に設定するか否かを決定する枝刈り処理を実行する（Ｓ９０６）。
【０１６１】
以下、枝刈り処理について詳細に説明する。
【０１６２】
まず、局所対応抽出部１０５は、Ｓ９０５で算出された処理対象のセルの最大のスコアＳｍａｘが「０」であるか否かを判定する。
【０１６３】
Ｓ９０５で算出された処理対象のセルの最大のスコアＳｍａｘが「０」である場合、局所対応抽出部１０５は、当該セルに対応する文字は局所対応に属さないので、Ｓ９０４の処理に戻り、次の処理対象の列を選択する。
【０１６４】
一方、Ｓ９０５で算出された処理対象のセルの最大のスコアＳｍａｘが「０」でない場合、局所対応抽出部１０５は、図１０に示す始点行列のうち遷移元のセルに登録された局所対応のＩＤを取得する。具体的には、局所対応抽出部１０５は、始点行列のセルのうち遷移元のセルの座標（ｒ１、ｃ１）に対応するセルに登録された局所対応のＩＤ（Ｐ［ｒ１］［ｃ１］）を取得する。なお、局所対応抽出部１０５は、取得した局所対応のＩＤをｋとして記憶する。
【０１６５】
そして、局所対応抽出部１０５は、取得した遷移元のセルの局所対応のＩＤが「−１」であるか否かを判定する。
【０１６６】
取得した遷移元のセルの局所対応のＩＤが「−１」である場合、処理対象のセルから新たな局所対応が始まるので、局所対応抽出部１０５は、新たな局所対応を設定する。
【０１６７】
具体的には、局所対応抽出部１０５は、始点行列のセルのうち処理対象のセルの座標（ｒ、ｃ）に対応するセルの局所対応ＩＤ（Ｐ［ｒ］［ｃ］）に新たな局所対応のＩＤ（ａ）を登録する。また、局所対応抽出部１０５は、処理対象のセルの座標（ｒ、ｃ）を始点配列Ｂ［ａ］及び終点配列Ｅ［ａ］に登録する。そして、局所対応抽出部１０５は、新たな局所対応のＩＤ（ａ）をインクリメントしておく。このように、新たな局所対応のＩＤ（ａ）は、新たに局所対応があった場合に備えて、局所対応が見つかるとインクリメントされる。
【０１６８】
一方、取得した遷移元のセルの局所対応のＩＤが「−１」でない場合、処理対象のセルは遷移元のセルと同じ局所対応に属するため、局所対応抽出部１０５は、始点行列のセルのうち処理対象のセルの座標（ｒ、ｃ）のセルに、遷移元のセルと同じ局所対応のＩＤ（ｋ）を登録する。つまり、始点行列のセルの局所対応のＩＤ（Ｐ［ｒ］［ｃ］）には、遷移元のセルの局所対応のＩＤ（Ｐ［ｒ１］［ｃ１］）が登録される。
【０１６９】
そして、局所対応抽出部１０５は、遷移元のセルの局所対応のＩＤ（ｋ）のスコア配列Ｓ［ｋ］に登録されたスコア（局所対応最大スコア）を取得し、処理対象のセルの最大のスコア（Ｓｍａｘ）が局所対応最大スコア（Ｓ［ｋ］）よりも大きいか否かを判定する。
【０１７０】
処理対象のセルの最大のスコア（Ｓｍａｘ）が局所対応最大スコア（Ｓ［ｋ］）よりも大きいと判定された場合、局所対応抽出部１０５は、処理対象のセルを終点にするために処理対象のセルの座標（ｒ、ｃ）を終点配列Ｅ［ｋ］に登録し、処理対象のセルの最大のスコアをスコア配列Ｓ［ｋ］に登録する。
【０１７１】
一方、処理対象のセルの最大のスコア（Ｓｍａｘ）が局所対応最大スコア（Ｓ［ｋ］）以下であると判定された場合、局所対応抽出部１０５は、Ｓ９０４の処理に戻り、次の処理対象の列を選択する。
【０１７２】
なお、Ｓ９０６で始点行列のセルに当該セルが属する局所対応のＩＤが登録されるので、Ｓ９０６を始点行列生成処理という。
【０１７３】
以上によって、局所対応抽出部１０５は、スコア行列の各セルのスコアを算出しながら、局所対応を収集する。なお、各局所対応の始点、終点、及び局所対応最大スコアは、それぞれ始点配列Ｂ、終点配列Ｅ、及びスコア配列Ｓに記憶される。これによって、局所対応抽出部１０５によって抽出される局所対応は、始点が一致する局所対応内でスコアが最大の文字が終点となるので、代表性が保証される。
【０１７４】
図１１は、本発明の第１の実施形態の局所対応抽出処理のフローチャートである。
【０１７５】
局所対応抽出処理は、図９に示す局所対応収集処理が実行された後に、局所対応抽出部１０５によって実行される処理であり、局所対応収集処理で収集された局所対応のうち局所対応最大スコアが所定値よりも大きい局所対応を抽出する処理である。
【０１７６】
まず、局所対応抽出部１０５は、図２及び図３に示すスコア閾値入力エリア２０６に入力されたスコア閾値の入力を受け付け、受け付けたスコア閾値をｔｈｒｅｓｈｏｌｄとして記憶する（Ｓ１１０１）。
【０１７７】
次に、局所対応抽出部１０５は、Ｓ１１０３の処理対象となる局所対応のＩＤを選択する（Ｓ１１０２）。ここで、Ｓ１１０２の処理で処理対象の局所対応のＩＤとして選択したＩＤを「ｉ」とする。
【０１７８】
具体的には、局所対応抽出部１０５は、局所対応のＩＤが「０」から順に選択し、局所対応のＩＤが「ａ」の局所対応にＳ１１０３の処理が実行されるまで繰り返す。
【０１７９】
次に、局所対応抽出部１０５は、Ｓ１１０２の処理で選択された局所対応のＩＤによって特定される局所対応の局所対応最大スコアがスコア閾値よりも大きいか否かを判定する。
【０１８０】
具体的には、局所対応抽出部１０５は、Ｓ１１０２の処理で選択された局所対応のＩＤ「ｉ」に対応するスコア配列Ｓ［ｉ］に登録された局所対応最大スコアがスコア閾値よりも大きいか否かを判定する。
【０１８１】
Ｓ１１０２の処理で選択された局所対応のＩＤによって特定される局所対応の局所対応最大スコアがスコア閾値よりも大きいと判定された場合、局所対応抽出部１０５は、当該局所対応のＩＤによって特定される局所対応を局所対応として抽出する（Ｓ１１０３）。
【０１８２】
例えば、局所対応のＩＤ「ｉ」によって特定される局所対応が局所対応として抽出され、当該抽出された局所対応の始点配列Ｂ［ｉ］の座標が（ｒ１、ｃ１）であり、終点配列Ｅ［ｉ］の座標が（ｒ２、ｃ２）である場合、一方の対象文字列の配列Ｘ［ｒ１．．ｒ２］が示す部分文字列、及び他方の対象文字列の配列Ｙ［ｃ１．．ｃ２］が示す部分文字列が局所対応となる。
【０１８３】
したがって、局所対応抽出部１０５は局所対応最大スコアが所定値よりも大きい局所対応を抽出し、この抽出された局所対応が局所対応表示制御部１０６によって表示される。ここで、局所対応最大スコアが小さい局所対応は、始点の座標と終点の座標との距離が短く（つまり、局所対応の面積が小さく）、局所対応最大スコアが大きい局所対応は、始点の座標と終点の座標との距離が長い（つまり、局所対応の面積が大きい）。このため、図１１に示す局所対応抽出処理が実行されることによって、局所対応表示制御部１０６は、あまりにも面積が小さい局所対応を図２に示す局所対応表示エリア２１１に表示しないので、局所対応表示エリア２１１の表示が煩雑になることを防止できる。
【０１８４】
なお、本実施形態では、局所対応抽出部１０５が、図１１に示す局所対応抽出処理を実行したが、局所対応表示制御部１０６が実行してもよい。具体的には、局所対応抽出部１０５は、図９に示す局所対応収集処理で収集されたすべての局所対応を局所対応として抽出する。そして、局所対応表示制御部１０６は、抽出された局所対応に対して図１１に示す局所対応抽出処理を実行して、局所対応最大スコアがスコア閾値よりも大きい局所対応のみを表示するようにしてもよい。
【０１８５】
（第２の実施形態）
以下、本発明の第２の実施形態を図１２〜図１５を用いて説明する。
【０１８６】
本実施形態は、網羅性を向上させるための処理（最大ギャップ長制約処理）を第１の実施形態の局所対応処理に追加した実施形態である。
【０１８７】
まず、第１実施形態による局所対応処理では所望の局所対応が抽出できない場合について説明する。図１２は、二つの文字列間に本発明の第１の実施形態の局所対応処理を実行し、局所対応が抽出されない場合の説明図である。
【０１８８】
図１２では、文字列Ｃ「ａａａａａ１２３４ｂｂｂ」と文字列Ｄ「ａａａａａ１２３４ｂｂｂ」との間で、第１の実施形態による局所対応処理によって局所対応を抽出する場合について説明する。
【０１８９】
この場合、文字列Ｃ及び文字列Ｄの間で共通する「ａａａａａ」及び「ｂｂｂ」が局所対応として抽出されると直観的に想定される。
【０１９０】
しかしながら、図９に示す第１の実施形態による局所対応収集処理では、「ａａａａａ」しか局所対応として抽出されない。
【０１９１】
これについて以下に具体的に説明する。
【０１９２】
文字列Ｃ及び文字列Ｄ間で「ａａａａａ」部分が一致するため、５番目の「ａ」のスコアが「１０」となる（１２０１）。この後、文字列Ｃの「１２３４」部分と文字列Ｄ「５６７８」部分とが一致しないので、スコアは「−２」ずつ減少し、文字列Ｃの「４」及び文字列Ｄの「８」に対応するスコアは「２」となる（１２０２）。そして、文字列Ｃ及び文字列Ｄで「ｂｂｂ」部分が一致するため、３番目の「ｂ」のスコアは「８」となる。
【０１９３】
ここで、前述したように、図９に示すＳ９０５では、処理対象のセルの最大スコアＳｍａｘが０よりも大きい場合であって、当該処理対象のセルの遷移元のセルの局所対応のＩＤが「−１」である場合、当該処理対象のセルから新たな局所対応が開始することとなる。図９に示すＳ９０５では、処理対象のセルの最大スコアＳｍａｘが０である場合、局所対応抽出部１０５は当該セルに対して何もしないため、始点行列の処理対象のセルには、初期値「−１」が登録されたままとなっている。
【０１９４】
このため、図９に示す局所対応収集処理では、処理対象のセルの最大スコアが０よりも大きい値で、遷移元のセルの最大スコアＳｍａｘが０である場合にのみ、新たな局所対応が開始される。すなわち、セルの最大スコアがいったん０より大きくなると、最大スコアが０になるセルがあるまで同じ局所対応に属することになる。
【０１９５】
したがって、一度最大スコアが大きくなると、最大スコアが０になるまでの間に新たな局所対応が存在しても抽出できず、当該新たな局所対応は隠匿されてしまう。
【０１９６】
図１２では、１２０１のスコア「１０」が一番目の「ｂ」までに「０」まで減衰しないため、「ｂｂｂ」を新たな局所対応として抽出できない。
【０１９７】
図１３は、酷似する二つの文書に第１の実施形態の局所対応処理を実行することによって抽出された局所対応の表示例である。
【０１９８】
局所対応処理によって抽出された局所対応は、局所対応表示制御部１０６によって、図２に示す局所対応表示エリア２１１に二次元マップ表示される。局所対応は、局所対応最大スコアが大きいほど大きな矩形で局所対応表示エリア２１１に表示される。
【０１９９】
図１３に示す１３０１は、二つの文書の局所対応のうち最大の局所対応を示す。当該最大の局所対応の右下には局所対応が抽出されていない空白部分が存在する（１３０２）。最大の局所対応の局所対応最大スコアが大きいため、後方（右下部）のスコアが０に減衰しないため、この部分に局所対応があっても新たな局所対応として抽出されない。
【０２００】
つまり、第１の実施形態の局所対応収集処理では、始点一致による枝刈りによって、局所対応の代表性を重視するあまり、局所対応が網羅的に抽出されないという問題が生ずる。
【０２０１】
そこで、本実施形態では、最大ギャップ長制約を行うことによって前述の問題を解決する。
【０２０２】
ここで、ギャップ長とは、局所対応の終点から不一致又は読み飛ばしが連続する文字数である。ここで、図１２に示す文字列Ｃ「ａａａａａ１２３４ｂｂｂ」及び文字列Ｄ「ａａａａａ５６７８ｂｂｂ」の場合、５番目の「ａ」のスコアが「１０」で局所対応最大スコアとなるため、５番目の「ａ」が局所対応の終点となる。そして、終点である５番目の「ａ」から「１２３４」と「５６７８」とが一致しないので、ギャップ長は４となる。
【０２０３】
最大ギャップ長制約は、局所対応のギャップ長が所定値（最大ギャップ長）以下であるとの制約である。図１２では、ギャップ長の所定値が「３」に設定されていれば、「１２３４」と「５６７８」とが一致しないと判定された時点で、「ａａａａａ」の局所対応は、文字列Ｃでは「４」、文字列Ｄでは「８」以降まで継続し得ないため、当該個所で局所対応がリセットされる。このため、後方の「ｂｂｂ」が新たな局所対応として抽出できる。
【０２０４】
図１４を用いて、最大ギャップ長制約の詳細について説明する。
【０２０５】
図１４は、本発明の第２の実施形態の局所対応収集処理の説明図である。
【０２０６】
最大ギャップ長制約を実現するためには、第１の実施形態の図９に示す局所対応収集処理に最大ギャップ長制約処理を追加するだけでよい。図１４に示す処理のうち、図９に示す処理と同じ処理は同じ符号を付与し、説明を省略する。
【０２０７】
まず、局所対応抽出部１０５は、図２に示すギャップ入力ボックス２０５に入力された値を最大ギャップ長（ｇａｐ）として取得する（１４０１）。
【０２０８】
そして、局所対応抽出部１０５は、Ｓ９０１〜Ｓ９０５を実行し、最大ギャップ長制約処理を実行する（１４０２）。
【０２０９】
局所対応抽出部１０５は、Ｓ９０５の処理で、処理対象のセルの最大スコアとして、処理対象のセルに対応する二つの文字が一致しない場合（図１４に示すＳ９０５の４．２）のスコアが選択された場合にのみ、最大ギャップ長制約処理を実行する。
【０２１０】
まず、局所対応抽出部１０５は、図１０に示す始点行列のうち遷移元のセルに登録された局所対応のＩＤを取得する。具体的には、局所対応抽出部１０５は、始点行列のセルのうち遷移元のセルの座標（ｒ１、ｃ１）に対応するセルに登録された局所対応のＩＤ（Ｐ［ｒ１］［ｃ１］）を取得する。なお、局所対応抽出部１０５は、取得した局所対応のＩＤをｋとして記憶する。
【０２１１】
次に、局所対応抽出部１０５は、取得した局所対応のＩＤによって特定される局所対応の終点の座標（ｒ２、ｃ２）を取得する。具体的には、局所対応抽出部１０５は、終点配列Ｅのうち、取得した局所対応のＩＤ（ｋ）に対応する終点配列Ｅ［ｋ］に登録される終点の座標（ｒ２、ｃ２）を取得する。
【０２１２】
次に、局所対応抽出部１０５は、終点の座標（ｒ２、ｃ２）から処理対象のセルの座標（ｒ、ｃ）までのギャップ長を算出する。具体的には、局所対応抽出部１０５は、行方向のギャップ長をｒ−ｒ２によって算出し、列方向のギャップ長をｃ−ｃ２によって算出する。
【０２１３】
そして、局所対応抽出部１０５は、算出した行方向のギャップ長及び列方向のギャップ長の少なくとも一方が最大ギャップ長（ｇａｐ）よりも大きい場合、新たな局所対応を設定し、Ｓ９０６に進む。
【０２１４】
具体的には、局所対応抽出部１０５は、始点行列のセルのうち処理対象のセルの座標（ｒ、ｃ）に対応するセルの局所対応ＩＤ（Ｐ［ｒ］［ｃ］）に新たな局所対応のＩＤ（ａ）を登録する。また、局所対応抽出部１０５は、処理対象のセルの座標（ｒ、ｃ）を始点配列Ｂ［ａ］及び終点配列Ｅ［ａ］に登録する。そして、局所対応抽出部１０５は、新たな局所対応のＩＤ（ａ）をインクリメントしておく。
【０２１５】
一方、局所対応抽出部１０５は、算出した行方向のギャップ長及び列方向のギャップ長が最大ギャップ長（ｇａｐ）以下である場合、何もせずに、Ｓ９０６に進む。
【０２１６】
なお、図１４に示す局所対応処理のＳ１４０２では、処理対象のセルの最大スコアとして、処理対象のセルに対応する二つの文字が一致しない場合のスコアが選択された場合にのみ、最大ギャップ長制約処理が実行されるとしたが、処理対象のセルの最大スコアとして読み飛ばしのスコアが選択された場合にも実行されてもよい。
【０２１７】
以上のように、本実施形態では、局所対応の終点から不一致又は読み飛ばしの文字が所定回数連続する場合には、新たな局所対応を設定するため、スコアの大きな局所対応が抽出されても、当該スコアの大きな局所対応の後の局所対応を網羅的に抽出できる。
【０２１８】
また、最大ギャップ長制約処理は、スコア行列の各セルのスコアを算出しながら実行されるため、従来のＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法とほぼ同じ計算量で実行できる。
【０２１９】
図１５は、本発明の第２の実施形態の局所対応処理を実行することによって抽出された局所対応の表示例である。
【０２２０】
図１５は、図１３と同じ文書に対して図１４に示す局所対応収集処理を実行した場合の局所対応の表示例である。
【０２２１】
図１５では、二つの文書の局所対応のうち最大の局所対応（１３０１）の右下部の局所対応も抽出されている。
【０２２２】
以上によって、本実施形態では、代表的な局所対応の抽出の網羅性を向上させることができる。
【符号の説明】
【０２２３】
１０ 局所対応抽出装置
１０１ ＣＰＵ
１０２ メモリ
１０３ キーボード・マウス
１０４ ディスプレイ
１０５ 局所対応抽出部
１０６ 局所対応表示制御部
１０７ 通信部
１１ ネットワーク
１２ 検索サーバ
【技術分野】
【０００１】
本発明は、二つの文書間で類似する文字列対である局所対応を抽出する局所対応抽出装置に関し、特に、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法を用いて局所対応を抽出する局所対応抽出装置に関する。
【背景技術】
【０００２】
長い文書間では、文書全体が互いに類似することは稀であり、部分的な類似個所が存在する。例えば、書籍間の類似性を考える。書籍間での類似個所は一つではなく、複数ある場合も多い。数個の文字からなる単語が書籍間で一致する場合まで考慮すると、書籍間での類似個所の数は膨大になる。二つの文書間での類似箇所（類似文字列対）のことを局所対応という。この局所対応を数え上げることができれば、二つの文書全体を読まなくても、局所対応の周辺を読むだけで二つの文書間の類似性の根拠を把握できる。
【０００３】
例えば、特許審査等の審査業務において、審査対象となる出願と特許文献や非特許文献との間で内容の同一性及び類似性を判定しなければならない。判定対象となる文書間で局所対応を数え上げることができれば、文書全体を読まずとも局所対応の周辺のみを読むことによって対象文書間の同一性及び類似性が判定でき、審査業務を促進できる。
【０００４】
概念検索では、文字列が入力された場合、入力された文字列と類似する文書を類似度順にランキングして提示する。この場合、ユーザは、入力した文字列に適合しそうな文書を上から順に調べていくことができる。しかし、ユーザは、ランキングの根拠が解りにくいため、入力した文字列と提示された文書との適合性を判定するために、提示された文書自体を読まなければならならない場合が多い。文書が長ければ読解時間も長くなる。
【０００５】
一方、全文検索では、入力された文字列と一致する文字列の周辺部を提示することによって、文書全体を読む作業を軽減する。
【０００６】
そこで、概念検索においても、入力された文字列と入力された文字列に適合する文書との間で類似箇所（局所対応）が抽出され、抽出された局所対応が提示されることによって、文書全体を読まずに文書の適合性を判定できる。
【０００７】
また、特許出願の請求項と明細書との間で局所対応を抽出すれば、請求項に関連する実施例を即座に探すこともできる。
【０００８】
局所対応を抽出する従来技術として、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法（非特許文献１）がある。Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法は、動的計画法によってスコアが最大の局所対応を効率良く探索する。ここで、スコアとは、部分文字列間の類似度のことである。
【０００９】
局所対応を抽出するために生成されたスコア行列から、スコアが所定値以上の局所対応を抽出することによって、より多くの局所対応を網羅的に抽出できる。しかしながら、この方法では、単純にスコアのみで局所対応か否かを判断するため、既に抽出された局所対応の周辺の意味のない文字も含む局所対応が大量に抽出されてしまう。このため、局所対応の中でも代表的なもののみを取捨選択する必要がある。つまり、代表性と網羅性双方を満足させる必要がある。
【００１０】
特許文献１には、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法の局所対応の抽出精度を出来るだけ低減させずに、局処対応の抽出の効率を高める方法が記載されている。具体的には、完全に一致する文字列対を抽出し、抽出した文字列対の中である一定のギャップ以内にある文列対を連結する。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００２−１９１３７１号公報
【非特許文献】
【００１２】
【非特許文献１】“Ａｌｇｏｒｉｔｈｍｓ ｏｎ Ｓｔｒｉｎｇｓ，Ｔｒｅｅｓ， ａｎｄ Ｓｅｑｕｅｎｃｅｓ”（ｐｐ．２３２−２３４），Ｇｕｓｆｉｅｌｄ，Ｄ．，Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，１９９７
【発明の概要】
【発明が解決しようとする課題】
【００１３】
ただし、特許文献１に記載された方法で、完全に一致する文字列対を抽出するためには、接尾辞配列等のインデックスを事前に作成しなければならない。また、特許文献１に記載された方法の局所対応の抽出精度もＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法に劣る。遺伝子配列の検索に用いられるＢＬＡＳＴ、ＦＡＳＴＡといったソフトウェアも、特許文献１に記載された方法と同じく、精度を犠牲にして高速化を図るものであり、インデックスが事前に作成されていなければならない。
【００１４】
したがって、インデックス化されていないデータについては局所対応が抽出しにくいという問題がある。
【００１５】
事前にインデックス化されていない任意の長い文字列の間で局所対応を抽出する場合、代表的な局所対応を網羅的に抽出することは困難である。また、局所対応の網羅性を重視すると代表性を損い、代表性を重視すると網羅性を損なうものであった。
【００１６】
このため、本発明は、事前にインデックス化されてない任意の文字列の間で代表的な局所対応を網羅的に抽出する局所対応抽出装置を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の代表的な一例を示せば、任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出装置において、前記局所対応抽出部は、前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とし、前記行の文字列を構成する文字及び前記列の文字列を構成する文字に対応するセルに、当該セルに対応する二つの文字の類似度を示すスコアを登録して、第一行列を生成する第一行列生成部と、前記第一行列のセルに対応するセルによって構成される第二行列のセルのうち前記第一行列生成部によってスコアが算出されたセルに対応するセルに、当該セルに対応する二つの文字が属する局所対応の識別子を登録して、前記第二行列を生成する第二行列生成部と、を有し、前記第一行列のセルに登録されるスコアは、当該セルに対応する二つの文字の類似度が大きいほど大きい値を示し、前記第一行列生成部は、前記スコアの算出対象のセルに隣接するセルのうちすでにスコアが算出されたセルから当該算出対象のセルまでのパスに予め設定された値に基づいて前記算出対象のセルのスコアを算出し、前記算出されたスコアのうち最大のスコアを前記算出対象のセルのスコアとして登録し、前記最大のスコアを算出したパスのセルを遷移元セルとして記憶し、前記第二行列生成部は、前記遷移元セルに対応する前記第二行列のセルがどの局所対応にも属しないことを示し、かつ、前記第一行列生成部によって算出された最大のスコアが所定値である場合、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶し、前記遷移元セルに対応する前記第二行列のセルがいずれかの局所対応に属することを示し、かつ、前記第一行列生成部によって算出された最大のスコアが前記所定値よりも大きい場合、前記算出対象のセルに対応する前記第二行列のセルに、前記遷移元セルに対応する前記第二行列のセルに登録された局所対応の識別子を登録し、さらに、前記算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、前記算出対象のセルに対応する二つの文字が前記局所対応の終点となることを記憶することを特徴とする。
【発明の効果】
【００１８】
本発明によれば、事前にインデックス化されてない任意の文字列の間で代表的な局所対応を網羅的に抽出できる。
【図面の簡単な説明】
【００１９】
【図１】本発明の第１の実施形態の局所対応抽出システムの構成の説明図である。
【図２】本発明の第１の実施形態のディスプレイに表示される局所対応表示画面２０の説明図である。
【図３】本発明の第１の実施形態の変形例の局所対応表示画面の説明図である。
【図４】本発明の第１の実施形態の変形例の要約バーチャートを追加した局所対応表示画面の説明図である。
【図５】本発明の第１の実施形態の二つの文字列間におけるスコアの説明図である。
【図６】本発明の第１の実施形態のスコア行列の説明図である。
【図７】本発明の第１の実施形態のスコア算出方法の説明図である。
【図８】本発明の第１の実施形態の初期化処理の説明図である。
【図９】本発明の第１の実施形態の局所対応収集処理の説明図である。
【図１０】本発明の第１の実施形態の始点行列の説明図である。
【図１１】本発明の第１の実施形態の局所対応抽出処理のフローチャートである。
【図１２】二つの文字列間に本発明の第１の実施形態の局所対応処理を実行し、局所対応が抽出されない場合の説明図である。
【図１３】酷似する二つの文書に第１の実施形態の局所対応処理を実行することによって抽出された局所対応の表示例である。
【図１４】本発明の第２の実施形態の局所対応収集処理の説明図である。
【図１５】本発明の第２の実施形態の局所対応処理を実行することによって抽出された局所対応の表示例である。
【発明を実施するための形態】
【００２０】
本発明の第１の実施形態を図１〜図１１を用いて説明する。
【００２１】
図１は、本発明の第１の実施形態の局所対応抽出システムの構成の説明図である。
【００２２】
抽出対象となる二つの文字列（文書）間で類似する文字列対を局所対応という。
【００２３】
局所対応抽出システムは、二つの文字列間で局所対応を抽出し、抽出した局所対応を表示するシステムである。局所対応抽出システムは、クライアント１０、及び、クライアント１０にネットワーク１１を介してアクセス可能な検索サーバ１２を備える。
【００２４】
検索サーバ１２は、局所対応の抽出の対象となる対象文字列（対象文書）をクライアント１０にネットワーク１１を介して送信する計算機である。
【００２５】
対象文字列がキーボード・マウス１０３を介してクライアント１０に直接入力される場合には、局所対応抽出システムはネットワーク１１及び検索サーバ１２を備えなくてもよい。
【００２６】
クライアント１０は、ＣＰＵ１０１、メモリ１０２、キーボード・マウス１０３、ディスプレイ１０４、局所対応抽出部１０５、局所対応表示制御部１０６、及びデータ通信部１０７を備える。
【００２７】
ＣＰＵ１０１は、局所対応抽出部１０５及び局所対応表示制御部１０６を構成する各種プログラムを実行する。メモリ１０２は、ＣＰＵ１０１が実行するプログラム、及び当該プログラムを実行するために必要なデータを一時的に記憶する。
【００２８】
キーボード・マウス１０３は、ユーザからの入力を受け付ける入力部である。ディスプレイ１０４は、局所対応抽出部１０５によって抽出された局所対応を局所対応表示制御部１０６の制御下で表示する表示部である。
【００２９】
局所対応抽出部１０５は、対象文字列から局所対応を抽出する。局所対応表示制御部１０６は、局所対応抽出部１０５によって抽出された局所対応をディスプレイ１０４に表示するための制御を行う。
【００３０】
データ通信部１０７は、ネットワーク１１を介してデータを通信するインターフェースであり、例えば、ＴＣＰ／ＩＰプロトコルによって通信可能なＬＡＮカードである。
【００３１】
局所対応抽出システムの全体的な処理の概略を説明する。
【００３２】
まず、クライアント１０が対象文字列を取得する。クライアント１０が対象文字列を取得する方法には種々の方法がある。例えば、クライアント１０が検索サーバ１２から対象文字列を取得する方法、及び、ユーザがキーボード・マウス１０３を操作して対象文字列をクライアント１０に入力する方法などがある。
【００３３】
クライアント１０が検索サーバ１２から対象文字列を取得する場合、まず、クライアント１０は、取得する対象文字列の文書番号を検索サーバ１２に送信する。そして、検索サーバ１２は、文書番号を受信した場合、受信した文書番号に対応する文書の文字列を対象文字列としてクライアント１０に送信する。
【００３４】
次に、局所対応抽出部１０５は、クライアント１０が取得した対象文字列から局所対応を抽出する。なお、局所対応抽出部１０５が局所対応を抽出するための具体的な処理については図５〜図１０で詳細を説明する。
【００３５】
そして、局所対応表示制御部１０６は、局所対応抽出部１０５によって抽出された局所対応をディスプレイ１０４に表示する。なお、ディスプレイ１０４に表示される局所対応については図２〜図４で詳細を説明する。
【００３６】
なお、図６で詳述するが、局所対応抽出部１０５は、対象文字列から局所対応を抽出する場合、対象文字列の文字列情報のみを用いるので、対象文字列がインデックス化されてなくてもよい。このため、本実施形態の対象文字列は、検索サーバ１２で検索された文書であってもよいし、ユーザによって直接入力された文字列であってもよい。
【００３７】
図２は、本発明の第１の実施形態のディスプレイ１０４に表示される局所対応表示画面２０の説明図である。
【００３８】
局所対応表示画面２０は、局所対応表示制御部１０６の制御下でディスプレイ１０４に表示される。
【００３９】
局所対応表示画面２０は、抽出ボタン２０１、一致スコア入力ボックス２０２、不一致スコア入力ボックス２０３、読み飛ばしスコア入力ボックス２０４、ギャップ入力ボックス２０５、スコア閾値入力エリア２０６、文書番号入力エリア２０７、２０８、テキストエリア２０９、２１０、及び、局所対応表示エリア２１１を含む。
【００４０】
まず、テキストエリア２０９及び２１０について説明する。テキストエリア２０９及び２１０には、対象文字列が表示される。
【００４１】
テキストエリア２０９及び２１０は、ユーザのキーボード・マウス１０３を介した文字入力を受け付ける。このため、ユーザは、テキストエリア２０９及び２１０に表示される文字列をキーボード・マウス１０３を用いて自由に編集できる。
【００４２】
また、クライアント１０が対象文字列を検索サーバ１２から取得する場合、ユーザは、文書番号入力エリア２０７及び２０８に取得を所望する対象文字列の文書番号を入力する。そして、それぞれの文書番号入力エリア２０７及び２０８に改行が入力されると、クライアント１０は、文書番号入力エリア２０７及び２０８に入力された文書番号を検索サーバ１２に送信する。
【００４３】
検索サーバ１２は、文書番号を受信した場合、受信した文書番号に対応する文書を検索し、検索した文書をクライアント１０に送信する。クライアント１０は、検索サーバ１２から送信された文書を受信した場合、受信した文書に対応する文書番号が入力された文書番号入力エリア２０７及び２０８の下方に位置するテキストエリア２０９及び２１０に、受信した文書の文字列を表示する。
【００４４】
なお、局所対応表示制御部１０６は、局所対応表示画面２０をディスプレイ１０４に表示する場合、文書番号入力エリア２０７及び２０８に前回入力された文書番号を検索サーバ１２に送信するようにしてもよい。
【００４５】
そして、ユーザが抽出ボタン２０１を操作した場合、局所対応表示制御部１０６は、テキストエリア２０９及び２１０に表示された対象文字列を局所対応抽出部１０５に入力する。そして、局所対応抽出部１０５は、入力された対象文字列から局所対応を抽出し、抽出した局所対応を局所対応表示制御部１０６に入力する。
【００４６】
局所対応表示制御部１０６は、入力された局所対応を局所対応表示エリア２１１に表示する。
【００４７】
なお、一致スコア入力ボックス２０２、不一致スコア入力ボックス２０３、読み飛ばしスコア入力ボックス２０４、ギャップ入力ボックス２０５、及びスコア閾値入力エリア２０６には、局所対応抽出部１０５が局所対応を抽出する場合に用いられるパラメータが入力される。これらのパラメータについては、図６〜図１０で詳細を説明する。
【００４８】
なお、局所対応表示制御部１０６は、局所対応表示画面２０をディスプレイ１０４に表示させる場合に対象文字列が決まっていれば、抽出ボタン２０１の操作を自動化してもよい。
【００４９】
次に、局所対応抽出部１０５によって抽出された局所対応を表示する局所対応表示エリア２１１について説明する。
【００５０】
局所対応表示エリア２１１は、対象文字列となる二つの文字列を二次元の行列によって表現する。具体的には、局所対応表示エリア２１１の横軸がテキストエリア２０９に入力された文字列に対応し、局所対応表示エリア２１１の縦軸がテキストエリア２１０に入力された文字列に対応する。横軸においては、先頭の文字が左端に位置し、末尾の文字が右端に位置する。縦軸においては、先頭の文字が上端に位置し、末尾の文字が下端に位置する。
【００５１】
なお、図２では、局所対応表示エリア２１１の上方の表示領域２１５に横軸に対応する文字列を表示し、また、局所対応表示エリア２１１の左側の表示領域２１６に縦軸に対応する文字列を表示するが、これらの表示領域２１４、２１５には文字列が表示されなくてもよい。例えば、横軸及び縦軸に対応する文字列の文字数が所定数以上である場合には、局所対応表示制御部１０６は、表示領域２１４、２１５には文字列を表示しない。
【００５２】
局所対応表示エリア２１１の縦軸に対応する文字列と横軸に対応する文字列との間の局所対応を矩形によって表示する。図２では、二つの局所対応が抽出されており、この抽出された局所対応を二つの矩形２１２Ａ及び２１２Ｂ（以下、総称して２１２という）によって表示する。
【００５３】
矩形２１２の縦辺の位置及び長さは、局所対応表示エリア２１１の縦軸が示す文字列の局所対応の範囲に対応し、矩形２１２の横辺の位置及び長さは、局所対応表示エリア２１１の横軸が示す文字列の局所対応の範囲に対応する
具体的には、矩形２１２Ａは、局所対応表示エリア２１１の横軸が示す文字列の一部の「特許を検索」と、縦軸が示す文字列の一部の「特許検索」との間の局所対応である。矩形２１２Ｂは、局所対応表示エリア２１１の横軸が示す文字列の一部の「精度向上」と、縦軸が示す文字列の一部の「精度の向上」との間の局所対応である。
【００５４】
ユーザは、マウスポインタ２１４によって特定の矩形２１２を指すことによって、局所対応表示エリア２１１に表示された複数の矩形２１２（局所対応）の中から特定の矩形２１２を選択できる。なお、局所対応表示制御部１０６は、ユーザによって選択された矩形２１２を、選択されていることをユーザに把握可能な態様で表示する。具体的には、局所対応表示制御部１０６は、ユーザによって選択された矩形２１２をハイライト（例えば、グレーの塗りつぶし等）で表示する。
【００５５】
また、局所対応表示制御部１０６は、テキストエリア２０９及び２１０に表示された文字列のうち、ユーザによって選択された矩形２１２に対応する部分文字列を、当該部分文字列に対応する矩形２１２が選択されていることをユーザに把握可能な態様で表示する。具体的には、局所対応表示制御部１０６は、当該部分文字列をハイライト（例えば、反転表示等）で表示する。
【００５６】
これによって、ユーザは、局所対応表示エリア２１１に表示される矩形２１２を選択しながら、テキストエリア２０９及び２１０に表示される文字列のうち選択した矩形２１２に対応する文字列を即座に探すことができ、テキストエリア２０９及び２１０から探した文字列周辺を比較しながら読むことができる。
【００５７】
また、局所対応の文字列が長い場合には、矩形２１２の面積は大きくなるので、ユーザは一目で重要な局所対応を判別できる。通常、ユーザは、局所対応表示エリア２１１に表示された大きな矩形を探し、当該矩形をマウスポインタ２１４によって差すことによって当該矩形を選択し、当該矩形に対応する文字列をテキストエリア２０９及び２１０から探し、当該文字列の周辺も含めて読む。
【００５８】
なお、テキストエリア２０９及び２１０に表示される文字列の文字数が所定数よりも大きい場合、局所対応表示制御部１０６は、選択された矩形２１２に対応する部分文字列がテキストエリア２０９及び２１０の最上部に位置するように、自動スクロールして表示する。なお、当該所定数は、例えば、テキストエリア２０９及び２１０にスクロールなしで表示可能な文字数よりも大きい値に設定される。
【００５９】
テキストエリア２０９及び２１０に入力される文字列が長くなると、局所対応表示エリア２１１に表示される矩形２１２も相対的に小さく表示されるため、ユーザは、面積の小さい矩形２１２を判別しにくくなる。このため、図３に示すように、局所対応表示エリア２１１の一部を拡大表示するズームエリア３０３を追加する変形例も考えられる。
【００６０】
図３は、本発明の第１の実施形態の変形例の局所対応表示画面３０の説明図である。
【００６１】
図３に示す局所対応表示画面３０の構成のうち、図２に示す局所対応表示画面２０の構成と同じ構成は、同じ符号を付与し、説明を省略する。
【００６２】
図３に示す局所対応表示エリア２１１は、テキストエリア２０９及び２１０に表示される対象文字列の行列の全体を表示するエリアである。
【００６３】
当該局所対応表示エリア２１１内には、ユーザがマウスによって操作可能なスコープ３０２が表示される。スコープ３０２内に位置する範囲が、ズームエリア３０３に拡大表示される。なお、スコープ３０２が移動すると、局所対応表示制御部１０６は、ズームエリア３０３の表示内容を移動したスコープ３０２に対応する表示内容に更新する。
【００６４】
図４は、本発明の第１の実施形態の変形例の局所対応表示画面４０の説明図である。
【００６５】
図４に示す局所対応表示画面４０は、図２又は図３に示す局所対応表示エリア２１１に要約バーチャート４１及び４２が追加された画面である。
【００６６】
ユーザは、局所対応表示エリア２１１に表示される矩形２１２がどの部分に集中しているかを即座に把握したい場合がある。ユーザは、局所対応表示エリア２１１を探すことによって、矩形２１２が局所対応表示エリア２１１のどの部分に集中しているかをある程度把握できる。しかしながら、この方法は一覧性に欠ける。
【００６７】
そこで、局所対応表示制御部１０６は、局所対応表示エリア２１１に表示される矩形２１２の横方向の分布を集約し、縦方向の分布度を示す要約バーチャート４１を生成し、また、局所対応表示エリア２１１に表示される矩形２１２の横方向の分布を示す要約バーチャート４２を生成して、生成した要約バーチャート４１及び４２を表示する。
【００６８】
要約バーチャート４１は、局所対応表示エリア２１１に表示される矩形２１２を横方向に射影した結果のバーチャートで、縦方向の文字列中での局所対応の分布を示す。一方、要約バーチャート４２は、横方向の文字列中での局所対応の分布を示す。例えば、矩形２１２Ｃは、要約バーチャート４１の４１１及び４１２の部分に射影される。なお、局所対応の最大スコアが大きいほど濃い色で表示することで、ユーザにとって重要な局所対応を注視しやすくすることもできる。なお、スコアは類似度を意味し、具体的なスコアの算出法は後述する。
【００６９】
一方の文字列中の部分文字列が、他方の文字列中の複数の部分と対応がとれる場合も多い。例えば、図４では、縦方向の文字列中の「精度」は横方向で３か所出現している。このため、縦方向の「精度」に対応する要約バーチャート４１の部分４１２は他と比べて色が濃く表示される。
【００７０】
このように、局所対応表示エリア２１１に表示される矩形２１２を行方向及び列方向に射影した場合、当該行方向及び列方向に位置する局所対応のスコアの総和に比例して要約バーチャート４１及び４２の色を濃く表示すれば、ユーザは、要約バーチャート４１及び４２を見るだけで、スコアが大きい局所対応が存在する部分や、多くの局所対応が存在する部分をすぐに見つけることができる。要約バーチャート４１及び４２中でマウスをクリックすると、局所対応表示エリア２１１でも対応する部分が頭出しされて表示される。
【００７１】
以下に、要約バーチャート生成処理について説明する。要約バーチャート生成処理は、局所対応表示制御部１０６によって実行される。
【００７２】
なお、局所対応表示制御部１０６による要約バーチャート生成処理は、局所対応抽出部１０５によって抽出された局所対応が局所対応表示制御部１０６に入力された後に実行される。
【００７３】
ここで、局所対応は始点と終点とを有し、始点は局所対応表示エリア２１１に表示される矩形２１２の左上点の座標（ｂｒ，ｂｃ）に相当し、終点は矩形２１２の右下点の座標（ｅｒ，ｅｃ）に相当する。また、局所対応のスコアをＳとし、局所対応表示エリア２１１に表示されるすべての矩形２１２（局所対応）の中で最大のスコアの局所対応のスコアをＳｍａｘという。
【００７４】
まず、局所対応表示制御部１０６は、各局所対応の透明度を、各局所対応のスコアＳ及び最大スコアＳｍａｘに基づいて決定する。透明度は０〜２５５で示され、透明度が０であれば完全な透明で、透明度が２５５であれば完全な不透明である。
【００７５】
各局所対応の透明度は、当該局所対応のスコアＳが大きければ大きいほど不透明であるように決定される。これによって、要約バーチャート４１及び４２ではスコアＳの大きい局所対応ほど濃い色で表示されるようになり、ユーザが注視しやすくなる。
【００７６】
具体的には、最大スコアＳｍａｘの局所対応の透明度Ｔｍａｘが予め設定されていれば、局所対応表示制御部１０６は、各局所対応の透明度Ｔを透明度Ｔｍａｘに基づいて等比配分することによって決定する。換言すれば、局所対応表示制御部１０６は、透明度ＴをＴｍａｘ＊（Ｓ／Ｓｍａｘ）を計算することによって決定する。
【００７７】
次に、局所対応表示制御部１０６は、要約バーチャート４１において、矩形２１２の始点のｙ座標ｂｃから終点のｙ座標ｅｃまでの範囲を当該矩形２１２の局所対応の透明度Ｔで塗りつぶす。また、局所対応表示制御部１０６は、要約バーチャート４２において、矩形２１２の始点のｘ座標ｂｒから終点のｘ座標ｅｒまでの範囲を当該矩形２１２の局所対応の透明度Ｔで塗りつぶす。局所対応表示制御部１０６は、当該処理をすべての局所対応に対して実行する。ここで、局所対応表示制御部１０６は、要約バーチャート４１及び４２で局所対応が重複する箇所については重複する局所対応の透明度Ｔを加算し、加算した透明度で塗りつぶすので、当該個所の色を濃く表示する。
【００７８】
なお、以上の処理では、各局所対応の透明度Ｔは各局所対応のスコアに比例した値である。このため、要約バーチャート４１及び４２で色が濃い箇所は、当該個所に対応する局所対応のスコアが大きいか、又は、当該個所で局所対応が重複しているかである。いずれの場合であっても、要約バーチャート４１及び４２で色が濃い箇所には、ユーザにとって重要な局所対応が存在することを意味する。しかし、ユーザは、スコアが大きい局所対応は局所対応表示エリア２１１で矩形２１２の面積が大きくなるため、ユーザはスコアが大きい局所対応を見つけやすいが、縦方向及び横方向に重複する局所対応は局所対応表示エリア２１１で見つけにくいという観点で、局所対応が重複する箇所のみを知りたい場合もある。
【００７９】
このため、局所対応表示制御部１０６は、局所対応の透明度Ｔを当該局所対応のスコアＳを用いて決定するのではなく、すべての局所対応の透明度Ｔを所定値に設定し、局所対応が縦方向又は横方向に重複する場合、重複する局所対応の透明度Ｔを加算し、加算した透明度で塗りつぶしてもよい。
【００８０】
これによって、要約バーチャート４１及び４２の色の濃さは、スコアに依存せず、重複する局所対応の数に依存するので、ユーザは、縦方向及び横方向に重複する局所対応は局所対応表示エリア２１１で見つけやすくなる。
【００８１】
次に、局所対応抽出部１０５が局所対応を抽出する処理について説明する。
【００８２】
局所対応の抽出では、前述したように、代表的な局所対応のみを網羅的に抽出することが課題となる。本発明では、既存のＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法に、始点一致による枝刈りを組み込むことによって、前述の課題を解決する。
【００８３】
図５は、本発明の第１の実施形態の二つの文字列間におけるスコアの説明図である。
【００８４】
文字列Ａ「特許の検索精度の向上」と文字列Ｂ「特許検索の精度の向上」との間の各文字が対応付けられる。この各文字単位の対応をアラインメントという。アラインメントには、対応する文字同士が一致する一致アラインメント、及び、対応する文字同士が一致しない不一致アラインメントがある。図５では、「を」と「の」とのアラインメント５０が不一致アラインメントであり、その他のアラインメントは一致アラインメントである。
【００８５】
文字列Ａ及び文字列Ｂのすべての文字でアラインメントがあるわけではない。図５では、文字列Ａの「の」（５１）及び文字列Ｂの「の」（５２）はいずれの文字にも対応付けられていない。このアラインメントがない文字は当該文字が読み飛ばされたことを意味し、これを以下読み飛ばしという。
【００８６】
一致アラインメント、不一致アラインメント、及び読み飛ばしには、予め所定値が設定されている。図５では、一致アラインメントには＋２点、不一致アラインメントには−２点、読み飛ばしには−１点が設定されているとする。この場合、文字列Ａと文字列Ｂとの間でこれらの値を合計した値（スコア）は１２点になり、このスコアが文字列Ａと文字列Ｂとの類似度となる。
【００８７】
また、局所対応は、対象文字列中でスコアが局所的に大きくなる部分文字列対であり、局所対応抽出部１０５によって抽出される。局所対応抽出部１０５は、一致アラインメント、不一致アラインメント、及び読み飛ばしに設定された値次第で、異なる局所対応を抽出する。
【００８８】
なお、ユーザは、図２に示す一致スコア入力ボックス２０２、不一致スコア入力ボックス２０３、及び読み飛ばしスコア入力ボックス２０４を介して、一致アラインメント、不一致アラインメント、及び読み飛ばしの値に所望の値を設定できる。
【００８９】
また、不一致アラインメントの値は、不一致アラインメントの文字の種類によって異なるものであってもよい。例えば、不一致アラインメントの文字の種類が助詞である場合の値は、不一致アラインメントの文字の種類が助詞以外である場合の値よりも低く設定されてもよい。
【００９０】
また、文字列において出現回数の多い部分文字列はユーザにとって重要である可能性が高いため、局所対応抽出部１０５が出現回数を把握できるように、スコアに出現回数を含ませてもよい。これによって、局所対応抽出部１０５は、出現回数が所定値以上である部分文字列のスコアに１以上の所定値を乗算することによって、出現回数が所定値未満の部分文字列よりもスコアを大きくできる。
【００９１】
本実施形態では、局所対応抽出部１０５が対象文字列のスコアを算出して、局所対応を抽出するために、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法を用いる。Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法は動的計画法によって効率良くスコアを算出する方法である。
【００９２】
以下に、本実施形態のスコア算出方法について図６を用いて説明する。
【００９３】
図６は、本発明の第１の実施形態のスコア行列の説明図である。
【００９４】
局所対応抽出部１０５は、二つの対象文字列のうち一方の対象文字列を行に配置し、他方の対象文字列を列に配置する。そして、局所対応抽出部１０５は、行列のセルのスコアを左上のセルから順番に計算して、計算したスコアをセルに登録して、スコア行列を生成する。
【００９５】
なお、行列のセルは、当該セルに対応する行の文字と当該セルに対応する列の文字とに対応する。また、各セルに登録されるスコアは、当該セルまでのスコアの合計値である。
【００９６】
ここで、スコアの算出方法について、図７を用いて説明する。
【００９７】
図７は、本発明の第１の実施形態のスコア算出方法の説明図である。
【００９８】
あるセルのスコアを算出する場合、局所対応抽出部１０５は、算出対象のセルに隣接し、かつすでにスコアが算出されたセルから算出対象のセルまでの各パスごとのスコアを算出し、算出したスコアのうち最大のスコアを算出対象のセルに登録する。
【００９９】
以下、図７のセル７３のスコアを算出する場合について具体的に説明する。
【０１００】
セル７３に隣接し、かつすでにスコアが算出されたセルは、セル７０、７１、および７２である。セル７３の真上に位置するセル７１からのパスを第１パス７４とし、セル７３の左上に位置するセル７０からのパスを第２パス７５とし、セル７３の左に位置するセル７２からのパスを第３パス７６とする。
【０１０１】
まず、第１パス７４を経由した場合のセル７３のスコアについて説明する。
【０１０２】
算出対象のセル７３の真上に位置するセル７１に対応する文字は「検」（７０２）及び「許」（７０３）であり、セル７３に対応する文字は「検」（７０２）及び「検」（７０４）である。当該セル７１で「検」（７０４）が読み飛ばされたことになる。つまり、「検」（７０２）は変化せず、真上のセルから算出対象のセルまでのパスは、行の文字は変化せずに、列の文字が変化することになり、当該列の「検」（７０４）が読み飛ばされたこと（読み飛ばし）を意味する。
【０１０３】
ここで、読み飛ばしには「−１」が予め設定されているので、第１パス７４を経由した場合のセル７３のスコアは、セル７１のスコアの値「２」に、第１パス７４に設定された値（読み飛ばしに設定された値）「−１」を加算し、「１」と算出される。
【０１０４】
次に、第３パス７６を経由した場合のセル７３のスコアについて説明する。
【０１０５】
算出対象のセル７３の左に位置するセル７２に対応する文字は「を」（７０１）及び「検」（７０４）であり、セル７３に対応する文字は「検」（７０２）及び「検」（７０４）である。当該セル７０の段階で「検」（７０２）が読み飛ばされたことになる。つまり、左のセルから算出対象のセルまでのパスは、列の文字は変化せずに、行の文字が変化することになり、当該行の「検」（７０２）が読み飛ばされたこと（読み飛ばし）を意味する。
【０１０６】
ここで、読み飛ばしには「−１」が予め設定されているので、第３パス７６を経由した場合のセル７３のスコアは、セル７２のスコアの値「２」に、第３パス７６に設定された値（読み飛ばしに設定された値）「−１」を加算し、「１」と算出される。
【０１０７】
次に、第２パス７５を経由した場合のセル７３のスコアについて説明する。
【０１０８】
左上に位置するセル７０に対応する文字は「を」（７０１）及び「許」（７０３）であり、セル７３に対応する文字は「検」（７０２）及び「検」（７０４）である。この場合、左上に位置するセル７０に対応する行の文字及び列の文字と、セル７３に対応する行の文字及び列の文字とが異なるので読み飛ばしではない。第２パス７５は、セル７３に対応する行の文字と列の文字とが一致する場合、一致アラインメントを意味し、セル７３に対応する行の文字と列の文字とが一致しない場合、不一致アラインメントを意味する。なお、図７では、セル７３に対応する行の文字「検」（７０４）と列の文字（７０２）とは一致するので、第２パス７５は一致アラインメントを意味する。
【０１０９】
ここで、一致アラインメントには「２」が予め設定され、不一致アラインメントには「−２」が予め設定されている。第２パス７５を経由した場合のセル７３のスコアは、セル７０のスコアの値「３」に、一致アラインメントに設定された値「２」を加算し、「５」と算出される。
【０１１０】
以上のように、第１パス７４〜第３パス７６を経由した場合のセル７３のスコアが算出される。そして、算出されたスコアから最大のスコアのパスが選択され、当該最大のスコアがセル７３に登録される。図７では、第２パス７５を経由した場合のスコア「５」が最大となるので、セル７３にはスコア「５」が登録される。
【０１１１】
以上のように、局所対応抽出部１０５は、図６に示す左上端のセルから順に横方向にスコアを登録する。そして、局所対応抽出部１０５は、一行のすべてのセルにスコアを登録した場合、次の行の左端のセルから順にスコアを登録する。このため、算出対象のセルの左のセル、左上のセル、及び左のセルのスコアは必ず登録されていることになる。
【０１１２】
また、局所対応抽出部１０５は、初期化処理として、行に対応する対象文字列（図６に示す「精度向上の特許を検索」）の先頭文字の前に列を一列挿入し、列に対応する対象文字列（図６に示す「特許検索の精度の向上」）の先頭文字の前に行を一列挿入する。この挿入された行及び列は初期行列という。そして、局所対応抽出部１０５は、初期行列のセルにスコア「０」を予め登録する。
【０１１３】
ここで、従来のＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法を用いた局所対応抽出処理の問題点について説明する。
【０１１４】
図７で説明したスコア算出方法によって図６に示すスコア行列が生成された後、スコア行列のセルから最大のスコアが登録されたセルが選択される。当該選択されたセルまでのパスを逆順に辿ることによって、最大のスコアの局所対応が抽出される。
【０１１５】
図６では、最大のスコアは「７」であり、最大のスコアが登録されたセルはセル６０及び６１である。セル６０からパスを逆順に辿ることによって、対象文字列（「精度向上の特許を検索」）からは「特許を検索」が抽出され、セル６１からパスを逆順に辿ることによって、対象文字列（「特許検索の精度の向上」）からは「特許検索」が抽出される。なお、「特許を検索」及び「特許検索」が局所対応である。
【０１１６】
この場合、スコア行列の中で最大スコアの局所対応しか抽出できず、最大スコアよりも低い局所対応は抽出できない。例えば、図６において、仮に、「特許を検索」及び「特許検索」のスコアが「７」で、「精度向上」及び「精度の向上」のスコアが「６」であるとすると、「精度向上」及び「精度の向上」は局所対応として抽出されない。したがって、スコア行列生成後に最大のスコアが登録されたセルからパスを逆順に辿る方法では、代表的な局所対応しか抽出できず、局所対応を網羅的に抽出できない。
【０１１７】
このため、スコアが所定値以上のセルを抽出し、抽出したセルからパスを逆順に辿ることによって、局所対応を抽出する方法が考えられる。しかしながら、この方法では、網羅的に局所対応を抽出できるが、局所対応を重複して抽出してしまい、抽出される局所対応が冗長となってしまう。
【０１１８】
図６で、抽出するセルのスコアの所定値が「６」に設定された場合、セル６２及び６３が抽出される。この場合、セル６２からパスを逆順に辿ることによって抽出される局所対応は、「特許を検索」と「特許検索の」である。この「特許検索の」は、本来「特許を検索」と対応する局所対応として抽出されるべき文字列「特許検索」の末尾に「の」を追加しただけの文字列であり、本来の局所対応「特許検索」のバリエーションにすぎない。
【０１１９】
本来の局所対応として抽出される文字列の最後の文字は、スコアが最大となるセルに対応する文字である。一致のアラインメントであればスコアを加算し、不一致のアラインメント及び読み飛ばしであればスコアが減少するように設定されている場合、二つの対象文字列の各文字が一致していればスコアは増加し、その他の場合スコアは減少するためであり、スコアが減少せずスコアが最大となる文字が最後の文字が本来の局所対応として抽出される文字列の最後の文字となる。
【０１２０】
前述した方法では、スコアが最大となるセルの周辺のセルに対応する文字が局所対応の最後の文字として抽出されてしまう場合があり、この局所対応は本来の局所対応のバリエーションにすぎず、抽出された局所対応は冗長化してしまう。
【０１２１】
本実施形態では、局所対応抽出部１０５は、スコア行列を生成する際に算出したスコアが、当該算出したスコアのセルが属する局所対応内における最大スコアよりも大きい場合、当該算出したスコアのセルを局所対応の終点として登録する。なお、算出したスコアのセルが属する局所対応を構成するセルは、当該算出したスコアに至るまでのパスの始点と同じ始点からのすべてのパスが経由するセルである。この処理を、始点一致による枝刈りという。
【０１２２】
これによって、本来の局所対応のバリエーションを抽出せず、冗長化しない局所対応を網羅的に抽出できる。
【０１２３】
なお、対象文字列が長くなり、スコア行列のサイズが大きくなると、スコア行列を生成してから始点一致による枝刈りを実行すると、始点が同じパスを探索するための計算量が増大してしまう。このため、本実施形態では、局所対応抽出処理をスコア行列の生成と同時に実行するので、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法による局所対応抽出処理とほぼ同じ計算量で局所対応を抽出できる。
【０１２４】
図８〜図１１を用いて本実施形態の局所対応抽出処理を説明する。
【０１２５】
図８は、本発明の第１の実施形態の初期化処理の説明図である。
【０１２６】
初期化処理は、局所対応抽出部１０５によって実行される。
【０１２７】
まず、局所対応抽出部１０５は、二つの対象文字列を登録し、一致スコア、不一致スコア、及び読み飛ばしスコアを設定する（Ｓ８０１）。
【０１２８】
具体的には、二つの対象文字列は、配列Ｘ［ｌ．．ｌｘ］及び配列Ｙ［ｌ．．ｌｙ］によって表現される。便宜上、各対象文字列の先頭文字は各配列の要素１に登録される。また、各対象文字列の長さは１ｘ及び１ｙである。
【０１２９】
また、局所対応抽出部１０５は、図２に示す一致スコア入力ボックス２０２、不一致スコア入力ボックス２０３、及び読み飛ばしスコア入力ボックス２０４に入力された値を、一致スコア（Ｍａｔｃｈ）、不一致スコア（Ｕｎｍａｔｃｈ）、及び読み飛ばしスコア（Ｓｋｉｐ）に設定する。
【０１３０】
次に、局所対応抽出部１０５は、スコア行列を初期化する（Ｓ８０２）。スコア行列は、図６で説明した行列であり、Ｍ［０．．ｌｘ］［０．．ｌｙ］で表現される。［０．．ｌｘ］が配列Ｘによって表現される対象文字列に相当し、［０．．ｌｙ］が配列Ｘによって表現される対象文字列に相当する。
【０１３１】
また、配列Ｘのｉ番目の文字Ｘ［ｉ］及び配列Ｙのｊ番目の文字Ｙ［ｊ］に対応するセルはＭ［ｉ］［ｊ］である。スコア行列の各セルには図６と同じく、そのセルへ至るパスのスコア合計値が登録される。また、局所対応抽出部１０５は、スコア行列の０行目のセル及び０行目の列にスコア「０」を登録する。
【０１３２】
次に、局所対応抽出部１０５は、局所対応を初期化する（Ｓ８０３）。局所対応は、始点配列Ｂ、終点配列Ｅ、スコア配列Ｓの三つの配列によって表現される。局所対応の一意な識別子であるＩＤは、これらの配列のインデックスに相当する。
【０１３３】
始点配列Ｂには、各局所対応の始点の座標が登録され、終点座標Ｅには、各局所対応の終点の座標が登録される。ここで、座標とは、スコア行列のインデックス対のことである。例えば、配列Ｘのi番目の文字Ｘ［ｉ］及び配列Ｙのｊ番目の文字Ｙ［ｊ］が始点である場合、始点の座標は（ｉ，ｊ）である
。
【０１３４】
スコア配列Ｓには、各局所対応のスコアが登録される。スコア配列Ｓには、初期値として０が登録される。
【０１３５】
ＩＤがｉである局所対応の始点座標はＢ［ｉ］であり、終点座標はＥ［ｉ］であり、当該局所対応のスコアはＳ［ｉ］である。
【０１３６】
本実施形態では、局所対応に関する情報として、始点情報、終点情報、及びスコア情報が記憶されるが、局所対応のパス情報（アラインメント）も記憶してもよい。
【０１３７】
図９は、本発明の第１の実施形態の局所対応収集処理の説明図である。
【０１３８】
局所対応抽出部１０５は、図８に示す初期化処理を実行した後、局所対応収集処理を実行する。
【０１３９】
まず、局所対応抽出部１０５は、局所対応のＩＤが登録される変数ａを０に初期化する（Ｓ９０１）。
【０１４０】
局所対応のＩＤは、前述したように、局所対応の始点配列Ｂ、終点配列Ｅ、スコア配列Ｓのインデックスに相当する。Ｓ９０１では、局所対応が未抽出であるため、局所対応抽出部１０５は、局所対応のＩＤを０に初期化する。
【０１４１】
次に、局所対応抽出部１０５は、図１０に示す始点行列を初期化する（Ｓ９０２）。始点行列のセルはスコア行列のセルと対応しており、始点行列のセルには、当該セルが属する局所対応のＩＤが登録される。
【０１４２】
Ｓ９０２では、局所対応抽出部１０５は、始点行列のすべてのセルに初期値「−１」を登録する。始点行列の局所対応のＩＤが「−１」であることは、当該セルはいずれの局所対応にも属さないことを意味する。
【０１４３】
ここで、始点行列について、図１０を用いて説明する。図１０は、本発明の第１の実施形態の始点行列の説明図である。
【０１４４】
始点行列の各セルの座標は図６に示すスコア行列の座標と同じであり、各セルにはセルが属する局所対応のＩＤが登録される。なお、前述したように各セルには初期値として「−１」が登録されるため、「−１」が登録されているセルは、いずれの局所対応にも属さない。
【０１４５】
次に、局所対応抽出部１０５は、処理対象となるスコア行列の行を選択する（Ｓ９０３）。
【０１４６】
具体的には、局所対応抽出部１０５は、スコア行列の行のうち対象文字列の先頭の文字列に対応する行（配列Ｙの最初のインデックスに対応する行）を処理対象の行として選択し、当該処理対象の行にＳ９０４〜Ｓ９０６を実行する。局所対応抽出部１０５は、Ｓ９０４〜Ｓ９０６の処理を実行すると、選択した行の次の行（下の行）を処理対象の行として選択する。局所対応抽出部１０５は、Ｓ９０４〜Ｓ９０６がすべての行に実行されるまで繰り返す。
【０１４７】
次に、局所対応抽出部１０５は、処理対象の行に含まれる列から処理対象の列を選択する（Ｓ９０４）。
【０１４８】
具体的には、局所対応抽出部１０５は、処理対象の行に含まれる列のうち対象文字列の先頭の文字列に対応する列（配列Ｘの最初のインデックスに対応する行）を処理対象の列として選択し、当該処理対象の列にＳ９０５〜Ｓ９０６を実行する。局所対応抽出部１０５は、Ｓ９０５〜Ｓ９０６の処理を実行すると、選択した列の次の列（右の列）を処理対象の列として選択する。局所対応抽出部１０５は、Ｓ９０５〜Ｓ９０６が処理対象の行に含まれるすべての列に実行されるまで繰り返す。
【０１４９】
Ｓ９０３及びＳ９０４によって、スコア行列のセルからＳ９０５及び９０６の実行対象となるセル（以下、処理対象のセルという）が決まり、スコア行列のすべてのセルに対してＳ９０５及び９０６が実行される。
【０１５０】
次に、局所対応抽出部１０５は、処理対象のセルのスコアを算出する（Ｓ９０５）。
【０１５１】
具体的には、局所対応抽出部１０５は、図９のＳ９０５の１〜４に示すパスのスコアを算出し、算出したスコアから最大のスコア（Ｓｍａｘ）を選択して、選択した最大のスコアを処理対象のセル（Ｍ［ｒ］［ｃ］）に登録する。この場合、局所対応抽出部１０５は、パスの遷移元のセルの座標を（ｒ１、ｃ１）として記憶する。
【０１５２】
以下に、図９のＳ９０５の１〜４に示すパスについて説明する。
【０１５３】
Ｓ９０５の１は、スコアの最大値がマイナスの値にならないようにするためのものであり、スコアが「０」に設定されている。
【０１５４】
Ｓ９０５の２は、処理対象のセル（ｒ、ｃ）の真上に位置するセル（ｒ−１、ｃ）からの遷移で、縦方向の文字の読み飛ばしに相当する。この場合の処理対象のセルのスコアは、遷移元のセル（ｒ−１、ｃ）のスコア（Ｍ［ｒ−１］、［ｃ］）に読み飛ばしスコア（Ｓｋｉｐ）を加算することによって算出される。
【０１５５】
Ｓ９０５の３は、処理対象のセル（ｒ、ｃ）の左に位置するセル（ｒ、ｃ−１）からの遷移で、横方向の文字の読み飛ばしに相当する。この場合の処理対象のセルのスコアは、遷移元のセル（ｒ、ｃ−１）のスコア（Ｍ［ｒ］、［ｃ−１］）に読み飛ばしスコア（Ｓｋｉｐ）を加算することによって算出される。
【０１５６】
Ｓ９０５の４は、処理対象のセル（ｒ、ｃ）の左上に位置するセル（ｒ−１、ｃ−１）からの遷移で、処理対象のセルに対応する二つの文字（配列Ｘ［ｒ］と配列Ｙ［ｃ］）が一致するか否かで算出するスコアが異なる。
【０１５７】
処理対象のセルに対応する二つの文字が一致する場合の処理対象のセルのスコアは、遷移元の遷移元のセル（ｒ−１、ｃ−１）のスコア（Ｍ［ｒ−１］、［ｃ−１］）に一致スコア（Ｍａｔｃｈ）を加算することによって算出される。
【０１５８】
一方、処理対象のセルに対応する二つの文字が一致しない場合の処理対象のセルのスコアは、遷移元の遷移元のセル（ｒ−１、ｃ−１）のスコア（Ｍ［ｒ−１］、［ｃ−１］）に不一致スコア（Ｕｎｍａｔｃｈ）を加算することによって算出される。
【０１５９】
Ｓ９０５によってスコア行列のセルにスコアが登録されるので、Ｓ９０５をスコア行列生成処理という。
【０１６０】
次に、局所対応抽出部１０５は、Ｓ９０５で算出された処理対象のセルの最大のスコアＳｍａｘに基づいて、当該処理対象のセルの座標を局所対応の終点に設定するか否かを決定する枝刈り処理を実行する（Ｓ９０６）。
【０１６１】
以下、枝刈り処理について詳細に説明する。
【０１６２】
まず、局所対応抽出部１０５は、Ｓ９０５で算出された処理対象のセルの最大のスコアＳｍａｘが「０」であるか否かを判定する。
【０１６３】
Ｓ９０５で算出された処理対象のセルの最大のスコアＳｍａｘが「０」である場合、局所対応抽出部１０５は、当該セルに対応する文字は局所対応に属さないので、Ｓ９０４の処理に戻り、次の処理対象の列を選択する。
【０１６４】
一方、Ｓ９０５で算出された処理対象のセルの最大のスコアＳｍａｘが「０」でない場合、局所対応抽出部１０５は、図１０に示す始点行列のうち遷移元のセルに登録された局所対応のＩＤを取得する。具体的には、局所対応抽出部１０５は、始点行列のセルのうち遷移元のセルの座標（ｒ１、ｃ１）に対応するセルに登録された局所対応のＩＤ（Ｐ［ｒ１］［ｃ１］）を取得する。なお、局所対応抽出部１０５は、取得した局所対応のＩＤをｋとして記憶する。
【０１６５】
そして、局所対応抽出部１０５は、取得した遷移元のセルの局所対応のＩＤが「−１」であるか否かを判定する。
【０１６６】
取得した遷移元のセルの局所対応のＩＤが「−１」である場合、処理対象のセルから新たな局所対応が始まるので、局所対応抽出部１０５は、新たな局所対応を設定する。
【０１６７】
具体的には、局所対応抽出部１０５は、始点行列のセルのうち処理対象のセルの座標（ｒ、ｃ）に対応するセルの局所対応ＩＤ（Ｐ［ｒ］［ｃ］）に新たな局所対応のＩＤ（ａ）を登録する。また、局所対応抽出部１０５は、処理対象のセルの座標（ｒ、ｃ）を始点配列Ｂ［ａ］及び終点配列Ｅ［ａ］に登録する。そして、局所対応抽出部１０５は、新たな局所対応のＩＤ（ａ）をインクリメントしておく。このように、新たな局所対応のＩＤ（ａ）は、新たに局所対応があった場合に備えて、局所対応が見つかるとインクリメントされる。
【０１６８】
一方、取得した遷移元のセルの局所対応のＩＤが「−１」でない場合、処理対象のセルは遷移元のセルと同じ局所対応に属するため、局所対応抽出部１０５は、始点行列のセルのうち処理対象のセルの座標（ｒ、ｃ）のセルに、遷移元のセルと同じ局所対応のＩＤ（ｋ）を登録する。つまり、始点行列のセルの局所対応のＩＤ（Ｐ［ｒ］［ｃ］）には、遷移元のセルの局所対応のＩＤ（Ｐ［ｒ１］［ｃ１］）が登録される。
【０１６９】
そして、局所対応抽出部１０５は、遷移元のセルの局所対応のＩＤ（ｋ）のスコア配列Ｓ［ｋ］に登録されたスコア（局所対応最大スコア）を取得し、処理対象のセルの最大のスコア（Ｓｍａｘ）が局所対応最大スコア（Ｓ［ｋ］）よりも大きいか否かを判定する。
【０１７０】
処理対象のセルの最大のスコア（Ｓｍａｘ）が局所対応最大スコア（Ｓ［ｋ］）よりも大きいと判定された場合、局所対応抽出部１０５は、処理対象のセルを終点にするために処理対象のセルの座標（ｒ、ｃ）を終点配列Ｅ［ｋ］に登録し、処理対象のセルの最大のスコアをスコア配列Ｓ［ｋ］に登録する。
【０１７１】
一方、処理対象のセルの最大のスコア（Ｓｍａｘ）が局所対応最大スコア（Ｓ［ｋ］）以下であると判定された場合、局所対応抽出部１０５は、Ｓ９０４の処理に戻り、次の処理対象の列を選択する。
【０１７２】
なお、Ｓ９０６で始点行列のセルに当該セルが属する局所対応のＩＤが登録されるので、Ｓ９０６を始点行列生成処理という。
【０１７３】
以上によって、局所対応抽出部１０５は、スコア行列の各セルのスコアを算出しながら、局所対応を収集する。なお、各局所対応の始点、終点、及び局所対応最大スコアは、それぞれ始点配列Ｂ、終点配列Ｅ、及びスコア配列Ｓに記憶される。これによって、局所対応抽出部１０５によって抽出される局所対応は、始点が一致する局所対応内でスコアが最大の文字が終点となるので、代表性が保証される。
【０１７４】
図１１は、本発明の第１の実施形態の局所対応抽出処理のフローチャートである。
【０１７５】
局所対応抽出処理は、図９に示す局所対応収集処理が実行された後に、局所対応抽出部１０５によって実行される処理であり、局所対応収集処理で収集された局所対応のうち局所対応最大スコアが所定値よりも大きい局所対応を抽出する処理である。
【０１７６】
まず、局所対応抽出部１０５は、図２及び図３に示すスコア閾値入力エリア２０６に入力されたスコア閾値の入力を受け付け、受け付けたスコア閾値をｔｈｒｅｓｈｏｌｄとして記憶する（Ｓ１１０１）。
【０１７７】
次に、局所対応抽出部１０５は、Ｓ１１０３の処理対象となる局所対応のＩＤを選択する（Ｓ１１０２）。ここで、Ｓ１１０２の処理で処理対象の局所対応のＩＤとして選択したＩＤを「ｉ」とする。
【０１７８】
具体的には、局所対応抽出部１０５は、局所対応のＩＤが「０」から順に選択し、局所対応のＩＤが「ａ」の局所対応にＳ１１０３の処理が実行されるまで繰り返す。
【０１７９】
次に、局所対応抽出部１０５は、Ｓ１１０２の処理で選択された局所対応のＩＤによって特定される局所対応の局所対応最大スコアがスコア閾値よりも大きいか否かを判定する。
【０１８０】
具体的には、局所対応抽出部１０５は、Ｓ１１０２の処理で選択された局所対応のＩＤ「ｉ」に対応するスコア配列Ｓ［ｉ］に登録された局所対応最大スコアがスコア閾値よりも大きいか否かを判定する。
【０１８１】
Ｓ１１０２の処理で選択された局所対応のＩＤによって特定される局所対応の局所対応最大スコアがスコア閾値よりも大きいと判定された場合、局所対応抽出部１０５は、当該局所対応のＩＤによって特定される局所対応を局所対応として抽出する（Ｓ１１０３）。
【０１８２】
例えば、局所対応のＩＤ「ｉ」によって特定される局所対応が局所対応として抽出され、当該抽出された局所対応の始点配列Ｂ［ｉ］の座標が（ｒ１、ｃ１）であり、終点配列Ｅ［ｉ］の座標が（ｒ２、ｃ２）である場合、一方の対象文字列の配列Ｘ［ｒ１．．ｒ２］が示す部分文字列、及び他方の対象文字列の配列Ｙ［ｃ１．．ｃ２］が示す部分文字列が局所対応となる。
【０１８３】
したがって、局所対応抽出部１０５は局所対応最大スコアが所定値よりも大きい局所対応を抽出し、この抽出された局所対応が局所対応表示制御部１０６によって表示される。ここで、局所対応最大スコアが小さい局所対応は、始点の座標と終点の座標との距離が短く（つまり、局所対応の面積が小さく）、局所対応最大スコアが大きい局所対応は、始点の座標と終点の座標との距離が長い（つまり、局所対応の面積が大きい）。このため、図１１に示す局所対応抽出処理が実行されることによって、局所対応表示制御部１０６は、あまりにも面積が小さい局所対応を図２に示す局所対応表示エリア２１１に表示しないので、局所対応表示エリア２１１の表示が煩雑になることを防止できる。
【０１８４】
なお、本実施形態では、局所対応抽出部１０５が、図１１に示す局所対応抽出処理を実行したが、局所対応表示制御部１０６が実行してもよい。具体的には、局所対応抽出部１０５は、図９に示す局所対応収集処理で収集されたすべての局所対応を局所対応として抽出する。そして、局所対応表示制御部１０６は、抽出された局所対応に対して図１１に示す局所対応抽出処理を実行して、局所対応最大スコアがスコア閾値よりも大きい局所対応のみを表示するようにしてもよい。
【０１８５】
（第２の実施形態）
以下、本発明の第２の実施形態を図１２〜図１５を用いて説明する。
【０１８６】
本実施形態は、網羅性を向上させるための処理（最大ギャップ長制約処理）を第１の実施形態の局所対応処理に追加した実施形態である。
【０１８７】
まず、第１実施形態による局所対応処理では所望の局所対応が抽出できない場合について説明する。図１２は、二つの文字列間に本発明の第１の実施形態の局所対応処理を実行し、局所対応が抽出されない場合の説明図である。
【０１８８】
図１２では、文字列Ｃ「ａａａａａ１２３４ｂｂｂ」と文字列Ｄ「ａａａａａ１２３４ｂｂｂ」との間で、第１の実施形態による局所対応処理によって局所対応を抽出する場合について説明する。
【０１８９】
この場合、文字列Ｃ及び文字列Ｄの間で共通する「ａａａａａ」及び「ｂｂｂ」が局所対応として抽出されると直観的に想定される。
【０１９０】
しかしながら、図９に示す第１の実施形態による局所対応収集処理では、「ａａａａａ」しか局所対応として抽出されない。
【０１９１】
これについて以下に具体的に説明する。
【０１９２】
文字列Ｃ及び文字列Ｄ間で「ａａａａａ」部分が一致するため、５番目の「ａ」のスコアが「１０」となる（１２０１）。この後、文字列Ｃの「１２３４」部分と文字列Ｄ「５６７８」部分とが一致しないので、スコアは「−２」ずつ減少し、文字列Ｃの「４」及び文字列Ｄの「８」に対応するスコアは「２」となる（１２０２）。そして、文字列Ｃ及び文字列Ｄで「ｂｂｂ」部分が一致するため、３番目の「ｂ」のスコアは「８」となる。
【０１９３】
ここで、前述したように、図９に示すＳ９０５では、処理対象のセルの最大スコアＳｍａｘが０よりも大きい場合であって、当該処理対象のセルの遷移元のセルの局所対応のＩＤが「−１」である場合、当該処理対象のセルから新たな局所対応が開始することとなる。図９に示すＳ９０５では、処理対象のセルの最大スコアＳｍａｘが０である場合、局所対応抽出部１０５は当該セルに対して何もしないため、始点行列の処理対象のセルには、初期値「−１」が登録されたままとなっている。
【０１９４】
このため、図９に示す局所対応収集処理では、処理対象のセルの最大スコアが０よりも大きい値で、遷移元のセルの最大スコアＳｍａｘが０である場合にのみ、新たな局所対応が開始される。すなわち、セルの最大スコアがいったん０より大きくなると、最大スコアが０になるセルがあるまで同じ局所対応に属することになる。
【０１９５】
したがって、一度最大スコアが大きくなると、最大スコアが０になるまでの間に新たな局所対応が存在しても抽出できず、当該新たな局所対応は隠匿されてしまう。
【０１９６】
図１２では、１２０１のスコア「１０」が一番目の「ｂ」までに「０」まで減衰しないため、「ｂｂｂ」を新たな局所対応として抽出できない。
【０１９７】
図１３は、酷似する二つの文書に第１の実施形態の局所対応処理を実行することによって抽出された局所対応の表示例である。
【０１９８】
局所対応処理によって抽出された局所対応は、局所対応表示制御部１０６によって、図２に示す局所対応表示エリア２１１に二次元マップ表示される。局所対応は、局所対応最大スコアが大きいほど大きな矩形で局所対応表示エリア２１１に表示される。
【０１９９】
図１３に示す１３０１は、二つの文書の局所対応のうち最大の局所対応を示す。当該最大の局所対応の右下には局所対応が抽出されていない空白部分が存在する（１３０２）。最大の局所対応の局所対応最大スコアが大きいため、後方（右下部）のスコアが０に減衰しないため、この部分に局所対応があっても新たな局所対応として抽出されない。
【０２００】
つまり、第１の実施形態の局所対応収集処理では、始点一致による枝刈りによって、局所対応の代表性を重視するあまり、局所対応が網羅的に抽出されないという問題が生ずる。
【０２０１】
そこで、本実施形態では、最大ギャップ長制約を行うことによって前述の問題を解決する。
【０２０２】
ここで、ギャップ長とは、局所対応の終点から不一致又は読み飛ばしが連続する文字数である。ここで、図１２に示す文字列Ｃ「ａａａａａ１２３４ｂｂｂ」及び文字列Ｄ「ａａａａａ５６７８ｂｂｂ」の場合、５番目の「ａ」のスコアが「１０」で局所対応最大スコアとなるため、５番目の「ａ」が局所対応の終点となる。そして、終点である５番目の「ａ」から「１２３４」と「５６７８」とが一致しないので、ギャップ長は４となる。
【０２０３】
最大ギャップ長制約は、局所対応のギャップ長が所定値（最大ギャップ長）以下であるとの制約である。図１２では、ギャップ長の所定値が「３」に設定されていれば、「１２３４」と「５６７８」とが一致しないと判定された時点で、「ａａａａａ」の局所対応は、文字列Ｃでは「４」、文字列Ｄでは「８」以降まで継続し得ないため、当該個所で局所対応がリセットされる。このため、後方の「ｂｂｂ」が新たな局所対応として抽出できる。
【０２０４】
図１４を用いて、最大ギャップ長制約の詳細について説明する。
【０２０５】
図１４は、本発明の第２の実施形態の局所対応収集処理の説明図である。
【０２０６】
最大ギャップ長制約を実現するためには、第１の実施形態の図９に示す局所対応収集処理に最大ギャップ長制約処理を追加するだけでよい。図１４に示す処理のうち、図９に示す処理と同じ処理は同じ符号を付与し、説明を省略する。
【０２０７】
まず、局所対応抽出部１０５は、図２に示すギャップ入力ボックス２０５に入力された値を最大ギャップ長（ｇａｐ）として取得する（１４０１）。
【０２０８】
そして、局所対応抽出部１０５は、Ｓ９０１〜Ｓ９０５を実行し、最大ギャップ長制約処理を実行する（１４０２）。
【０２０９】
局所対応抽出部１０５は、Ｓ９０５の処理で、処理対象のセルの最大スコアとして、処理対象のセルに対応する二つの文字が一致しない場合（図１４に示すＳ９０５の４．２）のスコアが選択された場合にのみ、最大ギャップ長制約処理を実行する。
【０２１０】
まず、局所対応抽出部１０５は、図１０に示す始点行列のうち遷移元のセルに登録された局所対応のＩＤを取得する。具体的には、局所対応抽出部１０５は、始点行列のセルのうち遷移元のセルの座標（ｒ１、ｃ１）に対応するセルに登録された局所対応のＩＤ（Ｐ［ｒ１］［ｃ１］）を取得する。なお、局所対応抽出部１０５は、取得した局所対応のＩＤをｋとして記憶する。
【０２１１】
次に、局所対応抽出部１０５は、取得した局所対応のＩＤによって特定される局所対応の終点の座標（ｒ２、ｃ２）を取得する。具体的には、局所対応抽出部１０５は、終点配列Ｅのうち、取得した局所対応のＩＤ（ｋ）に対応する終点配列Ｅ［ｋ］に登録される終点の座標（ｒ２、ｃ２）を取得する。
【０２１２】
次に、局所対応抽出部１０５は、終点の座標（ｒ２、ｃ２）から処理対象のセルの座標（ｒ、ｃ）までのギャップ長を算出する。具体的には、局所対応抽出部１０５は、行方向のギャップ長をｒ−ｒ２によって算出し、列方向のギャップ長をｃ−ｃ２によって算出する。
【０２１３】
そして、局所対応抽出部１０５は、算出した行方向のギャップ長及び列方向のギャップ長の少なくとも一方が最大ギャップ長（ｇａｐ）よりも大きい場合、新たな局所対応を設定し、Ｓ９０６に進む。
【０２１４】
具体的には、局所対応抽出部１０５は、始点行列のセルのうち処理対象のセルの座標（ｒ、ｃ）に対応するセルの局所対応ＩＤ（Ｐ［ｒ］［ｃ］）に新たな局所対応のＩＤ（ａ）を登録する。また、局所対応抽出部１０５は、処理対象のセルの座標（ｒ、ｃ）を始点配列Ｂ［ａ］及び終点配列Ｅ［ａ］に登録する。そして、局所対応抽出部１０５は、新たな局所対応のＩＤ（ａ）をインクリメントしておく。
【０２１５】
一方、局所対応抽出部１０５は、算出した行方向のギャップ長及び列方向のギャップ長が最大ギャップ長（ｇａｐ）以下である場合、何もせずに、Ｓ９０６に進む。
【０２１６】
なお、図１４に示す局所対応処理のＳ１４０２では、処理対象のセルの最大スコアとして、処理対象のセルに対応する二つの文字が一致しない場合のスコアが選択された場合にのみ、最大ギャップ長制約処理が実行されるとしたが、処理対象のセルの最大スコアとして読み飛ばしのスコアが選択された場合にも実行されてもよい。
【０２１７】
以上のように、本実施形態では、局所対応の終点から不一致又は読み飛ばしの文字が所定回数連続する場合には、新たな局所対応を設定するため、スコアの大きな局所対応が抽出されても、当該スコアの大きな局所対応の後の局所対応を網羅的に抽出できる。
【０２１８】
また、最大ギャップ長制約処理は、スコア行列の各セルのスコアを算出しながら実行されるため、従来のＳｍｉｔｈ−Ｗａｔｅｒｍａｎ法とほぼ同じ計算量で実行できる。
【０２１９】
図１５は、本発明の第２の実施形態の局所対応処理を実行することによって抽出された局所対応の表示例である。
【０２２０】
図１５は、図１３と同じ文書に対して図１４に示す局所対応収集処理を実行した場合の局所対応の表示例である。
【０２２１】
図１５では、二つの文書の局所対応のうち最大の局所対応（１３０１）の右下部の局所対応も抽出されている。
【０２２２】
以上によって、本実施形態では、代表的な局所対応の抽出の網羅性を向上させることができる。
【符号の説明】
【０２２３】
１０ 局所対応抽出装置
１０１ ＣＰＵ
１０２ メモリ
１０３ キーボード・マウス
１０４ ディスプレイ
１０５ 局所対応抽出部
１０６ 局所対応表示制御部
１０７ 通信部
１１ ネットワーク
１２ 検索サーバ
【特許請求の範囲】
【請求項１】
任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出装置において、
前記局所対応抽出部は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とし、前記行の文字列を構成する文字及び前記列の文字列を構成する文字に対応するセルに、当該セルに対応する二つの文字の類似度を示すスコアを登録して、第一行列を生成する第一行列生成部と、
前記第一行列のセルに対応するセルによって構成される第二行列のセルのうち前記第一行列生成部によってスコアが算出されたセルに対応するセルに、当該セルに対応する二つの文字が属する局所対応の識別子を登録して、前記第二行列を生成する第二行列生成部と、を有し、
前記第一行列のセルに登録されるスコアは、当該セルに対応する二つの文字の類似度が大きいほど大きい値を示し、
前記第一行列生成部は、
前記スコアの算出対象のセルに隣接するセルのうちすでにスコアが算出されたセルから当該算出対象のセルまでのパスに予め設定された値に基づいて前記算出対象のセルのスコアを算出し、
前記算出されたスコアのうち最大のスコアを前記算出対象のセルのスコアとして登録し、
前記最大のスコアが算出されたパスの起点となる前記セルを遷移元セルとして記憶し、
前記第二行列生成部は、
前記遷移元セルに対応する前記第二行列のセルがどの局所対応にも属しないことを示し、かつ、前記第一行列生成部によって算出された最大のスコアが所定値である場合、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記新たな局所対応の始点として前記算出対象のセルを記憶し、
前記遷移元セルに対応する前記第二行列のセルがいずれかの局所対応に属することを示し、かつ、前記第一行列生成部によって算出された最大のスコアが前記所定値よりも大きい場合、前記算出対象のセルに対応する前記第二行列のセルに、前記遷移元セルに対応する前記第二行列のセルに登録された局所対応の識別子を登録し、さらに、前記算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、前記局所対応の終点として前記算出対象のセルを記憶することを特徴とする局所対応抽出装置。
【請求項２】
前記第一行列生成部は、
前記第一行列の最も上に位置する行を選択し、前記選択された行の左側の列のセルから順に前記スコアを算出し、
前記選択された行のすべてのセルの前記スコアを算出した場合、当該選択された行の下方に位置する行を選択し、
前記算出対象のセルの上に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、前記上に隣接するセルのすでに計算されたスコアから第一所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、前記左に隣接するセルのすでに計算されたスコアから第二所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左上に隣接するセルから該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、当該算出対象のセルに対応する二つの文字が一致するか否かを判定し、
当該算出対象のセルに対応する二つの文字が一致すると判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第三所定値を加算して前記算出対象のスコアを算出し、
当該算出対象のセルに対応する二つの文字が一致しないと判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第四所定値を減算して前記算出対象のスコアを算出することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項３】
前記第二行列生成部は、
前記二つの文字が一致しないセルが、当該セルが属する前記局所対応の前記終点となるセルから所定回数連続するか否かを判定し、
前記二つの文字が一致しないセルが前記終点となるセルから所定回数連続すると判定された場合、前記第一行列生成部によって算出された最大のスコアが所定値より大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項４】
前記局所対応抽出部は、
前記第一行列生成部によって算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録するための前記所定回数をユーザによって入力された値に設定することを特徴とする請求項２に記載の局所対応抽出装置。
【請求項５】
前記局所対応抽出部によって抽出された局所対応の表示を制御する局所対応表示制御部を備え、
前記局所対応表示制御部は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とする２次元マップ上で、前記局所対応抽出部によって抽出された局所対応の始点と終点とを、矩形によって表示し、
前記行方向及び前記列方向の局所対応の分布の一覧を表示することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項６】
前記局所対応表示制御部は、
前記行方向に存在する局所対応の最大スコアを加算することによって、前記行方向の局所対応の分布を算出し、
前記列方向に存在する局所対応の最大スコアを加算することによって、前記列方向の局所対応の分布を算出することを特徴とする請求項５に記載の局所対応抽出装置。
【請求項７】
前記局所対応表示制御部は、
前記行方向に存在する局所対応の数を加算することによって、前記行方向の局所対応の分布を算出し、
前記列方向に存在する局所対応の数を加算することによって、前記列方向の局所対応の分布を算出することを特徴とする請求項５に記載の局所対応抽出装置。
【請求項８】
任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出方法において、
前記方法は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とし、前記行の文字列を構成する文字及び前記列の文字列を構成する文字に対応するセルに、当該セルに対応する二つの文字の類似度を示すスコアを登録して、第一行列を生成する第一行列生成ステップと、
前記第一行列のセルに対応するセルによって構成される第二行列のセルのうち前記第一行列生成部によってスコアが算出されたセルに対応するセルに、当該セルに対応する二つの文字が属する局所対応の識別子を登録して、前記第二行列を生成する第二行列生成ステップと、を含み、
前記第一行列のセルに登録されるスコアは、当該セルに対応する二つの文字の類似度が大きいほど大きい値を示し、
前記第一行列生成ステップは、
前記スコアの算出対象のセルに隣接するセルのうちすでにスコアが算出されたセルから当該算出対象のセルまでのパスに予め設定された値に基づいて前記算出対象のセルのスコアを算出するステップと、
前記算出されたスコアのうち最大のスコアを前記算出対象のセルのスコアとして登録するステップと、
前記最大のスコアが算出されたパスの起点となる前記セルを遷移元セルとして記憶するステップと、を含み、
前記第二行列生成ステップは、
前記遷移元セルに対応する前記第二行列のセルがどの局所対応にも属しないことを示し、かつ、前記第一行列生成部によって算出された最大のスコアが所定値である場合、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶するステップと、
前記遷移元セルに対応する前記第二行列のセルがいずれかの局所対応に属することを示し、かつ、前記第一行列生成部によって算出された最大のスコアが前記所定値よりも大きい場合、前記算出対象のセルに対応する前記第二行列のセルに、前記遷移元セルに対応する前記第二行列のセルに登録された局所対応の識別子を登録し、さらに、前記算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、前記算出対象のセルに対応する二つの文字が前記局所対応の終点となることを記憶するステップと、を含むことを特徴とする局所対応抽出方法。
【請求項９】
前記第一行列生成ステップは、
前記第一行列の最も上に位置する行を選択し、前記選択された行の左側の列のセルから順に前記スコアを算出するステップと、
前記選択された行のすべてのセルの前記スコアを算出した場合、当該選択された行の下方に位置する行を選択するステップと、を含み、
前記算出対象のセルの上に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップでは、前記上に隣接するセルのすでに計算されたスコアから第一所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップでは、前記左に隣接するセルのすでに計算されたスコアから第二所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左上に隣接するセルから該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップは、当該算出対象のセルに対応する二つの文字が一致するか否かを判定するステップを含み、
当該算出対象のセルに対応する二つの文字が一致すると判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第三所定値を加算して前記算出対象のスコアを算出し、
当該算出対象のセルに対応する二つの文字が一致しないと判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第四所定値を減算して前記算出対象のスコアを算出することを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１０】
前記第二行列生成ステップは、
前記二つの文字が一致しないセルが、当該セルが属する前記局所対応の前記終点となるセルから所定回数連続するか否かを判定するステップと、
前記二つの文字が一致しないセルが前記終点となるセルから所定回数連続すると判定された場合、前記第一行列生成部によって算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶するステップと、を含むことを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１１】
前記方法は、前記第一行列生成ステップによって算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録するための前記所定回数をユーザによって入力された値に設定するステップを含むことを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１２】
前記方法は、前記局所対応抽出ステップによって抽出された局所対応の表示を制御する局所対応表示制御ステップを含み、
前記局所対応表示制御ステップは、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とする２次元マップ上で、前記局所対応抽出部によって抽出された局所対応の始点と終点とを、矩形によって表示するステップと、
前記行方向及び前記列方向の局所対応の分布の一覧を表示するステップと、を含むことを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１３】
前記局所対応表示制御ステップは、
前記行方向に存在する局所対応の最大スコアを加算することによって、前記行方向の局所対応の分布を算出するステップと、
前記列方向に存在する局所対応の最大スコアを加算することによって、前記列方向の局所対応の分布を算出するステップと、を含むことを特徴とする請求項１２に記載の局所対応抽出方法。
【請求項１４】
前記局所対応表示制御ステップは、
前記行方向に存在する局所対応の数を加算することによって、前記行方向の局所対応の分布を算出するステップと、
前記列方向に存在する局所対応の数を加算することによって、前記列方向の局所対応の分布を算出するステップと、を含むことを特徴とする請求項１２に記載の局所対応抽出方法。
【請求項１】
任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出装置において、
前記局所対応抽出部は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とし、前記行の文字列を構成する文字及び前記列の文字列を構成する文字に対応するセルに、当該セルに対応する二つの文字の類似度を示すスコアを登録して、第一行列を生成する第一行列生成部と、
前記第一行列のセルに対応するセルによって構成される第二行列のセルのうち前記第一行列生成部によってスコアが算出されたセルに対応するセルに、当該セルに対応する二つの文字が属する局所対応の識別子を登録して、前記第二行列を生成する第二行列生成部と、を有し、
前記第一行列のセルに登録されるスコアは、当該セルに対応する二つの文字の類似度が大きいほど大きい値を示し、
前記第一行列生成部は、
前記スコアの算出対象のセルに隣接するセルのうちすでにスコアが算出されたセルから当該算出対象のセルまでのパスに予め設定された値に基づいて前記算出対象のセルのスコアを算出し、
前記算出されたスコアのうち最大のスコアを前記算出対象のセルのスコアとして登録し、
前記最大のスコアが算出されたパスの起点となる前記セルを遷移元セルとして記憶し、
前記第二行列生成部は、
前記遷移元セルに対応する前記第二行列のセルがどの局所対応にも属しないことを示し、かつ、前記第一行列生成部によって算出された最大のスコアが所定値である場合、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記新たな局所対応の始点として前記算出対象のセルを記憶し、
前記遷移元セルに対応する前記第二行列のセルがいずれかの局所対応に属することを示し、かつ、前記第一行列生成部によって算出された最大のスコアが前記所定値よりも大きい場合、前記算出対象のセルに対応する前記第二行列のセルに、前記遷移元セルに対応する前記第二行列のセルに登録された局所対応の識別子を登録し、さらに、前記算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、前記局所対応の終点として前記算出対象のセルを記憶することを特徴とする局所対応抽出装置。
【請求項２】
前記第一行列生成部は、
前記第一行列の最も上に位置する行を選択し、前記選択された行の左側の列のセルから順に前記スコアを算出し、
前記選択された行のすべてのセルの前記スコアを算出した場合、当該選択された行の下方に位置する行を選択し、
前記算出対象のセルの上に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、前記上に隣接するセルのすでに計算されたスコアから第一所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、前記左に隣接するセルのすでに計算されたスコアから第二所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左上に隣接するセルから該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、当該算出対象のセルに対応する二つの文字が一致するか否かを判定し、
当該算出対象のセルに対応する二つの文字が一致すると判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第三所定値を加算して前記算出対象のスコアを算出し、
当該算出対象のセルに対応する二つの文字が一致しないと判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第四所定値を減算して前記算出対象のスコアを算出することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項３】
前記第二行列生成部は、
前記二つの文字が一致しないセルが、当該セルが属する前記局所対応の前記終点となるセルから所定回数連続するか否かを判定し、
前記二つの文字が一致しないセルが前記終点となるセルから所定回数連続すると判定された場合、前記第一行列生成部によって算出された最大のスコアが所定値より大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項４】
前記局所対応抽出部は、
前記第一行列生成部によって算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録するための前記所定回数をユーザによって入力された値に設定することを特徴とする請求項２に記載の局所対応抽出装置。
【請求項５】
前記局所対応抽出部によって抽出された局所対応の表示を制御する局所対応表示制御部を備え、
前記局所対応表示制御部は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とする２次元マップ上で、前記局所対応抽出部によって抽出された局所対応の始点と終点とを、矩形によって表示し、
前記行方向及び前記列方向の局所対応の分布の一覧を表示することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項６】
前記局所対応表示制御部は、
前記行方向に存在する局所対応の最大スコアを加算することによって、前記行方向の局所対応の分布を算出し、
前記列方向に存在する局所対応の最大スコアを加算することによって、前記列方向の局所対応の分布を算出することを特徴とする請求項５に記載の局所対応抽出装置。
【請求項７】
前記局所対応表示制御部は、
前記行方向に存在する局所対応の数を加算することによって、前記行方向の局所対応の分布を算出し、
前記列方向に存在する局所対応の数を加算することによって、前記列方向の局所対応の分布を算出することを特徴とする請求項５に記載の局所対応抽出装置。
【請求項８】
任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出方法において、
前記方法は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とし、前記行の文字列を構成する文字及び前記列の文字列を構成する文字に対応するセルに、当該セルに対応する二つの文字の類似度を示すスコアを登録して、第一行列を生成する第一行列生成ステップと、
前記第一行列のセルに対応するセルによって構成される第二行列のセルのうち前記第一行列生成部によってスコアが算出されたセルに対応するセルに、当該セルに対応する二つの文字が属する局所対応の識別子を登録して、前記第二行列を生成する第二行列生成ステップと、を含み、
前記第一行列のセルに登録されるスコアは、当該セルに対応する二つの文字の類似度が大きいほど大きい値を示し、
前記第一行列生成ステップは、
前記スコアの算出対象のセルに隣接するセルのうちすでにスコアが算出されたセルから当該算出対象のセルまでのパスに予め設定された値に基づいて前記算出対象のセルのスコアを算出するステップと、
前記算出されたスコアのうち最大のスコアを前記算出対象のセルのスコアとして登録するステップと、
前記最大のスコアが算出されたパスの起点となる前記セルを遷移元セルとして記憶するステップと、を含み、
前記第二行列生成ステップは、
前記遷移元セルに対応する前記第二行列のセルがどの局所対応にも属しないことを示し、かつ、前記第一行列生成部によって算出された最大のスコアが所定値である場合、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶するステップと、
前記遷移元セルに対応する前記第二行列のセルがいずれかの局所対応に属することを示し、かつ、前記第一行列生成部によって算出された最大のスコアが前記所定値よりも大きい場合、前記算出対象のセルに対応する前記第二行列のセルに、前記遷移元セルに対応する前記第二行列のセルに登録された局所対応の識別子を登録し、さらに、前記算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、前記算出対象のセルに対応する二つの文字が前記局所対応の終点となることを記憶するステップと、を含むことを特徴とする局所対応抽出方法。
【請求項９】
前記第一行列生成ステップは、
前記第一行列の最も上に位置する行を選択し、前記選択された行の左側の列のセルから順に前記スコアを算出するステップと、
前記選択された行のすべてのセルの前記スコアを算出した場合、当該選択された行の下方に位置する行を選択するステップと、を含み、
前記算出対象のセルの上に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップでは、前記上に隣接するセルのすでに計算されたスコアから第一所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップでは、前記左に隣接するセルのすでに計算されたスコアから第二所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左上に隣接するセルから該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップは、当該算出対象のセルに対応する二つの文字が一致するか否かを判定するステップを含み、
当該算出対象のセルに対応する二つの文字が一致すると判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第三所定値を加算して前記算出対象のスコアを算出し、
当該算出対象のセルに対応する二つの文字が一致しないと判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第四所定値を減算して前記算出対象のスコアを算出することを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１０】
前記第二行列生成ステップは、
前記二つの文字が一致しないセルが、当該セルが属する前記局所対応の前記終点となるセルから所定回数連続するか否かを判定するステップと、
前記二つの文字が一致しないセルが前記終点となるセルから所定回数連続すると判定された場合、前記第一行列生成部によって算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶するステップと、を含むことを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１１】
前記方法は、前記第一行列生成ステップによって算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録するための前記所定回数をユーザによって入力された値に設定するステップを含むことを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１２】
前記方法は、前記局所対応抽出ステップによって抽出された局所対応の表示を制御する局所対応表示制御ステップを含み、
前記局所対応表示制御ステップは、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とする２次元マップ上で、前記局所対応抽出部によって抽出された局所対応の始点と終点とを、矩形によって表示するステップと、
前記行方向及び前記列方向の局所対応の分布の一覧を表示するステップと、を含むことを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１３】
前記局所対応表示制御ステップは、
前記行方向に存在する局所対応の最大スコアを加算することによって、前記行方向の局所対応の分布を算出するステップと、
前記列方向に存在する局所対応の最大スコアを加算することによって、前記列方向の局所対応の分布を算出するステップと、を含むことを特徴とする請求項１２に記載の局所対応抽出方法。
【請求項１４】
前記局所対応表示制御ステップは、
前記行方向に存在する局所対応の数を加算することによって、前記行方向の局所対応の分布を算出するステップと、
前記列方向に存在する局所対応の数を加算することによって、前記列方向の局所対応の分布を算出するステップと、を含むことを特徴とする請求項１２に記載の局所対応抽出方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１４】
【図１３】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１４】
【図１３】
【図１５】
【公開番号】特開２０１２−５９１００（Ｐ２０１２−５９１００Ａ）
【公開日】平成２４年３月２２日（２０１２．３．２２）
【国際特許分類】
【出願番号】特願２０１０−２０２７４５（Ｐ２０１０−２０２７４５）
【出願日】平成２２年９月１０日（２０１０．９．１０）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２４年３月２２日（２０１２．３．２２）
【国際特許分類】
【出願日】平成２２年９月１０日（２０１０．９．１０）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]