(57)【要約】【課題】入力文書中に、他の文書内の文字列の改変が無い連続した２つ以上の文である引用が含まれているかどうかを、少ない計算量で正確に検出可能とすること。【解決手段】引用元の候補となる原典文書集合中の文書を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約を生成し、各要約を前記部分文字列の出現順に並べた前記文書のダイジェストを、前記部分文字列毎に前方最長一致検索可能な形式でその文書ＩＤとともに登録してなる原典文書ＤＢ４を用意し、ダイジェスト生成手段５により、入力文書を前記同様のダイジェストに変換し、引用検出手段６により、前記入力文書のダイジェストをキーとして原典文書ＤＢ４を前方最長一致で検索し、この際、連続して一致する要約の数が所定の閾値以上の他の文書があればその文書ＩＤを出力する。【選択図】図６
2010182238.tif 000002
【特許請求の範囲】
【請求項１】
入力文書中に、他の文書内の文字列の改変が無い連続した２つ以上の文である引用が含まれているかどうかを検出し、含まれていれば当該他の文書の文書ＩＤを出力する装置であって、
他の文書の集合である原典文書集合中の各文書について、文書の文字列を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約をそれぞれ生成し、各要約を前記部分文字列の出現順に並べて構成した前記文書のダイジェストを、前記部分文字列毎に前方最長一致検索可能な形式でその文書ＩＤとともに登録した原典文書データベースと、
入力文書の文字列を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約をそれぞれ生成し、各要約を前記部分文字列の出現順に並べて構成した前記入力文書のダイジェストをその文書ＩＤとともに出力するダイジェスト生成手段と、
前記入力文書のダイジェストをキーとして原典文書データベースを前方最長一致で検索し、一致する要約の数が所定の閾値以上の他の文書があればその文書ＩＤを出力する引用検出手段とを備えた
ことを特徴とする引用検出装置。
【請求項２】
請求項１に記載の引用検出装置において、
ダイジェスト生成手段は、
文書の文字列を引用の単位となり得るセグメントに分割し、各セグメントをその出現順の情報、前記文書の文書ＩＤとともに出力するセグメンテーション部と、
前記各セグメントを正規化する正規化部と、
前記正規化後の各セグメントのうち、一定の長さ以下のセグメントを削除する足切り部と、
残りの正規化後の各セグメントを任意のハッシュ関数に入力してフィンガープリントをそれぞれ生成し、各フィンガープリントを前記各セグメントの出現順の情報に従って並べて構成した前記文書のダイジェストをその文書ＩＤとともに出力するフィンガープリント生成部とからなる
ことを特徴とする引用検出装置。
【請求項３】
他の文書の集合である原典文書集合から原典文書データベースを生成する装置であって、
原典文書集合中の各文書について、文書の文字列を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約をそれぞれ生成し、各要約を前記部分文字列の出現順に並べて構成した前記文書のダイジェストをその文書ＩＤとともに出力するダイジェスト生成手段と、
原典文書集合中の各文書に対応するダイジェストについて、前記部分文字列毎に前方最長一致検索可能な形式でその文書ＩＤとともに登録して原典文書データベースを生成する原典文書データベース生成手段とを備えた
ことを特徴とする原典文書データベース生成装置。
【請求項４】
請求項３に記載の原典文書データベース生成装置において、
ダイジェスト生成手段は、
原典文書集合中の各文書について、文書の文字列を引用の単位となり得るセグメントに分割し、各セグメントをその出現順の情報、前記文書の文書ＩＤとともに出力するセグメンテーション部と、
前記各セグメントを正規化する正規化部と、
前記正規化後の各セグメントのうち、一定の長さ以下のセグメントを削除する足切り部と、
残りの正規化後の各セグメントを任意のハッシュ関数に入力してフィンガープリントをそれぞれ生成し、各フィンガープリントを前記各セグメントの出現順の情報に従って並べて構成した前記文書のダイジェストをその文書ＩＤとともに出力するフィンガープリント生成部とからなる
ことを特徴とする原典文書データベース生成装置。
【請求項５】
入力文書中に、他の文書内の文字列の改変が無い連続した２つ以上の文である引用が含まれているかどうかを検出し、含まれていれば当該他の文書の文書ＩＤを出力する方法であって、
他の文書の集合である原典文書集合中の各文書について、文書の文字列を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約をそれぞれ生成し、各要約を前記部分文字列の出現順に並べて構成した前記文書のダイジェストを、前記部分文字列毎に前方最長一致検索可能な形式でその文書ＩＤとともに登録した原典文書データベースを用い、
ダイジェスト生成手段が、入力文書の文字列を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約をそれぞれ生成し、各要約を前記部分文字列の出現順に並べて構成した前記入力文書のダイジェストをその文書ＩＤとともに出力するステップと、
引用検出手段が、前記入力文書のダイジェストをキーとして原典文書データベースを前方最長一致で検索し、一致する要約の数が所定の閾値以上の他の文書があればその文書ＩＤを出力するステップとを含む
ことを特徴とする引用検出方法。
【請求項６】
請求項５に記載の引用検出方法において、
ダイジェスト生成ステップは、
セグメンテーション部が、文書の文字列を引用の単位となり得るセグメントに分割し、各セグメントをその出現順の情報、前記文書の文書ＩＤとともに出力するステップと、
正規化部が、前記各セグメントを正規化するステップと、
足切り部が、前記正規化後の各セグメントのうち、一定の長さ以下のセグメントを削除するステップと、
フィンガープリント生成部が、残りの正規化後の各セグメントを任意のハッシュ関数に入力してフィンガープリントをそれぞれ生成し、各フィンガープリントを前記各セグメントの出現順の情報に従って並べて構成した前記文書のダイジェストをその文書ＩＤとともに出力するステップとを含む
ことを特徴とする引用検出方法。
【請求項７】
他の文書の集合である原典文書集合から原典文書データベースを生成する方法であって、
ダイジェスト生成手段が、原典文書集合中の各文書について、文書の文字列を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約をそれぞれ生成し、各要約を前記部分文字列の出現順に並べて構成した前記文書のダイジェストをその文書ＩＤとともに出力するステップと、
原典文書データベース生成手段が、原典文書集合中の各文書に対応するダイジェストについて、前記部分文字列毎に前方最長一致検索可能な形式でその文書ＩＤとともに登録して原典文書データベースを生成するステップとを含む
ことを特徴とする原典文書データベース生成方法。
【請求項８】
請求項７に記載の原典文書データベース生成方法において、
ダイジェスト生成ステップは、
セグメンテーション部が、原典文書集合中の各文書について、文書の文字列を引用の単位となり得るセグメントに分割し、各セグメントをその出現順の情報、前記文書の文書ＩＤとともに出力するステップと、
正規化部が、前記各セグメントを正規化するステップと、
足切り部が、前記正規化後の各セグメントのうち、一定の長さ以下のセグメントを削除するステップと、
フィンガープリント生成部が、残りの正規化後の各セグメントを任意のハッシュ関数に入力してフィンガープリントをそれぞれ生成し、各フィンガープリントを前記各セグメントの出現順の情報に従って並べて構成した前記文書のダイジェストをその文書ＩＤとともに出力するステップとを含む
ことを特徴とする原典文書データベース生成方法。
【請求項９】
コンピュータを、請求項１乃至４のいずれかに記載の装置の各手段として機能させるためのプログラム。
【請求項１０】
請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブログ等の任意の文書中に、ニュース、プレスリリース、Ｗｉｋｉｐｅｄｉａ等の他の文書からの引用が含まれているかどうかを検出する技術に関するものである。ここで、引用とは、他の文書内の文であって文字列の改変が無い連続した２つ以上の文と定義するものとする。
【背景技術】
【０００２】
従来のこの種の技術としては、以下の二つがあった。
【０００３】
・ＤＰ（Dynamic Programming）マッチング（従来技術１）
ＤＰマッチングでは、比較すべき２つの文字列を逐次照合しながら当該２つの文字列間の差分を計算して、２つの文書間の類似度を推定する（例えば、非特許文献１参照）。
【０００４】
・Ｓｉｍｈａｓｈ（従来技術２）
Ｓｉｍｈａｓｈでは、文書をベクトル表現し、ランダムに定義された超平面のどちら側にあるかを判別することにより特殊なハッシュ値（simhash）を得て、各文書のｓｉｍｈａｓｈ値を比較することで、２つの文書間の類似度を推定する。この際、各文書のＳｉｍｈａｓｈ間のハミング距離が文書ベクトル間のコサイン距離の近似値になる性質がある（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｎｅｅｄｌｅｍａｎ，Ｓ．Ｂ．，Ｗｕｎｓｃｈ，Ｃ．Ｄ．：”Ａ  ｇｅｎｅｒａｌ  ｍｅｔｈｏｄ  ａｐｐｌｉｃａｂｌｅ  ｔｏ  ｔｈｅ  ｓｅａｒｃｈ  ｆｏｒ  ｓｉｍｉｌａｒｉｔｉｅｓ  ｉｎ  ｔｈｅ  ａｍｉｎｏ  ａｃｉｄ  ｓｅｑｕｅｎｃｅ  ｏｆ  ｔｗｏ  ｐｒｏｔｅｉｎｓ．”Ｊ．Ｍｏｌ．Ｂｉｏｌ，Ｖｏｌ．４８，ｐｐ．４４３−４５３，１９７０．
【非特許文献２】Ｍ．Ｓ．Ｃｈａｒｉｋａｒ．Ｓｉｍｉｌａｒｉｔｙ  ｅｓｔｉｍａｔｉｏｎ  ｔｅｃｈｎｉｑｕｅｓ  ｆｒｏｍ  ｒｏｕｎｄｉｎｇ  ａｌｇｏｒｉｔｈｍｓ．Ｉｎ  ＳＴＯＣ’０２：Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｔｈｉｒｙ−ｆｏｕｒｔｈ  ａｎｎｕａｌ  ＡＣＭ  ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  ｃｏｍｐｕｔｉｎｇ，ｐｐ．３８０−３８８，２００２．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、前述した従来技術には、以下のような３つの課題があった。
【０００７】
即ち、従来技術１では、総当たりでマッチングを行う必要があるため、計算量が多くなり、大規模化に向かなかった（課題１）。
【０００８】
また、従来技術２は、大規模化に向いているが、文書全体に対する引用の割合が小さいと検出できなかった。例えば、図１（ａ）に示す例のように、引用元文書と引用先文書との間の共通部分の割合が少ないと類似度が低下するため、引用を検出できなかった（課題２）。
【０００９】
さらにまた、従来技術２では、単語の出現順序を考慮することなく、２つの文書間の類似度を推定するため、引用を正確に検出することができなかった。例えば、図１（ｂ）に示す例のように、引用関係にない２つの文書間でも、単語同士の共通割合が高いと類似度が高くなり、誤って判定してしまうことがあった（課題３）。
【課題を解決するための手段】
【００１０】
本発明では、他の文書、即ち引用元の候補となる文書の集合である原典文書集合中の文書を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約（例えば公知のフィンガープリント）を生成し、各要約を前記部分文字列の出現順に並べた前記文書のダイジェストを、前記部分文字列毎に前方最長一致検索可能な形式でその文書ＩＤとともに登録してなる原典文書データベース（ＤＢ）を用意し、一方、入力文書（対象文書）を前記同様のダイジェストに変換し、この入力文書のダイジェストをキーとして原典文書ＤＢを前方最長一致で検索し、この際、連続して一致する要約の数が所定の閾値以上の他の文書があればその文書ＩＤを出力することを特徴とする。
【発明の効果】
【００１１】
本発明によれば、他の文書のダイジェストを前方最長一致検索可能な形式にてその文書ＩＤとともに登録した原典文書ＤＢを用いるとともに、入力文書をダイジェストに変換し、ダイジェスト同士を比較して引用が含まれるか否かを判定するため、計算量を少なくすることができるとともに、メモリ使用量、ディスク使用量を削減することができるため、大規模化が可能となる。
【００１２】
また、ダイジェスト同士の一致する要約の数、即ち一致するダイジェストの長さによって引用か否かを判定するため、文書全体に対する引用の割合の大小にかかわらず、引用を検出可能となる。
【００１３】
さらにまた、引用の単位となり得る部分文字列の出現順を保存したまま、ダイジェストの一致する長さで判定するため、文書全体における類似度の高低にかかわらず、引用のみを正しく検出可能となる。
【図面の簡単な説明】
【００１４】
【図１】従来技術の課題を示す説明図
【図２】本発明の原典文書データベース生成装置の実施の形態の一例を示す構成図
【図３】ダイジェスト生成手段の詳細を示す構成図
【図４】ダイジェスト生成手段における処理の流れ図
【図５】原典文書ＤＢ生成手段における処理の流れ図
【図６】本発明の引用検出装置の実施の形態の一例を示す構成図
【図７】引用開始位置及び引用終了位置の説明図
【図８】引用検出手段における処理の流れ図
【図９】Ｓｕｆｆｉｘ  Ａｒｒａｙの説明図
【図１０】原典文書集合からダイジェストを生成する際の一例を示す説明図
【図１１】原典文書集合からダイジェストを生成する際の一例を示す説明図
【図１２】原典文書集合からダイジェストを生成する際の一例を示す説明図
【図１３】原典文書集合からダイジェストを生成する際の一例を示す説明図
【図１４】ダイジェストから原典文書ＤＢを生成する際の一例を示す説明図
【図１５】入力文書からダイジェストを生成する際の一例を示す説明図
【図１６】入力文書から引用を検出する際の一例を示す説明図
【発明を実施するための形態】
【００１５】
本発明において、引用検出を行うには、事前に原典文書ＤＢを作成しておく必要があるため、まず、原典文書集合から原典文書ＤＢを生成する原典文書データベース生成装置について説明し、その次に、原典文書ＤＢに基づいて入力文書中に引用が含まれているかどうかを判定する引用検出装置について説明する。
【００１６】
＜原典文書データベース生成装置＞
図２は本発明の原典文書データベース生成装置の実施の形態の一例を示すもので、図中、１は原典文書集合、２はダイジェスト生成手段、３は原典文書ＤＢ生成手段、４は原典文書ＤＢである。
【００１７】
原典文書集合１は、引用元の候補となる文書、例えば各種ニュースサイト、プレスリリース、Ｗｉｋｉｐｅｄｉａ等の文書の集合からなるもので、各文書には予め固有の文書ＩＤが付されているものとする。
【００１８】
ダイジェスト生成手段２は、原典文書集合１中の各文書について、文書の文字列を引用の単位となり得る部分文字列に分割し、当該部分文字列の要約、ここではフィンガープリントをそれぞれ生成し、各フィンガープリントを前記部分文字列の出現順に並べて構成した前記文書のダイジェストをその文書ＩＤとともに原典文書ＤＢ生成手段３へ出力する。
【００１９】
図３はダイジェスト生成手段２の詳細構成を示すもので、セグメンテーション部２１、正規化部２２、足切り部２３及びフィンガープリント生成部２４からなっている。また、図４はダイジェスト生成手段２における処理の流れを示すものである。
【００２０】
セグメンテーション部２１は、入力された文書（テキスト）の文字列を任意のセパレータで区切ることによって引用の単位となり得る部分文字列（以下、セグメント）に分割し、各セグメントをその出現順の情報、ここでは各セグメントの開始位置及び終了位置、並びに前記文書の文書ＩＤとともに正規化部２２へ出力する。なお、セパレータとしては、文の区切り位置に現れる頻度の高い任意の文字、記号、これらの組合せ（パターン）、制御文字、タグ等が考えられる。また、開始位置及び終了位置としては、文書の文頭からの文字位置等が考えられる。
【００２１】
正規化部２２は、セグメンテーション部２１から入力された各セグメントを正規化し、正規化後の各セグメントをその開始位置及び終了位置、並びに文書ＩＤとともに足切り部２３へ出力する。ここで、正規化としては、具体的には、アルファベットの大文字小文字の正規化、全角半角文字の正規化、記号の除去、ＨＴＭＬやＸＭＬ等のタグの除去等が考えられるが、任意に設定可能である。
【００２２】
足切り部２３は、正規化部２２から入力された正規化後の各セグメントのうち、一定の長さ（ｌｅｎｇｔｈ）以下のセグメントを削除し、残りの正規化後の各セグメントをその開始位置及び終了位置、並びに文書ＩＤとともにフィンガープリント生成部２４へ出力する。なお、前記一定の長さ（ｌｅｎｇｔｈ）の単位としては文字、バイト（ｂｙｔｅ）、ビット（ｂｉｔ）等が考えられ、その値は任意に変更可能である。
【００２３】
フィンガープリント生成部２４は、足切り部２３から入力された残りの正規化後の各セグメントを任意のハッシュ関数に入力してフィンガープリントをそれぞれ生成し、各フィンガープリントを前記各セグメントの開始位置及び終了位置に従って並べて構成した前記文書のダイジェスト（フィンガープリント列）を各セグメントの開始位置及び終了位置、並びに文書ＩＤとともに出力する。
【００２４】
原典文書ＤＢ生成手段３は、ダイジェスト生成手段２から入力された原典文書集合１中の各文書に対応するダイジェストについて、前記セグメント毎に前方最長一致検索可能な形式でその文書ＩＤとともに登録して原典文書ＤＢ４を生成する。図５は原典文書ＤＢ生成手段３における処理の流れを示すものである。
【００２５】
ここで、前方最長一致検索可能なデータベースの形式として、どのようなものを用いても良いが、一例として（後述する）公知のＳｕｆｆｉｘ  Ａｒｒａｙを用いることができる。
【００２６】
原典文書ＤＢ４は、原典文書集合１からダイジェスト生成手段２及び原典文書ＤＢ生成手段３によって生成されたデータベース、即ち原典文書集合１中の各文書について、文書の文字列を引用の単位となり得るセグメントに分割し、当該セグメントのフィンガープリントをそれぞれ生成し、各フィンガープリントを前記セグメントの出現順に並べて構成した前記文書のダイジェストを、前記セグメント毎に前方最長一致検索可能な形式でその文書ＩＤとともに登録してなるデータベースである。
【００２７】
図６は本発明の引用検出装置の実施の形態の一例を示すもので、図中、４は原典文書ＤＢ、５はダイジェスト生成手段、６は引用検出手段である。
【００２８】
ダイジェスト生成手段５は、処理対象が入力文書（引用検出対象文書）となる点を除き前述した原典文書データベース生成装置のダイジェスト生成手段２と同一であり、入力文書の文字列を引用の単位となり得るセグメントに分割し、当該セグメントのフィンガープリントをそれぞれ生成し、各フィンガープリントを前記セグメントの開始位置及び終了位置に従って並べて構成した前記入力文書のダイジェストを各セグメントの開始位置及び終了位置、並びにその文書ＩＤとともに引用検出手段６へ出力する。
【００２９】
引用検出手段６は、ダイジェスト生成手段５から入力された入力文書のダイジェストをキーとして原典文書ＤＢ４を前方最長一致で検索し、一致するフィンガープリントの数が所定の閾値以上の他の文書があればその文書ＩＤ（引用元文書ＩＤ）を、引用開始位置及び引用終了位置とともに出力する。
【００３０】
ここで、引用開始位置及び引用終了位置とは、図７に示すように、対象文書（入力文書）中の引用元文書からの引用部分の先頭位置及び終了位置をそれぞれ表すものとする。
【００３１】
図８は引用検出手段６における処理の流れを示すもので、以下、詳細に説明する。
【００３２】
ステップ１：一致するフィンガープリント数の最小値として予め定義された値ｍｉｎを所定の閾値Ｍｉｎに代入し、ステップ２に移る。
【００３３】
ステップ２：ダイジェスト生成手段５から入力された入力文書のダイジェストの末尾まで探索済みであれば終了し、探索済みでなければステップ３に移る。
【００３４】
ステップ３：入力文書のダイジェストをキーとして原典文書ＤＢ４から前方最長一致のエントリを検索し、ステップ４に移る。
【００３５】
ステップ４：一致したフィンガープリント数が所定の閾値Ｍｉｎ以上のエントリが検索された場合は引用であるとみなしてステップ５に移り、閾値未満の場合はステップ８に移る。
【００３６】
ステップ５：入力文書のダイジェスト中の前記一致したフィンガープリントのうち、先頭のフィンガープリントに対応するセグメントの開始位置及び末尾のフィンガープリントに対応するセグメントの終了位置をそれぞれ引用開始位置及び引用終了位置として、一致したエントリの文書ＩＤ（引用元文書ＩＤ）とともに出力し、ステップ６に移る。
【００３７】
ステップ６：Ｍｉｎの値をステップ４で検出した引用部分の長さ（一致したフィンガープリント数）に変更し、ステップ７に移る。
【００３８】
ステップ７：入力文書のダイジェストを１フィンガープリントだけ末尾側へシフトし、ステップ２に戻る。
【００３９】
ステップ８：入力文書のダイジェストを１フィンガープリントだけ末尾側へシフトし、ステップ９に移る。
【００４０】
ステップ９：Ｍｉｎの値を１だけ減算（但し、Ｍｉｎ≧ｍｉｎ）し、ステップ２に戻る。
【００４１】
＜Ｓｕｆｆｉｘ  Ａｒｒａｙ＞
Ｓｕｆｆｉｘ  Ａｒｒａｙ（接尾辞配列）とは、高速な文字列検索を可能にするデータ構造であり、どんな部分文字列でも検索可能、単純な仕組みなので実装が簡単という特徴を有する。但し、事前にインデックス（ｓｕｆｆｉｘ  Ａｒｒａｙ）を作成しておく必要がある。
【００４２】
Ｓｕｆｆｉｘを文字単位で構成する場合を例にとってＳｕｆｆｉｘ  Ａｒｒａｙの作成方法を説明すると、まず、文字列中の各文字に先頭から連番でインデックスポイント（Ｉｎｄｅｘ  ｐｏｉｎｔ）を割り当て、各インデックスポイントから末尾までの文字列（Ｓｕｆｆｉｘ）をそれぞれ作成する。そして、各Ｓｕｆｆｉｘを辞書順にソートし、その際のインデックスポイント列がｓｕｆｆｉｘ  Ａｒｒａｙとなる。
【００４３】
文字列が「ＡＢＡＢＤＡＣ」の場合、図９（ａ）に示すようにＩｎｄｅｘ  ｐｏｉｎｔが与えられ、さらに各Ｓｕｆｆｉｘとして「ＡＢＡＢＤＡＣ」，「ＢＡＢＤＡＣ」，「ＡＢＤＡＣ」，……と得られるが、これらをまとめると、図９（ｂ）に示すようになる。そして、各Ｓｕｆｆｉｘを辞書順にソートすると、図９（ｃ）に示すようになり、その結果、図９（ｄ）に示すようなＳｕｆｆｉｘ  Ａｒｒａｙが得られる。
【実施例１】
【００４４】
図１０乃至図１３はダイジェスト生成手段２により原典文書集合からダイジェストを生成する際の一例、ここでは原典文書集合中の文書ＩＤ：ＡＡＡの文書「今日は、良い天気だなぁ。明日は晴れるかな？晴れるといいな。」からダイジェストを生成する例を示すものである（なお、図１０乃至図１３には記載の一部に重複有り。）。
【００４５】
まず、セグメンテーション部２１により、“。”及び“？”をセパレータとしてセグメントに分割すると、セグメント＃１「今日は、良い天気だなぁ。」、セグメント＃２「明日は晴れるかな？」、セグメント＃３「晴れるといいな。」に分割される。この際、各セグメント＃１，＃２，＃３の開始位置は「１，１３，２２」であり、終了位置は「１２，２１，２９」である。
【００４６】
次に、正規化部２２により、句読点及び記号を除去する正規化を行うと、セグメント＃１「今日は良い天気だなぁ」、セグメント＃２「明日は晴れるかな」、セグメント＃３「晴れるといいな」となる。
【００４７】
次に、足切り部２３により、５文字以下のセグメントを削除するが、ここではいずれも５文字より多いため、削除されるセグメントはない。
【００４８】
最後に、フィンガープリント生成部２４により、任意のハッシュ関数を用いてセグメント＃１，＃２，＃３毎にフィンガープリントを生成、ここでは４バイトのハッシュ値からなるフィンガープリント＃１「ａ３１ｂ」、フィンガープリント＃２「ｅ２ｃｄ」、フィンガープリント＃３「ｄｆｄｅ」を生成し、これらを各セグメントの開始位置及び終了位置に従って並べてダイジェスト（フィンガープリント列）「ａ３１ｂｅ２ｃｄｄｆｄｅ」として、前記各セグメントの開始位置及び終了位置、並びに文書ＩＤ：ＡＡＡとともに出力する。
【実施例２】
【００４９】
図１４は原典文書ＤＢ生成手段３によりダイジェストから原典文書ＤＢを生成する際の一例、ここではＳｕｆｆｉｘをフィンガープリント長（ここでは４ｂｙｔｅ）単位で生成する例を示すものである。
【００５０】
原典文書として、前述した文書ＩＤ：ＡＡＡのダイジェスト（フィンガープリント列）「ａ３１ｂｅ２ｃｄｄｆｄｅ」とともに、文書ＩＤ：ＢＢＢのダイジェスト「３ｃｄｆａｅ５１ｂｄａｃ」、文書ＩＤ：ＣＣＣのダイジェスト「１２ａａｂ４ａｄ３ｂ４２」が入力されたとすると、文書ＩＤ：ＡＡＡのダイジェストのＳｕｆｆｉｘとして「ａ３１ｂｅ２ｃｄｄｆｄｅ」，「ｅ２ｃｄｄｆｄｅ」，「ｄｆｄｅ」、文書ＩＤ：ＢＢＢのダイジェストのＳｕｆｆｉｘとして「３ｃｄｆａｅ５１ｂｄａｃ」，「ａｅ５１ｂｄａｃ」，「ｂｄａｃ」、文書ＩＤ：ＣＣＣのダイジェスト「１２ａａｂ４ａｄ３ｂ４２」のＳｕｆｆｉｘとして「１２ａａｂ４ａｄ３ｂ４２」，「ｂ４ａｄ３ｂ４２」，「３ｂ４２」がそれぞれ得られ、辞書順にソートされて図１４の右側に示すような原典文書ＤＢが生成される。
【実施例３】
【００５１】
図１５はダイジェスト生成手段５により入力文書からダイジェストを生成する際の一例、ここでは前記文書ＩＤ：ＡＡＡの文書を引用として含む、文書ＩＤ：ＪＪＪの入力文書「友達がこんなこと書いてた。今日は、良い天気だなぁ。明日は晴れるかな？晴れるといいな。でも、明日雨らしいよ。」からダイジェストを生成する例を示すものである。
【００５２】
詳細は図１０乃至図１３に示した実施例１の場合と同様なので省略するが、最終的に、ダイジェスト（フィンガープリント列）「ｂ４ａ３ａ３１ｂｅ２ｃｄｄｆｄｅ３４ａ２」が、各セグメントの開始位置「１，１４，２６，３５，４３」及び終了位置「１３，２５，３４，４２，５３」、並びに文書ＩＤ：ＪＪＪとともに出力される。
【実施例４】
【００５３】
図１６は引用検出手段６により入力文書のダイジェストと原典文書ＤＢを比較して引用を検出する際の一例、ここでは前記文書ＩＤ：ＪＪＪの入力文書のダイジェストと図１４に示した原典文書ＤＢを比較して引用を検出する例を示すものである。
【００５４】
まず、ダイジェスト「ｂ４ａ３ａ３１ｂｅ２ｃｄｄｆｄｅ３４ａ２」をキーとして、図１４に示した原典文書ＤＢから前方最長一致のエントリを検索するが、一致するエントリは存在しない。そこで、入力文書のダイジェストをフィンガープリント長（ここでは４ｂｙｔｅ）だけシフトして「ａ３１ｂｅ２ｃｄｄｆｄｅ３４ａ２」とし、これをキーとして前記同様に図１４に示した原典文書ＤＢを検索すると、先頭から３フィンガープリント長分、原典文書ＤＢ中の文書ＩＤ：ＡＡＡのダイジェストのＳｕｆｆｉｘ「ａ３１ｂｅ２ｃｄｄｆｄｅ」と一致する。
【００５５】
この際、Ｍｉｎが「２」あるいは「３」であれば、一致したフィンガープリントのうち、先頭のフィンガープリントに対応するセグメントの開始位置及び末尾のフィンガープリントに対応するセグメントの終了位置、ここでは「１４」及び「４２」をそれぞれ引用開始位置及び引用終了位置として、文書ＩＤ：ＡＡＡとともに出力する。
【符号の説明】
【００５６】
１：原典文書集合、２，５：ダイジェスト生成手段、３：原典文書ＤＢ生成手段、４：原典文書ＤＢ、６は引用検出手段、２１：セグメンテーション部、２２：正規化部、２３：足切り部、２４：フィンガープリント生成部。
【図１】
2010182238.tif 000003
【図２】
2010182238.tif 000004
【図３】
2010182238.tif 000005
【図４】
2010182238.tif 000006
【図５】
2010182238.tif 000007
【図６】
2010182238.tif 000008
【図７】
2010182238.tif 000009
【図８】
2010182238.tif 000010
【図９】
2010182238.tif 000011
【図１０】
2010182238.tif 000012
【図１１】
2010182238.tif 000013
【図１２】
2010182238.tif 000014
【図１３】
2010182238.tif 000015
【図１４】
2010182238.tif 000016
【図１５】
2010182238.tif 000017
【図１６】
2010182238.tif 000018