←記事一覧

検索エンジンの仕組み — 転置インデックスと TF-IDF を図解で理解する

転置インデックスの構築からTF-IDF/BM25によるランキングまで、検索エンジンの核心技術をインタラクティブな図解で解説する。

検索エンジン転置インデックスTF-IDF情報検索データ構造

はじめに

Google 検索、IDE のコード検索、EC サイトの商品検索——私たちは日々、膨大なデータの中から目的の情報を瞬時に見つけ出す技術の恩恵を受けている。これらすべての裏側に共通する核心技術が検索エンジンだ。

この記事では、検索エンジンの中核をなす 3 つの技術を、インタラクティブな図解とともに解説する。

  1. 転置インデックス — 高速検索を実現するデータ構造
  2. ブーリアン検索 — クエリを集合演算で処理する仕組み
  3. TF-IDF / BM25 — 検索結果をランキングするアルゴリズム

検索エンジンの全体像

まず、検索エンジン全体のパイプラインを確認しよう。

収集ドキュメント解析トークン化索引構築インデックス検索処理クエリ順位付けスコア計算結果返却レスポンス

ドキュメントの収集から結果の返却まで、大きく 6 つのステージに分かれる。本記事では特にテキスト解析、インデックス構築、クエリ処理、ランキングに焦点を当てる。

テキスト解析 — ドキュメントをトークンに分解する

検索エンジンがドキュメントを処理する最初のステップはテキスト解析だ。生のテキストを検索可能な単位（トークン）に変換するパイプラインを見てみよう。

生テキスト"The Cats Were Running!"小文字化"the cats were running"トークン化["the", "cats", "were", "running"]ストップワード除去["cats", "running"]ステミング["cat", "run"]

このパイプラインは以下の処理で構成される。

1. 文字正規化

Unicode 正規化や、大文字から小文字への変換を行う。"The" と "the" を同じトークンとして扱うためだ。

2. トークナイゼーション

テキストを個々の単語（トークン）に分割する。英語では空白による分割が基本だが、日本語のように単語間にスペースがない言語では形態素解析（MeCab、Kuromoji など）が必要になる。

3. ストップワード除去

"the"、"is"、"on" のような高頻度で情報量の少ない単語を除去する。これにより、インデックスのサイズを削減し、検索精度を向上できる。

4. ステミング / レンマタイゼーション

"running" → "run"、"cats" → "cat" のように、単語を原形に戻す。これにより、表記揺れを吸収して検索のリコール（再現率）を高める。

転置インデックス — 検索の心臓部

なぜ転置インデックスが必要か

素朴な方法で全文検索を実装すると、各ドキュメントを先頭から走査してキーワードを探す必要がある。N 個のドキュメントに対して O(N×L)O(N \times L)（LL は平均ドキュメント長）の計算量になり、ドキュメント数が増えると破綻する。

転置インデックス（Inverted Index）は、この問題を解決するデータ構造だ。

Forward Index vs Inverted Index

通常の索引（Forward Index）は「ドキュメント → 含まれる単語」という対応を持つ。

Forward Index:
  D1 → [cat, sat, mat]
  D2 → [cat, dog]
  D3 → [dog, sat, log]

転置インデックスはこの関係を逆転させる。「単語 → その単語を含むドキュメント」という対応だ。

Inverted Index:
  cat → [D1, D2]
  dog → [D2, D3]
  log → [D3]
  mat → [D1]
  sat → [D1, D3]

これにより、あるキーワードを含むドキュメントを O(1)O(1) で参照できる。各単語に紐づくドキュメント ID のリストをポスティングリスト（Posting List）と呼ぶ。

インタラクティブデモ: 転置インデックスの構築と検索

以下のデモで、3つのドキュメントから転置インデックスを構築し、検索クエリを実行する過程をステップバイステップで確認しよう。

転置インデックス構築デモ

ドキュメントから転置インデックスを構築し、検索クエリに応答する過程を見てみましょう。

ドキュメント

D1"the cat sat on the mat"
D2"the cat and the dog"
D3"the dog sat on a log"
1 / 15

ポスティングリストの構造

実際の検索エンジンでは、ポスティングリストにはドキュメント ID だけでなく、以下の情報も含むことが多い。

フィールド用途
ドキュメント ID基本的なドキュメント識別
出現頻度（TF）ランキングに使用
出現位置フレーズ検索、近接検索
オフセットスニペット生成、ハイライト

位置情報を含むインデックスをポジショナルインデックスと呼び、"cat sat" のようなフレーズ検索を可能にする。

クエリ処理 — ブーリアン検索モデル

ユーザーのクエリがトークン化されたら、転置インデックスを使って該当するドキュメントを検索する。最も基本的なモデルがブーリアン検索だ。

AND (積集合)cat →D1D2sat →D1D3∩D1OR (和集合)cat →D1D2sat →D1D3∪D1D2D3ソート済みマージO(n + m)両リストはDoc ID順にソート済みNOT (補集合)例: "cat NOT dog" → {D1,D2} \ {D2,D3} = {D1}

AND（積集合）

"cat AND sat" は、cat のポスティングリストと sat のポスティングリストの積集合（intersection）を求める。両方のリストはドキュメント ID でソート済みなので、2つのポインタを同時に走査するソート済みマージで O(n+m)O(n + m) で処理できる。

def intersect(p1, p2):
    result = []
    i, j = 0, 0
    while i < len(p1) and j < len(p2):
        if p1[i] == p2[j]:
            result.append(p1[i])
            i += 1
            j += 1
        elif p1[i] < p2[j]:
            i += 1
        else:
            j += 1
    return result

OR（和集合）

"cat OR sat" は両方のポスティングリストの和集合で、いずれかのタームを含む全ドキュメントを返す。

クエリ最適化

複数の AND 条件がある場合、最もポスティングリストが短いタームから処理すると、中間結果が小さくなり効率が上がる。これをクエリ最適化と呼ぶ。

ランキング — TF-IDF と BM25

ブーリアン検索は「一致するかしないか」の二値しか返さない。しかし実際の検索では、どのドキュメントがクエリに最も関連するかを順位付けしたい。ここで登場するのが TF-IDF と BM25 だ。

TF-IDF(t, d) = TF(t, d) × IDF(t)TF(t, d)出現頻度（Term Frequency）文書 d 中のターム t の出現数→ この文書でどれだけ出現するか×IDF(t)逆文書頻度（Inverse Doc Freq）log(N / df(t))→ 全文書中でどれだけ珍しいかポイントTF-IDF が高い ＝ この文書に多く出現するが、全体では珍しいターム"the" → IDF低（どこにでもある） vs "アルゴリズム" → IDF高（珍しい）

TF: 出現頻度（Term Frequency）

TF(t,d)=ドキュメント d 中のターム t の出現回数\text{TF}(t, d) = \text{ドキュメント } d \text{ 中のターム } t \text{ の出現回数}

あるタームがドキュメント内で多く出現するほど、そのドキュメントはそのタームに関連する可能性が高い。

IDF: 逆文書頻度（Inverse Document Frequency）

IDF(t)=log⁡10 ⁣(Ndf(t))\text{IDF}(t) = \log_{10}\!\left(\frac{N}{\text{df}(t)}\right)

NN は全ドキュメント数、df(t)\text{df}(t) はターム tt を含むドキュメント数。"the" のようにどこにでも出現する単語は IDF が低く、"algorithm" のように特定のドキュメントにしか出現しない単語は IDF が高い。珍しい単語ほど重要度が高いという直感を数値化している。

TF-IDF スコア

TF-IDF(t,d)=TF(t,d)×IDF(t)\text{TF-IDF}(t, d) = \text{TF}(t, d) \times \text{IDF}(t)

クエリに複数タームがある場合、各タームの TF-IDF を合算してドキュメントの最終スコアとする。

計算デモ

実際に TF-IDF スコアを計算し、ランキングがどう決まるかを見てみよう。

TF-IDF スコア計算デモ

クエリ "cat mat" に対する TF-IDF スコア計算の過程を見てみましょう。

クエリ:"cat mat"N=3
D1[cat, sat, mat]
D2[cat, dog]
D3[dog, sat, log]
1 / 7

BM25: TF-IDF の改良

TF-IDF にはいくつかの問題がある。例えば、あるタームが 100 回出現するドキュメントは 1 回のドキュメントの 100 倍のスコアになるが、そこまでの差があるとは限らない。

BM25（Best Matching 25）は TF-IDF を改良したアルゴリズムで、現代の検索エンジンで広く使われている。

BM25(t,d)=IDF(t)⋅TF(t,d)⋅(k1+1)TF(t,d)+k1⋅(1−b+b⋅∣d∣avgdl)\text{BM25}(t, d) = \text{IDF}(t) \cdot \frac{\text{TF}(t,d) \cdot (k_1 + 1)}{\text{TF}(t,d) + k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)}

2 つのパラメータが鍵となる。

  • k1k_1（通常 1.2）: TF の飽和を制御する。TF が増えても TF 飽和因子 TF⋅(k1+1)TF+K\frac{\text{TF} \cdot (k_1+1)}{\text{TF}+K} は (k1+1)(k_1 + 1) に漸近し、際限なく増加しない
  • bb（通常 0.75）: 文書長の正規化。長いドキュメントは多くの単語を含むため TF が高くなりがちだが、bb によってこの偏りを補正する

実践的な話題

インデックス圧縮

ポスティングリストはドキュメント ID のソート済み整数列なので、差分符号化（delta encoding）と可変長バイト符号（Variable Byte Encoding）を組み合わせて効率的に圧縮できる。

元のリスト:  [101, 105, 108, 120]
差分符号化:    [101,   4,   3,  12]  ← 小さな数値になる
可変長バイト:  バイト列に効率的にパック

分散検索

大規模な検索エンジンでは、インデックスを複数のノードにシャーディング（分割配置）する。クエリは全シャードに配信され（scatter）、各シャードの結果を集約（gather）して最終ランキングを生成する。この scatter-gather パターンは Elasticsearch などで広く使われている。

Apache Lucene と Elasticsearch

Apache Lucene は、転置インデックスベースの全文検索ライブラリのデファクトスタンダードだ。Java で実装されており、内部で以下の最適化が行われている。

  • セグメント化: インデックスを不変のセグメントに分割し、書き込みと読み取りを並行化
  • スキップリスト: ポスティングリストの高速スキャン
  • ブロック符号化: SIMD を活用した高速なポスティングリスト処理

Elasticsearch は Lucene 上に構築された分散検索エンジンで、REST API、クラスタリング、リアルタイムインデキシングを提供する。

まとめ

検索エンジンの核心技術を 3 つの柱で見てきた。

  1. 転置インデックス: 「ターム → ドキュメントリスト」のデータ構造で O(1)O(1) ルックアップ
  2. ブーリアン検索: ポスティングリストの集合演算による高速なクエリ処理
  3. TF-IDF / BM25: 出現頻度と文書中での希少性を組み合わせた関連度スコアリング

私たちが体験する「一瞬で結果が返る」検索は、これらの技術が組み合わさって初めて実現している。次にテキストボックスに検索ワードを入力するとき、その裏側で転置インデックスが参照され、BM25 がドキュメントをランキングしている——この記事がそのメカニズムを想像する助けになれば幸いだ。

参考文献