(57)【特許請求の範囲】
【請求項１】
Ｗｅｂクローリング中に発見されたＷｅｂページのＵＲＬとコンテンツを受け取り、前記ＵＲＬから取り出したサイト名およびパス名と、前記コンテンツから算出したコンテンツ特徴量とを対応付けてＷｅｂページ状態情報として記憶部に記憶させるとともに、前記コンテンツ特徴量と前記パス名の組が一致するサイト名の集合を前記コンテンツ特徴量および前記パス名と対応付けて重複Ｗｅｂサイト候補情報として前記記憶部に記憶させる受付手段と、
前記サイト名の集合に含まれるそれぞれのサイト名について、各サイト名に対応する全てのパス名とコンテンツ特徴量から、複数のサイト名に対して１つのコンテンツ特徴量のみを有するパス名の数（ヒット数）と、複数のサイト名に対して複数のコンテンツ特徴量を有するパス名の数（ミス数）を求め、前記ヒット数および前記ミス数が所定範囲にある場合に前記サイト名の集合を重複Ｗｅｂサイト集合として検出する判定手段と
を備え、
前記受付手段は、サイト名と、同一のサイト名を有する異なるパス名の数に相当するパス数と、前記パス数としてカウントされたパス名の中で、パス名とコンテンツ特徴量との組と同一の組合せが、異なるサイト名に存在するパス名の数に相当する重複パス数とを対応づけてＷｅｂサイト状態情報として前記記憶部にさらに記憶させ、
前記判定手段は、前記サイト名の集合に含まれるそれぞれのサイト名に対応する前記パス数と、前記重複パス数に対する前記パス数の比とがともに所定範囲にある場合に前記重複Ｗｅｂサイト集合の検出を行う
ことを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項２】
請求項１に記載の重複Ｗｅｂサイト動的検出装置において、
前記判定手段は、検出した前記重複Ｗｅｂサイト集合に含まれる１つのサイト名を正規サイト名として選択し、残りのサイト名と前記正規サイト名とを対応付けてＷｅｂサイト名関連情報として前記記憶部にさらに記憶させ、
Ｗｅｂクローリング中に発見されたＷｅｂページのサイト名を受け取り、前記サイト名に対応付けられた正規サイト名が前記記憶部内の前記Ｗｅｂサイト名関連情報に記憶されている場合には、前記サイト名に対応する前記正規サイト名を出力する問合せ手段をさらに備える
ことを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項３】
請求項２に記載の重複Ｗｅｂサイト動的検出装置において、
前記判定手段は、前記重複Ｗｅｂサイト集合を検出する前処理として、前記サイト名の集合に含まれるそれぞれのサイト名に対応する正規サイト名が前記記憶部内の前記Ｗｅｂサイト名関連情報に記憶されている場合には、前記正規サイト名に対応するサイト名を前記サイト名の集合の中から取り除くことを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項４】
請求項２または３に記載の重複Ｗｅｂサイト動的検出装置において、
前記判定手段は、サイト名の文字列パターンおよびドメインレベル数によりあらかじめ規定されたスコア計算式に応じて、前記重複Ｗｅｂサイト集合に含まれるサイト名の中から最もスコアの高いサイト名を正規サイト名として選択することを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項５】
請求項１ないし４のいずれか１項に記載の重複Ｗｅｂサイト動的検出装置において、
前記判定手段は、全てのサイト名の数の所定割合以上である複数のサイト名に対して１つのコンテンツ特徴量のみを有するパス名の数をヒット数として数えることを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項６】
請求項１ないし５のいずれか１項に記載の重複Ｗｅｂサイト動的検出装置において、
前記受付手段は、受け取ったコンテンツデータに一方向性ハッシュ関数を適用することにより前記コンテンツ特徴量を算出することを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項７】
請求項１ないし５のいずれか１項に記載の重複Ｗｅｂサイト動的検出装置において、
前記受付手段は、受け取ったコンテンツデータからＨＴＭＬタグ、ＨＴＭＬコメント、スクリプト、およびスタイルを取り除いた残りのデータに一方向性ハッシュ関数を適用することにより前記コンテンツ特徴量を算出することを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項８】
請求項１に記載の重複Ｗｅｂサイト動的検出装置において、
前記受付手段は、パス名が所定の文字列パターンに合致しない場合には、前記重複Ｗｅｂサイト候補情報として前記記憶部に記憶させず、前記パス名を前記パス数および前記重複パス数のカウント対象から除外することを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項９】
請求項１に記載の重複Ｗｅｂサイト動的検出装置において、
前記受付手段は、Ｗｅｂクローリング中に発見されたＷｅｂページのサイト名が、パス数が所定の値に達している特定のサイト名と一致する場合には、前記重複Ｗｅｂサイト候補情報に含まれる前記サイト名の集合の要素として前記特定のサイト名と一致する前記サイト名を記憶させず、前記Ｗｅｂクローリング中に発見されたＷｅｂページのサイト名に対応するパス名を前記パス数および前記重複パス数のカウント対象から除外することを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項１０】
請求項１ないし９のいずれか１項に記載の重複Ｗｅｂサイト動的検出装置において、
前記判定手段は、前記サイト名の集合に含まれるそれぞれのサイト名について、各サイト名を構成要素に分割することによりそれぞれのサイト名の類似度を判定し、前記サイト名の集合の中に前記類似度が所定値以上となるサイト名が含まれていると判定した場合には、前記重複Ｗｅｂサイト集合を検出する際の前記ヒット数および前記ミス数に対する所定範囲を変更し、前記類似度の高いサイト名を重複Ｗｅｂサイトとして検出しやすくすることを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項１１】
請求項１ないし１０のいずれか１項に記載の重複Ｗｅｂサイト動的検出装置において、
前記受付手段は、受け取ったＵＲＬからサイト名およびパス名を取り出した際に、前記サイト名に前記パス名の上位ディレクトリ名を連結した擬似的なサイト名と、前記パス名において前記上位ディレクトリ名が連結されていない残りの部分からなる擬似的なパス名とを生成し、前記擬似的なサイト名および前記擬似的なパス名をそれぞれサイト名およびパス名に含めて扱うことを特徴とする重複Ｗｅｂサイト動的検出装置。
【請求項１２】
請求項１ないし１１のいずれか１項に記載の重複Ｗｅｂサイト動的検出装置において、
前記判定手段は、重複Ｗｅｂサイト集合として検出されなかったサイト名の集合について求めたヒット数が、第２の所定範囲内にある場合には、前記サイト名の集合に含まれるパス名を除外パス名として前記記憶部に記憶させ、Ｗｅｂクローリング中に発見されたＷｅｂページのパス名が前記除外パス名として記憶されているパス名と一致する場合には、前記パス名を重複Ｗｅｂサイト検出の際に参照しないことを特徴とする重複Ｗｅｂサイト動的検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｗｅｂサイトの重複性判定をＷｅｂクローリングに追随して動的に行う重複Ｗｅｂサイト動的検出装置に関する。
【背景技術】
【０００２】
重複Ｗｅｂサイト（ミラーサイト）とは、ＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）のサイト名（ホスト名）部分だけが異なり、同一内容を持つＷｅｂページを提供するＷｅｂサイトの集合である。重複Ｗｅｂサイトが生じる原因は、負荷分散やバックアップを目的とした物理的なコピー、あるいは検索エンジンでのランキングを向上させるためにＤＮＳ（Ｄｏｍａｉｎ  Ｎａｍｅ  Ｓｙｓｔｅｍ）へのホスト名の多重登録を行って論理的に多数のサイトに見せかける行為など、様々である。
【０００３】
重複Ｗｅｂサイトを検出することで、検索エンジンの結果から重複を減らし、Ｗｅｂクローリングによる情報収集の効率、およびプロキシサーバやブラウザにおけるキャッシュヒット率を向上させることが期待される。
【０００４】
従来の重複Ｗｅｂサイト検出装置では、Ｗｅｂクローリングにより収集されたＷｅｂページの集合を一括して分析し、ＵＲＬ文字列のパス名部分とＷｅｂページコンテンツのハッシュ値の共通性とに基づいて、２つ以上の複数サイトが重複Ｗｅｂサイトか否かを判定しているものがある（例えば、特許文献１参照）。
【０００５】
また、ＵＲＬ文字列の類似性、ＩＰアドレスの類似性、およびリンク先ＵＲＬの共通性などを一括して分析し、それらの指標が基準値より高い場合には、２つのサイトが重複Ｗｅｂサイトであると判定するものがある（例えば、特許文献２参照）。
【０００６】
【特許文献１】特開２００６−２１５７３５号公報
【特許文献２】特開２００４−２６４９２６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術には次のような課題がある。
従来の重複Ｗｅｂサイト検出方法は、各Ｗｅｂページの情報が一括して与えられることを前提としており、Ｗｅｂクローリング中に発見した未知のＷｅｂサイトが重複Ｗｅｂサイトであるか否かを即座に判断できない。そのため、当該サイトが重複Ｗｅｂサイトであった場合には、他のＷｅｂサイトと同一内容のＷｅｂページを多数取得することになり、Ｗｅｂクローリングの効率低下を招くとともに、収集結果の統計的性質が現実から乖離してしまう。
【０００８】
これに対して、新たに発見したＷｅｂサイトからのＷｅｂページ取得を少数に留めておき、Ｗｅｂクローリングを一度打ち切って重複Ｗｅｂサイト検出を実行する方法も考えられる。しかし、重複Ｗｅｂサイト検出は、Ｗｅｂページ情報全体の分析を必要とするため、実行時間（すなわち、Ｗｅｂクローリングの停止時間）が長くなり、急速に変化するＷｅｂ情報をタイムリに捉えることが困難になってしまう。
【０００９】
本発明は上述のような課題を解決するためになされたもので、Ｗｅｂサイトの重複性判定をＷｅｂクローリングに追随して動的に行い、Ｗｅｂ情報の効率的な収集と不要情報の除去を可能にする重複Ｗｅｂサイト動的検出装置を得ることを目的とする。
【課題を解決するための手段】
【００１０】
本発明に係る重複Ｗｅｂサイト動的検出装置は、Ｗｅｂクローリング中に発見されたＷｅｂページのＵＲＬとコンテンツを受け取り、ＵＲＬから取り出したサイト名およびパス名と、コンテンツから算出したコンテンツ特徴量とを対応付けてＷｅｂページ状態情報として記憶部に記憶させるとともに、コンテンツ特徴量とパス名の組が一致するサイト名の集合をコンテンツ特徴量およびパス名と対応付けて重複Ｗｅｂサイト候補情報として記憶部に記憶させる受付手段と、サイト名の集合に含まれるそれぞれのサイト名について、各サイト名に対応する全てのパス名とコンテンツ特徴量から、複数のサイト名に対して１つのコンテンツ特徴量のみを有するパス名の数（ヒット数）と、複数のサイト名に対して複数のコンテンツ特徴量を有するパス名の数（ミス数）を求め、ヒット数およびミス数が所定範囲にある場合にサイト名の集合を重複Ｗｅｂサイト集合として検出する判定手段とを備え、受付手段は、サイト名と、同一のサイト名を有する異なるパス名の数に相当するパス数と、パス数としてカウントされたパス名の中で、パス名とコンテンツ特徴量との組と同一の組合せが、異なるサイト名に存在するパス名の数に相当する重複パス数とを対応づけてＷｅｂサイト状態情報として記憶部にさらに記憶させ、判定手段は、サイト名の集合に含まれるそれぞれのサイト名に対応するパス数と、重複パス数に対するパス数の比とがともに所定範囲にある場合に重複Ｗｅｂサイト集合の検出を行うものである。
【発明の効果】
【００１１】
本発明によれば、コンテンツ特徴量とパス名の組が一致するサイト名の集合をコンテンツ特徴量およびパス名と対応付けた重複Ｗｅｂサイト候補情報を維持して重複Ｗｅｂサイトの可能性があるサイト集合を随時把握できるようにするとともに、コンテンツ特徴量とパス名との対応関係に基づいて重複判定を行うことにより、Ｗｅｂサイトの重複性判定をＷｅｂクローリングに追随して動的に行い、Ｗｅｂ情報の効率的な収集と不要情報の除去を可能にする重複Ｗｅｂサイト動的検出装置を得ることができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の重複Ｗｅｂサイト動的検出装置の好適な実施の形態につき図面を用いて説明する。
【００１３】
実施の形態１．
図１は、本発明の実施の形態１における重複Ｗｅｂサイト動的検出装置の構成図である。本実施の形態１における重複Ｗｅｂサイト動的検出装置は、受付手段１、記憶部２、判定手段６、および問合せ手段７で構成される。
【００１４】
さらに、記憶部２は、Ｗｅｂページ状態情報３、重複Ｗｅｂサイト候補情報４、およびＷｅｂサイト状態情報５が格納されている。また、このように構成された重複Ｗｅｂサイト動的検出装置は、Ｗｅｂクローラ８と接続される。
【００１５】
まず始めに、各構成要素の機能について説明する。
受付手段１は、Ｗｅｂクローラ８からＷｅｂページのＵＲＬとコンテンツを受け取り、記憶部２に格納されたＷｅｂページ状態情報３、重複Ｗｅｂサイト候補情報４、およびＷｅｂサイト状態情報５を更新する。また、受付手段１は、Ｗｅｂサイト状態情報５が一定の条件を満たす場合には、Ｗｅｂサイト名の集合を渡すことにより、判定手段６の動作を起動する。
【００１６】
判定手段６は、受付手段１からＷｅｂサイト名の集合を受け取り、記憶部２に格納されたＷｅｂページ状態情報３を参照して、当該Ｗｅｂサイト集合が重複Ｗｅｂサイトであるか否かを判定する。そして、判定手段６は、当該Ｗｅｂサイト集合が重複Ｗｅｂサイトであると判定した場合には、記憶部２に格納されたＷｅｂサイト状態情報５を更新する。
【００１７】
問合せ手段７は、Ｗｅｂクローラ８からＷｅｂサイト名を受け取り、記憶部２に格納されたＷｅｂサイト状態情報５を参照して、当該Ｗｅｂサイト名が重複Ｗｅｂサイトの別名（非正規名）である場合には、正規名に変換し、変換後の正規のＷｅｂサイト名をＷｅｂクローラ８に返す。
【００１８】
次に、図２〜図４を用いて、記憶部２内に格納されている各種情報について説明する。
図２は、本発明の実施の形態１における記憶部２に格納されたＷｅｂページ状態情報３の詳細を示した図である。Ｗｅｂページ状態情報３は、サイト名３１、パス名３２、およびコンテンツハッシュ値３３で構成される。サイト名３１およびパス名３２は、ＵＲＬ文字列のサイト名（ホスト名）部分およびパス名部分をそれぞれ表す。
【００１９】
Ｗｅｂページ状態情報３の各エントリは、Ｗｅｂページと１対１に対応しており、ＷｅｂページのＵＲＬに対応するサイト名３１およびパス名３２の組で一意に識別される。Ｗｅｂクローラ８から同一ＵＲＬのＷｅｂページを複数回受け取った際には、同一エントリがこのＷｅｂページ状態情報３に上書きされる。
【００２０】
また、Ｗｅｂページ状態情報３は、サイト名３１が指定した値を持つ複数エントリを効率的に検索できるように構成されているものとする。このためには、例えば、公知のＢ−ｔｒｅｅを用いて、各エントリをサイト名３１とパス名３２の組に基づいて整列された状態で維持すればよい。
【００２１】
コンテンツハッシュ値３３は、Ｗｅｂページのコンテンツデータ全体にハッシュ関数を適用した結果の値である。ここで用いるハッシュ関数には、異なるコンテンツデータに対して同一のハッシュ値が対応する確率が実用上無視できるほど低いものが適しており、例えば、公知のＭＤ５やＳＨＡ−１などを用いることができる。
【００２２】
次に、図３は、本発明の実施の形態１における記憶部２に格納された重複Ｗｅｂサイト候補情報４の詳細を示した図である。重複Ｗｅｂサイト候補情報４は、コンテンツハッシュ値４１、パス名４２、および候補サイト集合４３で構成される。重複Ｗｅｂサイト候補情報４の各エントリは、コンテンツハッシュ値４１およびパス名４２の組で一意に識別される。
【００２３】
図３に示した重複Ｗｅｂサイト候補情報４は、先の図２に示したコンテンツハッシュ値３３とパス名３２の組に基づいてＷｅｂページ状態情報３のエントリを並べ替え、それぞれコンテンツハッシュ値４１およびパス名４２とする。さらに、図３に示した重複Ｗｅｂサイト候補情報４は、先の図２において同一のコンテンツハッシュ値３３とパス名３２の組を持つ複数エントリのサイト名３１をまとめて、候補サイト集合４３に格納している。
【００２４】
次に、図４は、本発明の実施の形態１における記憶部２に格納されたＷｅｂサイト状態情報５の詳細を示した図である。Ｗｅｂサイト状態情報５は、サイト名５１、パス数５２、重複パス数５３、および正規名５４で構成される。Ｗｅｂサイト状態情報５の各エントリは、サイト名５１で一意に識別される。パス数５２は、先の図２におけるＷｅｂページ状態情報３のエントリの中のサイト名３１が、図４におけるサイト名５１と一致するものの数であり、当該Ｗｅｂサイトから取得したＷｅｂページ数を表す。
【００２５】
また、重複パス数５３は、先の図２におけるＷｅｂページ状態情報３のエントリの中のサイト名３１が、図４におけるサイト名５１と一致し、かつ、先の図２におけるパス名３２とコンテンツハッシュ値３３の組が、Ｗｅｂページ状態情報３全体で一意でないものの数である。すなわち、この重複パス数５３は、パス数としてカウントされたパス名の中で、パス名とコンテンツハッシュ値との組と同一の組合せが、異なるサイト名に存在するパス名の数に相当し、重複Ｗｅｂサイト候補情報４のエントリの内、候補サイト集合４３がサイト名５１を含み、かつサイト名５１と異なるサイト名を１つ以上含むものの数と等しい。
【００２６】
正規名５４には、重複Ｗｅｂサイト集合に属するＷｅｂサイトにおいて、重複Ｗｅｂサイト集合の代表元のサイト名が設定される。代表元Ｗｅｂサイト自体、あるいは重複Ｗｅｂサイト集合に属さないＷｅｂサイトにおいては、正規名５４は空文字列である。
【００２７】
なお、符号１〜７で示された各手段および各情報は、ＣＰＵ、メモリ、磁気ディスク装置、および通信インタフェースを備えた一般的なコンピュータで実現することができる。この場合、受付手段１、判定手段６、および問合せ手段７は、ＣＰＵに実行させるプログラムとして実現し、記憶部２は、磁気ディスク装置として実現する。
【００２８】
次に、フローチャートを用いて、各手段の一連の動作について説明する。
まず始めに、受付手段１の動作を説明する。図５は、本発明の実施の形態１における受付手段１の動作の詳細を示すフローチャートである。まず、ステップＳ５１において、受付手段１は、Ｗｅｂクローラ８からＷｅｂページのＵＲＬ文字列とコンテンツデータを受け取り、ＵＲＬ文字列からサイト名とパス名を切り出して、それぞれ入力サイト名および入力パス名とする。さらに、受付手段１は、コンテンツデータ全体にハッシュ関数を適用してハッシュ値に変換し、入力コンテンツハッシュ値を生成する。
【００２９】
次に、ステップＳ５２において、受付手段１は、入力サイト名に対応するＷｅｂサイト状態情報５のエントリが存在するか否かを調べる。そして、存在しない場合には、受付手段１は、Ｗｅｂサイト状態情報５に新たなエントリを挿入し、サイト名５１を入力サイト名に、パス数５２および重複パス数５３を０に、正規名５４を空文字列にそれぞれ設定する。
【００３０】
次に、ステップＳ５３において、受付手段１は、入力サイト名および入力パス名に対応するＷｅｂページ状態情報３のエントリが存在するか否かを調べる。そして、存在する場合には、ステップＳ５４に進み、存在しない場合には、ステップＳ５５に進む。
【００３１】
ステップＳ５４に進んだ場合には、受付手段１は、入力サイト名および入力パス名に対応するＷｅｂページ状態情報３のエントリにおけるコンテンツハッシュ値３３の値を入力コンテンツハッシュ値と比較する。そして、両者が一致する場合には、動作を終了し、一致しない場合には、ステップＳ５６に進む。
【００３２】
一方、先のステップＳ５３の判断によりステップＳ５５に進んだ場合には、受付手段１は、Ｗｅｂページ状態情報３に新たなエントリを挿入し、サイト名３１、パス名３２、およびコンテンツハッシュ値３３をそれぞれ入力サイト名、入力パス名、および入力コンテンツハッシュ値に設定する。さらに、受付手段１は、入力サイト名に対応するＷｅｂサイト状態情報５のエントリにおいて、パス数５２の値に１を加え、その後、ステップＳ５８に進む。
【００３３】
先のステップＳ５４の判断によりステップＳ５６に進んだ場合には、受付手段１は、Ｗｅｂページ状態情報３の既存エントリのコンテンツハッシュ値３３に対して、後述するコンテンツハッシュ値削除処理を実行する。さらに、続くステップＳ５７において、受付手段１は、当該エントリのコンテンツハッシュ値３３に入力コンテンツハッシュ値を設定することにより更新した後、ステップＳ５８に進む。
【００３４】
次に、ステップＳ５８において、受付手段１は、入力サイト名、入力パス名、および入力コンテンツハッシュ値に対して、後述するコンテンツハッシュ値挿入処理を実行し、動作を終了する。
【００３５】
次に、先の図５のステップＳ５６におけるコンテンツハッシュ値削除処理の詳細な動作を説明する。図６は、本発明の実施の形態１におけるコンテンツハッシュ値削除処理の動作の詳細を示すフローチャートである。
【００３６】
まず、ステップＳ６１において、受付手段１は、削除対象コンテンツハッシュ値および削除対象パス名（入力パス名に等しい）に対応する重複Ｗｅｂサイト候補情報４のエントリを検索し、当該エントリの候補サイト集合４３に含まれる要素サイト数に応じて条件分岐する。要素サイト数が１に等しければ、ステップＳ６２に、要素サイト数が２に等しければステップＳ６３に、それ以外の場合にはステップＳ６４にそれぞれ進む。
【００３７】
先のステップＳ６１の判断によりステップＳ６２に進んだ場合には、受付手段１は、ステップＳ６１で検索したエントリを重複Ｗｅｂサイト候補情報４から削除し、終了する。
【００３８】
また、先のステップＳ６１の判断によりステップＳ６３に進んだ場合には、受付手段１は、ステップＳ６１で検索したエントリの候補サイト集合４３に格納された２つのサイト名に対し、それぞれに対応するＷｅｂサイト状態情報５のエントリの重複パス数５３を１減少させ、ステップＳ６５に進む。
【００３９】
また、先のステップＳ６１の判断によりステップＳ６４に進んだ場合には、受付手段１は、削除対象サイト名（入力サイト名に等しい）に対応するＷｅｂサイト状態情報５のエントリの重複パス数５３を１減少させ、ステップＳ６５に進む。
【００４０】
そして、ステップＳ６５において、受付手段１は、先のステップＳ６１で検索したエントリの候補サイト集合４３から削除対象サイト名を取り除き、終了する。
【００４１】
上述のステップＳ６１〜Ｓ６５の動作により、重複Ｗｅｂサイト候補情報４およびＷｅｂサイト状態情報５は、削除対象コンテンツハッシュ値が挿入される前の状態に設定され、コンテンツハッシュ値の削除処理が完了する。
【００４２】
次に、先の図５のステップＳ５８におけるコンテンツハッシュ値挿入処理の詳細な動作を説明する。図７は、本発明の実施の形態１におけるコンテンツハッシュ値挿入処理の動作の詳細を示すフローチャートである。
【００４３】
まず、ステップＳ７１において、受付手段１は、挿入対象コンテンツハッシュ値（入力コンテンツハッシュ値に等しい）および挿入対象パス名（入力パス名に等しい）に対応する重複Ｗｅｂサイト候補情報４のエントリを検索し、その結果に応じて条件分岐する。エントリが存在しなければステップＳ７２に、エントリが存在し候補サイト集合４３の要素サイト数が１に等しければステップＳ７３に、それ以外の場合にはステップＳ７４にそれぞれ進む。
【００４４】
先のステップＳ７１の判断によりステップＳ７２に進んだ場合には、受付手段１は、重複Ｗｅｂサイト候補情報４に新たなエントリを挿入し、コンテンツハッシュ値４１に挿入対象コンテンツハッシュ値を、パス名４２に挿入対象パス名を、候補サイト集合４３に挿入対象サイト名（入力サイト名に等しい）をそれぞれ設定し、終了する。
【００４５】
また、先のステップＳ７１の判断によりステップＳ７３に進んだ場合には、受付手段１は、ステップＳ７１で検索した重複Ｗｅｂサイト候補情報４のエントリの候補サイト集合４３の単一要素サイト名に対応するＷｅｂサイト状態情報５のエントリを検索し、当該エントリの重複パス数５３に１を加え、ステップＳ７４に進む。
【００４６】
次に、ステップＳ７４において、受付手段１は、挿入対象サイト名に対応するＷｅｂサイト状態情報５のエントリを検索し、当該エントリの重複パス数５３に１を加えるとともに、ステップＳ７１で検索した重複Ｗｅｂサイト候補情報４のエントリの候補サイト集合４３に挿入対象サイト名を追加する。
【００４７】
さらに、ステップＳ７５において、受付手段１は、候補サイト集合４３の各要素サイト名に対応するＷｅｂサイト状態情報５のエントリを検索し、各エントリにおける重複パス数５３の値と、重複パス数５３のパス数５２に対する比を求め、それぞれに対する閾値と比較する。全てのエントリにおいて２つの値が閾値以上の場合には、ステップＳ７６に進み、そうでない場合には、終了する。ただし、このステップＳ７５の判断において、正規名５４が空文字列でないエントリは無視し、正規名５４が空文字列のエントリが１つ以下であれば終了する。
【００４８】
先のステップＳ７５の判断によりステップＳ７６に進んだ場合には、受付手段１は、候補サイト集合４３の複数サイト名の内、対応するＷｅｂサイト状態情報５の正規名５４が空文字列のものを渡して判定手段６の動作を起動し、終了する。
【００４９】
ここで、ステップＳ７５における閾値としては、例えば、重複パス数５３については３、重複パス数５３のパス数５２に対する比については０．４とする。ステップＳ７５の目的は、判定手段６により重複Ｗｅｂサイトでないと判定されることが明らかな候補サイト集合に対する判定を回避することである。
【００５０】
次に、判定手段６の動作を説明する。図８は、本発明の実施の形態１における判定手段６の動作の詳細を示すフローチャートである。このフローチャートは、先の図７のステップＳ７６で起動される。そして、ステップＳ８１において、判定手段６は、Ｗｅｂページ状態情報３のエントリの内、サイト名３１が受け取った候補サイト集合に属する各サイト名のいずれかと一致するものについて、パス名３２とコンテンツハッシュ値３３の値の組毎に出現頻度を数える。
【００５１】
続くステップＳ８２において、判定手段６は、パス名の種類と、２種類以上のコンテンツハッシュ値が対応しているパス名の種類（ミス）とを数え、後者の前者に対する割合をミス率として算出する。そして、ミス率がある第１の所定閾値以上である場合には、判定手段６は、判定結果は偽であるとし、処理を終了する。一方、ミス率が第１の所定閾値未満である場合には、ステップＳ８３に進む。
【００５２】
次に、ステップＳ８３において、判定手段６は、１種類のコンテンツハッシュ値が対応するパス名について、出現頻度（サイト数）が２以上であり、かつ候補サイト集合要素数の一定割合以上となっているもの（ヒット）を数え、ヒット数として算出する。そして、判定手段６は、ヒット数がある第２の所定閾値未満である場合には、判定結果は偽であるとし、処理を終了する。
【００５３】
なお、ステップＳ８３の判断において、判定手段６は、１種類のコンテンツハッシュ値が対応するパス名について、出現頻度（サイト数）が所定数以上であることのみを条件としてヒットとすることもできる。
【００５４】
一方、ヒット数のパス名の種類に対する割合（ヒット率）が第３の所定閾値未満である場合にも、判定手段６は、判定結果は偽であるとし、処理を終了する。ヒット数が第２の所定閾値以上であり、かつヒット率が第３の所定閾値以上である場合には、判定手段６は、判定結果は真であるとして、ステップＳ８４に進む。
【００５５】
ここで、ヒット数に対する第２の所定閾値およびヒット率に対する第３の所定閾値は、先の図７のステップＳ７５における重複パス数に対する閾値および重複パス数のパス数に対する比に対する閾値と対応しており、それぞれ同じ値を用いる（例えば、ステップＳ７５での説明と同様に、３と０．４を用いることができる）。
【００５６】
次に、ステップＳ８４において、判定手段６は、候補サイト集合から代表元のサイト名を１つ選択し、代表元以外のサイト名に対応するＷｅｂサイト状態情報５のエントリの正規名５４に代表元のサイト名を設定し、終了する。
【００５７】
ここで、候補サイト集合から代表元を選択する際には、各要素のサイト名にスコアを付与し、その順位が最も高いもの（値が最も小さいもの）を選択するものとする。図９は、本発明の実施の形態１におけるサイト名に対するスコアの例を示した図である。図９に示すように、サイト名の文字列パターンに応じて、サイト名文字列長およびドメインレベル数によりあらかじめ規定されるサイト名スコアを計算式として用意しておき、このスコア計算式を正規サイト名の選択に用いる。
【００５８】
より具体的には、適用優先度順にサイト名全体の文字列パターンを照合し、最初に適合した行のサイト名スコア計算式を用いる。ただし、ドメインレベル数は“．”で区切られたドメイン名要素の数とする。なお、スコアが同一のサイト名は、文字列順で先頭に来るものを優先する。
【００５９】
図１０は、本発明の実施の形態１における判定手段６の動作の意味を示す概念図である。先の図８のフローチャートによる一連の動作は、図１０に示すように、サイト名３１を各行に、パス名３２を各列に対応させてコンテンツハッシュ値３３を並べた行列において、列毎にヒットおよびミスの判定を行なって、それぞれの数を数えることに等しい。
【００６０】
コンテンツハッシュ値がＮ／Ａとなっている部分は、サイト名とパス名に対応するＷｅｂページをＷｅｂクローラ８から受け取っていないことを表している。Ｗｅｂクローラ８は、一般に、Ｗｅｂページ間のリンクを辿りながらＷｅｂページを収集するため、存在するＷｅｂページであってもアクセスしないことがあり得る。
【００６１】
図１０の例では、パス名“／”に対しては、全てのコンテンツハッシュ値が等しく、種類＝１、出現頻度＝３となることからヒットとなる。また、パス名“／ｌｉｎｋｓ．ｈｔｍｌ”に対しては、サイトａａａ．ｂｂｂ．ｃｃｃおよびｚｚｚ．ｗｗｗ．ａａａに対応する値が存在しないため、種類＝１、出現頻度＝１となってヒットでもミスでもないと見なされる。さらに、パス名“／ｎｅｗｓ．ｈｔｍｌ”に対しては、コンテンツハッシュ値の種類＝２となるため、ミスとなる。
【００６２】
次に、問合せ手段７の動作を説明する。図１１は、本発明の実施の形態１における問合せ手段７の動作の詳細を示すフローチャートである。まず、ステップＳ１１１において、問合せ手段７は、Ｗｅｂクローラ８から問合せを受け付け、問合せ対象のサイト名を結果サイト名に設定する。
【００６３】
次に、ステップＳ１１２において、問合せ手段７は、結果サイト名に対応するＷｅｂサイト状態情報５のエントリを検索し、エントリが存在しないか、または当該エントリの正規名５４が空文字列である場合には、ステップＳ１１４に進む。一方、当該エントリの正規名５４が空文字列でなくエントリが存在する場合には、問合せ手段７は、結果サイト名は重複Ｗｅｂサイトにおける非代表元であり、サイト名を変換する必要があると判断し、ステップＳ１１３に進む。
【００６４】
そして、ステップＳ１１３において、問合せ手段７は、エントリの正規名５４を結果サイト名に設定し、ステップＳ１１２に戻る。ここで、ステップＳ１１２の処理を繰り返すのは、ある重複Ｗｅｂサイトの代表元が、後に別の重複Ｗｅｂサイトに非代表元として含まれると判定される可能性があるためである。
【００６５】
一方、先のステップＳ１１２の判断によりステップＳ１１４に進んだ場合には、問合せ手段７は、結果サイト名の値をＷｅｂクローラ８に返し、終了する。
【００６６】
Ｗｅｂクローラ８は、Ｗｅｂページからリンクを抽出したとき、あるいはＷｅｂページのダウンロードを開始する前に、それらのＵＲＬからサイト名を取り出し、問合せ手段７に渡して得られる結果で元のサイト名を置き換えることにより、重複Ｗｅｂサイトの非代表元へのアクセスを回避することができる。
【００６７】
以上のように、実施の形態１によれば、ＷｅｂクローラからＷｅｂページを順次受け付ける受付手段を備え、重複Ｗｅｂサイト候補情報を維持して重複Ｗｅｂサイトの可能性があるサイト集合を随時把握できるようにするとともに、Ｗｅｂサイト状態情報を維持して判定手段による重複判定の実施タイミングを制御することができる。この結果、Ｗｅｂクローリングに追随した動的な重複Ｗｅｂサイト検出を実現することができる。
【００６８】
さらに、重複Ｗｅｂサイト検出結果を問い合わせる問合せ手段を備えている。この結果、Ｗｅｂクローラに対して重複Ｗｅｂサイトの代表元以外からのＷｅｂページ収集を回避する手段を提供することができる。
【００６９】
なお、上述の実施の形態１においては、コンテンツ特徴量の一例であるコンテンツハッシュ値を、コンテンツデータ全体に一方向性ハッシュ関数を適用した値としたが、別の算出法を用いることもできる。例えば、コンテンツがＨＴＭＬで記述されている場合に、ＨＴＭＬのタグ、コメント、スクリプト、およびスタイルを取り除いた残りのテキストデータに対して一方向性ハッシュ関数を適用した値を、コンテンツ特徴量であるコンテンツハッシュ値としても、全体の構成や動作には影響しない。このようなコンテンツハッシュ値を適用することにより、Ｗｅｂページに含まれる広告などの可変要素を無視することが可能となり、より多くの重複Ｗｅｂサイトが検出可能になる効果がある。
【００７０】
また、上述の実施の形態１では、サイト名の正規名を、パス数や重複パス数の情報とともに、Ｗｅｂサイト状態情報として記憶、管理する場合を説明した。しかしながら、パス数や重複パス数の管理とは別に、正規サイト名と残りのサイト名とを対応づけてＷｅｂサイト名関連情報として管理することによっても、問合せ手段を用いた正規サイト名の抽出が可能となる。
【００７１】
実施の形態２．
先の実施の形態１では、全ての入力パス名に対して重複Ｗｅｂサイト候補情報４の候補サイト集合４３を維持するため、Ｗｅｂサイト毎に収集範囲の偏りがあっても重複Ｗｅｂサイトの検出漏れを防ぐようにしていた。しかしながら、その一方で、重複Ｗｅｂサイト候補情報４のデータ量が大きくなり、更新負荷が高くなる問題がある。
【００７２】
そこで、本実施の形態２では、入力パス名の全てではなく、一部だけを重複Ｗｅｂサイト候補情報４およびＷｅｂサイト状態情報５に反映する場合について説明する。より具体的には、入力パス名が特定パターンに合致しない場合には、受付手段１が図５のステップＳ５５の後半の処理、ステップＳ５６およびステップＳ５８の処理を実行しないものとする。
【００７３】
入力パス名の特定パターンとしては、例えば、部分文字列として“ｉｎｄｅｘ”を含むものに合致するようにする。これにより、Ｗｅｂサイトの入り口として一般的なＵＲＬのみについて候補サイト集合４３を維持し、重複Ｗｅｂサイト候補情報４のデータ量を大幅に削減することができる。なお、Ｗｅｂページ状態情報３は、全てのパス名に関する情報を含むので、判定手段６の動作には影響しない。
【００７４】
また、入力パス名の特定パターンの別の例として、“／”を１つだけ含むものに合致するようにしてもよい。これにより、ディレクトリ最上位のパス名だけを反映することになる。一般に、Ｗｅｂページのリンクは、ディレクトリ上位のパス名を指し易い傾向にあるので、特定文字列を仮定することによる候補サイト集合の見逃しを防ぐことができる。
【００７５】
なお、更新負荷の削減策としては、入力パス名を特定パターンに限定する以外に、Ｗｅｂサイト状態情報５のパス数５２の値に基づく実現も可能である。すなわち、パス数５２が一定値に達した後は、入力パス名によらずステップＳ５５の後半の処理、ステップＳ５６およびステップＳ５８の処理を実行しない。これは、入力パス名を値ではなく、先着順で制限することに相当し、パターンに基づく方式では避けられない見逃しの問題を解決することができる。
【００７６】
以上のように、実施の形態２によれば、特定パターンを有する入力パス名に限定して、その入力パス名を重複Ｗｅｂサイト候補情報４およびＷｅｂサイト状態情報５に反映することができる。この結果、一般的なＵＲＬのみについて候補サイト集合を維持し、重複Ｗｅｂサイト候補情報のデータ量を大幅に削減することができる。
【００７７】
さらに、入力パス名の特定パターンではなく、入力パス名に対応するパス数が一定値に達する前に限定して、その入力パス名を重複Ｗｅｂサイト候補情報４およびＷｅｂサイト状態情報５に反映することができる。この結果、入力パス名を値ではなく、先着順で制限することができ、特定パターンに基づく方式では避けられない見逃しの問題を解決することができる。
【００７８】
実施の形態３．
本実施の形態３では、先の実施の形態１に加えて、候補サイト集合におけるサイト名の類似性を考慮し、類似サイト名からなる候補サイト集合に対してはコンテンツハッシュ値の不一致の許容範囲を広くし、重複Ｗｅｂサイトとして検出しやすくする場合について説明する。
【００７９】
図１２は、本発明の実施の形態３における判定手段６の動作の詳細を示すフローチャートである。本実施の形態３において、判定手段６は、先の実施の形態１で説明した図８のステップＳ８１に先立ち、図１２のフローチャートに示す動作を行う。
【００８０】
まず、ステップＳ１２１において、判定手段６は、候補サイト集合の各サイト名についてドメインレベル数（“．”で区切られた構成要素数に相当）を求め、その最小値を最小ドメインレベル数とする。例えば、サイト名がｘｘｘ.ｙｙｙ.ｚｚｚのとき、ドメインレベル数は、３である。
【００８１】
次に、ステップＳ１２２において、判定手段６は、各サイト名の構成要素（例えば”ｘｘｘ”、“ｙｙｙ”、“ｚｚｚ”のそれぞれ）毎にいくつのサイト名に含まれるかを求め、候補サイト集合の一定割合以上のサイト名に含まれるものを数えて頻出ドメインレベル数とする。
【００８２】
次に、ステップＳ１２３において、判定手段６は、頻出ドメインレベル数と最小ドメインレベル数とを比較し、頻出ドメインレベル数が最小ドメインレベル数より小さい場合には、終了する。一方、頻出ドメインレベル数が最小ドメインレベル数以上の場合には、ステップＳ１２４に進む。そして、ステップＳ１２４において、判定手段６は、候補サイト集合の要素数の対数に比例する係数をミス率の閾値に乗じ、当該係数の逆数をヒット数およびヒット率の閾値に乗じる。係数としては例えば、ｌｏｇ（サイト数）×４．５などを用いる。
【００８３】
このように、図１２に示した一連の前処理を施すことにより、判定手段６は、サイト名の類似性に関する情報も利用して重複判定を行うことができる。特に、候補サイト集合内のサイト名が高い類似性を持つ場合に、閾値の範囲を広げ、重複と判定し易い条件を整えることで、大規模な重複サイトの検出漏れを防ぐことができる。
【００８４】
以上のように、実施の形態３によれば、サイト名の類似性に関する情報も利用し、類似性に応じて重複判定に用いる閾値を変更することができる。この結果、特に、高い類似性を持つ大規模な重複サイトの検出漏れを防ぐことができる。
【００８５】
実施の形態４．
本実施の形態４では、先の実施の形態１に加えて、Ｗｅｂサイトがディレクトリ単位で重複しているときにも検出を可能にする場合について説明する。
【００８６】
本実施の形態４において、受付手段１は、先の実施の形態１で説明した図５のステップＳ５１において、受け取ったＵＲＬから入力サイト名および入力パス名を生成する際に、本来のサイト名とパス名だけでなく、サイト名にパス名の上位ディレクトリ名を連結した擬似的なサイト名と、上位ディレクトリ名が連結されていない残りのパス名の部分からなる擬似的なパス名とを生成する。
【００８７】
すなわち、ＵＲＬ“ｈｔｔｐ：／／ａａａ．ｂｂｂ．ｃｃｃ／〜ｕｓｅｒ１／ｄｉａｒｙ．ｈｔｍｌ”に対し、サイト名“ａａａ．ｂｂｂ．ｃｃｃ”およびパス名“／〜ｕｓｅｒ１／ｄｉａｒｙ．ｈｔｍｌ”だけでなく、擬似的なサイト名“ａａａ．ｂｂｂ．ｃｃｃ／〜ｕｓｅｒ１”および擬似的なパス名“／ｄｉａｒｙ．ｈｔｍｌ”を生成する。これ以外の動作は、先の実施の形態１と同様である。
【００８８】
このように、擬似的なサイト名、擬似的なパス名をも考慮して重複判定を行うことにより、Ｗｅｂサイトの一部が重複している場合であっても検出することができ、Ｗｅｂクローリングの効率低下を防ぐことができる。
【００８９】
以上のように、実施の形態４によれば、受け取ったＵＲＬから入力サイト名および入力パス名を生成する際に、擬似的なサイト名、擬似的なパス名も合わせて生成し、重複判定に利用している。この結果、Ｗｅｂサイトの一部が重複している場合にも確実に検出することができる。
【００９０】
実施の形態５．
本実施の形態５では、判定を誤る可能性の高いパス名を重複判定に使用しないようにする場合について説明する。
【００９１】
図１３は、本発明の実施の形態５において、記憶部２に新たに格納される除外パス名情報９を示した図である。この除外パス名情報９は、除外パス名９１の集合である。
【００９２】
判定手段６は、先の実施の形態１で説明した図８のステップＳ８１において、Ｗｅｂページ状態情報３のエントリを検索する際に、パス名３２が除外パス名９１と一致するものを無視するようにする。
【００９３】
また、判定手段６は、先の図８のステップＳ８２やステップＳ８３で判定結果が偽となった際に、ヒットしたパス名の内、出現するサイト名がある閾値以上（第２の所定範囲に相当）のものを見付け、除外パス名情報９に追加する。
【００９４】
このように、除外パス名情報９を設けることにより、全く関連性のないＷｅｂサイトであっても共通することのあるパス名（例えば、Ｗｅｂサーバソフトウェアのマニュアルページなど）の影響を排除し、誤って重複サイトと判定することを防ぐことができる。
【００９５】
以上のように、実施の形態５によれば、除外パス名を考慮して重複判定処理を行うことができる。この結果、全く関連性のないＷｅｂサイトであるがパス名が共通するものを、重複サイトと誤判定することを防止することができ、判定精度の向上を図ることができる。
【図面の簡単な説明】
【００９６】
【図１】本発明の実施の形態１における重複Ｗｅｂサイト動的検出装置の構成図である。
【図２】本発明の実施の形態１における記憶部に格納されたＷｅｂページ状態情報の詳細を示した図である。
【図３】本発明の実施の形態１における記憶部に格納された重複Ｗｅｂサイト候補情報の詳細を示した図である。
【図４】本発明の実施の形態１における記憶部に格納されたＷｅｂサイト状態情報の詳細を示した図である。
【図５】本発明の実施の形態１における受付手段の動作の詳細を示すフローチャートである。
【図６】本発明の実施の形態１におけるコンテンツハッシュ値削除処理の動作の詳細を示すフローチャートである。
【図７】本発明の実施の形態１におけるコンテンツハッシュ値挿入処理の動作の詳細を示すフローチャートである。
【図８】本発明の実施の形態１における判定手段の動作の詳細を示すフローチャートである。
【図９】本発明の実施の形態１におけるサイト名に対するスコアの例を示した図である。
【図１０】本発明の実施の形態１における判定手段の動作の意味を示す概念図である。
【図１１】本発明の実施の形態１における問合せ手段の動作の詳細を示すフローチャートである。
【図１２】本発明の実施の形態３における判定手段の動作の詳細を示すフローチャートである。
【図１３】本発明の実施の形態５において、記憶部に新たに格納される除外パス名情報を示した図である。
【符号の説明】
【００９７】
１  受付手段、２  記憶部、３  Ｗｅｂページ状態情報、３１  サイト名、３２  パス名、３３  コンテンツハッシュ値（コンテンツ特徴量）、４  重複Ｗｅｂサイト候補情報、４１  コンテンツハッシュ値、４２  パス名、４３  候補サイト集合、５  Ｗｅｂサイト状態情報、５１  サイト名、５２  パス数、５３  重複パス数、５４  正規名、６  判定手段、７  問合せ手段、８  Ｗｅｂクローラ、９  除外パス名情報、９１  除外パス名。
【図１】
0005174385.tif 000002
【図２】
0005174385.tif 000003
【図３】
0005174385.tif 000004
【図４】
0005174385.tif 000005
【図５】
0005174385.tif 000006
【図６】
0005174385.tif 000007
【図７】
0005174385.tif 000008
【図８】
0005174385.tif 000009
【図９】
0005174385.tif 000010
【図１０】
0005174385.tif 000011
【図１１】
0005174385.tif 000012
【図１２】
0005174385.tif 000013
【図１３】
0005174385.tif 000014