最適化のアイデア: 検索エンジンアルゴリズムのコピーウェブページ

検索エンジンは通常、次のような考え方に基づいて重複した Web ページを判断します。

各 Web ページに対して、一連の情報フィンガープリントが計算されます。2 つの Web ページに一定数の同一の情報フィンガープリントがある場合、2 つの Web ページのコンテンツの重複が非常に多い、つまり 2 つの Web ページに重複したコンテンツがあると考えられます。

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

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

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

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

1. 情報フィンガープリントとは何ですか?

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

2. アルゴリズムによって抽出された情報はウェブページ全体のものではない

代わりに、ナビゲーション バー、ロゴ、著作権情報などの 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 つの Web ページの最初の n 個のキーワードのランキングとそれらの重みが同じ場合、それらは重複した Web ページであると見なされます。

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個のキーワードが最も適切です。

元のタイトル: 最適化のアイデア: 検索エンジン アルゴリズムのコピー ウェブ ページ

キーワード: 検索エンジン