(57)【要約】【課題】適正なミラーサイト群を発見し、またその処理効率を高める。【解決手段】大量Ｗｅｂページ集合から、Ｗｅｂサイトのトップページとなるページを推定し（Ｓ１）、Ｗｅｂページ集合について推定したトップページと、それにリンクしたページからサイト集合を決定し（Ｓ２）、このサイト集合に対し、サイズが一定値以上のサイトを処理対象として絞り込み（Ｓ３）、サイト特徴素（サイトがもつリンク文字列、アンカー文字列、内部／外部リンク情報）のファイルを作成し（Ｓ４）、同じ特徴素をもつサイトペアをミラーサイト候補として選択し（Ｓ５）、ミラーサイト候補ペアの類似度からミラーサイトペアを検出する（Ｓ６）。【選択図】  図１
2004264926.tif 000002
【特許請求の範囲】
【請求項１】
Ｗｅｂページ集合から、Ｗｅｂサイトのトップページとなるページを推定するトップページ推定手段と、
前記Ｗｅｂページ集合について推定したトップページと、それにリンクしたページからサイト集合を決定する手段と、
前記Ｗｅｂページ集合について決定したサイト集合に対し、ミラーサイト群を求める手段とを有する、
ことを特徴とするミラーサイト群発見装置。
【請求項２】
前記ミラーサイト群を求める手段は、サイトのトップページおよびトップページからリンクされているある条件に一致するページの内、内部リンク数と外部リンク数をパラメタとする関数の値が規定値以上となるページ集合のリンク文字列とアンカー文字列もしくはリンク画像ファイル名の組をサイトの特徴素とし、このサイトの特徴素が同じ特徴素を持つサイトとどれだけ共有しているかをサイトの類似度として算出することを特徴とする、請求項１のミラーサイト群発見装置。
【請求項３】
前記特徴素の比較において、多くのページ中に出現する特徴素をストップ語リストに登録し、このストップ語に存在する特徴素はサイトの特徴素として抽出しないことを特徴とする、請求項２のミラーサイト群発見装置。
【請求項４】
前記特徴素の比較において、特徴素の共有数がある一定値を下回るサイトの組に関しては類似度の計算を行わないことを特徴とする、請求項２のミラーサイト群発見装置。
【請求項５】
前記類似度計算において、サイトの組Ａ，Ｂの類似度Ｒ（Ａ，Ｂ）およびＲ（Ｂ，Ａ）の値が異なる場合には、
・Ｒ（Ａ，Ｂ）とＲ（Ｂ，Ａ）の差が一定値α未満の場合、両者の平均値をサイトＡ，Ｂの類似度とする。
・差がα以上β未満の場合、Ｒ（Ａ，Ｂ）の値がある閾値を超えていれば、サイトＡはサイトＢの一部がミラーの関係にあるとみなす。
・差がβ以上の場合、両者はミラーの関係にはないとみなす。
ことで、サイト間の類似度を求めることを特徴とする、請求項２のミラーサイト群発見装置。
【請求項６】
Ｗｅｂページ集合から、Ｗｅｂサイトのトップページとなるページを推定するトップページ推定過程と、
前記Ｗｅｂページ集合について推定したトップページと、それにリンクしたページからサイト集合を決定する過程と、
前記Ｗｅｂページ集合について決定したサイト集合に対し、ミラーサイト群を求める過程とを有する、
ことを特徴とするミラーサイト群発見方法。
【請求項７】
前記ミラーサイト群を求める過程は、サイトのトップページおよびトップページからリンクされているある条件に一致するページの内、内部リンク数と外部リンク数をパラメタとする関数の値が規定値以上となるページ集合のリンク文字列とアンカー文字列もしくはリンク画像ファイル名の組をサイトの特徴素とし、このサイトの特徴素が同じ特徴素を持つサイトとどれだけ共有しているかをサイトの類似度として算出することを特徴とする、請求項６のミラーサイト群発見方法。
【請求項８】
前記特徴素の比較において、多くのページ中に出現する特徴素をストップ語リストに登録し、このストップ語に存在する特徴素はサイトの特徴素として抽出しないことを特徴とする、請求項７のミラーサイト群発見方法。
【請求項９】
前記特徴素の比較において、特徴素の共有数がある一定値を下回るサイトの組に関しては類似度の計算を行わないことを特徴とする、請求項７のミラーサイト群発見方法。
【請求項１０】
前記類似度計算において、サイトの組Ａ，Ｂの類似度Ｒ（Ａ，Ｂ）およびＲ（Ｂ，Ａ）の値が異なる場合には、
・Ｒ（Ａ，Ｂ）とＲ（Ｂ，Ａ）の差が一定値α未満の場合、両者の平均値をサイトＡ，Ｂの類似度とする。
・差がα以上β未満の場合、Ｒ（Ａ，Ｂ）の値がある閾値を超えていれば、サイトＡはサイトＢの一部がミラーの関係にあるとみなす。
・差がβ以上の場合、両者はミラーの関係にはないとみなす。
ことで、サイト間の類似度を求めることを特徴とする、請求項７のミラーサイト群発見方法。
【請求項１１】
請求項６〜１０のミラーサイト群発見方法を、コンピュータプログラムで記載してそれを実行可能にしたことを特徴とするミラーサイト群発見方法のプログラム。
【請求項１２】
請求項６〜１０のミラーサイト群発見方法を、コンピュータで実行可能に記載したプログラムとして記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、大量Ｗｅｂページ集合から、意味のあるページ集合を一まとめにしたサイトを単位として、同一内容のサイトを発見する技術であり、具体的には上記大量Ｗｅｂページ集合の検索結果から同一構造をもつサイト（ミラーサイト）を排除することによる検索結果改善、ＷＷＷのリンク解析に基づく検索エンジンの精度向上、上記大量Ｗｅｂページ収集に際して同内容のページの収集を回避することによるＷｅｂページ収集効率改善、およびネットワーク、サーバに対する総体的な負荷軽減、適切なミラーサイトへ利用者を誘導することによる同一コンテンツに対するアクセス負荷分散、等の技術に関わる。
【０００２】
【従来の技術】
ＷＷＷには様々な理由によりミラーと呼ばれる同一ページのコピーが存在する。例えば、１００ＵＲＬ以上のページを持つホストのうち約１０部分が別サーバに同一ページのコピーが存在すると報告されている。
【０００３】
このように、ＷＷＷ上に少なからぬ数のページと同じページが存在するという事実は、大量Ｗｅｂページの検索において、同じ内容のページが検索結果に含まれてしまう。また、各種のサーチエンジンにみられる、ＷＷＷのリンク解析に基づく検索結果のランキング方式においては、こうした検索結果として不要なミラーページが持つリンクがグラフの形状を変化させ、また処理パフォーマンスの低下をも招く。さらに、検索対象のＷｅｂページを収集する際に多くの同じ内容のページへアクセスしてしまうため、収集効率が悪化するという問題もある。
【０００４】
このような問題を解消しようとするものが報告されている（例えば、非特許文献１および非特許文献２）。
【０００５】
非特許文献１は、Ｗｅｂサーバ単位でのミラーホスト発見手法をいくつか比較している。例えば、同一ＩＰアドレスを持つホスト群からミラー候補のホストペアを抽出する、多くのホストからそれぞれ１０ｌｏｇｐ（ｐはホストに存在ナるページ数）個のパスのｐｒｅｆｉｘ部分を抽出し（但し、１００ホスト以上に存在するパス名は棄却、２５ホスト以上出現するパス名は２５ホスト中に出現したとみなす、同報告では６４６２９１個の異なるパス名が抽出されている）、それらを基底とするホストベクトルを作成し、ベクトルのコサイン値をホストのペアの類似度とし、類似度の大きいホストのペアを出力する、等である。
【０００６】
非特許文献２では、あるミラーサイトのトップページ候補のページからＮ回リンクを辿って到達可能な全ページに対して類似度計算を行っている。この類似度は、ミラーサイトのトップページ侯補ページからリンクを抽出し、検出対象のページとリンクをどれだけ共有しているかを計算した値である。
【０００７】
【非特許文献１】
Ｋｒｉｓｈｎａ  Ｂａｈａｒａｔ，  Ａｎｄｅｒｅｉ  Ｂｒｏｄｅｒ，Ｊｅｆｆｅｒｙ  Ｄｅａｎ，  Ｍｏｎｉｋａ  Ｒ．  Ｈｅｎａｉｎｇｅｒ  “Ａ  Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｔｅｃｈｎｉｑｕｅｓ  ｔｏ  Ｆｉｎｄ  Ｍｉｒｒｏｒｅｄ  Ｈｏｓｔｓ  ｏｎ  ｔｈｅ  ＷＷＷ”，  Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  Ａｍｅｒｉｃａｎ  Ｓｏｃｉｅｔｙ  ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｃｉｅｎｃｅ（ＪＡＳＩＳ），Ｖｏｌ．５１，Ｎｏ．１２，Ｎｏｖ．，ｐｐ．１１１４−１１２２，２０００，
【０００８】
【非特許文献２】
栗原  聡，廣津  登志夫，高田  敏弘，明石  修，菅原  俊治  “リンク情報によるＷｅｂページ間の類似度推定”，コンピュータソフトウェア  Ｖｏｌ．１８，Ｎｏ．６，２０００，
【０００９】
【発明が解決しようとする課題】
前記の非特許文献１では、Ｗｅｂサーバ単位でのミラーホスト発見手法をいくつか比較しているが、当該文献ではホスト単位での比較しか行うことができない。ＷＷＷにはそのようなミラーサイトだけでなく、例えば、
ｈｔｔｐ：／／ｗｗｗ．ｋａｌｅｉｄｏｓｃｏｐｅ−ｍｕｓｉｃｂｏｘ．ｃｏｍ／ｍｕｓｉｃｌｉｎｋ／
と、
ｈｔｔｐ：／／ｃｇｉ．ｍｅｍｂｅｒｓ．ｉｎｔｅｒｑ．ｏｒ．ｊｐ／ｊａｐａｎ／ｓｏｕｎｄ／ｍｕｓｉｃｌｉｎｋ／
のように、ホスト内のコンテンツ同士がミラーリングされているような場合も数多く存在する。
【００１０】
非特許文献２では、あるミラーサイトのトップページ侯補のページからＮ回リンクを辿って到達可能な全ページに対してミラーサイト検出の計算を行っている。しかし、この手法では、まずミラーサイトのトップページ侯補ページを見つける必要がある。同文献ではユーザがミラーサイトのトップページを与えるか、プロキシサーバのアクセスログに追加されたデータに対してミラーサイト検出処理を行うため、大量Ｗｅｂページセットからミラーサイトを発見する手法としては不適である。
【００１１】
また、同文献によれば、あるミラーサイトのトップページ侯補のページからＮ回リンクを辿って到達可能な全ページに対してミラーサイト検出の計算を行っているため、もしトップページ候補が適切に選ばれていたとしても、場合によっては非常に効率の悪い検出処理となってしまう。例えば、同文献ではｗｗｗ．ｙａｈｏｏ．ｃｏｍからリンクを３回辿って到達可能なページ数は２６８９４、そのうちミラーサイト検出処理を行う対象は１０４６８ページあるにも関わらず、ミラーサイトは検出されない。同文献ではこの問題に対処するために、ディレクトリ文字列に対する簡単なルールを用いてフィルタリングを行った後に比較を行う手法を提案しているが、その性能については触れられていない。
【００１２】
また、同文献におけるサイトＡ，Ｂの類似度Ｒ（Ａ，Ｂ）は（Ａ，Ｂが共有するリンクの数）／（Ａが持つリンクの総数）で計算されるが、ＡとＢが共有するリンクのカウント対象となるページは、まずＡのトップページ侯補のページのリンク数を求め、その値が一定値Ｎ以下であればそのページから内部リンクを１階層辿って到達可能な全ページをカウント対象に追加している。しかし、Ａ，Ｂがミラーの関係にあり、そのトップページが持つリンク数がＮを下回っており、かつトップページからリンクされたページの持つリンク数が非常に多い場合、他のサイトとの共有リンク判別を含めて比較回数が無駄に増大する虞がある。
【００１３】
また、同文献におけるサイトＡ，Ｂの類似度Ｒ（Ａ，Ｂ）の計算において、もしＡとＢの持つリンク数が異なる場合、サイトＡ，Ｂの類似度Ｒ（Ａ，Ｂ）、Ｒ（Ｂ，Ａ）は異なる値を示すため、大量Ｗｅｂページ集合に適用するためにはこれらのうち適当な値を選択する手段を新たに必要とする。
【００１４】
本発明の目的は、上記の課題を解決したＷＷＷ上のミラーサイト群発見装置、ミラーサイト群発見方法、この方法のプログラムおよびこのプログラムを記録した記録媒体を提供することにある。
【００１５】
【課題を解決するための手段】
本発明は、ホストからＷｅｂサイトのトップページとなるページを自動抽出し、それにリンクしたページからサイトを決定し、そのサイトを単位としてミラーサイト検出を行うことで、ホストより細かいページ集合であるサイト単位でのミラーサイトを発見可能とする。
【００１６】
また、大量Ｗｅｂページからトップページとなるページを推定し、このページを元にサイト集合を決定してミラーサイト発見に利用することで、大量Ｗｅｂページに適用を可能とし、またミラーサイト発見処理効率を高める。
【００１７】
また、あるミラーサイトのトップページ侯補のページからＮ回リンクを辿って到達可能な全ページに対してミラーサイト検出を行うのに、トップページに含まれるリンクタグで指定された文字列（リンク文字列）とそのタグに囲まれた文字列（アンカー文字列）の組を特徴素とし、この特徴素が少なくともＮ個共有されているページに対してのみミラーサイト検出処理を行うことで、効率良くミラーサイト侯補の類似度を計算可能とする。
【００１８】
また、多くのページに出現するリンクもしくは特徴素を数に入れないことで、さらに計算の効率を改善する。
【００１９】
また、サイトＡ，Ｂがミラーサイトの関係にあるか否かを比較する際、トップページ候補のリンク数がＮより小さい場合は追加したページの総リンク数を加えてＮを超えるまで、トップページのリンク先ページのうち、リンク数の多いページを１ページずつ追加することで、サイト特徴素の数が大きくなりすぎることを防ぎ、比較回数を削減することで、さらに計算の効率を改善することを可能とする。
【００２０】
また、サイトＡ，Ｂの類似度Ｒ（Ａ，Ｂ）とＲ（Ｂ，Ａ）の値が異なる場合は、Ｒ（Ａ，Ｂ）とＲ（Ｂ，Ａ）の差が一定値α未満の場合、両者の平均値をサイトＡ，Ｂの類似度とすること、差がα以上β未満の場合、Ｒ（Ａ，Ｂ）の値がある閾値を超えていれば、サイトＡはサイトＢの一部をミラーしているとみなすこと、および差がβ以上の場合、両者はミラーの関係にはないとみなすことで、適正な類似度を基にしたミラーサイト群発見を可能とする。
【００２１】
以上のことから、本発明は、以下の装置、方法、プログラムおよび記録媒体を特徴とする。
【００２２】
（装置の発明）
（１）Ｗｅｂページ集合から、Ｗｅｂサイトのトップページとなるページを推定するトップページ推定手段と、
前記Ｗｅｂページ集合について推定したトップページと、それにリンクしたページからサイト集合を決定する手段と、
前記Ｗｅｂページ集合について決定したサイト集合に対し、ミラーサイト群を求める手段とを有することを特徴とする。
【００２３】
（２）前記ミラーサイト群を求める手段は、サイトのトップページおよびトップページからリンクされているある条件に一致するページの内、内部リンク数と外部リンク数をパラメタとする関数の値が規定値以上となるページ集合のリンク文字列とアンカー文字列もしくはリンク画像ファイル名の組をサイトの特徴素とし、このサイトの特徴素が同じ特徴素を持つサイトとどれだけ共有しているかをサイトの類似度として算出することを特徴とする。
【００２４】
（３）前記特徴素の比較において、多くのページ中に出現する特徴素をストップ語リストに登録し、このストップ語に存在する特徴素はサイトの特徴素として抽出しないことを特徴とする。
【００２５】
（４）前記特徴素の比較において、特徴素の共有数がある一定値を下回るサイトの組に関しては類似度の計算を行わないことを特徴とする。
【００２６】
（５）前記類似度計算において、サイトの組Ａ，Ｂの類似度Ｒ（Ａ，Ｂ）およびＲ（Ｂ，Ａ）の値が異なる場合には、
・Ｒ（Ａ，Ｂ）とＲ（Ｂ，Ａ）の差が一定値α未満の場合、両者の平均値をサイトＡ，Ｂの類似度とする。
【００２７】
・差がα以上β未満の場合、Ｒ（Ａ，Ｂ）の値がある閾値を超えていれば、サイトＡはサイトＢの一部がミラーの関係にあるとみなす。
【００２８】
・差がβ以上の場合、両者はミラーの関係にはないとみなす。
ことで、サイト間の類似度を求めることを特徴とする。
【００２９】
（方法の発明）
（６）Ｗｅｂページ集合から、Ｗｅｂサイトのトップページとなるページを推定するトップページ推定過程と、
前記Ｗｅｂページ集合について推定したトップページと、それにリンクしたページからサイト集合を決定する過程と、
前記Ｗｅｂページ集合について決定したサイト集合に対し、ミラーサイト群を求める過程とを有することを特徴とする。
【００３０】
（７）前記ミラーサイト群を求める過程は、サイトのトップページおよびトップページからリンクされているある条件に一致するページの内、内部リンク数と外部リンク数をパラメタとする関数の値が規定値以上となるページ集合のリンク文字列とアンカー文字列もしくはリンク画像ファイル名の組をサイトの特徴素とし、このサイトの特徴素が同じ特徴素を持つサイトとどれだけ共有しているかをサイトの類似度として算出することを特徴とする。
【００３１】
（８）前記特徴素の比較において、多くのページ中に出現する特徴素をストップ語リストに登録し、このストップ語に存在する特徴素はサイトの特徴素として抽出しないことを特徴とする。
【００３２】
（９）前記特徴素の比較において、特徴素の共有数がある一定値を下回るサイトの組に関しては類似度の計算を行わないことを特徴とする。
【００３３】
（１０）前記類似度計算において、サイトの組Ａ，Ｂの類似度Ｒ（Ａ，Ｂ）およびＲ（Ｂ，Ａ）の値が異なる場合には、
・Ｒ（Ａ，Ｂ）とＲ（Ｂ，Ａ）の差が一定値α未満の場合、両者の平均値をサイトＡ，Ｂの類似度とする。
【００３４】
・差がα以上β未満の場合、Ｒ（Ａ，Ｂ）の値がある閾値を超えていれば、サイトＡはサイトＢの一部がミラーの関係にあるとみなす。
【００３５】
・差がβ以上の場合、両者はミラーの関係にはないとみなす。
ことで、サイト間の類似度を求めることを特徴とする。
【００３６】
（プログラムの発明）
（１１）上記（６）〜（１０）のミラーサイト群発見方法を、コンピュータプログラムで記載してそれを実行可能にしたことを特徴とする。
【００３７】
（記録媒体の発明）
（１２）上記（６）〜（１０）のミラーサイト群発見方法を、コンピュータで実行可能に記載したプログラムとして記録したことを特徴とする。
【００３８】
【発明の実施の形態】
図１は、本発明におけるミラーサイト群発見の基本処理手順を示し、以下詳細に説明する。
【００３９】
（Ｓ１）トップページの推定
大量Ｗｅｂページ集合から、Ｗｅｂサイトのトップページとなるページを推定し、ページＤＢ（ページデータベース）を作成する。
【００４０】
このトップページの推定方法については、本願出願人は既に提案しており（例えば、特願２００１−３８９４４７）、検索したＷｅｂページをサーバ別に分類しておき、メタ情報とページタイプからページクラスを抽出したページ分類木を獲得しておき、この分類木を基に各ページのページタイプの分類尤度を抽出しておき、同じサーバに属するページについて、ディレクトリ階層が０に位置するページを最優先でトップページとして推定し、階層０にトップページが存在しない場合にはトップページタイプの分類尤度を基にトップページが存在するディレクトリ階層を決定し、このディレクトリ階層に所属して下位階層にファイルが存在し、かつページタイプへの分類尤度が最大さらには閾値以上のページをトップページとして推定する。
【００４１】
このとき作成されるページデータベースは、図１中に例を示すように、大量Ｗｅｂトップページ集合の各ページのＩＤとＵＲＬ、内部リンク（ｉｎｌｉｎｋ）数、外部リンク（ｏｕｔｌｉｎｋ）数を管理している。
【００４２】
（Ｓ２）サイト集合決定
上記のＷｅｂページ集合について推定したトップページと、それにリンクしたページからサイト集合を決定し、サイトデータベースおよびリンクデータベースを作成する。
【００４３】
このサイト集合の決定方法については、本願出願人は既に提案しており（例えば特願２００１−３８９４４８）、検索したＷｅｂページ集合の各ページ、リンクについてメタ情報とリンク分類木を利用してリンクの各リンクタイプへの分類尤度を獲得しておき、さらにメタ情報とページタイプからページクラスを抽出したページ分類木を獲得して各ページのページタイプの分類尤度を抽出しておき、その後、Ｗｅｂページが属する全てのサーバについて、上記の分類尤度を基にしてＷｅｂサイトのトップページ候補集合を得てそれらの親ページを推定し、この推定でも親ページが未決のページ集合の中からディレクトリの最も浅い階層に存在しかつトップページ、インデックスページ、メニューページ尤度の和が最大のページをトップページ候補としてそれらの親ページを推定し、これら推定した親ページとこれにリンクするページ集合をサイト集合とする。
【００４４】
このとき作成されるサイトＤＢは、図１中に例を示すように、上記大量Ｗｅｂページ集合をサイト集合に分割した後、各サイト毎にサイトのＩＤ、サイトのトップページＵＲＬのＩＤ、サイトに属するページ数（サイズ）を管理している。
【００４５】
また、リンクＤＢは、図１中に例を示すように、上記大量Ｗｅｂページ集合の各ページ間のリンク、具体的にはリンク元ページのＩＤ、リンク先ページのＩＤ、リンク文字列、アンカー文字列を管理している。ここで、リンク文字列およびアンカー文字列とは、例えば、ＨＴＭＬのリンクタグで指定される、
＜ａ  ｈｒｅｆ＝“ｈｔｔｐ：／／ｗｗｗ．ａ．ｃｏｍ／”＞ＬＩＮＫ＜／ａ＞
のようなリンクについて、ｈｒｅｆ属性で指定された、
“ｈｔｔｐ：／／ｗｗｗ．ａ．ｃｏｍ／”
およびタグに囲まれた文字列“ＬＩＮＫ”に相当する。もし、リンクタグに囲まれたイメージタグが存在し、かつ上記“ＬＩＮＫ”のような文字列が存在しないリンクについては、
＜ｉｍｇ  ｓｒｃ＝“／ｉｍｇ／ａ．ｊｐｇ”＞
のようなイメージタグについてｓｒｃ属性で指定された文字列、
“／ｉｍｇ／ａ．ｊｐｇ”
をアンカー文字列に採用する。
【００４６】
以上までの前処理で作成されたデータベースの情報をもとに、以下の処理Ｓ３〜Ｓ６によってミラーサイト群を発見する。
【００４７】
（Ｓ３）処理対象の絞り込み
処理対象の絞り込みは、サイトＤＢを検索し、サイズが一定値Ｎ以上のサイトのトップページＩＤを得る。この処理により、サイズの小さいサイトはミラーサイトになり得る確率が小さいため、処理対象から削除する。例えば、図１中に示すサイトデータベースの例において、Ｎ＝１０の場合、サイトＩＤ＝０，１，３，４のトップページＩＤ＝０，１，３，４を得る。このとき、以後の処理対象となるサイトは０，１，３，４に絞られる。
【００４８】
（Ｓ４）サイト特徴素のファイル出力
サイト特徴素のファイル出力は、図２に示す手順で行う。まず、各サイトのトップページＰが持つリンクのリンク文字列、アンカー文字列、内部／外部リンクの情報（これらの組を以下では特徴素と呼ぶ）とサイトＩＤを一行としてファイルＡに出力する（Ｓ４１）。ファイルＡは、例えば下記表に示すような内容のテキストファイルである。ここで、後述するストップ語リストが作成されてある場合、ストップ語として登録されている特徴素はファイルに出力しない。ストップ語とは、同じ特徴素を持つサイト数が閾値Ｌを超えるような特徴素である。
【００４９】
【表１】
2004264926.tif 000003
【００５０】
次に、トップページの内部リンク数と外部リンク数の重みつき線形和の関数ｆの値を計算する（Ｓ４２）。ここで、関数ｆは以下の式で求める。
【００５１】
【数１】
ｆ（ｐ）＝（ｗｉｎ×ｐｉｎ）＋（ｗｏｕｔ×ｐｏｕｔ）
ｗｉｎ：内部リンクの重み、  ｐｉｎ：ページが持つ内部リンク数、
ｗｏｕｔ：外部リンクの重み、  ｐｏｕｔ：ページｐが持つ外部リンク数
例えば、ｗｉｎ，ｗｏｕｔをそれぞれ１に設定すると、上記トップページｐ１の例ではｆ（ｐ１）＝３＋１＝４である。
【００５２】
ここでｆ（ｐ）の値がＭ以下のトップページにおいては、そのトップページが持つ内部リンク先ページが持つリンクを抽出し、先のｐｉｎ，ｐｏｕｔにそれらのページが持つリンク数を加えた値ｐ’ｉｎ，ｐ’ｏｕｔを用いてｆ（ｐ）を計算し、その値がＭ以上になるまで計算し（Ｓ４３，Ｓ４４）、特徴素とサイトＩＤの組をファイルＡに追加出力する（Ｓ４５）。なお、トップページの内部リンク先ページの抽出はリンクＤＢに間い合わせることで可能である。
【００５３】
また、各サイトが持つ特徴素の数（ファイルＡに出力された数）を内部リンク、外部リンク毎に検索可能なデータベースファイル（以下、特徴素数データベース）を作成する（Ｓ４６）。
【００５４】
次に、先に生成されたファイルＡをソートしたファイルＢを出力する（Ｓ４７）。上記表１で示すファイルＡの例について、各行をソートしたファイルＢは以下の通りである。
【００５５】
【表２】
2004264926.tif 000004
【００５６】
（Ｓ５）ミラーサイト侯補ペアの選択
ミラーサイト候補ペアの選択は、図３に示す手順で行う。まず、ファイルＢを先頭から見て、同じ特徴素を持つサイトＩＤのペアをミラーサイト侯補としてそのデータベースを作成し、特徴素数データベースの共通している特徴素数のカウンタを１増やす（Ｓ５１）。
【００５７】
例えば、前記の表２に示すファイルＢの例において、特徴素／ｘ／ｙ．ｈｔｍｌ  ｓｔｒＢ  ｉｎはサイト０と４に共通しているため、サイトペア（０，４）をミラーサイト候補ＤＢに登録し、共通している特徴素数のカウンタを１増やす。
【００５８】
ミラーサイト侯補ＤＢは、サイトＩＤのペア（ｓｉｔｅＡ，ｓｉｔｅＢ）、共通している特徴素を内部リンク（Ｆｉｎ）、外部リンク（Ｆｏｕｔ）毎に記録したデータベースであり、図３中には、ファイルＢのエントリを処理した後のミラーサイト候補ＤＢの例を示す。
【００５９】
ここで、同じ特徴素を持つサイト数が閾値Ｌを超えるような特徴素は無視する。例えばＬ＝３の場合、上記ファイルＢの例において特徴素／ｘ／ｙ．ｈｔｍｌ  ｓｔｒＢ  ｉｎがもしサイト０と４だけでなく、サイト１，３とも共通していれば、この特徴素を持つサイト数は４となりＬを上回るため、この特徴素については考慮しない。また、このような特徴素が存在する場合（Ｓ５２）、この情報をストップ語リストとして作成しておく（Ｓ５３）。本発明の処理を再度実施する際にはこのストップ語リストを参照する。
【００６０】
次に、まだクラスタＩＤが割り振られていないサイトについて、ミラーサイトペアの検出に供する情報としてクラスタＩＤを割り当てておく（Ｓ５４）。この時点では、共通特徴素がカウントされた各サイトＩＤに対して唯一のクラスタＩＤが割り振られる。既にクラスタＩＤが付与されているサイトについては再割当は行わない。
【００６１】
以上の処理をファイルＢの最後まで繰り返す（Ｓ５５）。
【００６２】
（Ｓ６）ミラーサイトペアの検出
ミラーサイトペアの検出は、図４に示す手順で行う。まず、ミラーサイトクラスタ情報を初期化する（Ｓ６１）。ミラーサイトクラスタ情報とは、この時点ではミラーサイト候補ＤＢに登録されている各サイトが持つ（排他的）クラスタＩＤの集合を意味する。ミラーサイトクラスタ情報は、それら各クラスタが対応するサイトＩＤを要素に持つ集合として初期化される。
【００６３】
次に、ミラーサイト侯補ＤＢに登録された各サイトペア（Ａ，Ｂ）について以下の処理を行う。
【００６４】
まず、ミラーサイト侯補ＤＢに登録された各サイトペア（Ａ，Ｂ）について、同じクラスタＩＤを持っているかどうかをミラーサイトクラスタ情報から検索する（Ｓ６２）。もし、サイトＡとサイトＢが同じクラスタＩＤを持つていれば、以後の処理は行わない。
【００６５】
次に、異なるクラスタＩＤをもっているサイトペアについて、各々が所属しているミラーサイトクラスタが既にミスマッチ（後述）と判定されているかどうかをミスマッチ情報（後述）から検索する（Ｓ６３）。もし、サイトＡの属するクラスタＩＤ（以後クラスタＡ）とサイトＢが属するクラスタＩＤ（以後クラスタＢ）が既にミスマッチと判定されていたならば、以後の処理は行わない。
【００６６】
上記条件のいずれにも該当しない場合、ミラーサイト候補ＤＢに登録されたサイトペア（Ａ，Ｂ）に対して次の値を計算する（Ｓ６５）。
【００６７】
【数２】
2004264926.tif 000005
【００６８】
但し、ｕｒｌ（Ａ）ｉｎ：サイトＡの特徴素数（内部リンク）、
ｕｒｌ（Ａ）ｏｕｔ：サイトＡの特徴素数（外部リンク数）、
ｗｉｎ：内部リンク数の重み、ｗｏｕｔ：外部リンク数の重み、
ｕｒｌ（Ａ∩Ｂ）ｉｎ：Ａ，Ｂが共有している特徴素数（内部リンク）、
ｕｒｌ（Ａ∩Ｂ）ｏｕｔ：Ａ，Ｂが共有している特徴素数（外部リンク）
各サイトの特徴素数は、前述の特徴素数データベースをサイトＩＤ毎に検索することで得られる。ｗｉｎ，ｗｏｕｔについては前述のｆの定義中のものと同値である。
【００６９】
これら値α、βは、サイトＡとＢが特徴素をどの程度共有しているか求めるもので、本発明ではサイトＡとＢの特徴素の共有割合が高ければ、ＡとＢはミラーサイトであると判断する。また、αとβの２つの値を求める理由は、前記の従来法の課題となる、「ＡとＢの持つリンク数が異なる場合、サイトＡ，Ｂの類似度Ｒ（Ａ，Ｂ）、Ｒ（Ｂ，Ａ）は異なる値を示す」を解決するものである。例えば、サイトＡからＢをみれば共有数は多いが、Ｂからみれば共有数が少ない場合、（α−β）の絶対値は大きくなり、後述のように、この値がＪを越えた場合はαとβのうち小さい方をとり、これを基にサイトＡとＢが特徴素をどの程度共有しているかを判断する。
【００７０】
なお、α、βの計算前処理として、ミラーサイト候補ＤＢのＦｉｎ，Ｆｏｕｔを前記関数ｆのｐｉｎ，ｐｏｕｔに代入した値が閾値Ｐより小さい場合はこの値を計算せず、ミラーサイト候補ペアから除外する（Ｓ６４）。例えばＰ＝３の場合、前記ミラーサイト候補ＤＢの例（図３参照）において、サイトペア（０，４）のｆの値はｆ＝１＋０＝１≦３となるため、以後の計算は行われない。サイトペア（１，３）の場合はｆ＝３＋１＝４≧３となり、以後の計算の対象となる。ちなみに、このペアについては
【００７１】
【数３】
α＝（３＋１）／３＋１）＝１
β＝（３＋１）／３＋１）＝１
である。
【００７２】
次に、先に計算されαとβの差の絶対値δを条件として、サイトペア（Ａ，Ｂ）の類似度Ｒ（Ａ，Ｂ）を以下の規則に基づいて求める（Ｓ６６）。
【００７３】
【数４】
δ＜Ｉの場合、Ｒ（Ａ，Ｂ）＝（α＋β）／２
Ｉ＜δ＜Ｊの場合、Ｒ（Ａ，Ｂ）＝ｍａｘ（α，β）
δ＞Ｊの場合、Ｒ（Ａ，Ｂ）＝ｍｉｎ（α，β）
次に、類似度Ｒ（Ａ，Ｂ）が閾値Ｋを超えるものをミラーサイトペアと判定し（Ｓ６６）、クラスタＡとクラスタＢの新たなクラスタを生成する（Ｓ６７）。例えば、Ｉ＝０．２、Ｊ＝０．８、Ｋ＝０．９とすると、前記のサイトペア（１，３）についてはα＝β＝１であり、δ＝０となるため、Ｒ（１，３）＝（１＋１）／２＝１＞Ｋよりサイトペア（１，３）はミラーサイトペアであると判定される。
【００７４】
なお、新しいクラスタのＩＤはクラスタＡとクラスタＢのいずれかを採用する。ここで、新しいクラスタＩＤはクラスタＡとする。
【００７５】
次に、統合されたサイトＢの属するクラスタにおけるミスマッチ情報（後述）を検索する。もし、クラスタＢと他のクラスタ、例えばクラスタＣとのミスマッチ情報が存在すれば、それをクラスタＡとクラスタＣとのミスマッチ情報に置き換える。この操作をクラスタＢに関する全てのミスマッチ情報に対して行う（Ｓ６８）。
【００７６】
判定処理Ｓ６６で、類似度Ｒ（Ａ，Ｂ）が閾値Ｋを超えなかった場合は、サイトペア（Ａ，Ｂ）はミスマッチ（ミラーサイトペアでない）としてミスマッチ情報にクラスタＡとクラスタＢがミスマッチであるという情報を追加する（Ｓ６９）。
【００７７】
（Ｓ７）結果出力
ミラーサイトクラスタ情報をファイルもしくはデータベースに格納し、ミラーサイト群発見処理を終了する。
【００７８】
以上のように、本実施形態によれば、前述の問題は以下のようにして解決される。
【００７９】
・従来技術のホスト単位でのミラーサイト検出しか行うことができないという問題点を解決するために、ホストからＷｅｂサイトのトップページとなるページを自動抽出し、それにリンクしたページからサイトを決定し、そのサイトを単位としてミラーサイト検出を行うことで、ホストより細かいページ集合であるサイト単位でのミラーサイトを発見することが可能になる。
【００８０】
・ミラーサイトのトップページを大量Ｗｅｂページ集合から発見するために、従来提案されているトップページ発見手法を利用することで、従来技術においてミラーサイトのトップページ侯補を効率的に発見できないために、非特許文献２で紹介されているミラーサイト検出手法が大量Ｗｅｂページに対して適用できない問題を解決することができる。
【００８１】
・あるミラーサイトのトップページ侯補のページからＮ回リンクを辿って到達可能な全ページに対してミラーサイト検出の計算を行っているため、もしトップページ候補が適切に選ばれていたとしても、場合によっては非常に効率の悪い検出処理となってしまう問題に対しては、トップページに含まれるリンクタグで指定された文字列（リンク文字列）とそのタグに囲まれた文字列（アンカー文字列）の組を特徴素とし、この特徴素が少なくともＮ個共有されているページに対してのみミラーサイト検出処理を行うことで、従来手法よりも効率良くミラーサイト侯補の類似度を計算できる。
【００８２】
・多くのページに出現するリンクもしくは特徴素を数に入れないことで、さらに計算の効率を改善することができる。
【００８３】
・Ａ，Ｂがミラーの関係にあり、そのトップページが持つリンク数がＮを下回っており、かつトップページからリンクされたページの持つリンク数が非常に多い場合、他のサイトとの共有リンク判別を含めて比較回数が無駄に増大する虞れがある問題に関しては、トップページ候補のリンク数がＮより小さい場合は追加したページの総リンク数を加えてＮを超えるまで、トップページのリンク先ページのうち、リンク数の多いページを１ページずつ追加することで、サイト特徴素の数が大きくなりすぎることを防ぎ、比較回数を削減することで、さらに計算の効率を改善する。
【００８４】
・サイトＡ，Ｂの類似度Ｒ（Ａ，Ｂ）とＲ（Ｂ，Ａ）の値が異なる場合は、Ｒ（Ａ，Ｂ）とＲ（Ｂ，Ａ）の差が一定値α未満の場合、両者の平均値をサイトＡ，Ｂの類似度とすること、差がα以上β未満の場合、Ｒ（Ａ，Ｂ）の値がある閾値を超えていれば、サイトＡはサイトＢの一部をミラーしているとみなすこと、差がβ以上の場合、両者はミラーの関係にはないとみなすことにより、適正な類似度を決定することができる。
【００８５】
なお、本発明は、図１〜４に示した方法の一部又は全部をコンピュータプログラムで記載してそれを実行できるようにしたプログラムを配布することか可能である。また、このプログラムをコンピュータが読み取り可能な記録媒体、例えば、フレキシブルディスク、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることが可能であり、また、インターネットのような通信ネットワークを介して配布したりすることが可能である。
【００８６】
【発明の効果】
本発明によって、大量Ｗｅｂページ集合からホストより細かい、意味のあるページ集合であるサイトを単位とし、従来の方法に比べて格段に計算効率が良く、類似度の非対象性をも考慮したサイト間の類似度判定に基づくミラーサイトの発見が可能となる。本発明の効果の主なものは以下の通りである。
【００８７】
（１）大量Ｗｅｂページ集合の検索結果から同一構造をもつサイト（ミラーサイト）を排除することにより、検索結果を効率良く提示することができ、かつ利用者が検索結果を選択する際に、負荷の軽いミラーサイトへ自動的に誘導することで、ネットワークやサーバの負荷を低減することができる。
【００８８】
（２）ＷＷＷのリンク解析に基づく検索結果のランキング方式において、不要なミラーページが持つリンクをグラフから省くことで、精度の向上および処理パフォーマンスの向上が可能となる。
【００８９】
（３）大量Ｗｅｂページ収集に除して、同内容のページの収集を回避することによるＷｅｂページ収集の効率改善およびネットワーク、サーバに対する総体的な負荷軽減が可能となる。
【図面の簡単な説明】
【図１】本発明の実施形態を示す基本構成図。
【図２】実施形態におけるサイト特徴素のファイル出力処理手順図。
【図３】実施形態におけるミラーサイト候補ペアの選択処理手順図。
【図４】実施形態におけるミラーサイトペアの検出処理手順図。
【図１】
2004264926.tif 000006
【図２】
2004264926.tif 000007
【図３】
2004264926.tif 000008
【図４】
2004264926.tif 000009