検索エンジンはなぜ一瞬で見つけられるのか

クローラの正体は超大規模なHTTPクライアントでした。上級では「どう賢く回り、どう索引へ落とすか」を見ます。

• フロンティア ※1 — 未訪問URLの巨大な待ち行列。ただ古い順ではなく、更新頻度や重要度で優先度を付けて取り出す
• 重複除去 — URLを正規化し、本文のハッシュで同一コンテンツを弾く。ミラーやパラメータ違いの重複に持ち時間を奪われないため
• 差分クロール — 変わっていないページは再取得を控え、変化しやすいページを厚く回る
• レンダリング待ち — JSで中身を組み立てるページは、ブラウザ 相当の実行工程が要る。素のHTML取得より桁違いに重いので別枠の順番待ちになる

集めた文書は、バッチと増分で索引に落とします。大量の文書からセグメント（部分索引）を作り、それらをマージして大きな索引へ育てる、という積み上げ方が定番です。

登場人物メモ（※の説明）:

• ※1 フロンティア — これから訪問するURLの管理キュー。優先度付けが「クロールバジェット」の使い方を決める

中級で「単語→文書ID一覧」と紹介した索引を、もう一段開けます。単語ごとに紐づく文書の並びを ポスティングリスト ※1 と呼びます。

• ポスティングの中身 — 文書IDだけでなく、出現回数（後の採点用）と出現位置（フレーズ検索用）を添える
• 前処理の三点 — トークナイズ ※2（語に切る）→ 正規化（大文字小文字・全角半角・表記揺れを揃える）→ ステミング ※3（活用や語尾を語幹に寄せる）
• 辞書と圧縮 — 語→ポスティングの先頭を引く辞書を別に持ち、文書IDは差分（ギャップ）符号化などで圧縮して巨大化を抑える

登場人物メモ（※の説明）:

• ※1 ポスティングリスト — ある単語を含む文書の並び。転置インデックスの本体
• ※2 トークナイズ — 本文を索引の単位（トークン）に切り分ける処理。日本語では形態素解析がこれを担う
• ※3 ステミング — 「走る／走った／走れば」を同じ語幹に寄せる正規化。英語の running→run のような揺れの吸収

絞り込んだ候補に順位を付ける採点を、古典から見ます。

• TF-IDFの発想 — その文書に多く出る語（TF）ほど効き、世間では珍しい語（IDF）ほど効く、という重み付け。中級で触れた「関連度」の土台
• BM25 — TF-IDFの弱点を補う定番。出現回数の効果を飽和させ（同じ語を1万回書いても青天井にはならない）、文書長で正規化する（長い文書がただ有利になるのを防ぐ）
• 学習型ランキング — 現代の検索は、これら多数の特徴量を機械学習モデルで合成し、クリック傾向なども取り込んで並べる

素朴なTFの弱点（詰め込みが有利）を、BM25の飽和と正規化がどう塞ぐか——ここが古典的採点の要点です。

複数語のクエリは、ポスティングリストの集合演算として処理されます。

• AND — 各語のポスティングリストの積（共通する文書ID）を取る
• OR — 和を取る
• フレーズ検索 — 語が索引に持つ出現位置を使い、「隣り合っているか」を確かめる。位置がなければ「順不同で両方含む」までしか言えない
• 高速化 — ソート済みリストを飛ばし読みするスキップリストや、上位k件だけ確定できれば全走査を打ち切る枝刈りで、巨大なリストの積和を速く済ませる

Web検索特有の採点が、リンク構造の解析です。

• リンク＝推薦 — 信頼あるページから多くリンクされるページは、それ自体も信頼できるとみなす
• 反復計算 — 全ページの評価を、リンクをたどって少しずつ配り合い、値が落ち着くまで繰り返して求める（ランダムに links をたどり歩く閲覧者のモデル）
• スパム耐性 — 語の詰め込みだけでは上がらない軸を足すことで、本文操作だけのスパムに強くなった。もっとも、リンク売買という新たないたちごっこも生んだ

本文の関連度（BM25など）と、この外部からの評価を合成するのが、Web検索のランキングの骨格です。

何十億という文書は、1台の索引には収まりません。分割して並列に引くのが基本です。

• シャーディング — 文書集合を複数のシャードに分け、各シャードが自分の担当分の完全な転置インデックスを持つ
• 分散クエリ — 検索語を全シャードへ同時に投げ、各シャードで上位k件を出し、集約役がそれらをマージして最終順位を作る
• レプリカ — 各シャードを複製して、故障への冗長性と読み取りスループットを稼ぐ
• キャッシュ — よく出る検索結果や、頻出語のポスティングリストを キャッシュ して往復を減らす

同じ「索引」でも、DBの B木索引 と全文検索の転置インデックスは狙いが違います。

• B木索引 — 列の値をソートして並べる構造。等値・前方一致・範囲（WHERE age > 30 や LIKE 'ab%'）に強い。ただし本文の途中に出る語では引けない
• 転置インデックス — 本文を語に割り、語の側から文書を引く。だから「文章中のどこかにこの語がある文書」を全文から即座に集められる

DBで LIKE '%語%' が遅い（索引が効かず全表走査になりがち）のに対し、全文検索がそれを一撃で返せるのは、この索引の向きの違いが理由です。用途に応じて、両者は使い分けられます。