JP2015090528A - 連続引用判定装置及び方法 - Google Patents

Abstract

【課題】 複数文書が連続して引用されていることを検出する。
【解決手段】 本発明は、入力された文書の１つの文章から文字列区間を切り出し、該文字列区間の起点を決定し、該起点から一定文字数毎の文字列区間に対する文字列をハッシュ関数に変換したダイジェストを所定の文字数分スライドさせて該ダイジェストの文書ID及びダイジェスト群を前記ダイジェストDBに格納し、ダイジェストDBから前記ダイジェストを読み出し、該ダイジェストの所定のウィンドウサイズw分だけ離れた文字列区間にダイジェストが異なる文書を引用している場合に、複数文書が連続して引用されているものと判断する。
【選択図】 図５

Description

本発明は、連続引用判定装置及び方法に係り、特に、電子化された文書（例えば、Web上のブログ）が他の複数の文書を切れ目なく引用していることを判定するための連続引用判定装置及び方法に関する。

他の文書からの引用を判定する手法として、引用分析が用いられてきた。

特許文献１では、文書を引用可能なセグメントに分割し、それぞれのセグメントについてダイジェストを生成して連結した文字列を作成し、原典となる文書のDB内に保存された文書から同様にして得られた文字列と比較することで、当該原典からの引用を判定している。

また、特許文献２では、ネットワークパケットの異常を検出するため、スライディングウィンドウと呼ばれる方法を使用している。これは、データのシーケンスに対して、セグメント分割するのではなく、一定のデータ長をウィンドウとし、移動する（スライドする）ウィンドウ内のデータに対する関数値から異常を検出するものである。これを文書に適用することで文書内の文字列をデータのシーケンスと見做し、一定のサイズのウィンドウを文書の先頭から移動させることで、ウィンドウごとの異常値を発見することができる。

また、特許文献３では、２つの文書間の類似度に基づいて引用判定を行っている。

特開２０１０−１８２２３８号公報 特開２００９−１５２７１２号公報 特開２００９−２０５６７４号公報

図１、図２を例に従来の問題点について説明する。

図１に示すような複数の文書の断片によって構成されている文書に対して引用判定を行うことを考える。図２に示すように、１つの断片は日本語で５０文字程度であり、断片は文によっては分断されず、ランダムな位置で分断され、接続されている。また、原典の仮名が漢字に変換されていることがある。例えば、図２に示すように、原典（引用元）では「顧みて見る」であるが、同図の例では「顧みてみる」として一文字「見」が「み」と変換されて引用されている。このような文書では、文章を一部に着目すれば意味は通るが、全体では意味が通らないものの、キーワード検索でヒットしてしまう。

上記の特許文献１の方法を用いることで、明確にセグメント分割可能な文書に対しては有効に働くが、
（１）本発明が対象とするような、文の区切りを明らかに指定できないような文書ではセグメント分割が行えない；
（２）比較的短い文字列単位で引用されている場合には、引用されたことを判定しにくい；
という問題がある。

ここに、特許文献２のスライディングウィンドウを導入することで、文書内での任意の区間でダイジェストを作成することができ、文の区切りが明らかでない文書に対しても引用判定が可能となる。但し、以下の問題が残る。

（１）適切なスライディングウィンドウの起点の選択基準が不明確である。

（２）複数の文書が連続して引用されていることの判定が行えない。

（３）文書内に微少な修正が施されている時の判定が行えない。

（４）スライディングウィンドウ方式を使用すると、文書をセグメント分割する場合と比較して、ダイジェストを作成する区間数が増加するため、そのままダイジェストを作成すると、ダイジェストを保存するDBのサイズが爆発的に増大する。

（５）複数文書を切れ目なく引用している文書を判定することができない。

また、特許文献３の方法では、複数の文書の引用を想定していないため、複数の文書の断片によって構成される文書の引用判定は行えない。

本発明は、上記の点に鑑みなされたもので、複数文書が連続して引用されていることが検出可能な連続引用判定装置及び方法を提供することを目的とする。

一態様によれば、複数の文書の連続引用を判定するための連続引用判定装置であって、
入力された文書の１つの文章から文字列区間を切り出し、該文字列区間の起点を決定し、該起点から一定文字数毎の文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせて該ダイジェストの文書ID及びダイジェスト群をダイジェストDBに格納するダイジェスト計算手段と、
前記ダイジェストDBから前記ダイジェストを読み出し、該ダイジェストの所定のウィンドウサイズw分だけ離れた文字列区間にダイジェストが異なる文書を引用している場合に、複数文書が連続して引用されているものと判断する引用判定手段と、
を有する連続引用判定装置を提供する。

一態様によれば、複数文書が連続して引用されていることを検出することが可能であるため、正当な引用であれば、通常は引用と他の文が交互に出現するため、引用が連続していることを検出することで、正当な引用をスパムとして誤検出する危険性を低下させることができる。

引用判定の対象文書の例である。 対象文書の断片の例である。 本発明の基本的な考え方を示す図である。 本発明の一実施の形態におけるダイジェスト作成例である。 本発明の一実施の形態における連続引用判定装置の構成図である。 本発明の一実施の形態における連続引用判定装置の全体のフローチャートである。 本発明の一実施の形態におけるダイジェストDBの例である。 本発明の一実施の形態におけるダイジェスト計算部の処理のフローチャートである。 本発明の一実施の形態における単一文書のダイジェスト計算のアルゴリズムである。 本発明の一実施の形態における単一文書のダイジェスト計算のフローチャート（Ｓ２３０の詳細）である。 本発明の一実施の形態における引用判定部のフローチャートである。 本発明の一実施の形態における複数文書が連続して引用されていることの判定の例である。 本発明の一実施の形態における照合テーブルの例である。 本発明の一実施の形態における形態素区切りを用いるときの連続引用判定のためのダイジェストDBの例である。 本発明の一実施の形態における形態素区切りの場合の照合テーブル（連用引用で利用）例である。

以下、図面と共に本発明の実施の形態を説明する。

最初に、本明細書に用いられる用語について説明する。

・ダイジェスト：ある文字列が与えられたとき、その文字列をハッシュ関数によって短いバイト数（またはビット数）に変換したもの。

・ダイジェストサイズ：上記の短いバイト数。

・一致するダイジェスト：1つの文書に含まれる多くの文字列区間それぞれにダイジェストが生成されるが、ある文書から生成されるダイジェスト群の中に含まれ、他の文書のダイジェスト群の中にも出てくるダイジェスト。

・一致するダイジェスト数：２つのダイジェスト群の中で、一致するダイジェストの組の数。

本発明の概要を示す。

図３は、本発明の基本的な考え方を示す。

引用元Ａ，Ｂ，Ｃの文書から引用先において、引用元の文書Ａ，Ｂ，Ｃの一部を取り出してある文書を作成しているとする。

既存手法では、文単位でセグメント分割してダイジェスト集合を作り、比較し、一致すれば同一の文であると判断する。しかし、引用先の文書が文の体をなしていないときは、特許文献１の技術によるセグメント分割ができない。

これに対し、本発明では、一組の文書の対について引用分析するのではなく、スライディングウィンドウを使用する際に、ある１つの文書が他の複数の文書と同一のダイジェストを持っている文字列区間数の割合を用いる。また、他の文書と一致している文字列区間数の全体における割合によって引用を判定する。

本発明では、文書をより詳細な文字列区間に分割して、文字単位や形態素区切りを用いて起点を設定し、各起点から一定文字数ごとの文字列区間に対するダイジェストを作成する。図４に１つの文章から文字列区間を切り出し、ダイジェストを生成する例を示す。ここでは、文字列間の起点は１文字単位でずらすこととし、文字数は２０文字とした。また、ダイジェストは文字列をUTF-8で表現したときのMD５ハッシュ値（非特許文献１：The MD5 Message-Digest Algorithm. http://tools.ietf.org/html/rfc1321）の上位３２ビットの0からFまでの１６進表現（例えば、"c595"）を用いた例である。

このようにして作られたダイジェストを、順引き及び逆引きテーブルとしてダイジェストDBに保管する。

引用分析は、ダイジェストDBからダイジェストと当該ダイジェストに対応する文書IDを読み出して、所定のウィンドウサイズの長さだけずれた位置に分かれて複数の文書と共通のダイジェストを検出し、それを複数の文書が連続して引用されていると判定する。

以下、具体的に説明する。

図５は、本発明の一実施の形態における連続引用判定装置の構成を示す。

同図に示す連続引用判定装置１００は、ダイジェスト計算部１１０、引用判定部１２０、ダイジェストサイズ計算部１３０、ダイジェストサイズ選択テーブル１４０、ダイジェストDB１５０を有する。

図６は、本発明の一実施の形態における連続引用判定装置の全体の処理のフローチャートである。

ステップ１００） ダイジェストサイズ計算部１３０において、想定される最大の文書数、引用判定されるための一致数（k）、誤検出確率の最大値を入力とし、ダイジェストサイズの計算を行う。ダイジェストサイズは大きくすると通常は巨大となる一方、小さくすると誤検出が発生しやすくなるため、ダイジェストサイズを抑えながら、誤検出が最小となるダイジェストサイズを求める必要がある。ダイジェストサイズ計算部１３０は、文書数（想定される最大の文書数）、引用判定するための一致数(k)及び誤検出確率の最大値（許容される誤検出確率（例えば、0.01%））から後述するダイジェストサイズ選択テーブル１４０を参照することにより求める。詳細な処理については後述する。

ステップ２００）ダイジェスト計算部１１０は、文書DB１０１から文書を読み込み、オペレータから入力された文書の文字列長、ダイジェスト対象とする区間の文字列長、文書におけるi+1番目の起点までの先頭からの文字数、文書ｄにおけるi文字目からｗ文字分の文字列、文字列ｘのダイジェストを算出するダイジェスト関数、ダイジェストサイズ計算部１３０から取得したダイジェストサイズに応じて各文書について文字列区間毎のダイジェストを計算する。詳細な処理については図８にて説明する。

ステップ３００） ダイジェスト計算部１１０は計算されたダイジェストをダイジェストDB１５０に格納する。

ダイジェストDB１５０は、順引きテーブル１５１と、逆引きテーブル１５２と、を有する。図７にダイジェストDB１５０の例を示す。同図（ａ）に順引きテーブル１５１、同図（ｂ）に逆引きテーブル１５２を示す。

順引きテーブル１５１は、文書ＩＤをキーとし、作成日時、及びダイジェスト群を格納する。逆引きテーブル１５２は、ダイジェストをキーとし、対応する文書ID群を格納する。文書ＩＤに加えて、文書における文字列区間の出現順も合わせて格納することができる。図７の例では、ダイジェストサイズは１６ビットとし、ビット列は１６進数で表現した。また、逆引きテーブル１５２においては、文書ＩＤは出現順の組で表現している。

ステップ４００） 引用判定部１２０は、ダイジェストDB１５０から、同じダイジェストを持つ文字列区間を含む文書の集合を読み出す。

ステップ５００） 引用判定部１２０は、オペレータから入力されたウィンドウサイズｗと文字列区間の開始位置の差分（許容誤差）αを用いて、読み出された文書の集合の複数文書が連続している引用されていることを判定する。詳細な処理については図１１、図１２にて説明する。

ステップ６００） 引用判定部１２０は、判定結果が「真」（引用あり）であった文書IDを出力する。

上記の各処理について詳細に説明する。

●ダイジェストサイズ計算部１３０の処理：
ここでは、ステップ１００のダイジェストサイズ計算部１３０のダイジェストサイズの計算について説明する。

本発明の実施に当たっては、ダイジェストDB１５０のサイズが巨大になる恐れがある。これは、ダイジェストDB１５０のサイズは、１つの文書あたりに作成されるダイジェストの数に影響されるため、スライディングウィンドウを用いると、文字列区間の数が、使用したウィンドウの数だけ必要になるためである。

既存手法であれば文書を文単位に分割するため、仮に文の平均文字数が５０文字であれば、ダイジェストサイズをgバイト、文書の平均長をwバイトとすれば、１つの文書あたりのダイジェストサイズはgw／50バイトとなっていた。例えば、ダイジェストサイズを５バイトとしても、文書あたりのダイジェストの合計サイズは、文書サイズの1／10で収まる。

しかし、本発明では、スライディングウィンドウを使用するため、文字列区間の数が増えるとダイジェストの合計サイズが膨大になる。しかし、ダイジェストサイズを小さくすると、異なる文字列区間に対しても偶然同じダイジェストが与えられることになり、検出誤りが増大する。

そこで、異なる文書に対して与えられたダイジェスト集合のうち、一定個数以上のダイジェストが一致した場合に、確率的に「偶然ではない」と判断することとする。

本発明では、ダイジェストサイズ、区間の起点の考え方、及び閾値を同時に考慮することで、ダイジェストDB１５０のサイズを最低限に抑える。

起点の考え方としては、
（１）１文字毎に起点とする（例えば、図４）；
（２）形態素区切りを起点とする；
（３）ある程度の形態素のまとまりを起点とする；
（４）文の区切りを起点とする；
等が考えられる。但し、引用が文の構成を無視して行われることが多いため、（３）及び（４）は現実的ではない。そこで、（１）及び（２）について検討する。

＜定義＞
・ダイジェストサイズをｇバイトとする。

・文書の文字数の平均をＬバイトとする。

・文書あたりの区間の数の平均をｓとする。

このとき、文書あたりに必要となるダイジェストの総バイト数はgsとなり、この値を小さくすることを目標とする。

ダイジェストサイズを小さくすると、複数の文字列が同じダイジェストを持つことになり、引用判定の誤りが発生することになる。この確率を下げられれば、ダイジェストサイズを限界まで小さくすることができる。

文書d_hには平均してｓ個の区間が含まれるため、文書のダイジェスト集合を（簡単のため）｛h₁,h₂,…,h_n｝と表現すると、任意のダイジェストがこの文書のダイジェスト集合に含まれる可能性は、p=s/2^gと書ける。つまり、定数ｓ（文書DB１０１の文書数に含まれる区間の平均）とダイジェストサイズｇ（バイト）が与えられることによりpが求められる。

ある文書に含まれるｓ個のダイジェストのうち、任意の１つが別のある文書に同時に出現する確率は、sp=s²/2^gであり、任意のk個の別の文書に同時に出現する確率は以下のように書ける（ｓに比べてｋは十分小さいものとする）。

この値が十分小さくなるように文書DB１０１に格納されている文書数（想定される最大の文書数）に応じて、ｐとｋを選ぶことで、偶然を排除する。ｐ、ｋは、ダイジェストサイズ計算部１３０によってｇとｋを選択し、ｇと文書ＤＢ101内の文書中に含まれる区間の数の平均ｓにより、p=s/2^gによって求められる。上記の式(1)で求められた値がダイジェストサイズ選択テーブル１４０に格納される。

＜形態素区切りを区間の起点とする場合＞
形態素区切りを区間の起点とすると、１つの形態素あたりの文字列長を平均３文字と考えると、UTF-8では１文字が３バイトとなるため、

である。例えば、文書の平均長が10キロバイトとすると、s=1111だが、簡単のため、

とする。

例えば、g＝24（ビット）とすると、
p=1000/2²⁴=5.96×10^-5
であるが、このとき、1つ以上のダイジェストが一致する確率は5.96×10^-2となる。これは、文書数が20程度あれば、平均1回以上の誤検出を生じることを示している。

一致するダイジェスト数を増やす方向と、ダイジェストサイズを増やす方向から誤検出確率を下げることができる。

表１に、ダイジェスト数k及びダイジェストサイズｇをそれぞれ増やした場合の誤検出確率を格納したダイジェストサイズ選択テーブル１４０の例を示す。表1の例は文書あたりのセグメント数を1000と仮定している。但し、ｇについて誤検出確率が10^-13前後となるkまでに限定している。

ダイジェストサイズを求める際には、ダイジェスト選択テーブル１４０に対し、文書数の逆数に誤検出確率を乗じたものを基準とし、その数値よりもダイジェストサイズ選択テーブル１４０の値が小さくなるようなｋとｇの組み合わせを選択する。以下に詳述するが、例えば、文書数が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億＝10⁹と仮定して、合計の誤検出確率を10^-4（0.01％）未満とする場合は、10^-13を閾値とし、これを下回る[g=20bit,k=6]、[g=24bit,k=4]、[g=28bit,k=3]、[g=32bit,k=2]のいずれかを用いればよい。

また、引用される文書が、過去の一定期間内に限られると仮定すると、より小さな値が設定可能となる。例えば、対象文書数が100万＝10⁶であれば、合計の誤検出確率を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=10³とすると、誤検出確率は10^-6減少させられるため、表１の値を10^-6倍すればよい。

例えば、文書数を10億＝10⁹と仮定して、合計の誤検出確率を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)があれば、ステップ２３５に移行し、ない場合は、ダイジェスト集合（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）、判定結果としてスパム集合Ｓを出力する（ステップ４７０）。

上記のステップ４４０における引用判定部１２０の処理について説明する。

引用判定部１２０は、本発明が対象としている文書では、複数の文書が切れ目なく引用されている。従って、複数の文書が切れ目なく引用されていることが判定されれば、より精度よく引用判定することができる。

入力されたウィンドウサイズをｗとすると、丁度ｗの長さだけずれた位置に分かれて複数の文書と共通のダイジェストが検出されれば、それは複数の文書が連続して引用されていると判定できる。図１２の例では、ｗをウィンドウサイズ、αを許容可能な文字列区間の開始位置の差分（許容誤差）であるとしたとき、ｗあるいはw＋αだけ離れたダイジェストが異なる引用している場合、複数文書が連続して引用されていると判定する。ここで、許容誤差αは、形態素解析結果の文字数の平均値または最大長を用いるものとする。当該許容誤差αを用いることで、複数の文書が連続して引用されていることを見逃す確率を低減させることが可能となる。

図１２において、各ダイジェストは1文字ずつずらす、または、形態素区切りで生成されているとする。同図の例において、最後に一致した「文書1」を引用しているダイジェストｂの次に一致したウィンドウサイズｗだけ離れた位置にあるダイジェストｃは、「文書２」を引用しているため、連続して引用されていると判断する。最初に一致したダイジェストｂと次に一致したダイジェストｃの区間はウィンドウｗと略同じである。

引用判定部１２０では、図１３に示す文書内位置と一致候補からなる照合テーブル１２１において、以下の（１）〜（３）のすべてが満たされている場合、複数の文書が連続して（間隔なしで）引用されていると判定する。

（１）ある文書との連続したダイジェストの一致：
一致候補の文書内の位置が連続していることで、連続したダイジェストであることを判定する。

（２）別の文書との連続したダイジェストの一致：
２つ目の一致候補の文書内位置が連続していることで判定する。

（３）（１）、（２）に挟まれた不一致区間がウィンドウサイズ＋許容誤差（α）：
当該文書の文書内位置の不一致区間がウィンドウサイズ+αだけ離れていることで判定する。

図１３の照合テーブルの場合は、ウィンドウサイズが１０の場合、文書"０００２"、"０００３"が連続して引用されていると判定する。

上記の判定では、文字列区間を１文字ずつずらす場合を示したが、以下に形態素区切りでずらす場合について説明する。

形態素区切りで引用判定する場合は、ダイジェスト計算部１１０において、ダイジェストDB１５０を生成する際に、図７の順引きテーブル１５１に、形態素解析結果に基づく文書先頭からの文字数を加えた構成とする。各ダイジェストの元となった文字列区間の開始位置が、文書先頭から何文字目に書かれているかが記載される。その例を図１４に示す。図１４のダイジェストDB１５０の例では、文書IDhttp://example.com/00001のダイジェスト"c595"は先頭（０）であり、"d03e"は先頭から3文字目であり、"ea79"は先頭から7文字目であることを示す。

さらに、形態素区切りを用いる場合の照合テーブルの例を図１５に示す。当該照合テーブル１２１'は、図１３の照合テーブル１２１に、文書内位置に対応させて文書先頭からの文字数の情報も加えられている。

形態素区切りにおける引用判定の場合には、ダイジェストDB１５０'の順引きテーブル１５１'から取得した文書iの文書IDに基づいて、逆引きテーブル１５２'から当該文書IDに対応するダイジェスト集合を読み出し、照合テーブル１２１'の文書先頭からの文字数及び一致候補を参照して、当該文書と他の文書と連続した不一致区間が、文字数としてウィンドウサイズ+αだけ不一致となっていることで判定する。

上記の図５に示す連続引用判定装置の構成要素の動作をプログラムとして構築し、連続引用判定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。

本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。

１００ 連続引用判定装置
１０１ 文書DB
１１０ ダイジェスト計算部
１２０ 引用判定部
１２１，１２１' 照合テーブル
１３０ ダイジェストサイズ計算部
１４０ ダイジェストサイズ選択テーブル
１５０，１５０' ダイジェストDB
１５１，１５１' 順引きテーブル
１５２，１５２' 逆引きテーブル

Claims (8)

1. 複数の文書の連続引用を判定するための連続引用判定装置であって、
   入力された文書の１つの文章から文字列区間を切り出し、該文字列区間の起点を決定し、該起点から一定文字数毎の文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせて該ダイジェストの文書ID及びダイジェスト群をダイジェストDBに格納するダイジェスト計算手段と、
   前記ダイジェストDBから前記ダイジェストを読み出し、該ダイジェストの所定のウィンドウサイズw分だけ離れた文字列区間にダイジェストが異なる文書を引用している場合に、複数文書が連続して引用されているものと判断する引用判定手段と、
   を有することを特徴とする連続引用判定装置。
2. 前記引用判定手段は、
   前記ウィンドウサイズｗに所定の文字列区間の開始位置の許容誤差αを加えた分だけ離れた文字列区間でダイジェストが異なる文書を引用している場合に、複数文書が連続して引用されているものと判断する手段を含む
   請求項1記載の連続引用判定装置。
3. 前記引用判定手段は、
   文書内位置と一致候補となる文書IDを格納した照合テーブルを更に有し、
   前記ダイジェストを１文字単位でずらした場合の文書内位置に基づいて、前記照合テーブルを参照し、
   ある文書との連続したダイジェストの一致：
   最後に一致したダイジェストと次に一致したダイジェストの間がウィドウサイズに許容誤差（α）を加えた長さだけが不一致：
   別の文書との連続したダイジェストの一致：
   の全てを満たす場合は、複数の文書が連続して引用されていると判定する手段を含む
   請求項２記載の連続引用判定装置。
4. 前記ダイジェストDBは、ダイジェストの文書先頭からの文字数を含み、
   前記引用判定手段は、
   文書内位置と一致候補となる文書ID、ダイジェストの文書先頭からの文字数を格納した照合テーブルを更に有し、
   前記ダイジェストを形態素区切りでずらした場合の文書位置に基づいて、前記照合テーブルを参照し、
   ある文書と他の文書と連続した不一致区間が、文字数としてウィンドウサイズに所定の許容誤差を加えたサイズだけ不一致である場合は、複数の文書が連続して引用されていると判定する手段を含む
   請求項２記載の連続引用判定装置。
5. 複数の文書の連続引用を判定するための連続引用判定方法であって、
   ダイジェスト計算手段、ダイジェストDB、引用判定手段を有する装置において、
   前記ダイジェスト計算手段が、入力された文書の１つの文章から文字列区間を切り出し、該文字列区間の起点を決定し、該起点から一定文字数毎の文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせて該ダイジェストの文書ID及びダイジェスト群を前記ダイジェストDBに格納するダイジェスト計算ステップと、
   前記引用判定手段が、前記ダイジェストDBから前記ダイジェストを読み出し、該ダイジェストの所定のウィンドウサイズw分だけ離れた文字列区間にダイジェストが異なる文書を引用している場合に、複数文書が連続して引用されているものと判断する引用判定ステップと、
   を行うことを特徴とする連続引用判定方法。
6. 前記引用判定ステップにおいて、
   前記ウィンドウサイズｗに所定の文字列区間の開始位置の許容誤差（α）を加えた分だけ離れた文字列区間でダイジェストが異なる文書を引用している場合に、複数文書が連続して引用されているものと判断する
   請求項５記載の連続引用判定方法。
7. 文書内位置と一致候補となる文書IDを格納した第１の照合テーブルを更に有する装置において、
   前記引用判定ステップにおいて、
   前記ダイジェストの文書内位置に基づいて、前記第１の照合テーブルを参照し、
   ある文書との連続したダイジェストの一致：
   最後に一致したダイジェストと次に一致したダイジェストの間がウィドウサイズ（ｗ）に前記許容誤差（α）を加えた長さだけが不一致：
   別の文書との連続したダイジェストの一致：
   の全てを満たす場合は、複数の文書が連続して引用されていると判定する
   請求項６記載の連続引用判定方法。
8. 文書内位置と一致候補となる文書ID、ダイジェストの文書先頭からの文字数を格納した第２の照合テーブルを更に有する装置において、
   前記ダイジェストDBは、ダイジェストの文書先頭からの文字数を含み、
   前記引用判定ステップにおいて、
   前記ダイジェストを形態素区切りでずらした場合の文書位置に基づいて、前記第２の照合テーブルを参照し、
   ある文書と他の文書と連続した不一致区間が、文字数としてウィンドウサイズ（ｗ）に前記許容誤差（α）を加えたサイズだけ不一致である場合は、複数の文書が連続して引用されていると判定する
   請求項６記載の連続引用判定方法。

Images