(57)【要約】識別性が高いテキストの断片を使用することにより、ドキュメントコレクション（＃１００）内で複製または複製に近いドキュメントまたはテキストスパンを見つけるためのコンピュータ支援方法が開示されている。ドキュメントまたはテキストスパンの顕著な特徴が識別される（＃１１０）。少なくとも１つの顕著な特徴を共有する一対のドキュメントまたはテキストスパン毎に、各ドキュメントまたはテキストスパンの顕著な特徴が比較され、これらの対が複製もしくは複製に近いか否かが判断される（＃１１４）。【選択図】図１
2004519761.tif 000002
【特許請求の範囲】
【請求項１】
大きなドキュメントのコレクション内で複製または複製に近いドキュメントを識別するためのコンピュータ支援方法において、
最初に、ドキュメントのコレクション内に含まれる顕著な特徴を選択する工程と、
その後、各ドキュメント毎に、ドキュメントに含まれる顕著な特徴を識別する工程と、
その後、少なくとも１つの顕著な特徴を共有する一対のドキュメント毎に、ドキュメントの顕著な特徴を比較して、ドキュメントが複製または複製に近いドキュメントであるか否かを判断する工程と、
を含んだことを特徴とするコンピュータ支援方法。
【請求項２】
ドキュメントコレクション内の複製を取り除くために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項３】
盗作を見つけるために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項４】
著作権侵害を見つけるために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項５】
ドキュメントの出所を判断するために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項６】
ドキュメントコレクションの中からドキュメントの連続するバージョンを集めるために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項７】
複製または複製に近いドキュメントのセットに、テキスト分類アルゴリズムまたはテキスト集積アルゴリズムを導入するために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項８】
電子メールメッセージを電子メールメッセージへの応答とマッチさせるために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項９】
電子メールメッセージへの応答を電子メールメッセージとマッチさせるために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項１０】
問い合わせシステムと共に使用されるドキュメントインデックスを作成し、問い合わせに応じて、特定のフレーズまたは引用句を含むドキュメントを効果的に見つけるために適用されることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項１１】
特定のフレーズまたは引用句がドキュメントまたは問い合わせにおいて正しく記録されていなかった場合でも、ドキュメントインデックスを使用できることを特徴とする請求項１０に記載のコンピュータ支援方法。
【請求項１２】
顕著な特徴は、各ドキュメント中に異なる状態で現われることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項１３】
顕著な特徴は、ドキュメントコレクション内のドキュメントからの顕著なテキストの断片であることを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項１４】
情報検索方法に適用されることを特徴とする請求項１３に記載のコンピュータ支援方法。
【請求項１５】
情報検索方法がテキスト分類方法であることを特徴とする請求項１４に記載のコンピュータ支援方法。
【請求項１６】
情報検索方法はワードが独立であると仮定しており、顕著なテキストの断片がインデックスセットに加えられることを特徴とする請求項１４に記載のコンピュータ支援方法。
【請求項１７】
顕著なテキストの断片は、ドキュメントコレクション内の限られた数のドキュメントに現われる少なくとも２つのワードから成る配列であることを特徴とする請求項１３に記載のコンピュータ支援方法。
【請求項１８】
一方の顕著なテキストの断片が、同じドキュメント中の他方の顕著なテキストの断片内に含まれる場合、最も長い顕著なテキストの断片だけが顕著な特徴と見なされることを特徴とする請求項１４に記載のコンピュータ支援方法。
【請求項１９】
少なくともユーザ仕様の最小の回数で、少なくとも２つのワードから成る配列をドキュメントが含んでいる場合、少なくとも２つのワードから成る配列がそのドキュメント中に現われていると見なされることを特徴とする請求項１７に記載のコンピュータ支援方法。
【請求項２０】
少なくともユーザ仕様の最小の頻度で、少なくとも２つのワードから成る配列をドキュメントが含んでいる場合、少なくとも２つのワードから成る配列がそのドキュメント中に現われていると見なされることを特徴とする請求項１７に記載のコンピュータ支援方法。
【請求項２１】
少なくとも２つのワードから成る各配列毎に、識別性スコアが演算され、
ドキュメントコレクション中の少なくとも２つのドキュメントに見出される最もスコアが高い配列が顕著なテキストの断片として見なされることを特徴とする請求項１７に記載のコンピュータ支援方法。
【請求項２２】
識別性スコアは、フレーズ中のワード数の単調関数によって乗じられたフレーズを含むドキュメントの数の逆数であることを特徴とする請求項２１に記載のコンピュータ支援方法。
【請求項２３】
単調関数がフレーズ中のワードの数であることを特徴とする請求項２１に記載のコンピュータ支援方法。
【請求項２４】
識別性スコアは、フレーズ中のワード数の単調関数によって乗じられたフレーズを含まないドキュメントのパーセンテージであることを特徴とする請求項２１に記載のコンピュータ支援方法。
【請求項２５】
単調関数がフレーズ中のワードの数であることを特徴とする請求項２４に記載のコンピュータ支援方法。
【請求項２６】
限られた数がユーザによって選択されることを特徴とする請求項１７に記載のコンピュータ支援方法。
【請求項２７】
限られた数は、ドキュメントコレクション中のドキュメントの数の一次関数によって規定されることを特徴とする請求項１７に記載のコンピュータ支援方法。
【請求項２８】
顕著なテキストの断片がグルーワードを含んでいることを特徴とする請求項１７に記載のコンピュータ支援方法。
【請求項２９】
グルーワードは、いずれかの極端に顕著なテキストの断片で現われないことを特徴とする請求項２８に記載のコンピュータ支援方法。
【請求項３０】
少なくとも１つの顕著な特徴を共有する一対のドキュメント毎に、共通する顕著な特徴の数をカウントする工程を更に有し、
一対のドキュメントが複製または複製に近いか否かの判断は、
一対のドキュメント毎に、共通する顕著な特徴の数を、少ない各ドキュメントの顕著な特徴の数で割ることにより、重なり率を演算する工程と、
重なり率を閾値と比較して、重なり率が閾値よりも大きければ、一対のドキュメントが複製または複製に近いとし、重なり率が閾値よりも大きくなければ、一対のドキュメントが複製でもなく複製に近くもないとする工程と、
を含んだことを特徴とする請求項１に記載のコンピュータ支援方法。
【請求項３１】
各ドキュメントをその対応する顕著な特徴にマッピングするドキュメントインデックスを形成し、１つのドキュメント内で１つの顕著な特徴が繰り返される場合に、インデックスが１回だけドキュメントを顕著な特徴にマッピングする工程と、
各顕著な特徴をその対応するドキュメントにマッピングする特徴インデックスを形成し、１つのドキュメント内で１つの顕著な特徴が繰り返される場合に、インデックスが１回だけ顕著な特徴をドキュメントにマッピングする工程と、
一対のドキュメントが複製または複製に近いか否かの判断は、
ドキュメントインデックスから特有の顕著な特徴のリストを形成する工程と、
特有の顕著な特徴毎に、特有の顕著な特徴を含むドキュメントのリストを作成する工程と、
各ドキュメント毎に、ドキュメントに共通する少なくとも１つの特徴を有するドキュメントおよびドキュメントに共通する特徴の数のリストを作成する工程と、
を含んだことを特徴とする請求項３０に記載のコンピュータ支援方法。
【請求項３２】
顕著な特徴が顕著なフレーズを含んでいることを特徴とする請求項３１に記載のコンピュータ支援方法。
【請求項３３】
顕著な特徴は、異なる状態で各ドキュメントに現われることを特徴とする請求項３１に記載のコンピュータ支援方法。
【請求項３４】
顕著な特徴がテキストスパンを含んでいることを特徴とする請求項３１に記載のコンピュータ支援方法。
【請求項３５】
テキストスパンが文を含んでいることを特徴とする請求項３４に記載のコンピュータ支援方法。
【請求項３６】
テキストスパンがテキストの行を含んでいることを特徴とする請求項３４に記載のコンピュータ支援方法。
【請求項３７】
大きなテキストスパンのコレクション内で複製または複製に近いテキストスパンを識別するためのコンピュータ支援方法において、
最初に、テキストスパンのコレクション内に含まれる顕著な特徴を選択する工程と、
その後、各テキストスパン毎に、テキストスパンに含まれる顕著な特徴を識別する工程と、
その後、少なくとも１つの顕著な特徴を共有する一対のテキストスパン毎に、テキストスパンの顕著な特徴を比較して、テキストスパンが複製または複製に近いテキストスパンであるか否かを判断する工程と、
を含んだことを特徴とするコンピュータ支援方法。
【請求項３８】
テキストスパンが文であることを特徴とする請求項３７に記載のコンピュータ支援方法。
【請求項３９】
大きなドキュメントのコレクション内で複製または複製に近いドキュメントを識別するための方法を可能にする装置において、
最初に、ドキュメントのコレクション内に含まれる顕著な特徴を選択するための手段と、
その後、各ドキュメントに含まれる顕著な特徴を識別する手段と、
その後、少なくとも１つの顕著な特徴を共有する一対のドキュメントのそれぞれの顕著な特徴を比較して、ドキュメントが複製または複製に近いドキュメントであるか否かを判断する手段と、
を備えたことを特徴とする装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ドキュメントまたはテキストスパンのコレクション内で、複製および複製に近いドキュメントまたはテキストスパンを識別するためのコンピュータ支援方法および装置に関する。
【０００２】
【従来の技術】
現在の技術は、類似していることが分かっているドキュメントの１つの対を比較して、ドキュメント同士の差異を識別する発明を含んでいる。たとえば、Ｕｎｉｘ（Ｒ）“ｄｉｆｆ”プログラムは、２つのドキュメント中の行（ライン）などの２つの配列間で最も長い共通したサブ配列（ＬＣＳ）を見つける有効なアルゴリズムを使用する。これについては、非特許文献１を参照のこと。ＬＳＣが除去される時に残るライン（行）は、一方のドキュメントを他方のドキュメントに変換するために必要な変化を示している。また、特許文献１は、アンカーポイント（２つのファイルに共通のポイント）を使用して、ドキュメントのオリジナルバージョンと修正バージョンとの間の差異を識別する。また、Ｕｎｉｘ（Ｒ）“ｃｍｐ”プログラム等の一対のファイルを比較するためのプログラムもある。
【０００３】
ドキュメントを比較する他の手法は、各ドキュメント毎にチェックサムを演算することである。２つのドキュメントが同じチェックサムを有している場合、これらのドキュメントは同一である可能性が高い。しかし、チェックサムを使用したドキュメントの比較は、ドキュメントの文字が１つ変化しただけでチェックサムが異なってしまうため、極端に脆い方法である。したがって、チェックサムは、正確な複製を識別する場合にはよいが、複製に近いものを識別する場合には適さない。特許文献２は、チェックサムを使用して複製記録を識別することを教示している。特許文献３は、チェックサムを使用して、ドキュメントの領域が変更されたか否かを、ＨＴＭＬタグ間のテキスト等のサブドキュメントの一節とチェックサムとを比較することにより識別する。
【０００４】
非特許文献２で論じられているパトリック・ジュオラの方法は、平均的な長さのマッチングｎ重文字（ｎ重文字は、全てのワードまたは一部のワードから構成されてもよい一続きの文字である）を使用して、同様のドキュメントを識別する。ソースドキュメントにおける連続した文字の各ウインドウ毎に、ターゲットとなるドキュメントの各位置で、平均的な長さのマッチングサブ配列が演算される。これは、ソースドキュメント内の全ての可能なｎ重文字において、ターゲットとなるドキュメント内の各位置で、平均的な長さのマッチを有効に演算する（最初のｎ重文字から始まる連続するマッチング文字の数を数える）。この技術は、ｎ重文字および全てのサブパーツ（少なくとも接頭語サブパーツ）に高頻度を要求することにより、ドキュメント内でのｎ重文字の頻度に依存している。ジュオラの方法は、非常に小さなトレーニングコーパス含む用途に重点を置いており、言語識別、ドキュメントの出所の検出、テキスト分類を含む様々な領域に適用されてきている。この方法は、識別性の尺度を提供しない。
【０００５】
【特許文献１】
米国特許第４８０７１８２号明細書
【特許文献２】
米国特許第５６８０６１１号明細書
【特許文献３】
米国特許第５８９８８３６号明細書
【非特許文献１】
Ａｈｏ，  Ｈｏｐｃｒｏｆｔ，  ａｎｄ  Ｕｌｍａｎ，  Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅｓ  ａｎｄ  Ａｌｇｏｒｉｔｈｍｓ，  Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ，  Ａｐｒｉｌ  １９８７、第１８９頁〜第１９２頁
【非特許文献２】
Ｊｕｏｌａ，  Ｐａｔｒｉｃｋ，  Ｗｈａｔ  Ｃａｎ  Ｗｅ  Ｄｏ  Ｗｉｔｈ  Ｓｍａｌｌ  Ｃｏｒｐｏｒａ  ？  Ｄｏｃｕｍｅｎｔ  Ｃａｔｅｇｏｒｉｚａｔｉｏｎ  ｖｉａ  Ｃｒｏｓｓ−Ｅｎｔｒｏｐｙ，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｉｍｉｌａｒｉｔｙ  ａｎｄ  Ｃａｔｅｇｏｒｉｚａｔｉｏｎ，  １９９７
【０００６】
【発明が解決しようとする課題】
従来技術は３つ以上のドキュメントを比較せず、また、従来技術によって各ドキュメント中のテキストの断片を様々な状態または任意の状態で現わすことができない。また、従来技術はドキュメントを比較するために使用されるｎ重文字を選択せず、また、従来技術は、ドキュメントを比較するために使用されるｎ重文字を選択するためにドキュメントにわたるｎ重文字の頻度を使用しない。また、従来技術は、ｎ重文字における非常に低い頻度要素と非常に高い頻度要素との組合せを許容しない。
【０００７】
本発明の目的は、複製および複製に近いドキュメントおよびテキストスパンを有効に識別できる方法および装置を提供することである。
【０００８】
【課題を解決するための手段】
したがって、ドキュメントを比較できる識別性が高いテキストの断片を使用して、複製および複製に近い（すなわち、実質的に複製）ドキュメントおよびテキストスパンを有効に識別する方法および装置を開発した。
【０００９】
複製に近いドキュメントは、他の複製でないドキュメント中には存在しない長い一続きの同じテキストを含んでいる。幾つかのドキュメントだけに存在するこの長いテキストの断片（高−中程度の珍しさ）は、同様のドキュメントを異なるドキュメントから好ましい方法で区別するために使用できる顕著な特徴である。これらのテキストの断片は、ドキュメントを複製に近いドキュメントにマッチさせ且つそのドキュメントを複製でないドキュメントから区別するために使用できる、ドキュメントにおけるある種の“サイン”である。そのようなテキストの断片に関して著しく重なり合うドキュメントは、殆どの場合、複製または複製に近い。このような重なり合いは、テキストが引用される時ではなく、言い替え、他の筆者によるコメントの散在、完全な盗作など、意図的な変更がテキストに成された時に生じる。
【００１０】
一般に、ドキュメントが完全に書き換えられていない限り、そのドキュメントおよびその複製に特有の大きなテキストの断片が存在する。一方、複製でない２つのドキュメント間に共通するテキストの断片は、他の多くのドキュメントにも共通している可能性がある。
【００１１】
本発明は、各ドキュメントにおける少数の顕著な特徴、たとえば複製または複製に近いドキュメントに現われる可能性がある顕著なｎ重文字のワードを識別することにより、複製および複製に近いドキュメントおよびテキストスパンを識別する。この特徴はドキュメント全体のための代替物として機能し、これにより、本発明は、ドキュメントをその顕著な特徴を比較することにより比較することができる。少なくとも１つの特徴を共有するドキュメントが互いに比較される。複製に近いドキュメントは、２つのドキュメント間に共通する特徴の割合をカウントすることにより識別される。これらの共通の特徴を使用することにより、本発明は、各ドキュメントをコレクション内の他の全てのドキュメントと比較することなく、たとえば２つ一組の比較により、複製に近いドキュメントを有効に見つけることができる。ドキュメント全部の代わりに特徴を比較することにより、本発明は、従来のドキュメント比較アルゴリズムを用いて行なうことができる場合よりもずっと速く、大きなコレクション内で複製および複製に近いドキュメントを見つけることができる。
【００１２】
この方法の有効性において重要なのは、顕著な特徴を見出す能力である。この特徴は、複製に近いドキュメントだけに共通している程度に十分珍しい必要があるが、１つのドキュメントだけに特有のものであるといったほど珍しい必要はない。個々のワードは、十分に珍しくなくてもよいが、ｎ重文字のワードである必要がある。長いｎ重文字のワードは非常に稀である。また、顕著な特徴は、特徴内にグルーワード（すなわち、非常に共通したワード）を含んでいてもよいが、いずれかの末尾に含んでいないことが好ましい。したがって、顕著な特徴は、幾つかのドキュメントだけに共通するワードや、全てのドキュメントに共通しないが幾つかのドキュメントに共通するワードを含んでいてもよい。
【００１３】
適当な珍しさを有する全てのｎ重文字のワードを盲目的に集めると、コンピュータ的に高価なアルゴリズムが生じる。したがって、アルゴリズムをコンピュータ的に有効にするためには、使用される顕著な特徴の数は少なくなければならない。本発明は、適当な珍しさと計算コストとの間の釣り合いをとる幾つかの方法を組み込んでいる。
【００１４】
本発明の用途は、ドキュメントコレクション（ウェブカタログおよびサーチエンジンを含む）内での重複を取り除くこと、要約文を対応するドキュメントの文にマッチさせること、テキストのドキュメントおよび一節における盗作および著作権侵害の検出を含んでいる。
【００１５】
【発明の実施の形態】
図１に示されるように、本発明は、ドキュメントコレクション１００内で複製ドキュメントまたは複製に近いドキュメントを見つけるために利用される。ステップ１１０は、ドキュメントコレクション１００およびドキュメントコレクション１００内の各ドキュメントにおける顕著な特徴を識別する。ループ１１２は、一対のドキュメント毎に繰り返される。ループ１１２内において、ステップ１１４は、一対のドキュメントが少なくとも１つの顕著な特徴を共有しているか否かを判断する。顕著な特徴を共有しているという判断が成されると、一対のドキュメントは、ステップ１１６で比較され、これらが複製ドキュメントもしくは複製に近いドキュメントであるか否かが判断される。その後、ループ１１２は、次の一対のドキュメントに関して続けられる。一対のドキュメントが少なくとも１つの顕著な特徴を共有していない場合には、比較が行なわれず、次の一対のドキュメントに関してループ１１２が続けられる。
【００１６】
図１に示される方法は、たとえば、ドキュメントコレクション内のドキュメントを除去するため、盗作を見破るため、著作権侵害を見つけるため、ドキュメントの出所を判断するため、ドキュメントのコレクションの中からドキュメントの一連のバージョンを集めるため、テキスト分類またはテキスト集積アルゴリズムに複製ドキュメントまたは複製に近いドキュメントのセットを与えるために、電子メールのメッセージとそのメッセージへの応答とをマッチさせるために、あるいは、その逆のために、また、問い合わせシステムと共に使用できるドキュメントインデックスを作成し、たとえ特定の語句（フレーズ）または引用句がドキュメントまたは問い合わせにおいて正確に記録されていなかった場合であっても、問い合わせに応じて特定の語句または引用句を含むドキュメントを効率的に見つけるために、適用できる。
【００１７】
また、図１に示される方法は、ワード数が多い少数の用語と共に１つのワードから成る用語を使用する情報検索アルゴリズムまたはテキスト分類アルゴリズムを増やす場合にも適用することができる。ワードバッグモデル（ｂａｇ−ｏｆ−ｗｏｒｄｓ  ｍｏｄｅｌ）に基づくこの種のアルゴリズムは、各ワードが単独で現われることを想定している。このようなアルゴリズムは、二字で一音を表す二重文字のワードや三重文字のワード等に拡大して適用することができるが、特定の長さを有するｎ重文字の全てのワードを許容すると、コンピュータで迅速に処理することができなくなる。本発明は、ｎ重文字のワードから成る小さなリストを形成して、ワードバッグインデックス（ｂａｇ−ｏｆ−ｗｏｒｄｓ  ｉｎｄｅｘ）を増やすために使用されてもよい。これらのｎ重文字のワードは、ドキュメントを区別する可能性が高い。したがって、これらのｎ重文字のワードは、それらが問い合わせ中に存在する場合、検索結果をかなり狭めるのに役立つ可能性がある。これは、ドキュメントのセットにある程度共通したｎ重文字のワードを生じる共起統計的なワード（ｗｏｒｄ  ｃｏ−ｏｃｃｕｒｒｅｎｃｅ  ｓｔａｔｉｓｔｉｃｓ）に基づく方法とは著しく異なる。
【００１８】
図１に示される方法は、顕著な特徴がドキュメント毎に異なる順序（順位）で現われる場合であっても、ドキュメントが複製または複製に近いか否かを判断するために使用されてもよい。
【００１９】
顕著な特徴は、ドキュメントコレクション１００内で見つけられる顕著なテキストの断片であってもよい。したがって、方法は、テキスト分類方法等の情報検索方法や、ワードの独立性を想定してインデックスのセットに顕著なテキストの断片を加える任意の情報検索方法に適用されてもよい。
【００２０】
顕著なテキストの断片は、ドキュメントコレクション１００内の限られた数のドキュメントに現われる少なくとも２つのワードから成る配列であってもよい。１つの顕著なテキストの断片が他の顕著なテキストの断片中に見出される場合には、最も長い顕著なテキストの断片だけが特徴として見なされてもよい。少なくともユーザ仕様の最小数の回数で、あるいは、ユーザ仕様の最小数の頻度で、少なくとも２つのワードから成る配列をドキュメントが含んでいる場合、少なくとも２つのワードから成る配列がドキュメント中に現われていると見なされてもよい。前記頻度は、ドキュメントの長さによって分けられるドキュメントの発生数として規定されてもよい。
【００２１】
少なくとも２つのワードから成る各配列毎に、識別スコアが演算されてもよく、また、ドキュメントコレクション１００内の少なくとも２つのドキュメントに見出される最も高いスコア配列がテキストの断片として見なされてもよい。識別スコアは、語句（フレーズ）中のワード数の単調関数によって乗じられた語句（フレーズ）を含むドキュメントの数の逆数であってもよい。この場合、単調関数は、語句（フレーズ）中のワード数であってもよい。
【００２２】
少なくとも２つのワードから成る配列を有するドキュメントの数を規制する限定数は、定数または百分率として、ユーザにより選択されてもよい。限定数は、ドキュメントコレクション１００内のドキュメントの数の一次関数として、たとえば、ドキュメントコレクション１００内のドキュメントの数の一次平方関数または一次対数関数として規定されてもよい。
【００２３】
顕著なテキストの断片は、グルーワード（すなわち、ドキュメントのほぼ全てに現われることから、その不存在が目立つワード）を含んでいてもよい。グルーワードは“ｔｈｅ”や“ｏｆ”等のストップワ−ドを含んでおり、このグルーワードにより“Ｕｎｉｔｅｄ  Ｓｔａｔｅｓ  ｏｆ  Ａｍｅｒｉｃａ”といった語句（フレーズ）を顕著な語句（フレーズ）としてカウントすることができる。前記方法は、いずれかの極端に顕著なテキストの断片に現われるグルーワードを排除してもよい。この場合も、少なくともユーザ仕様の最小数の回数で、あるいは、ユーザ仕様の最小数の頻度で、少なくとも２つのワードから成る配列をドキュメントが含んでいる場合、少なくとも２つのワードから成る配列がドキュメント中に現われていると見なされてもよい。前記頻度は、ドキュメントの長さによって分けられるドキュメントの発生数として規定されてもよい。
【００２４】
図２は、ドキュメントコレクション２００内で複製ドキュメントまたは複製に近いドキュメントを見つける本発明の他の実施例を示している。ステップ２１０は、ドキュメントコレクション２００およびドキュメントコレクション２００内の各ドキュメントにおける顕著なドキュメント特徴を識別する。ループ２１２は、一対のドキュメント毎に繰り返される。ループ２１２内において、ステップ２１４は、一対のドキュメントが少なくとも１つの顕著な特徴を共有しているか否かを判断する。顕著な特徴を共有しているという判断が成されると、ステップ２１６は、一対のドキュメントが共有している特徴の数を、各ドキュメントの小さな数の特徴数で割る。ステップ２１８は、ステップ２１６の結果が閾値よりも大きいか否かを判断する。閾値は、定数、ドキュメントコレクション２００内のドキュメントの数の所定のパーセンテージ（百分率）、ドキュメントの数の対数、あるいは、ドキュメントの数の平方根であってもよい。結果が閾値よりも大きい場合、ステップ２２０はドキュメントを複製または複製に近いと判断し、次の一対のドキュメントに関してループ２１２が続けられる。結果が閾値よりも大きくない場合、ドキュメントは、複製ではなくまた、複製に近くもなく、ループ２１２が続けられる。
【００２５】
図３Ａおよび図３Ｂは、ドキュメントコレクション３００内で複製ドキュメントまたは複製に近いドキュメントを見つける本発明の他の実施例を示している。図３Ａで始めると、ステップ３１０は、ドキュメントコレクション３００およびドキュメントコレクション３００内の各ドキュメントにおける顕著なドキュメント特徴を識別する。ステップ３１２はドキュメントインデックス３１４を形成するとともに、ステップ３１６は特徴インデックス３１８を形成する。ドキュメントインデックス３１４は各ドキュメントをそのドキュメント内に含まれる特徴に対してマッピングする。特徴インデックス３１８は、特徴を、その特徴を含むドキュメントに対してマッピングする。インデックス３１４，３１８は、複製を無視する形態で形成される（すなわち、特徴がドキュメント内で繰り返される場合、１回だけ特徴がマッピングされる）。ループ３２０は、各ドキュメント毎に繰り返され、これにより、ステップ３２２は、ステップ３１０で識別された独特の顕著な各特徴を含むリスト３２４を作成することができる。リスト３２４内の顕著な各特徴において、ループ３２６は特徴インデックス３１８毎に繰り返される。これにより、ステップ３２８は、顕著な各特徴および顕著な特徴があるドキュメントを含むリスト３３０を作成することができる。
【００２６】
図３Ｂに示されるように、ループ３３２はリスト３３０にわたって繰り返される。ループ３３２内において、ステップ３３４は、少なくとも１つの特徴を共有する一対のドキュメントおよびドキュメントが共有する特徴の数のリスト３３６を作成する。ループ３３８は、リスト３３６にわたって繰り返される。リスト３３６内の一対のドキュメント毎に、ステップ３４０は、一対のドキュメントが共有する特徴の数を、（ドキュメントインデックス３１４からの）各ドキュメント内の小さい数の特徴数で割る。ステップ３４２は、ステップ３４０の結果が閾値よりも大きいか否かを判断する。閾値は、たとえば、定数、ドキュメントコレクション３００内のドキュメントの数の所定のパーセンテージ（百分率）、ドキュメントの数の対数、あるいは、ドキュメントの数の平方根であってもよい。結果が閾値よりも大きい場合、ステップ３４４はドキュメントを複製または複製に近いと判断し、次の一対のドキュメントに関してループ３３８が続けられる。結果が閾値よりも大きくない場合、ドキュメントは、複製ではなくまた、複製に近くもなく、ループ３３８が続けられる。
【００２７】
図３Ｃは、ドキュメントインデックス３１４のためのフォーマットの一例を示している。同様に、図３Ｄは特徴インデックス３１８のためのフォーマットの一例を示し、図３Ｅはリスト３２４のためのフォーマットの一例を示し、図３Ｆはリスト３３０のためのフォーマットの一例を示し、図３Ｇは２段階で構成されるリスト３３６のためのフォーマットの一例を示している。
【００２８】
図４に示されるように、本発明に係る方法は、テキストスパンコレクション４００内で複製または複製に近い文（センテンス）を含むテキストスパン（テキスト長さ）を見つけるために利用される。コレクション４００内のテキストスパンは、文であってもよい。ステップ４１０は、テキストスパンコレクション４００およびテキストスパンコレクション４００内の各テキストスパンにおける顕著なテキストスパン特徴を識別する。ループ４１２は、一対のテキストスパン毎に繰り返される。ループ４１２内において、ステップ４１４は、一対のテキストスパンが少なくとも１つの顕著な特徴を共有しているか否かを判断する。顕著な特徴を共有しているという判断が成されると、一対のテキストスパンがステップ４１６で比較され、これらのテキストスパンが複製または複製に近いテキストスパンか否かが判断される。その後、ループ４１２は、次の一対のテキストスパンに関して続けられる。一対のテキストスパンが少なくとも１つの顕著な特徴を共有していない場合には、比較が行なわれず、次の一対のテキストスパンに関してループ４１２が続けられる。
【００２９】
この方法は、一方のドキュメントからの文を他方のドキュメントからの文とマッチさせるために使用されてもよい。これは、オリジナルドキュメントに関して人が書いた要約文をオリジナルドキュメントからの文とマッチさせる場合に役立つ。同様に、盗作検出においては、ドキュメントも適用された方法が複製のドキュメントを見つけた場合、文のバージョンを使用して、盗作されたコピーの文をオリジナルドキュメントからの対応する文とマッチさせることができる。文のマッチングにおける他の用途においては、ワード処理アプリケーションにおいてドキュメントに成された変更が識別される。ワード処理アプリケーションにおいて、そのような変更は、文、行、他のテキストの断片をオリジナルの状態に保持する必要はない。
【００３０】
図５に示されるように、本発明は、画像コレクション５００内で複製または複製に近い画像を見つけるために利用される。ステップ５１０は、画像コレクション５００および画像コレクション５００内の各画像における顕著な画像特徴を識別する。顕著な特徴は、画像からの少なくとも２つの隣接するタイトルの配列であってもよい。ループ５１２は、一対の画像毎に繰り返される。ループ５１２内において、ステップ５１４は、一対の画像が少なくとも１つの顕著な特徴を共有しているか否かを判断する。顕著な特徴を共有しているという判断が成されると、一対の画像がステップ５１６で比較され、これらの画像が複製または複製に近い画像か否かが判断される。その後、ループ５１２は、次の一対の画像に関して続けられる。一対の画像が少なくとも１つの顕著な特徴を共有していない場合には、比較が行なわれず、次の一対の画像に関してループ５１２が続けられる。
【００３１】
図５に示される方法に係る本発明の好ましい実施例において、この方法は、画像を白および黒に変換するとともに画像を複数の解像度でサンプリングすることにより、画像の正規化を行なう。テキストに適用された方法と比べると、僅かに重なり合うタイトルがワードに対応し、水平および垂直な配列がテキストの断片に対応する。
【００３２】
図５に示される方法は、オリジナル画像が電子透かしを有さない画像内容に基づいて著作権侵害を見つけるために適用されてもよい。また、この方法は、他の用途もあるが、指紋による識別や、手書きのサインの認証に適用されてもよい。
【００３３】
また、本発明は、大きなドキュメントのコレクション内で複製または複製に近いドキュメントを識別できる装置を含んでいる。この装置は、最初にドキュメントのコレクション内に含まれる顕著な特徴を選択する手段と、その後に各ドキュメントに含まれる顕著な特徴を識別する手段と、少なくとも１つの顕著な特徴を共有する一対のドキュメントのそれぞれの顕著な特徴を比較して、ドキュメントが複製または複製に近いドキュメントであるか否かを判断する手段とを有している。
【００３４】
図６は、本発明の方法を可能にする本発明の装置の実施例を示している。コンピュータシステム６００は、方法を可能にするために使用される。コンピュータシステム６００は、ディスプレイユニット６１０と入力装置６１２とを有している。入力装置６１２は、ユーザ入力を受けることができる装置であればどのようなものであってもよく、たとえばキーボードやスキャナであってもよい。また、コンピュータシステム６００は、ドキュメントコレクションを記憶するための記憶装置６１４と、本発明に係る方法を記憶するための記憶装置６１６とを有している。プロセッサ６１８は、記憶装置６１６に記憶された方法を実行するとともに、記憶装置６１４に記憶されたドキュメントコレクションにアクセスする。また、プロセッサは、ディスプレイユニット６１０に情報を送ることができるとともに、入力装置６１２から情報を受けることができる。これらに限定されないが、デスクトップシステム、ラップトップシステム、あるいは、任意のネットワークシステムを含む、本発明に係る方法を可能にする様々なソフトウエア要素およびハードウエア要素を有する任意のタイプのコンピュータシステムを使用してもよい。
【００３５】
図３Ａおよび図３Ｂに示される方法にしたがって本発明を実施した。実施において、ＤＦ（ｘ）はテキスト“ｘ”を含むドキュメントの数、Ｎはドキュメントの総数、ＲはＤＦに関する閾値であった。Ｒが取り得る選択には、定数、Ｎの所定のパーセンテージ（たとえば５％）、Ｎの対数、Ｎの平方根が含まれていた。
全てのドキュメントにわたる最初の関門では、ワードを小文字に変換してワードの先頭と末尾から句読点を除去した後、ドキュメント中の全てのワードに関してＤＦ（ｘ）が計算された。ドキュメント内でのワードの頻度がユーザ仕様の閾値を下回る場合には、選択的に、特定のドキュメント内のワードをＤＦ（ｘ）に寄与しないように規制してもよい。
【００３６】
第２の関門では、顕著な特徴すなわち語句（フレーズ）が集められた。語句は、２個以上で且つＲ個を越えない数（１＜ＤＦ（ｘ）＜Ｒ）のドキュメント中に現われる少なくとも２つのワードから成っていた。また、語句は、少なくとも（Ｎ−Ｒ）個のドキュメント中に現われるグルーワードも含んでいた。グルーワードは、１つの語句中に現われるが、語句の最も左側の位置または最も右側の位置には現われない。基本的に、ドキュメントは中間の珍しいワードで分割され（Ｒ＜ＤＦ（ｘ）＜Ｒ−Ｎ）、残されたものが顕著な語句と見なされる。また、選択的に、語句をグルーワードで分割して、別個の顕著なサブフレーズ（代わりの語句）を得てもよい。たとえば、“Ｕｎｉｔｅｄ  Ｓｔａｔｅｓ  ｏｆ  Ａｍｅｒｉｃａ”を“ｏｆ”で分割すると、“Ｕｎｉｔｅｄ  Ｓｔａｔｅｓ”が生じる。また、第２の関門では、ドキュメント識別子およびフレーズ識別子を使用して、各ドキュメントをその顕著なフレーズ（語句）およびサブフレーズのセットにマッピングするドキュメントインデックスが形成された。また、フレーズ識別子およびドキュメント識別子を使用して、フレーズからフレーズを含むドキュメントへとマッピングするフレーズインデックスが形成された。
【００３７】
ＤＦが低い１つのワードとは異なり、フレーズ（語句）は、たまたま同じ語彙を使用したドキュメントを区別することができる十分な長さを有していたが、複製のドキュメント間で共通となるにはあまりにも短かった。
【００３８】
第３の関門は、ドキュメントインデックスのドキュメント識別子にわたって繰り返された（インデックスが形成されても、実際のドキュメントを使用する必要はない）。各ドキュメント識別子毎に、ドキュメントインデックスを使用して、フレーズ識別子のリストを集めた。各フレーズ識別子毎に、フレーズインデックスから得られたドキュメント識別子が繰り返され、各ドキュメント識別子が現われた回数の総数がカウントされた。したがって、各ドキュメント識別子毎に、少なくとも１つのフレーズ（語句）でドキュメントと重なり合うドキュメントおよび重なり合うフレーズの数のリストが集められた。ドキュメント識別子から成るこのリストは、ソースドキュメントを他の全てのドキュメントと比較する必要性を無くすため、ソースドキュメントと共通する少なくとも１つのフレーズ（語句）を有するドキュメントのみを含んでいた。一対のドキュメント毎に、共通のフレーズの数を各ドキュメント内の少数のフレーズ数で割ることにより、重なり率が演算された。これにより、長いドキュメントから引用される小さな一節を検出することができた。重なり率をマッチパーセント閾値と比較した。重なり率がこの閾値を越えている場合、一対のドキュメントは、複製に近い可能性があるとして記録された。選択的に、結果が現状のまま受け入れられてもよく、あるいは、より詳細にわたる比較アルゴリズムを、複製に近いドキュメント対に適用してもよい。
【００３９】
どちらかと言えば、この実施が好ましい。なぜなら、ドキュメントへの変更が僅かであれば、方法の有効性に影響を与えないからである。オリジナルドキュメントの証拠となるサインが何かしら残っている場合、そのようなサインをこの方法で見つけることができる。また、複製のドキュメント中に同じ状態で顕著なフレーズが現われる必要はない。
【００４０】
また、この実施は非常に有効である。最初の２つの関門は、Ｎにおいてリニアである。第３の関門はＮ＊Ｐ回行なわれる。ここで、Ｐは、少なくとも１つのフレーズで重なり合うドキュメントの数の平均である。最悪の場合、ＰがＮであるが、一般的に、ＰはＲである。なお、Ｒが増えるにつれて、精度も増すが、実行時間も増える。しかしながら、実際に、許容できるレベルの精度は、Ｎにおいてリニアである実行時間において達成される。これは、全てのドキュメントの対での比較あるいは少なくともＮ乗実行時間を必要とするアルゴリズムにおいて、著しい向上である。
【００４１】
この実施は、１２５個の新聞記事およびこれらの対応する手書きの要約において、すなわち、２５０個のドキュメントに関して実行された。複製に近いとして識別された一対のドキュメントのそれぞれにおいて、その対が記事とその要約とから成っている場合には、対が正しい相手（マッチ）としてカウントされた。あるいは、対が誤った相手（マッチ）としてカウントされた。実験の目的で、ドキュメントおよびそれ自体から成る対を除去した。なぜなら、実施によって任意のドキュメントとそれ自体とをうまくマッチさせることができるためである。最小の重なり閾値２５％およびＤＦ閾値５％を使用して、方法は、２５０個の全てのドキュメントを１３秒で処理するとともに、２５０個のドキュメントのうちの２３２個を対応する要約すなわち記事と正確に間違えることなくマッチさせることができた。このことは、１００％の正確さ（精度）、９２．８％のリコール（カバレージ）、９６．３％のＦ１スコア（正確さおよびリコールの調和平均）を示している。結果を検討すると、アルゴリズムが一致（マッチ）を見出さなかった全ての場合において、最も高いランキングのドキュメントは、閾値を下回ったが、正しいマッチであることが分かった。
【００４２】
実施は、頻度が低いワードおよびグルーワードに関して、様々な閾値を使用してもよい。配列それ自体が低いＤＦを有している中程度のＤＦワードの配列が含まれてもよい。また、珍しさの他、フレーズの複雑度の尺度として、フレーズ中のワードの数が考慮に入れられてもよい。この場合、たとえば、フレーズの長さをフレーズのＤＦで割る（ＴＬ／ＤＦまたはｌｏｇ（ＴＬ）／ＤＦ）。これは長いフレーズのための優先権を生じるが、これによって、長いフレーズは、高いＤＦを有することができ、したがって、顕著性が低下する。
【００４３】
当業者であれば分かるように、以上の説明は、本発明の詳細な好ましい実施例を示しており、本発明の思想および範囲から逸脱することなく、これらの実施例に修正、付加、変更を成すことができる。したがって、本発明を詳細に説明するため、また、特許法で特に必要とされるため、特許証による保護を望むものを特許請求の範囲に記載する。
【図面の簡単な説明】
【図１】
ドキュメントに適用される本発明に係る方法の第１の実施例のフローチャートである。
【図２】
ドキュメントに適用される本発明に係る方法の第２の実施例のフローチャートである。
【図３Ａ】
ドキュメントに適用される本発明に係る方法の第３の実施例のフローチャートである。
【図３Ｂ】
ドキュメントに適用される本発明に係る方法の第３の実施例のフローチャートである。
【図３Ｃ】
ドキュメントインデックスを示す図である。
【図３Ｄ】
特徴インデックスを示す図である。
【図３Ｅ】
リスト３２４を示す図である。
【図３Ｆ】
リスト３３０を示す図である。
【図３Ｇ】
リスト３３６を示す図である。
【図４】
テキストスパンに適用される本発明に係る方法の実施例のフローチャートである。
【図５】
画像に適用される本発明に係る方法の実施例のフローチャートである。
【図６】
本発明に係る装置を示す図である。
【図１】
2004519761.tif 000003
【図２】
2004519761.tif 000004
【図３Ａ】
2004519761.tif 000005
【図３Ｂ】
2004519761.tif 000006
【図３Ｃ】
2004519761.tif 000007
【図３Ｄ】
2004519761.tif 000008
【図３Ｅ】
2004519761.tif 000009
【図３Ｆ】
2004519761.tif 000010
【図３Ｇ】
2004519761.tif 000011
【図４】
2004519761.tif 000012
【図５】
2004519761.tif 000013
【図６】
2004519761.tif 000014
【国際公開パンフレット】
2004519761.tif 000015
2004519761.tif 000016
2004519761.tif 000017
2004519761.tif 000018
2004519761.tif 000019
2004519761.tif 000020
2004519761.tif 000021
2004519761.tif 000022
2004519761.tif 000023
2004519761.tif 000024
2004519761.tif 000025
2004519761.tif 000026
2004519761.tif 000027
2004519761.tif 000028
2004519761.tif 000029
2004519761.tif 000030
2004519761.tif 000031
2004519761.tif 000032
2004519761.tif 000033
2004519761.tif 000034
2004519761.tif 000035
2004519761.tif 000036
2004519761.tif 000037
2004519761.tif 000038
2004519761.tif 000039
2004519761.tif 000040
2004519761.tif 000041
2004519761.tif 000042
2004519761.tif 000043
【国際調査報告】
2004519761.tif 000044
2004519761.tif 000045