【手続補正書】
【提出日】平成24年12月20日(2012.12.20)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
【特許文献１】特開２００４−３８３２９号公報
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
なお、図２では、局所対応表示エリア２１１の上方の表示領域２１５に横軸に対応する文字列を表示し、また、局所対応表示エリア２１１の左側の表示領域２１６に縦軸に対応する文字列を表示するが、これらの表示領域２１５、２１６には文字列が表示されなくてもよい。例えば、横軸及び縦軸に対応する文字列の文字数が所定数以上である場合には、局所対応表示制御部１０６は、表示領域２１５、２１６には文字列を表示しない。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００８４
【補正方法】変更
【補正の内容】
【００８４】
文字列Ａ「特許の検索精度を向上」と文字列Ｂ「特許検索の精度の向上」との間の各文字が対応付けられる。この各文字単位の対応をアラインメントという。アラインメントには、対応する文字同士が一致する一致アラインメント、及び、対応する文字同士が一致しない不一致アラインメントがある。図５では、「を」と「の」とのアラインメント５０が不一致アラインメントであり、その他のアラインメントは一致アラインメントである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１１１
【補正方法】変更
【補正の内容】
【０１１１】
以上のように、局所対応抽出部１０５は、図６に示す左上端のセルから順に横方向にスコアを登録する。そして、局所対応抽出部１０５は、一行のすべてのセルにスコアを登録した場合、次の行の左端のセルから順にスコアを登録する。このため、算出対象のセルの上のセル、左上のセル、及び左のセルのスコアは必ず登録されていることになる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１１９
【補正方法】変更
【補正の内容】
【０１１９】
本来の局所対応として抽出される文字列の最後の文字は、スコアが最大となるセルに対応する文字である。一致のアラインメントであればスコアを加算し、不一致のアラインメント及び読み飛ばしであればスコアが減少するように設定されている場合、二つの対象文字列の各文字が一致していればスコアは増加し、その他の場合スコアは減少するためであり、スコアが減少せずスコアが最大となる文字が本来の局所対応として抽出される文字列の最後の文字となる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１３０
【補正方法】変更
【補正の内容】
【０１３０】
次に、局所対応抽出部１０５は、スコア行列を初期化する（Ｓ８０２）。スコア行列は、図６で説明した行列であり、Ｍ［０．．ｌｘ］［０．．ｌｙ］で表現される。［０．．ｌｘ］が配列Ｘによって表現される対象文字列に相当し、［０．．ｌｙ］が配列Ｙによって表現される対象文字列に相当する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１３３
【補正方法】変更
【補正の内容】
【０１３３】
始点配列Ｂには、各局所対応の始点の座標が登録され、終点配列Ｅには、各局所対応の終点の座標が登録される。ここで、座標とは、スコア行列のインデックス対のことである。例えば、配列Ｘのi番目の文字Ｘ［ｉ］及び配列Ｙのｊ番目の文字Ｙ［ｊ］が始点である場合、始点の座標は（ｉ，ｊ）である。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１４６
【補正方法】変更
【補正の内容】
【０１４６】
具体的には、局所対応抽出部１０５は、スコア行列の行のうち対象文字列の先頭の文字に対応する行（配列Ｙの最初のインデックスに対応する行）を処理対象の行として選択し、当該処理対象の行にＳ９０４〜Ｓ９０６を実行する。局所対応抽出部１０５は、Ｓ９０４〜Ｓ９０６の処理を実行すると、選択した行の次の行（下の行）を処理対象の行として選択する。局所対応抽出部１０５は、Ｓ９０４〜Ｓ９０６がすべての行に実行されるまで繰り返す。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１４８
【補正方法】変更
【補正の内容】
【０１４８】
具体的には、局所対応抽出部１０５は、処理対象の行に含まれる列のうち対象文字列の先頭の文字に対応する列（配列Ｘの最初のインデックスに対応する列）を処理対象の列として選択し、当該処理対象の列にＳ９０５〜Ｓ９０６を実行する。局所対応抽出部１０５は、Ｓ９０５〜Ｓ９０６の処理を実行すると、選択した列の次の列（右の列）を処理対象の列として選択する。局所対応抽出部１０５は、Ｓ９０５〜Ｓ９０６が処理対象の行に含まれるすべての列に実行されるまで繰り返す。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１５７
【補正方法】変更
【補正の内容】
【０１５７】
処理対象のセルに対応する二つの文字が一致する場合の処理対象のセルのスコアは、遷移元のセル（ｒ−１、ｃ−１）のスコア（Ｍ［ｒ−１］、［ｃ−１］）に一致スコア（Ｍａｔｃｈ）を加算することによって算出される。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１５８
【補正方法】変更
【補正の内容】
【０１５８】
一方、処理対象のセルに対応する二つの文字が一致しない場合の処理対象のセルのスコアは、遷移元のセル（ｒ−１、ｃ−１）のスコア（Ｍ［ｒ−１］、［ｃ−１］）に不一致スコア（Ｕｎｍａｔｃｈ）を加算することによって算出される。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１８８
【補正方法】変更
【補正の内容】
【０１８８】
図１２では、文字列Ｃ「ａａａａａ１２３４ｂｂｂ」と文字列Ｄ「ａａａａａ５６７８ｂｂｂ」との間で、第１の実施形態による局所対応処理によって局所対応を抽出する場合について説明する。
【手続補正１３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出装置において、
前記局所対応抽出部は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とし、前記行の文字列を構成する文字及び前記列の文字列を構成する文字に対応するセルに、当該セルに対応する二つの文字の類似度を示すスコアを登録して、第一行列を生成する第一行列生成部と、
前記第一行列のセルに対応するセルによって構成される第二行列のセルのうち前記第一行列生成部によってスコアが算出されたセルに対応するセルに、当該セルに対応する二つの文字が属する局所対応の識別子を登録して、前記第二行列を生成する第二行列生成部と、を有し、
前記第一行列のセルに登録されるスコアは、当該セルに対応する二つの文字の類似度が大きいほど大きい値を示し、
前記第一行列生成部は、
前記スコアの算出対象のセルに隣接するセルのうちすでにスコアが算出されたセルから当該算出対象のセルまでのパスに予め設定された値に基づいて前記算出対象のセルのスコアを算出し、
前記算出されたスコアのうち最大のスコアを前記算出対象のセルのスコアとして登録し、
前記最大のスコアが算出されたパスの起点となる前記セルを遷移元セルとして記憶し、
前記第二行列生成部は、
前記遷移元セルに対応する前記第二行列のセルがどの局所対応にも属しないことを示し、かつ、前記第一行列生成部によって算出された最大のスコアが所定値である場合、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記新たな局所対応の始点として前記算出対象のセルを記憶し、
前記遷移元セルに対応する前記第二行列のセルがいずれかの局所対応に属することを示し、かつ、前記第一行列生成部によって算出された最大のスコアが前記所定値よりも大きい場合、前記算出対象のセルに対応する前記第二行列のセルに、前記遷移元セルに対応する前記第二行列のセルに登録された局所対応の識別子を登録し、さらに、前記算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、前記局所対応の終点として前記算出対象のセルを記憶することを特徴とする局所対応抽出装置。
【請求項２】
前記第一行列生成部は、
前記第一行列の最も上に位置する行を選択し、前記選択された行の左側の列のセルから順に前記スコアを算出し、
前記選択された行のすべてのセルの前記スコアを算出した場合、当該選択された行の下方に位置する行を選択し、
前記算出対象のセルの上に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、前記上に隣接するセルのすでに計算されたスコアから第一所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、前記左に隣接するセルのすでに計算されたスコアから第二所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左上に隣接するセルから該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出する場合、当該算出対象のセルに対応する二つの文字が一致するか否かを判定し、
当該算出対象のセルに対応する二つの文字が一致すると判定された場合、前記左上に隣接するセルのすでに計算されたスコアに第三所定値を加算して前記算出対象のスコアを算出し、
当該算出対象のセルに対応する二つの文字が一致しないと判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第四所定値を減算して前記算出対象のスコアを算出することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項３】
前記第二行列生成部は、
前記二つの文字が一致しないセルが、当該セルが属する前記局所対応の前記終点となるセルから所定回数連続するか否かを判定し、
前記二つの文字が一致しないセルが前記終点となるセルから所定回数連続すると判定された場合、前記第一行列生成部によって算出された最大のスコアが所定値より大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項４】
前記局所対応抽出部は、
前記第一行列生成部によって算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録するための前記所定回数をユーザによって入力された値に設定することを特徴とする請求項３に記載の局所対応抽出装置。
【請求項５】
前記局所対応抽出部によって抽出された局所対応の表示を制御する局所対応表示制御部を備え、
前記局所対応表示制御部は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とする２次元マップ上で、前記局所対応抽出部によって抽出された局所対応の始点と終点とを、矩形によって表示し、
行方向及び列方向の局所対応の分布の一覧を表示することを特徴とする請求項１に記載の局所対応抽出装置。
【請求項６】
前記局所対応表示制御部は、
前記行方向に存在する局所対応の最大スコアを加算することによって、前記行方向の局所対応の分布を算出し、
前記列方向に存在する局所対応の最大スコアを加算することによって、前記列方向の局所対応の分布を算出することを特徴とする請求項５に記載の局所対応抽出装置。
【請求項７】
前記局所対応表示制御部は、
前記行方向に存在する局所対応の数を加算することによって、前記行方向の局所対応の分布を算出し、
前記列方向に存在する局所対応の数を加算することによって、前記列方向の局所対応の分布を算出することを特徴とする請求項５に記載の局所対応抽出装置。
【請求項８】
任意の二つの文書間で類似する文字列である局所対応を抽出する局所対応抽出部を備える局所対応抽出方法において、
前記方法は、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とし、前記行の文字列を構成する文字及び前記列の文字列を構成する文字に対応するセルに、当該セルに対応する二つの文字の類似度を示すスコアを登録して、第一行列を生成する第一行列生成ステップと、
前記第一行列のセルに対応するセルによって構成される第二行列のセルのうち前記第一行列生成ステップでスコアが算出されたセルに対応するセルに、当該セルに対応する二つの文字が属する局所対応の識別子を登録して、前記第二行列を生成する第二行列生成ステップと、を含み、
前記第一行列のセルに登録されるスコアは、当該セルに対応する二つの文字の類似度が大きいほど大きい値を示し、
前記第一行列生成ステップは、
前記スコアの算出対象のセルに隣接するセルのうちすでにスコアが算出されたセルから当該算出対象のセルまでのパスに予め設定された値に基づいて前記算出対象のセルのスコアを算出するステップと、
前記算出されたスコアのうち最大のスコアを前記算出対象のセルのスコアとして登録するステップと、
前記最大のスコアが算出されたパスの起点となる前記セルを遷移元セルとして記憶するステップと、を含み、
前記第二行列生成ステップは、
前記遷移元セルに対応する前記第二行列のセルがどの局所対応にも属しないことを示し、かつ、前記第一行列生成ステップで算出された最大のスコアが所定値である場合、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶するステップと、
前記遷移元セルに対応する前記第二行列のセルがいずれかの局所対応に属することを示し、かつ、前記第一行列生成ステップで算出された最大のスコアが前記所定値よりも大きい場合、前記算出対象のセルに対応する前記第二行列のセルに、前記遷移元セルに対応する前記第二行列のセルに登録された局所対応の識別子を登録し、さらに、前記算出されたスコアが同じ局所対応に属するセルの最大のスコアよりも大きい場合、前記算出対象のセルに対応する二つの文字が前記局所対応の終点となることを記憶するステップと、を含むことを特徴とする局所対応抽出方法。
【請求項９】
前記第一行列生成ステップは、
前記第一行列の最も上に位置する行を選択し、前記選択された行の左側の列のセルから順に前記スコアを算出するステップと、
前記選択された行のすべてのセルの前記スコアを算出した場合、当該選択された行の下方に位置する行を選択するステップと、を含み、
前記算出対象のセルの上に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップでは、前記上に隣接するセルのすでに計算されたスコアから第一所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左に隣接するセルから当該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップでは、前記左に隣接するセルのすでに計算されたスコアから第二所定値を減算して前記算出対象のスコアを算出し、
前記算出対象のセルの左上に隣接するセルから該算出対象のセルまでのパスに基づき前記算出対象のセルのスコアを算出するステップは、当該算出対象のセルに対応する二つの文字が一致するか否かを判定するステップを含み、
当該算出対象のセルに対応する二つの文字が一致すると判定された場合、前記左上に隣接するセルのすでに計算されたスコアに第三所定値を加算して前記算出対象のスコアを算出し、
当該算出対象のセルに対応する二つの文字が一致しないと判定された場合、前記左上に隣接するセルのすでに計算されたスコアから第四所定値を減算して前記算出対象のスコアを算出することを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１０】
前記第二行列生成ステップは、
前記二つの文字が一致しないセルが、当該セルが属する前記局所対応の前記終点となるセルから所定回数連続するか否かを判定するステップと、
前記二つの文字が一致しないセルが前記終点となるセルから所定回数連続すると判定された場合、前記第一行列生成ステップで算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録し、前記算出対象のセルに対応する二つの文字が前記新たな局所対応の始点となることを記憶するステップと、を含むことを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１１】
前記方法は、前記第一行列生成ステップによって算出された最大のスコアが所定値よりも大きくても、前記算出対象のセルに対応する前記第二行列のセルに新たな局所対応の識別子を登録するための前記所定回数をユーザによって入力された値に設定するステップを含むことを特徴とする請求項１０に記載の局所対応抽出方法。
【請求項１２】
前記方法は、前記局所対応抽出部によって抽出された局所対応の表示を制御する局所対応表示制御ステップを含み、
前記局所対応表示制御ステップは、
前記二つの文書のうち一方の文書を構成する文字列を行とし、他方の文書を構成する文字列を列とする２次元マップ上で、前記局所対応抽出部によって抽出された局所対応の始点と終点とを、矩形によって表示するステップと、
行方向及び列方向の局所対応の分布の一覧を表示するステップと、を含むことを特徴とする請求項８に記載の局所対応抽出方法。
【請求項１３】
前記局所対応表示制御ステップは、
前記行方向に存在する局所対応の最大スコアを加算することによって、前記行方向の局所対応の分布を算出するステップと、
前記列方向に存在する局所対応の最大スコアを加算することによって、前記列方向の局所対応の分布を算出するステップと、を含むことを特徴とする請求項１２に記載の局所対応抽出方法。
【請求項１４】
前記局所対応表示制御ステップは、
前記行方向に存在する局所対応の数を加算することによって、前記行方向の局所対応の分布を算出するステップと、
前記列方向に存在する局所対応の数を加算することによって、前記列方向の局所対応の分布を算出するステップと、を含むことを特徴とする請求項１２に記載の局所対応抽出方法。
【手続補正１４】
【補正対象書類名】図面
【補正対象項目名】図１１
【補正方法】変更
【補正の内容】
【図１１】
2012059100.tif 000001