インターネット検索エンジンのアルゴリズム - 並べ替えと記述子

インターネット検索エンジンの原理に関するこのレッスンでは、検索エンジンがどのように結果を分類し、記述し、評価するのかを理解します。

結果の並べ替え

現在、検索サーバーに用意されている完成品の樽を想像してみよう。最初の検索クエリは、ユーザーから送られてきたものです。ここで、最初の「大まかな」ソートを行い、さらに洗練されたものにします。

次のような入力クエリの例を見てみましょう。

[O (and) pejskovi (and) a (and) kočičce]

そう、これは検索サーバーがユーザーから処理されたクエリを受け取り、あとは結果が返ってくるのを待つという形だ。合計で300ミリ秒以下なので、とても速いです :)

最初のステップでは、将来の結果ID（候補とも呼ばれる）と実行すべきオペレーションを満載したバレルを取得する。この取得されたバレルは、場合によっては完全ではなく、サーバーがある所定の時間間隔（タイムアウトとも呼ばれる）でディスクから読み取ることができた値のみを含む。 例えば、次のような数列（あらかじめ部分的にソートされている）を取得することができる。

ここで、すべての集合の粗交差を行い、すべてのバレルで同じである文書IDのリストを得ることができる。実際には、最短のリストを通過して、それ以外を検索します。

すべての樽に共通するIDは「19, 42, 58」なので、未来の結果ページには、まだ知られていない何らかの順序で3つのアイテムが含まれています。書類をIDで見るのは、これが膨大なデータ量を節約するためです。しかし、検索結果では、一般的にユーザーに対して文書番号を羅列するのではなく、文書のタイトル（見出し）、説明文、URLなどの情報を羅列することが望まれる。これは、"descriptor "コンポーネントによって提供される。

ディスクリプタ

前章から、今後の成果の候補が残されています。システム的に、つまり検索エンジンがインデックスで順次ランク付けしたように、ソートされた形で検索したのです。このとき、もはやビッグデータの逐次読み込みはできず、ある種のリレーショナルデータベースを逐次巡回して、ユーザーにとってより分かりやすい別のタイプのソートのための追加情報を探し出さなければならないのだ。

例えば、データベースのスライスは次のようになります。

関連性の算出

最後に、回答の妥当性を計算する。ほとんどの結果では、関連性を1つの数値で表し、その数値で結果を並べ替える固定半径で十分である。順位によって、結果は再びいくつかのグループに「大まかに」分類され（グループの数は順位の分散に依存する）、これらのグループはさらに作業される。

最高ランクのグループが最初に取得されます。多くの場合、これだけで結果の1ページ目がソートされるので、それ以外のことには対処する必要がありません。しかし、複数の異なる文書が同じランクを持つ場合、より詳細な分析を行い、ページのランク付けに役立つ補助ランクを追加で計算する必要があります。追加ランクは、例えばリンクの質、文書の古さ、タイトルの長さ、URLの「ルック＆フィール」、その他多くの要素になります。

結果をユーザーに返す

万歳!結果が出たので、あとはユーザー向けにページをレンダリングするだけです。サーバーは、あらかじめ用意されたテンプレートに結果をはめ込み、ページの周囲に広告バナーを挿入して、ユーザーにページを送り返す。同時に、結果をキャッシュするなど、他の補助的な処理も行うことができる。近い将来、誰かが同じクエリを検索した場合（例えば、過去1時間以内）、結果は再び検索されることはなく、一時記憶から読み込まれるだけです。これは、しばしば検索エンジン全体のパフォーマンスの向上に役立ちます。

結論とセマンティクスへの洞察

この論文は、検索エンジンの内部動作の基本原理と、理論上無限の数の文書を、依然として合理的な時間で検索する方法を説明することを意図したものである。これらは、最高のプログラミングチームが何年もかけて開発した膨大な数学的最適化である。

その詳細については、本稿では割愛させていただきます。また、他のほとんどのステップは、検索エンジンの企業秘密であるため、どの検索エンジンも詳細を説明していないという事実が、全体を複雑にしています。

また、検索エンジンはいまだにページの内容や結果の意味を理解しておらず、生の計算能力と人々が質の高いテキストにリンクする能力に基づいた統計的計算に過ぎず、このシステムもかなり脆弱であることも重要です（卑劣なウェブマスターが検索クエリに無関係なコンテンツを強制的に掲載する「Google爆弾」の例を見てみましょう）。

この問題は、すべての検索エンジンが徐々に統合しようとしている人工知能によって部分的に解決されるはずである。しかし、これは簡単なことではなく、ほとんどが統計的な計算方法の改良に過ぎないため、まだ遠い未来の音楽である。Googleのグラフ検索を例にとると、これはクエリに直接答えようとする（ただし、その内部構造としては、やはりあらかじめ定義された知識ベースを検索しているだけである）。

ですから、次にあなたがお気に入りの検索エンジンにクエリを発行するときは、検索クエリに対する上位10文書を見つけるために、検索エンジンがどれだけの仕事をし、ディスクから何TBのデータを読み込まなければならなかったかを思い出してください。

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Kontakt