(57)【特許請求の範囲】
【請求項１】
引用元の文書の一部が改変されていることを検出するための引用文書改変検出装置であって、
入力された文書の１つの文章から文字列区間を切り出し、該文字列区間の起点を決定し、該起点から一定文字数毎の文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせて該ダイジェストの文書ID及びダイジェスト集合をダイジェストDBに格納するダイジェスト計算手段と、
前記ダイジェストDBから前記ダイジェストを読み出し、ダイジェストの所定のウィンドウサイズwと文字列間隔の開始位置の許容誤差αが与えられると、ｗ＋αだけ離れた位置に同じ文書と共有のダイジェストを持つ文字列区間が検出された場合、該ウィンドウサイズｗ以下の改変があると判定する引用判定手段と、
を有することを特徴とする引用文書改変検出装置。
【請求項２】
文書内位置と一致候補となる文書IDを格納した照合テーブルを更に有する装置において、
前記引用判定手段は、
前記ダイジェストを１文字単位でずらした場合の文書内位置に基づいて、前記照合テーブルを参照し、
ある文書との連続したダイジェストの一致する（条件１）；
前記条件１で一致した文書と、不一致区間を挟んで、再度連続したダイジェストの一致する（条件２）；
前記条件１と前記条件２に挟まれた不一致区間の文字数がウィンドウサイズに前記許容誤差αを加えた数であること（条件３）；
の全ての条件を満たす場合に、複数の文書が連続して引用されていると判定する手段を含む
請求項１記載の引用文書改変検出装置。
【請求項３】
前記ダイジェストDBは、ダイジェストの文書先頭からの文字数を含み、
前記引用判定手段は、
文書内位置と一致候補となる文書ID、ダイジェストの文書先頭からの文字数を格納した照合テーブルを更に有し、
前記ダイジェストを形態素区切りでずらした場合の文書位置に基づいて、前記照合テーブルを参照し、
ある文書と他の文書と連続した不一致区間が、文字数としてウィンドウサイズに所定の許容誤差を加えたサイズだけ不一致である場合は、複数の文書が連続して引用されていると判定する手段を含む
請求項１記載の引用文書改変検出装置。
【請求項４】
引用元の文書の一部が改変されていることを検出するための引用文書改変検出方法であって、
ダイジェスト計算手段、ダイジェストDB、引用判定手段を有する装置において、
前記ダイジェスト計算手段が、入力された文書の１つの文章から文字列区間を切り出し、該文字列区間の起点を決定し、該起点から一定文字数毎の文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせて該ダイジェストの文書ID及びダイジェスト集合を前記ダイジェストDBに格納するダイジェスト計算ステップと、
前記引用判定手段が、前記ダイジェストDBから前記ダイジェストを読み出し、ダイジェストの所定のウィンドウサイズwと文字列間隔の開始位置の許容誤差αが与えられると、ｗ＋αだけ離れた位置に同じ文書と共有のダイジェストを持つ文字列区間が検出された場合、該ウィンドウサイズｗ以下の改変があると判定する引用判定ステップと、
を行うことを特徴とする引用文書改変検出方法。
【請求項５】
文書内位置と一致候補となる文書IDを格納した第１の照合テーブルを更に有する装置において、
前記引用判定ステップにおいて、
前記ダイジェストの文書内位置に基づいて、前記第１の照合テーブルを参照し、
ある文書との連続したダイジェストの一致する（条件１）；
前記条件１で一致した文書と、不一致区間を挟んで、再度連続したダイジェストの一致する（条件２）；
前記条件１と前記条件２に挟まれた不一致区間の文字数がウィンドウサイズに前記許容誤差αを加えた数であること（条件３）；
の全ての条件を満たす場合に、複数の文書が連続して引用されていると判定する
請求項４記載の引用文書改変検出方法。
【請求項６】
文書内位置と一致候補となる文書ID、ダイジェストの文書先頭からの文字数を格納した第２の照合テーブルを更に有する装置において、
前記ダイジェストDBは、ダイジェストの文書先頭からの文字数を含み、
前記引用判定ステップにおいて、
前記ダイジェストを形態素区切りでずらした場合の文書位置に基づいて、前記第２の照合テーブルを参照し、
ある文書と他の文書と連続した不一致区間が、文字数としてウィンドウサイズに所定の許容誤差を加えたサイズだけ不一致である場合は、複数の文書が連続して引用されていると判定する
請求項４記載の引用文書改変検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、引用文書改変検出装置及び方法に係り、特に、文書を引用する際に一部が改変されていることを検出するための引用文書改変検出装置及び方法に関する。
【背景技術】
【０００２】
他の文書からの引用を判定する手法として、引用分析が用いられてきた。
【０００３】
特許文献１では、文書を引用可能なセグメントに分割し、それぞれのセグメントについてダイジェストを生成して連結した文字列を作成し、原典となる文書のDB内に保存された文書から同様にして得られた文字列と比較することで、当該原典からの引用を判定している。
【０００４】
また、特許文献２では、ネットワークパケットの異常を検出するため、スライディングウィンドウと呼ばれる方法を使用している。これは、データのシーケンスに対して、セグメント分割するのではなく、一定のデータ長をウィンドウとし、移動する（スライドする）ウィンドウ内のデータに対する関数値から異常を検出するものである。これを文書に適用することで文書内の文字列をデータのシーケンスと見做し、一定のサイズのウィンドウを文書の先頭から移動させることで、ウィンドウごとの異常値を発見することができる。
【０００５】
また、特許文献３では、２つの文書間の類似度に基づいて引用判定を行っている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１０−１８２２３８号公報
【特許文献２】特開２００９−１５２７１２号公報
【特許文献３】特開２００９−２０５６７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
図１、図２を例に従来の問題点について説明する。
【０００８】
図１に示すような複数の文書の断片によって構成されている文書に対して引用判定を行うことを考える。図２に示すように、１つの断片は日本語で５０文字程度であり、断片は文によっては分断されず、ランダムな位置で分断され、接続されている。また、原典の仮名が漢字に変換されていることがある。例えば、図２に示すように、原典（引用元）では「顧みて見る」であるが、同図の例では「顧みてみる」として一文字「見」が「み」と変換されて引用されている。このような文書では、文章を一部に着目すれば意味は通るが、全体では意味が通らないものの、キーワード検索でヒットしてしまう。
【０００９】
上記の特許文献１の方法を用いることで、明確にセグメント分割可能な文書に対しては有効に働くが、
（１）本発明が対象とするような、文の区切りを明らかに指定できないような文書ではセグメント分割が行えない；
（２）比較的短い文字列単位で引用されている場合には、引用されたことを判定しにくい；
という問題がある。
【００１０】
ここに、特許文献２のスライディングウィンドウを導入することで、文書内での任意の区間でダイジェストを作成することができ、文の区切りが明らかでない文書に対しても引用判定が可能となる。但し、以下の問題が残る。
【００１１】
（１）適切なスライディングウィンドウの起点の選択基準が不明確である。
【００１２】
（２）複数の文書が連続して引用されていることの判定が行えない。
【００１３】
（３）文書内に微少な修正が施されている時の判定が行えない。
【００１４】
（４）スライディングウィンドウ方式を使用すると、文書をセグメント分割する場合と比較して、ダイジェストを作成する区間数が増加するため、そのままダイジェストを作成すると、ダイジェストを保存するDBのサイズが爆発的に増大する。
【００１５】
（５）引用した文書の一部を改変している場合、例えば、文書中の1文字のみを改変している、または、少数の文字列を加えたような場合には引用と判定されない。
【００１６】
また、特許文献３の方法では、複数の文書の引用を想定していないため、複数の文書の断片によって構成される文書の引用判定は行えない。
【００１７】
スパムブログには、引用に際してランダムな文字列を加えるものや、文字の仮名−漢字の変換を行うものなどが存在し、ダイジェストを利用して文書の引用判定を行うアルゴリズムが十分に機能しない場合がある。
【００１８】
本発明は、上記の点に鑑みなされたもので、引用時に、引用元の文書の一部例えば、1文字のみ、あるいは、数文字のみ）の改変を判定することが可能な引用文書改変検出装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１９】
一態様によれば、引用元の文書の一部が改変されていることを検出するための引用文書改変検出装置であって、
入力された文書の１つの文章から文字列区間を切り出し、該文字列区間の起点を決定し、該起点から一定文字数毎の文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせて該ダイジェストの文書ID及びダイジェスト集合をダイジェストDBに格納するダイジェスト計算手段と、
前記ダイジェストDBから前記ダイジェストを読み出し、ダイジェストの所定のウィンドウサイズwと文字列間隔の開始位置の許容誤差αが与えられると、ｗ＋αだけ離れた位置に同じ文書と共有のダイジェストを持つ文字列区間が検出された場合、該ウィンドウサイズｗ以下の改変があると判定する引用判定手段と、を有する引用文書改変検出装置を提供する。
【発明の効果】
【００２０】
一態様によれば、引用元の文字列から1文字だけ、または、n文字（n＜ウィンドウサイズ）変更されているような場合であっても、引用パターンを分析することにより、当該引用元の文書の引用を検出することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】引用判定の対象文書の例である。
【図２】対象文書の断片の例である。
【図３】本発明の基本的な考え方を示す図である。
【図４】本発明の一実施の形態におけるダイジェスト作成例である。
【図５】本発明の一実施の形態における引用文書改変検出装置の構成図である。
【図６】本発明の一実施の形態における引用文書改変検出装置の全体のフローチャートである。
【図７】本発明の一実施の形態におけるダイジェストDBの例である。
【図８】本発明の一実施の形態におけるダイジェスト計算部の処理のフローチャートである。
【図９】本発明の一実施の形態における単一文書のダイジェスト計算のアルゴリズムである。
【図１０】本発明の一実施の形態における単一文書のダイジェスト計算のフローチャート（Ｓ２３０の詳細）である。
【図１１】本発明の一実施の形態における引用判定部のフローチャートである。
【図１２】本発明の一実施の形態における一部改変の例である。
【図１３】本発明の一実施の形態における文書の一部が変更されている判定の例である。
【図１４】本発明の一実施の形態における照合テーブルの例である。
【図１５】本発明の一実施の形態における形態素区切りを用いるときの引用文書改変検出を行うためのダイジェストDBの例である。
【図１６】本発明の一実施の形態における形態素区切りの場合の照合テーブル（一部改変で利用）の例である。
【発明を実施するための形態】
【００２２】
以下、図面と共に本発明の実施の形態を説明する。
【００２３】
最初に、本明細書に用いられる用語について説明する。
【００２４】
・ダイジェスト：ある文字列が与えられたとき、その文字列をハッシュ関数によって短いバイト数（またはビット数）に変換したもの。
【００２５】
・ダイジェストサイズ：上記の短いバイト数。
【００２６】
・一致するダイジェスト：1つの文書に含まれる多くの文字列区間それぞれにダイジェストが生成されるが、ある文書から生成されるダイジェスト群の中に含まれ、他の文書のダイジェスト群の中にも出てくるダイジェスト。
【００２７】
・一致するダイジェスト数：２つのダイジェスト群の中で、一致するダイジェストの組の数。
【００２８】
本発明の概要を示す。
【００２９】
図３は、本発明の基本的な考え方を示す。
【００３０】
引用元Ａ，Ｂ，Ｃの文書から引用先において、引用元の文書Ａ，Ｂ，Ｃの一部を取り出してある文書を作成しているとする。
【００３１】
既存手法では、文単位でセグメント分割してダイジェスト集合を作り、比較し、一致すれば同一の文であると判断する。しかし、引用先の文書が文の体をなしていないときは、特許文献１の技術によるセグメント分割ができない。
【００３２】
これに対し、本発明では、一組の文書の対について引用分析するのではなく、スライディングウィンドウを使用する際に、ウィンドウサイズと文字列の開始の差分を用いてウィンドウサイズ以下の文字列の改変を検出する。
【００３３】
本発明では、文書をより詳細な文字列区間に分割して、文字単位や形態素区切りを用いて起点を設定し、各起点から一定文字数ごとの文字列区間に対するダイジェストを作成する。図４に１つの文章から文字列区間を切り出し、ダイジェストを生成する例を示す。ここでは、文字列間の起点は１文字単位でずらすこととし、文字数は２０文字とした。また、ダイジェストは文字列をUTF-8で表現したときのMD５ハッシュ値（非特許文献１：The MD5 Message-Digest Algorithm. http://tools.ietf.org/html/rfc1321）の上位３２ビットの0からFまでの１６進表現（例えば、"c595"）を用いた例である。
【００３４】
このようにして作られたダイジェストを、順引き及び逆引きテーブルとしてダイジェストDBに保管する。
【００３５】
引用分析は、ウィンドウサイズ（ｗ）と文字列間隔の開始位置の差分（α）が与えられ、ウィンドウサイズ以下の改変を検出するものであり、ｗとαを用いて、ｗ＋αだけ離れた位置に同じ文書と共有のダイジェストを持つ文字列区間が検出された場合、引用文の一部だけが変更されていると判定する。
【００３６】
以下、具体的に説明する。
【００３７】
図５は、本発明の一実施の形態における引用文書改変検出装置の構成を示す。
【００３８】
同図に示す引用文書改変検出装置１００は、ダイジェスト計算部１１０、引用判定部１２０、ダイジェストサイズ計算部１３０、ダイジェストサイズ選択テーブル１４０、ダイジェストDB１５０を有する。
【００３９】
図６は、本発明の一実施の形態における引用文書改変検出装置の全体の処理のフローチャートである。
【００４０】
ステップ１００）  ダイジェストサイズ計算部１３０において、想定される最大の文書数、引用判定されるための一致数（k）、誤検出確率の最大値を入力とし、ダイジェストサイズの計算を行う。ダイジェストサイズは大きくすると通常は巨大となる一方、小さくすると誤検出が発生しやすくなるため、ダイジェストサイズを抑えながら、誤検出が最小となるダイジェストサイズを求める必要がある。ダイジェストサイズ計算部１３０は、文書数（想定される最大の文書数）、引用判定するための一致数(k)及び誤検出確率の最大値（許容される誤検出確率（例えば、0.01%））から後述するダイジェストサイズ選択テーブル１４０を参照することにより求める。詳細な処理については後述する。
【００４１】
ステップ２００）ダイジェスト計算部１１０は、文書DB１０１から文書を読み込み、ダイジェスト計算部１１０は、オペレータから入力された文書の文字列長、ダイジェスト対象とする区間の文字列長、文書におけるi+1番目の起点までの先頭からの文字数、文書ｄにおけるi文字目からｗ文字分の文字列、文字列ｘのダイジェストを算出するダイジェスト関数、ダイジェストサイズ計算部１３０から取得したダイジェストサイズに応じて各文書について文字列区間毎のダイジェストを計算する。詳細な処理については図８にて説明する。
【００４２】
ステップ３００）  ダイジェスト計算部１１０は計算されたダイジェストをダイジェストDB１５０に格納する。
【００４３】
ダイジェストDB１５０は、順引きテーブル１５１と、逆引きテーブル１５２と、を有する。図７にダイジェストDB１５０の例を示す。同図（ａ）に順引きテーブル、同図（ｂ）に逆引きテーブルを示す。
【００４４】
順引きテーブル１５１は、文書ＩＤをキーとし、作成日時、及びダイジェスト群を格納する。逆引きテーブル１５２は、ダイジェストをキーとし、対応する文書ID群を格納する。文書ＩＤに加えて、文書における文字列区間の出現順も合わせて格納することができる。図７の例では、ダイジェストサイズは１６ビットとし、ビット列は１６進数で表現した。また、逆引きテーブル１５２においては、文書ＩＤは出現順の組で表現している。
【００４５】
ステップ４００）  引用判定部１２０は、ダイジェストDB１５０から、同じダイジェストを持つ文字列区間を含む文書の集合を読み出す。
【００４６】
ステップ５００）  引用判定部１２０は、オペレータから入力されたウィンドウサイズ(w)と文字列区間の開始位置の差分（α）、照合テーブル１４０を用いて、読み出された文書の集合のある文書と他の文書群との間の引用関係を計算する。詳細な処理については後述する。
【００４７】
ステップ６００）  引用判定部１２０は、判定結果が「真」であった文書IDを出力する。
【００４８】
上記の各処理について詳細に説明する。
【００４９】
●ダイジェストサイズ計算部１３０の処理：
ここでは、ステップ１００のダイジェストサイズ計算部１３０のダイジェストサイズの計算について説明する。
【００５０】
本発明の実施に当たっては、ダイジェストDB１５０のサイズが巨大になる恐れがある。これは、ダイジェストDB１５０のサイズは、１つの文書あたりに作成されるダイジェストの数に影響されるため、スライディングウィンドウを用いると、文字列区間の数が、使用したウィンドウの数だけ必要になるためである。
【００５１】
既存手法であれば文書を文単位に分割するため、仮に文の平均文字数が５０文字であれば、ダイジェストサイズをgバイト、文書の平均長をwバイトとすれば、１つの文書あたりのダイジェストサイズはgw／50バイトとなっていた。例えば、ダイジェストサイズを５バイトとしても、文書あたりのダイジェストの合計サイズは、文書サイズの1／10で収まる。
【００５２】
しかし、本発明では、スライディングウィンドウを使用するため、文字列区間の数が増えるとダイジェストの合計サイズが膨大になる。しかし、ダイジェストサイズを小さくすると、異なる文字列区間に対しても偶然同じダイジェストが与えられることになり、検出誤りが増大する。
【００５３】
そこで、異なる文書に対して与えられたダイジェスト集合のうち、一定個数以上のダイジェストが一致した場合に、確率的に「偶然ではない」と判断することとする。
【００５４】
本発明では、ダイジェストサイズ、区間の起点の考え方、及び閾値を同時に考慮することで、ダイジェストDB１５０のサイズを最低限に抑える。
【００５５】
起点の考え方としては、
（１）１文字毎に起点とする（例えば、図４）；
（２）形態素区切りを起点とする；
（３）ある程度の形態素のまとまりを起点とする；
（４）文の区切りを起点とする；
等が考えられる。但し、引用が文の構成を無視して行われることが多いため、（３）及び（４）は現実的ではない。そこで、（１）及び（２）について検討する。
【００５６】
＜定義＞
・ダイジェストサイズをｇバイトとする。
【００５７】
・文書の文字数の平均をＬバイトとする。
【００５８】
・文書あたりの区間の数の平均をｓとする。
【００５９】
このとき、文書あたりに必要となるダイジェストの総バイト数はgsとなり、この値を小さくすることを目標とする。
【００６０】
ダイジェストサイズを小さくすると、複数の文字列が同じダイジェストを持つことになり、引用判定の誤りが発生することになる。この確率を下げられれば、ダイジェストサイズを限界まで小さくすることができる。
【００６１】
文書dhには平均してｓ個の区間が含まれるため、文書のダイジェスト集合を（簡単のため）｛h1,h2,…,hn｝と表現すると、任意のダイジェストがこの文書のダイジェスト集合に含まれる可能性は、p=s/2gと書ける。つまり、定数ｓ（文書DB１０１の文書数に含まれる区間の平均）とダイジェストサイズｇ（バイト）が与えられることによりpが求められる。
【００６２】
ある文書に含まれるｓ個のダイジェストのうち、任意の１つが別のある文書に同時に出現する確率は、sp=s2/2gであり、任意のk個の別の文書に同時に出現する確率は以下のように書ける（ｓに比べてｋは十分小さいものとする）。
【００６３】
【数１】
0005948304.tif 000002
この値が十分小さくなるように文書DB１０１に格納されている文書数（想定される最大の文書数）に応じて、ｐとｋを選ぶことで、偶然を排除する。ｐ、ｋは、ダイジェストサイズ計算部１３０によってｇとｋを選択し、ｇと文書ＤＢ１０１内の文書中に含まれる区間の数の平均ｓにより、p=s/2gによって求められる。上記の式(1)で求められた値がダイジェストサイズ選択テーブル１４０に格納される。
【００６４】
＜形態素区切りを区間の起点とする場合＞
形態素区切りを区間の起点とすると、１つの形態素あたりの文字列長を平均３文字と考えると、UTF-8では１文字が３バイトとなるため、
【００６５】
【数２】
0005948304.tif 000003
である。例えば、文書の平均長が10キロバイトとすると、s=1111だが、簡単のため、
【００６６】
【数３】
0005948304.tif 000004
とする。
【００６７】
例えば、g＝24（ビット）とするとp=1000/224=5.96×10-5
であるが、このとき、1つ以上のダイジェストが一致する確率は5.96×10-2となる。これは、文書数が20程度あれば、平均1回以上の誤検出を生じることを示している。
【００６８】
一致するダイジェスト数を増やす方向と、ダイジェストサイズを増やす方向から誤検出確率を下げることができる。
【００６９】
表１に、ダイジェスト数k及びダイジェストサイズｇをそれぞれ増やした場合の誤検出確率を格納したダイジェストサイズ選択テーブル１４０の例を示す。表1の例は文書あたりのセグメント数を1000と仮定している。但し、ｇについて誤検出確率が10-13前後となるkまでに限定している。
【００７０】
【表１】
0005948304.tif 000005
ダイジェストサイズを求める際には、ダイジェストサイズ選択テーブル１４０に対し、文書数の逆数に誤検出確率を乗じたものを基準とし、その数値よりもダイジェストサイズ選択テーブル１４０の値が小さくなるようなｋとｇの組み合わせを選択する。以下に詳述するが、例えば、文書数が100個、誤検出確率を１％（0.01=1/100）とすると、
1/100+1/100=1/10000=0.0001=10-4
を基準としてこれを下回るようなｋとｇの組み合わせを選択する。k=2であればg=24ビット、k=3であればg=20ビットが選択される。
【００７１】
＜具体的な値の設定＞
実装に当たっては、一致する数ｋと誤検出確率の最大値に基づいて表1のダイジェストサイズ選択テーブル１４０のｋ行を横に走査し、その値が誤検出確率の最大値を下回ったとき、その列のビット数ｇの行の値をダイジェストサイズdsとして出力する。例えば、文書数を10億＝109と仮定して、合計の誤検出確率を10-4（0.01％）未満とする場合は、10-13を閾値とし、これを下回る[g=20bit,k=6]、[g=24bit,k=4]、[g=28bit,k=3]、[g=32bit,k=2]のいずれかを用いればよい。
【００７２】
また、引用される文書が、過去の一定期間内に限られると仮定すると、より小さな値が設定可能となる。例えば、対象文書数が100万＝106であれば、合計の誤検出確率を10-4（0.01%）未満とすれば、10-10を閾値とし、[g=20bit,k=5]、[g=24bit，k=4]、[g=28bit,k=2]、[g=32bit,k=2]のいずれかを用い、誤検出確率未満のｇの行の値をダイジェストサイズdsとすればよい。
【００７３】
上記の計算は、文書内での文字列区間の出現位置について考慮していないが、文字列位置を考慮すると、更に偶然性を排除できる。1つの文書について文字列区間の平均を1,000=103とすると、誤検出確率は10-6減少させられるため、表１の値を10-6倍すればよい。
【００７４】
例えば、文書数を10億＝109と仮定して、合計の誤検出確率を10-4(0.01%)未満とする（0．01％は許容できる誤検出確率）場合は、閾値は10-13を10-7と読み替えて、[g=16bit,k=6]、[g=20bit,k=4]、[g=24bit,k=3]、[g=28bit,k=2]、[g=32bit,k=2]のいずれかを用いればよい。
【００７５】
●ダイジェスト計算部１１０の処理：
次に、図６のステップ２００におけるダイジェスト計算部１１０の処理について説明する。
【００７６】
図８は、本発明の一実施の形態におけるダイジェスト計算部の処理のフローチャートである。
【００７７】
ダイジェスト計算部１１０は、文書DB１０１から1つの文書が読み出されると（ステップ２２０）、当該1つの文書についてダイジェスト計算を行い（ステップ２３０）、ダイジェストDB１５０に格納する（ステップ２４０）。これを繰り返すことで、文書DB101中の全ての文書についてダイジェストを計算する。
【００７８】
ステップ２２０における文書の読み出し時には、文書ID、文書の作成日時、及び文書（より厳密には文書の内容文字列）の３つ組が得られる。文書IDは、文書を同定できる記号であり、例えば、URL(Uniform Resource Locator)などのURI(Uniform Resource Identifier)の形式が使用される。
【００７９】
なお、図８では全ての文書について一括してダイジェストを計算して格納しているが、一度処理を行ってダイジェストDB１５０に格納した文書については、再度処理をする必要はない。従って、一通り全ての文書についてダイジェストを計算した後は、新たな文書が文書DB１０１に格納されるタイミングでステップ２２０〜２４０の処理を行えばよい。
【００８０】
ステップ２３０の単一文書のダイジェスト計算のアルゴリズムを図９に、フローチャートを図１０に示す。図９，図１０に示す処理は、読み出した文書の1つの文章から文字列区間を切り出し、ダイジェストを生成する例を示す。ここで、文字列区間の起点は図４に示すように1文字単位でずらすこととし、文字数は２０文字とした。つまり、図９において、w=20であり、任意のi番目の文書d,iについてnext(d,i)=i+1である。ここでは、1文字単位でずらす例を示しているが、1文字単位に限定されるものではない。但し、粒度は細かい方が厳密に判定することが可能である。また、比較する文書間のダイジェストのずらす文字単位は同じであること、形態素解析結果による区切りを用いて起点を揃える必要がある。形態素解析結果を用いて起点を揃えることによりダイジェストDB１５０に格納するデータ量を圧縮することが可能となる。
【００８１】
また、ダイジェスト（digest）は、文字列をUTF-8で表現したときのMD5ハッシュ値（非特許文献1参照）の上位16位ビットの16進数表現を用いている。また、1つの文章から切り出す文字列区間は、形態素解析した形態素区切りの直後を用いることで、文字ずれがおきにくくなり、同粒度で比較が可能となる。
【００８２】
ダイジェスト計算部１１０は、ダイジェストサイズ計算部１３０からダイジェストサイズdsを取得し、文字列ｘのダイジェストサイズdsを用いてダイジェスト関数(digest(x,ds))を算出する（ステップ２３１）。当該ダイジェスト関数は1ビットでも異なると全く異なる結果となる一方向性の関数である。
【００８３】
文書ｄの文字列長を（length（d））、ダイジェスト対象とする区間の文字列長を（ｗ）、次の区間までの文字数（next(d,i)）、文書dにおけるi文字目からw文字分の文字列（部分文字列）を（substr［（d，i，w），ds］）ハッシュによるダイジェストを（digest）とする（ステップ２３２）。
【００８４】
インデックス値（idx）の初期値を０とし（ステップ２３３）、ダイジェスト集合（digest）を空集合とする（ステップ２３４）。
【００８５】
ダイジェスト計算部１１０は、ダイジェスト関数(digest(x,ds))と入力された上記のパラメータから文書dにおけるi文字目からw文字分の文字列（substr［（d，i，w），ds］）のハッシュ値(hash)を求め（ステップ２３５）、ハッシュ値をダイジェスト集合に加える（digest←digest∪{hash}）（ステップ２３６）。i=i+1とし（ステップ２３７）、next(d,i)があれば（ステップ２３８,Yes）、ステップ２３５に移行し、ない場合は（ステップ２３８,No）、ダイジェスト集合（digest）をダイジェストDB１５０に出力する（ステップ２３９）。
【００８６】
ダイジェストDB１５０は、図７に示したように、順引きテーブル１５１と逆引きテーブル１５２から構成されている。ダイジェスト計算部１１０は、ダイジェスト集合の各要素について、読み出した文書の文書ID、作成日時、ダイジェスト群を抽出して順引きテーブル１５１に格納する。また、ダイジェストをキーとして、当該ダイジェストに対応する文書ID群を逆引きテーブル１５２に格納する。このとき、文書における文字列区間の出現順も合わせて格納することが可能である。図７の逆引きテーブル１５１の例では、ダイジェスト"0abc"に対応する文書ID"http://example.com/00002,2"の後に"http://example.com/00003,1"が存在しており、時系列順に格納されていることを示している。
【００８７】
また、引用判定処理において、形態素区切りを用いる場合には、順引きテーブル１５１'に、ダイジェストが文書の先頭から何文字目であるかについての情報を加える。
【００８８】
●引用判定部１２０の処理：
次に、図６のステップ５００の引用判定処理について説明する。
【００８９】
図１１は、本発明の一実施の形態における引用判定処理部の処理のフローチャートである。
【００９０】
引用判定部１２０は、メモリ（図示せず）上の引用判定が「真」となったスパム集合Sを初期化（φ）し、ウィンドウサイズ（ｗ）と文字列区間の開始位置の差分（α）を取得し、ておき（ステップ４１０）、ダイジェストDB１５０の順引きテーブル１５１から取得した文書iの文書IDに基づいて、逆引きテーブル１５２から当該文書IDに対応するダイジェスト集合を読み出し（ステップ４３０）、ダイジェストの文書内位置に基づいて、照合テーブル１２１を参照し、ｗとαを用いて引用文が一部だけ改変されていることを判定し（ステップ４４０）、判定結果が「真」であれば（ステップ４６０,Yes）、スパム集合Sに文書iを追加する（ステップ４６０）。このときスパム集合Ｓに追加するダイジェストサイズの情報を順引きテーブル１５１から取得して追加する。ダイジェストDB１５０の全ての文書についての処理が終了したら（ステップ４２０，No）、スパム集合Sを出力する（ステップ４７０）。
【００９１】
上記のステップ４４０における引用判定部１２０の処理について説明する。
【００９２】
引用元の文字列から１文字だけ、または、ｎ（n＜ｗ）文字変更されている場合に、その文字を含んだ区間ではダイジェストが一致しないが、その文字を含んだ区間を外れると、再度ダイジェストが一致することになる。例えば、図１２に示すように、引用元が
『もろこしわがちょうにもろもろの』
であり、引用先では
『もろこしわがちゃうにもろもろの』
のように１文字だけ変更されている場合を考える。これを形態素解析すると、
「もろこし」「わが」「ちゃう」「に」「もろもろ」「の」
となる。例えば、与えられたウィンドウサイズが５である場合に、ダイジェストｖ（１）の後のダイジェストｖ（２）、ダイジェストｖ（３）は、引用元の「ちゃう」が引用先では「ちょう」に変換されているため、引用元の文字列と一致しないが、ダイジェストｖ（４）、ダイジェストｖ（５）は引用元の文字列と一致する。なお、上記のウィンドウサイズ（ｗ）は形態素解析結果の平均値または最大値を用いるものとする。
【００９３】
図１２をモデル化した例を図１３に示す。図１３に示すように、ウィンドウサイズ（ｗ）＋文字列区間の開始位置の差分（α）（図９のNext関数で表される）だけ離れた位置に、同じ文書（図１３では「文書１」）と共通のダイジェストを持つ文字列区間が検出される。  引用判定部１２０は、文書内位置に基づいて照合テーブル１２１を参照し、以下の（１）〜（３）のすべての条件を満たす場合には、文書が一部改変されていると判断する。照合テーブル１２１は、図１４に示すように、文書内位置と一致候補が格納されている。
【００９４】
（１）ある文書との連続したダイジェストの一致：一致候補の文書内位置が連続していることで、連続したダイジェストであること。
【００９５】
（２）（１）で一致した文書と、不一致区間を挟んで、再度連続したダイジェストの一致：同じ一致候補の文書内位置が、不一致区間を挟んで再度連続していることで、不一致区間を挟んで再度連続していること。
【００９６】
（３）（１）と（２）に挟まれた不一致区間の文字数がウィンドウサイズ＋許容誤差（α）であること。
【００９７】
図１４の照合テーブル１４０の場合は、文書ウィンドウサイズが１０の場合、（１）文書内位置０から３までが文書"０００２"と一致しており、（２）文書内位置１３以降が"０００２"と一致しており、（３）その不一致区間の文字長が１０であり、これがウィンドウサイズに一致しているため、文書"０００２"が１文字だけ改変されていると判定する。
【００９８】
上記の判定では、文字列区間を１文字ずつずらす場合を示したが、以下に形態素区切りでずらす場合について説明する。
【００９９】
形態素区切りで引用判定する場合は、ダイジェスト計算部１１０において、ダイジェストDB１５０を生成する際に、図７の順引きテーブル１５１に、形態素解析結果に基づく文書先頭からの文字数を加えた構成とする。各ダイジェストの元となった文字列区間の開始位置が、文書先頭から何文字目に書かれているかが記載される。その例を図１５に示す。図１５ダイジェストDB１５０の例では、文書IDhttp://example.com/00001のダイジェスト"c595"は先頭（０）であり、"d03e"は先頭から3文字目であり、"ea79"は先頭から7文字目であることを示す。
【０１００】
さらに、形態素区切りを用いる場合の照合テーブルの例を図１６に示す。当該照合テーブル１２１'は、図１４の照合テーブル１２１に、文書内位置に対応させて文書先頭からの文字数の情報も加えられている。
【０１０１】
形態素区切りにおける引用判定の場合には、ダイジェストDB１５０'の順引きテーブル１５１'から取得した文書iの文書IDに基づいて、逆引きテーブル１５２'から当該文書IDに対応するダイジェスト集合を読み出し、照合テーブル１２１'の文書先頭からの文字数及び一致候補を参照して、当該文書と他の文書と連続した不一致区間が、文字数としてウィンドウサイズ+αだけ不一致となっていることで判定する。
【０１０２】
上記の図５に示す引用文書改変検出装置の構成要素の動作をプログラムとして構築し、引用文書改変検出装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１０３】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１０４】
１００  引用文書改変検出装置
１０１  文書DB
１１０  ダイジェスト計算部
１２０  引用判定部
１２１，１２１'  照合テーブル
１３０  ダイジェストサイズ計算部
１４０  ダイジェストサイズ選択テーブル
１５０，１５０'  ダイジェストDB
１５１，１５１'  順引きテーブル
１５２，１５２'  逆引きテーブル
【図１】
0005948304.tif 000006
【図２】
0005948304.tif 000007
【図３】
0005948304.tif 000008
【図４】
0005948304.tif 000009
【図５】
0005948304.tif 000010
【図６】
0005948304.tif 000011
【図７】
0005948304.tif 000012
【図８】
0005948304.tif 000013
【図９】
0005948304.tif 000014
【図１０】
0005948304.tif 000015
【図１１】
0005948304.tif 000016
【図１２】
0005948304.tif 000017
【図１３】
0005948304.tif 000018
【図１４】
0005948304.tif 000019
【図１５】
0005948304.tif 000020
【図１６】
0005948304.tif 000021