(57)【特許請求の範囲】
【請求項１】
複数の文書それぞれの一部を取り出して構成されている文書について、他の文書からの引用を判定するための自動構成文書判定装置であって、
入力された文書から一定文字数の文字列区間を切り出し、該文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせる毎に算出したダイジェスト群と文書IDとを、ダイジェストDBに格納するダイジェスト計算手段と、
前記ダイジェストDBから読み出した判定対象の文書のダイジェスト集合diのうち、別の文書に含まれるダイジェストの集合c(di)の数を該ダイジェスト集合diの数で除した値が閾値θrateより大きい場合には、あるいは、前記ダイジェストの集合c(di)の数を前記ダイジェスト集合diの数で除した値が閾値θrateより大きく、かつ、該ダイジェストの集合c(di)の数が閾値θnumより大きい場合には、前記判定対象の文書が引用によって構成された文書と判断する引用判定手段と、
を有することを特徴とする自動構成文書判定装置。
【請求項２】
引用判定されるための一致数ｋ、許容できる誤検出確率と与えられた文書数に基づいて、該許容できる誤検出確率の範囲内で、誤検出確率を下げつつダイジェストサイズが限界まで小さくなるように決定するダイジェストサイズ計算手段を更に有する
請求項１記載の自動構成文書判定装置。
【請求項３】
前記ダイジェストサイズ計算手段は、
引用判定するための一致数ｋ及びダイジェストサイズｇ、該引用判定するための一致数及び該ダイジェストサイズｇに対応する誤検出確率からなるダイジェストサイズ選択テーブルと、
前記引用判定するための一致数ｋ、誤検出確率の最大値及び想定される最大の文書数が与えられると、該想定される最大の文書数の逆数に誤検出確率を乗算した値を基準として、前記ダイジェストサイズ選択テーブルの前記一致数ｋの行に存在する誤検出確率が、該誤検出確率の最大値を下回る列のダイジェストサイズｇを、前記引用判定に最低限必要なダイジェストサイズとして決定する手段と、
を含む請求項２記載の自動構成文書判定装置。
【請求項４】
複数の文書それぞれの一部を取り出して構成されている文書について、他の文書からの引用を判定するための自動構成文書判定方法であって、
ダイジェスト計算手段、ダイジェストDB、引用判定手段を有する装置において、
前記ダイジェスト計算手段が、入力された文書から一定文字数の文字列区間を切り出し、該文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせる毎に算出したダイジェスト群と文書IDとを、ダイジェストDBに格納するダイジェスト計算ステップと、
前記引用判定手段が、前記ダイジェストDBから読み出した判定対象の文書のダイジェスト集合diのうち、別の文書に含まれるダイジェストの集合c(di)の数を該ダイジェスト集合diの数で除した値が閾値θrateより大きい場合には、あるいは、前記ダイジェストの集合c(di)の数を前記ダイジェスト集合diの数で除した値が閾値θrateより大きく、かつ、該ダイジェストの集合c(di)の数が閾値θnumより大きい場合には、前記判定対象の文書が引用によって構成された文書と判断する引用判定ステップと、
を行うことを特徴とする自動構成文書判定方法。
【請求項５】
ダイジェストサイズ計算手段を更に有する装置において、
前記ダイジェストサイズ計算手段が、許容できる誤検出確率と与えられた文書数に基づいて、該許容できる誤検出確率の範囲内で、誤検出確率を下げつつダイジェストサイズが限界まで小さくなるように決定するダイジェストサイズ計算ステップを更に行う
請求項４記載の自動構成文書判定方法。
【請求項６】
前記ダイジェストサイズ計算ステップにおいて、
引用判定するための一致数ｋ、誤検出確率の最大値及び想定される最大の文書数が与えられると、該想定される最大の文書数の逆数に誤検出確率を乗算した値を基準として、該引用判定するための一致数ｋ及びダイジェストサイズｇ、該引用判定するための一致数及び該ダイジェストサイズｇに対応する誤検出確率からなるダイジェストサイズ選択テーブルの該一致数ｋの行に存在する誤検出確率が、該誤検出確率の最大値を下回る列のダイジェストサイズｇを、前記引用判定に最低限必要なダイジェストサイズとして決定する
請求項５記載の自動構成文書判定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自動構成文書判定装置及び方法に係り、特に、電子化された文書（例えば、Web上のブログ）の断片を組み合わせることによって自動的に作成された文書の引用関係の分析を行うための自動構成文書判定装置及び方法に関する。
【背景技術】
【０００２】
他の文書からの引用を判定する手法として、引用分析が用いられてきた。
【０００３】
特許文献１では、文書を引用可能なセグメントに分割し、それぞれのセグメントについてダイジェストを生成して連結した文字列を作成し、原典となる文書のDB内に保存された文書から同様にして得られた文字列と比較することで、当該原典からの引用を判定している。
【０００４】
また、特許文献２では、ネットワークパケットの異常を検出するため、スライディングウィンドウと呼ばれる方法を使用している。これは、データのシーケンスに対して、セグメント分割するのではなく、一定のデータ長をウィンドウとし、移動する（スライドする）ウィンドウ内のデータに対する関数値から異常を検出するものである。これを文書に適用することで文書内の文字列をデータのシーケンスと見做し、一定のサイズのウィンドウを文書の先頭から移動させることで、ウィンドウごとの異常値を発見することができる。
【０００５】
また、特許文献３では、２つの文書間の類似度に基づいて引用判定を行っている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１０−１８２２３８号公報
【特許文献２】特開２００９−１５２７１２号公報
【特許文献３】特開２００９−２０５６７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
図１、図２を例に従来の問題点について説明する。
【０００８】
図１に示すような複数の文書の断片によって構成されている文書に対して引用判定を行うことを考える。図２に示すように、１つの断片は日本語で５０文字程度であり、断片は文によっては分断されず、ランダムな位置で分断され、接続されている。また、原典の仮名が漢字に変換されていることがある。例えば、図２に示すように、原典（引用元）では「顧みて見る」であるが、同図の例では「顧みてみる」として一文字「見」が「み」と変換されて引用されている。このような文書では、文章の一部に着目すれば意味は通るが、全体では意味が通らないものの、キーワード検索でヒットしてしまう。
【０００９】
上記の特許文献１の方法を用いることで、明確にセグメント分割可能な文書に対しては有効に働くが、
（１）本発明が対象とするような、文の区切りを明らかに指定できないような文書ではセグメント分割が行えない；
（２）比較的短い文字列単位で引用されている場合には、引用されたことを判定しにくい；
という問題がある。
【００１０】
ここに、特許文献２のスライディングウィンドウを導入することで、文書内での任意の区間でダイジェストを作成することができ、文の区切りが明らかでない文書に対しても引用判定が可能となる。但し、以下の問題が残る。
【００１１】
（１）適切なスライディングウィンドウの起点の選択基準が不明確である。
【００１２】
（２）複数の文書が連続して引用されていることの判定が行えない。
【００１３】
（３）文書内に微少な修正が施されている時の判定が行えない。
【００１４】
（４）スライディングウィンドウ方式を使用すると、文書をセグメント分割する場合と比較して、ダイジェストを作成する区間数が増加するため、そのままダイジェストを作成すると、ダイジェストを保存するDBのサイズが爆発的に増大する。
【００１５】
また、特許文献３の方法では、複数の文書の引用を想定していないため、複数の文書の断片によって構成される文書の引用判定は行えない。
【００１６】
本発明は、上記の点に鑑みなされたもので、引用が連接している、あるいは、少数の文字を挟んで連接しており、かつ、引用が全体の一定以上の部分を占めているようなダイジェストを抽出すると共に、ダイジェストを格納するDBのサイズを抑えながら誤検出を最小にすることが可能な自動構成文書判定装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１７】
一態様によれば、複数の文書それぞれの一部を取り出して構成されている文書について、他の文書からの引用を判定するための自動構成文書判定装置であって、
入力された文書から一定文字数の文字列区間を切り出し、該文字列区間に対する文字列をハッシュ関数により変換したダイジェストを所定の文字数分スライドさせる毎に算出したダイジェスト群と文書IDとを、ダイジェストDBに格納するダイジェスト計算手段と、
前記ダイジェストDBから読み出した判定対象の文書のダイジェスト集合diのうち、別の文書に含まれるダイジェストの集合c(di)の数を該ダイジェスト集合diの数で除した値が閾値θrateより大きい場合には、あるいは、前記ダイジェストの集合c(di)の数を前記ダイジェスト集合diの数で除した値が閾値θrateより大きく、かつ、該ダイジェストの集合c(di)の数が閾値θnumより大きい場合には、前記判定対象の文書が引用によって構成された文書と判断する引用判定手段と、を有する自動構成文書判定装置を提供する。
【発明の効果】
【００１８】
一態様によれば、原典からの引用が連接している、あるいは、少数の文字を挟んで連接しており、かつ、引用が全体の一定以上の部分を占めているような文書を抽出することが可能となる。また、文書の引用判定に使用するダイジェストに最低限必要なサイズ（ダイジェストサイズ）を用いて引用判定を行うことで、ダイジェストを格納するDBのサイズを抑えながら誤検出（ダイジェストサイズを小さくすると発生しやすくなる）を最小とするよう計算をすることが可能となる。
【図面の簡単な説明】
【００１９】
【図１】引用判定の対象文書の例である。
【図２】対象文書の断片の例である。
【図３】本発明の基本的な考え方を示す図である。
【図４】本発明の一実施の形態におけるダイジェスト作成例である。
【図５】本発明の一実施の形態における自動構成文書判定装置の構成図である。
【図６】本発明の一実施の形態における自動構成文書判定装置の全体のフローチャートである。
【図７】本発明の一実施の形態におけるダイジェストDBの例である。
【図８】本発明の一実施の形態におけるダイジェスト計算部の処理のフローチャートである。
【図９】本発明の一実施の形態における単一文書のダイジェスト計算のアルゴリズムである。
【図１０】本発明の一実施の形態における単一文書のダイジェスト計算のフローチャート（Ｓ２３０の詳細）である。
【図１１】本発明の一実施の形態における引用判定部のフローチャートである。
【図１２】本発明の一実施の形態における照合テーブルの例である。
【図１３】本発明の一実施の形態における引用判定アルゴリズムである。
【図１４】本発明の一実施の形態における引用判定の詳細処理のフローチャート（Ｓ４４０の詳細）である。
【発明を実施するための形態】
【００２０】
以下、図面と共に本発明の実施の形態を説明する。
【００２１】
最初に、本明細書に用いられる用語について説明する。
【００２２】
・ダイジェスト：ある文字列が与えられたとき、その文字列をハッシュ関数によって短いバイト数（またはビット数）に変換したもの。
【００２３】
・ダイジェストサイズ：上記の短いバイト数。
【００２４】
・一致するダイジェスト：1つの文書に含まれる多くの文字列区間それぞれにダイジェストが生成されるが、ある文書から生成されるダイジェスト群の中に含まれ、他の文書のダイジェスト群の中にも出てくるダイジェスト。
【００２５】
・一致するダイジェスト数：２つのダイジェスト群の中で、一致するダイジェストの組の数。
【００２６】
本発明の概要を示す。
【００２７】
図３は、本発明の基本的な考え方を示す。
【００２８】
引用元Ａ，Ｂ，Ｃの文書から引用先において、引用元の文書Ａ，Ｂ，Ｃの一部を取り出してある文書を作成しているとする。
【００２９】
既存手法では、文単位でセグメント分割してダイジェスト集合を作り、比較し、一致すれば同一の文であると判断する。しかし、引用先の文書が文の体をなしていないときは、特許文献１の技術によるセグメント分割ができない。
【００３０】
これに対し、本発明では、一組の文書の対について引用分析するのではなく、スライディングウィンドウを使用する際に、ある１つの文書が他の複数の文書と同一のダイジェストを持っている文字列区間数の割合を用いる。また、他の文書と一致している文字列区間数の全体における割合によって引用を判定する。
【００３１】
本発明では、文書をより詳細な文字列区間に分割して、文字単位や形態素区切りを用いて起点を設定し、各起点から一定文字数ごとの文字列区間に対するダイジェストを作成する。図４に１つの文章から文字列区間を切り出し、ダイジェストを生成する例を示す。ここでは、文字列間の起点は１文字単位でずらすこととし、文字数は２０文字とした。また、ダイジェストは文字列をUTF-8で表現したときのMD５ハッシュ値（非特許文献１：The MD5 Message-Digest Algorithm. http://tools.ietf.org/html/rfc1321）の上位３２ビットの0からFまでの１６進表現（例えば、"c595"）を用いた例である。
【００３２】
このようにして作られたダイジェストを、順引き及び逆引きテーブルとしてダイジェストDBに保管する。
【００３３】
引用分析は、以下のように行う。文書集合Dについて、ある文書ｉ∈D内の文字列区間群に対して生成されたダイジェストの集合diを
【００３４】
【数１】
0005906228.tif 000002
とする。（niはdiから得られた文字列区間の数）。このとき、di内のダイジェストのうち、別の文書に含まれる割合が一定より多い場合、引用によって構成された文書と判断する。
【００３５】
以下、具体的に説明する。
【００３６】
図５は、本発明の一実施の形態における自動構成文書判定装置の構成を示す。
【００３７】
同図に示す自動構成文書判定装置１００は、ダイジェスト計算部１１０、引用判定部１２０、ダイジェストサイズ計算部１３０、ダイジェストサイズ選択テーブル１４０、ダイジェスト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となり、この値を小さくすることを目標とする。
【００５９】
ダイジェストサイズを小さくすると、複数の文字列が同じダイジェストを持つことになり、引用判定の誤りが発生することになる。この確率を下げることができれば、ダイジェストサイズを限界まで小さくすることができる。
【００６０】
文書dhには平均してｓ個の区間が含まれるため、文書のダイジェスト集合を（簡単のため）｛h1,h2,…,hn｝と表現すると、任意のダイジェストがこの文書のダイジェスト集合に含まれる可能性は、p=s/2gと書ける。つまり、定数ｓ（文書DB１０１の文書数に含まれる区間の平均）とダイジェストサイズｇ（バイト）が与えられることによりpが求められる。
【００６１】
ある文書に含まれるｓ個のダイジェストのうち、任意の１つが別のある文書に同時に出現する確率は、sp=s2/2gであり、任意のk個の別の文書に同時に出現する確率は以下のように書ける（ｓに比べてｋは十分小さいものとする）。
【００６２】
【数２】
0005906228.tif 000003
この値が十分小さくなるように文書DB１０１に格納されている文書数（想定される最大の文書数）に応じて、ｐとｋを選ぶことで、偶然を排除する。ｐ、ｋは、ダイジェストサイズ計算部１３０によってｇとｋを選択し、ｇと文書DB１０１内の文書中に含まれる区間の数の平均ｓにより、p=s/2gによって求められる。上記の式(1)で求められた値がダイジェストサイズ選択テーブル１４０に格納される。
【００６３】
＜形態素区切りを区間の起点とする場合＞
形態素区切りを区間の起点とすると、１つの形態素あたりの文字列長を平均３文字と考えると、UTF-8では１文字が３バイトとなるため、
【００６４】
【数３】
0005906228.tif 000004
である。例えば、文書の平均長が10キロバイトとすると、s=1111だが、簡単のため、
【００６５】
【数４】
0005906228.tif 000005
とする。
【００６６】
例えば、g＝24（ビット）とすると,
p=1000/224=5.96×10-5
であるが、このとき、1つ以上のダイジェストが一致する確率は5.96×10-2となる。これは、文書数が20程度あれば、平均1回以上の誤検出を生じることを示している。
【００６７】
一致するダイジェスト数を増やす方向と、ダイジェストサイズを増やす方向から誤検出確率を下げることができる。
【００６８】
表１に、ダイジェスト数k及びダイジェストサイズｇをそれぞれ増やした場合の誤検出確率を格納したダイジェストサイズ選択テーブル１４０の例を示す。表1の例は文書あたりのセグメント数を1000と仮定している。但し、ｇについて誤検出確率が10-13前後となるkまでに限定している。
【００６９】
【表１】
0005906228.tif 000006
ダイジェストサイズを求める際には、ダイジェスト選択テーブル１４０に対し、文書数の逆数に誤検出確率を乗じたものを基準とし、その数値よりもダイジェストサイズ選択テーブル１４０の値が小さくなるようなｋとｇの組み合わせを選択する。以下に詳述するが、例えば、文書数が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１５０に格納する（ステップ２４０）。これを繰り返すことで、文書DB１０１中の全ての文書についてダイジェストを計算する。
【００７７】
ステップ２２０における文書の読み出し時には、文書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に対応するダイジェスト集合を読み出し（ステップ４３０）、文書iの引用判定を行い（ステップ４４０）、判定結果が「真」であれば（ステップ４６０,Yes）、スパム集合Sに文書iを追加する（ステップ４６０）。このときスパム集合Ｓに追加するダイジェストサイズの情報を順引きテーブル１５１から取得して追加する。ダイジェストDB１５０の全ての文書についての処理が終了したら（ステップ４２０，No）、スパム集合Sを出力する（ステップ４７０）。
【００８９】
上記のステップ４４０の引用判定部１２０の処理について説明する。
【００９０】
ステップ４４０では、ダイジェストDB１５０から読み出した文書のダイジェストが他の文書と一致するダイジェストの数、または、他の文書と一致しているダイジェストの全体における割合が所定の閾値より大きい場合に引用されたものであると判定する。
【００９１】
以下に詳細に説明する。
【００９２】
引用判定部１２０は、メモリ（図示せず）上に、ダイジェストDB１５０内の文書のダイジェスト集合と一致するダイジェスト候補の配列を格納する照合テーブル１２１（図１２）を有する。
【００９３】
引用判定部１２０は、ダイジェストDB１５０の順引きテーブルよりダイジェストの集合を読み出す。文書の集合Dについて、ある文書i∈D内の文字列区間群に対して生成されたダイジェストの集合を
【００９４】
【数５】
0005906228.tif 000007
とする（niはdiから得られた文字列区間の数）。このときダイジェスト集合d i内のダイジェストのうち、別の文書に含まれる割合が一定の値より多い場合、引用によって構成された文書と判断する。
【００９５】
具体的に以下に示す。
【００９６】
c(di)を文書iについて他の文書にも含まれるダイジェスト集合とする。c(di)の定義としては以下が考えられる。
【００９７】
【数６】
0005906228.tif 000008
ここで、txは、文書の作成日時（順引きテーブル１５１の作成日時より取得）を表し、より新しい日時が大きい値を持つ。
【００９８】
閾値θrate（0≦θ≦1）及びθnum(θ≧１)の2つの閾値を設定し、下記の式(2)に合致する場合、ダイジェストd iは引用によって構成されていると判断する。
【００９９】
【数７】
0005906228.tif 000009
但し、card(x)は、集合の要素数を表す。ここで、θrateは文書のダイジェストが他の文書と一致している比率に対する閾値であり、θnumは文書のダイジェストが他の文書と一致している数に対する閾値である。つまり、文書のダイジェストが他の文書と同じであるとき、その比率及び個数の双方が一定値以上であれば、引用によって構成された文書であると判定する。
【０１００】
なお、文書DB１０１内の全ての文書について引用判定を行ったが、一度全ての文書についてダイジェスト計算をしてダイジェストDB１５０に格納してからは、最新の単一文書にみについてダイジェスト計算及び引用判定を行うことができる。
【０１０１】
最新の文書について引用を判定する場合には、当該文書について図８のステップ２３０によってダイジェストを計算してダイジェストDB１５０に格納し、引き続き図１１のステップ４４０の引用判定処理によって引用を判定する。
【０１０２】
引用判定アルゴリズムを図１３に、フローチャートを図１４に示す。
【０１０３】
引用判定の閾値として、閾値θrate（０≦θ≦1）と、θnum(（θ≧１）が入力される（ステップ４４１）。
【０１０４】
ダイジェストDB１５０の逆引きテーブル１５２から文書iのダイジェスト集合d iを取得する（ステップ４４２）。文書iのダイジェスト集合diについて他の文書と一致するダイジェスト集合の数（マッチカウント：ｍ）を０に初期化する（ステップ４４３）。
【０１０５】
文書iのダイジェスト集合d iについて、他の文書と一致するダイジェスト候補の配列を抽出し、その文書内位置と一致候補の文書IDを組にして照合テーブル１２１（図１２）に格納する（ステップ４４４）。
【０１０６】
図１２に示す照合テーブル１２１の一致候補の文書IDを昇順にサーチし（ステップ４４５）、一致する候補がある場合は（ステップ４４６,Yes）、マッチカウントmを1インクリメントし（ｍ＝ｍ＋１）、
【０１０７】
【数８】
0005906228.tif 000010
であるかを判定し、上記の関係が成り立たつ場合には（ステップ４４８，Yes）、引用あり（「真」）と判定し（ステップ４４９）、成り立たない場合には（ステップ４４８,No）、引用ではないと判断する（ステップ４５０）。
【０１０８】
上記の図５に示す自動構成文書判定装置の構成要素の動作をプログラムとして構築し、自動構成文書判定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１０９】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１１０】
１００  自動構成文書判定装置
１０１  文書DB
１１０  ダイジェスト計算部
１２０  引用判定部
１２１  照合テーブル
１３０  ダイジェストサイズ計算部
１４０  ダイジェストサイズ選択テーブル
１５０  ダイジェストDB
１５１  順引きテーブル
１５２  逆引きテーブル
【図１】
0005906228.tif 000011
【図２】
0005906228.tif 000012
【図３】
0005906228.tif 000013
【図４】
0005906228.tif 000014
【図５】
0005906228.tif 000015
【図６】
0005906228.tif 000016
【図７】
0005906228.tif 000017
【図８】
0005906228.tif 000018
【図９】
0005906228.tif 000019
【図１０】
0005906228.tif 000020
【図１１】
0005906228.tif 000021
【図１２】
0005906228.tif 000022
【図１３】
0005906228.tif 000023
【図１４】
0005906228.tif 000024