重複ページの検索エンジンアルゴリズム分析

検索エンジンは一般的に、各 Web ページに対して一連の情報フィンガープリントが計算されるという考え方に基づいて、重複する Web ページを判断します。2 つの Web ページに一定数の同一の情報フィンガープリントがある場合、2 つの Web ページのコンテンツは重複度が高いとみなされ、2 つの Web ページに重複したコンテンツがあることを意味します。

多くの検索エンジンでは、主に次の 2 つの違いにより、コンテンツの重複を判断する方法が異なります。

1. 情報フィンガープリントを計算するアルゴリズム。

2. 情報指紋の類似性を判断するためのパラメータ。

具体的なアルゴリズムを説明する前に、2 つの点を明確にしておきたいと思います。

1. 情報フィンガープリントとは何ですか?情報フィンガープリントは、Web ページ内のテキスト情報から特定の情報（キーワード、単語、文、段落、および Web ページ内のそれらの重み）を抽出し、MD5 暗号化などの方法で暗号化して文字列を形成します。情報指紋は人間の指紋のようなものです。コンテンツが異なれば、情報指紋も異なります。

2. アルゴリズムによって抽出される情報は、Web ページ全体の情報ではなく、ナビゲーションバー、ロゴ、著作権、その他の情報など、Web サイトの共通部分を除外した後に残るテキストです (これらは、Web ページの「ノイズ」と呼ばれます)。

セグメント署名アルゴリズム

このアルゴリズムは、特定のルールに従って Web ページを N 個のセグメントに分割し、各セグメントに署名し、各セグメントの情報フィンガープリントを形成します。これらの N 個の情報フィンガープリントのうち M 個が同じである場合 (m はシステムによって定義されたしきい値)、2 つは重複した Web ページであると見なされます。

このアルゴリズムは、小規模で重複した Web ページを判別するのに適したアルゴリズムですが、Google のような大規模な検索エンジンの場合、アルゴリズムの複雑さは非常に高くなります。

キーワードベースのウェブページ複製アルゴリズム

Google などの検索エンジンは、Web ページをクロールするときに次の Web ページ情報を記録します。

1. ウェブページ内に登場するキーワード（中国語単語分割技術）と各キーワードの重み（キーワード密度）

2. 各 Web ページからメタ説明または 512 バイトの有効なテキストを抽出します。

2 番目の点に関しては、Baidu と Google は異なります。Google は、クエリキーワードに関連する 512 バイトがない場合にメタディスクリプションを抽出しますが、Baidu は後者を直接抽出します。使ったことのある人なら誰でもこれを経験しています。

次のアルゴリズムの説明では、いくつかの情報フィンガープリント変数に同意します。

Pi は i 番目の Web ページを表します。

ウェブページ上で最も重みの高いN個のキーワードは集合Ti={t1,t2,...tn}を形成し、対応する重みはWi={w1,w2,...wi}となる。
要約情報はDes(Pi)で表され、最初のn個のキーワードで構成される文字列はCon(Ti)で表され、n個のキーワードをソートして形成された文字列はSort(Ti)で表されます。

上記の情報フィンガープリントは MD5 関数を使用して暗号化されます。

キーワードに基づいて Web ページをコピーするアルゴリズムには、次の 5 種類があります。

1. MD5(Des(Pi))=MD5(Des(Pj))は、要約情報がまったく同じであり、2つのWebページiとjが重複Webページであると見なされることを意味します。

2. MD5(Con(Ti))=MD5(Con(Tj))、2つのウェブページの最初のn個のキーワードの順位と重みが同じ場合、それらは重複ウェブページであると見なされます。

3. MD5(Sort(Ti))=MD5(Sort(Tj))。2 つの Web ページの最初の n 個のキーワードが同じ場合、重みが異なる可能性があり、重複した Web ページと見なされます。

4. MD5(Con(Ti))=MD5(Con(Tj))であり、Wi-Wjの二乗をWiとWjの二乗の合計で割った値がしきい値a未満の場合、両方とも重複したWebページであると見なされます。

5. MD5(Sort(Ti))=MD5(Sort(Tj))であり、Wi-Wjの二乗をWiとWjの二乗の合計で割った値がしきい値a未満の場合、両方とも重複したWebページであると見なされます。

4位と5位の閾値aについては、主に、以前の判定条件では、多くのWebページが依然として偶発的に破損してしまうためです。検索エンジンの開発では、重みの配分比率に基づいて調整を行い、偶発的な破損を防止します。

これは北京大学Skynet検索エンジンの重複排除アルゴリズムです（書籍「検索エンジン-原理、技術、システム」を参照できます）。上記の5つのアルゴリズムを実行する場合、アルゴリズムの効果は選択されたキーワードの数であるNに依存します。もちろん、選択肢を多くすればするほど判断の精度は上がりますが、計算速度も遅くなります。したがって、計算速度と重複排除の精度のバランスを考慮する必要があります。 Skynetのテスト結果によると、約10個のキーワードが最も適切です。

追記

上記は、大規模な検索エンジンが Web ページをコピーする際のすべての側面を網羅しているわけではありません。何らかの補助的な情報フィンガープリント判定が必要です。この記事は、検索エンジン最適化のアイデアとして役立ちます。

【編集者のおすすめ】