インターネット検索エンジンのアルゴリズム-インデックス作成と正規化

今日のレッスンでは、インターネット上の文書のインデックス付けと正規化について見ていきます。

インデックス作成

インデックスの作成は、インデクサと呼ばれるコンポーネントが行う。これは、ダウンロードしたデータ（クローラーがダウンロードしたデータ）を検索するための特別なデータ型であるバレルにするための専用プログラムです。

インデックスの問題は、文書を「スマートに」閲覧できないことですが、シーケンシャルリーディング（最初から最後まで全文を読むこと）は避けられないので、厳しい訓練が必要で、検索エンジンはこの活動のために最も強力なサーバーを使用しています。検索プロセスにおいて、プレーンテキストがインデックスになるインデックス作成ほど要求の厳しいタスクはない。

例えば、Wikipediaからダウンロードした猫に関するページ。インデクサはページの完全なテキストを取得し、不要なもの（ユーザー制御メニュー、広告、フッターなど）を削除し、ページを解析してプレーンテキストを取得しなければならないのです。例えば、こんな文章が考えられます。

家猫（Felis silvestris f. catus）は、野生の猫を家畜化したもので、数千年にわたり人間のコンパニオンとして活躍してきました。野生の近縁種と同様、小型ネコ亜科に属し、その代表的な存在である。狩りに最適なしなやかで筋肉質な体、鋭い爪と歯、優れた視力、聴力、嗅覚を持っている。

Wikipedia】(http://cs.wikipedia.org/wiki/Ko%C4%8Dka_dom%C3%A1c%C3…)より抜粋。

検索エンジンは今、テキストから個々の単語を解析し、個々の樽に書き込んでいる。しかし、バレルの書き込みを直接行うことはできないので（主に各バレルは多くのコピーで存在し、また検索の妨げになるため）、将来のバレルがどうあるべきかの要件リストを作成し、これを一時メモリに格納する。この場合、このようなリストは次のようになります（重要でない単語は無視するか、ストップワードとしてマークすることができます）。

ドキュメントID｜ワード｜ポジション｜タイプ｜｜｜。
1｜ネコ｜1｜ノーマル｜｜｜。
1｜国内｜2｜通常｜3｜海外
1｜フェリス｜3｜ノーマル
1｜Is｜7｜StopWord｜。
1｜家畜｜8｜ノーマル｜｜？

このようなリストは巨大（原文よりはるかに大きい）だが、それでも検索が速いのは、すべての文章を順次読む必要がなく、各列のインデックスで検索できることと、あるページの単語が次々と行でソートされるためである。

ある程度の時間が経過すると（あるいはある程度の数の文書が完成すると）、インデクサはこの要求リストの構築作業を止め（将来のバレルのために）、再びデータを読み込んで個々のバレルを再構築し始めます（このリストには、すでに作業中のバレルにある古いレコードも含まれます）。既知のアドレスから新しいレコードが追加された場合は、この処理で更新され、新しい文書については、そのレコードが含まれるようになります。

このようにして、インデクサは再びリストを見ながら、すべての要素を含む新しいバレルをゆっくりと作成し（前の章の例で示したものと同じように見えるでしょう）、すべてのバレルが完成したら、個々の検索サーバに送信されます。サーバー上のバレルを更新するのは時間がかかるので（主に膨大なデータを移動するため）、この作業中はサーバーを利用できず、別のサーバーで時間をずらしてデータを更新しているのです。この結果、例えば、ユーザーごとに異なる調剤サーバで検索を行うため、ユーザーによっては異なる結果を得ることができる（負荷分散による）。アップデートが完了すると、すべてが元通りになり、すべてのユーザーがすべてのドキュメントを平等に見つけることができます。

インデックス作成作業はどの検索エンジンにとっても重要であり、それを最も頻繁に、最も注意深く行っているのは、インターネットを最もよく見ている検索エンジンであると言えるでしょう。Googleは数時間に一度、Seznamは週に一度、この操作を行っています（しかもデータ量は100万倍も少ない）。

ドキュメントの正規化

全文検索エンジンの当初の設計では、インターネットは常に新しいコンテンツを生み出すメディアであったため、正規化のようなものは必要なかったのです。しかし、時間の経過とともに重複（同じコンテンツが複数の異なるURLで表示されること）が発生し、検索エンジンはこれに対応する必要がある。その典型的な例が、多くの記事を持つWikipediaである。他のページの作者がこれらのテキストを（部分的に、あるいは完全に）引き継ぐことで、重複が発生することがあります。しかし、ほとんどの場合、ソースページの方が盗作されたページよりもはるかに高いランク（リンク品質）を持っているので、これは問題ではありませんが、時には、海賊版を犠牲にしてオリジナルを劣化させることが起こり得ます。

検索エンジンはこの悪癖に適応しなければならず、特定のページをインデックスから「削除」すると理解できる「正規化」という用語が生まれました。ちなみに、これによってインデックスが小さくなり、検索エンジンは不必要に同じコンテンツをずっとクロールする必要がなくなります。

重複は、各検索エンジンによって内部的に大きく2つに分類されます。

ナチュラルデュプリケート

これらは、インターネットの自然な振る舞いと、その特性によって生み出されるものです。

例えば、URL http://mathematicator.cz は、URL http://www.mathematicator.cz や http://mathematicator.cz/index.php と同じ内容を持つ可能性が高いです。これは、Apacheサーバ（およびインターネット全般）の標準的な動作だからです。

自然な重複が見つかった場合、検索エンジンは「カノニカルセット」を作成し、その中から検索で目立つ代表的な1ページを選び出す。リンクがcanonicalセットからいずれかのページにつながる場合、そのランクは自動的にメインの代表に渡されます。

このセットを作成し、サイト上で正しくリダイレクトを設定することで、検索エンジンがサイトをよく見るようになり、主要な代表がよりよく選択されるようになることが多いのです。

盗用につながる重複部分

インターネット上では「盗用」が問題になっていますが、盗用があること自体はそれほど問題ではありません。また、あるクエリに対して、同じテキストを含む複数のページを発見したことはありませんか？これはまさに、検索エンジンが防ごうとしている行動です。

最大の問題は、どのページが元ネタなのかを判断することであり、それを機械で行うことである。この場合も、検索エンジンは類似したページをすべて正規化し、その中から主要な代表ページを選択する。ソースが異なるドメインの場合、状況を自然な重複として見ることはできず（そしてどの候補も選ばれる）、すべてのページを定性的に評価し、最適なものを客観的に選ぶ必要があります - そして理想的にはコンテンツのオリジナルソースが選ばれるのです。

検索エンジンは、ドメイン全体のランクや、ある文書へのリンクネットワークの強さに基づいて判断することが多いのですが、これさえもかなり信頼性の低い方法です。2つ目の要因も、通常は文書の作成（索引付け）時期である。そのため、各検索エンジンは、どのページが頻繁に新しいコンテンツを生み出しているかを把握し、それらのページを頻繁に訪問することで、新しいページにすぐに気づき、その結果、他のページを代理として選択することがないように理想的です。

この選択の仕組みの詳細な説明は、本稿の範囲を超えており、一冊の本の題材となり得るものである。