←記事一覧

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

検索エンジンがテキストをトークンに分解し、転置インデックスで候補を絞り込み、TF-IDF/BM25 で順位を付けるまでを、インタラクティブな図解で解説する。

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

はじめに

Google 検索、IDE のコード検索、EC サイトの商品検索は、大量のドキュメントの中からクエリーに合うものを短時間で探して並べる。どれも検索エンジンの同じ基本技術の上に成り立っている。

その中心となるのは次の 3 つの技術で、この記事ではそれぞれをインタラクティブな図解で説明する。

  1. 転置インデックス — 単語から、それを含むドキュメントを引くデータ構造
  2. ブーリアン検索 — クエリーを集合演算で処理する仕組み
  3. TF-IDF / BM25 — 検索結果に順位を付けるスコア計算
動画で読む4:20合成音声ナレーション・字幕付き
文字起こしを表示

検索窓に言葉を入れると、なぜ一瞬で結果が返るのでしょうか。その裏側にある、転置インデックス、ブーリアン検索、TF-IDFとBM25を見ていきます。

検索エンジンの流れは、ドキュメント収集から結果の返却まで、大きく6段階です。この記事では特に、テキスト解析、インデックス構築、クエリ処理、ランキングに注目します。検索エンジンは生の文章を検索しやすい形に変えておき、クエリが来たら必要な部分だけを読みに行きます。

ドキュメントを処理する最初のステップはテキスト解析です。文章を、検索可能な単位であるトークンへ分解します。文字正規化でUnicodeや大文字小文字をそろえ、英語なら空白を手がかりに単語へ分けます。日本語のように空白がない言語では、MeCabやKuromojiのような形態素解析が必要です。

その後、高頻度で情報量の少ないストップワードを取り除きます。ステミングやレンマタイゼーションで、runningをrun、catsをcatのように原形に戻し、表記揺れを吸収します。こうして、ただの文字列だったドキュメントが、検索に使えるターム列へ変わります。

素朴な全文検索は、すべてのドキュメントを先頭から走査します。N個のドキュメントと平均長Lに対して、計算量はO(N×L)になり、規模が増えると破綻します。転置インデックスは、文書からタームを探すのではなく、タームから、それを含むドキュメントのリストへ直接たどります。

たとえばcatはD1とD2、satはD1とD3、という対応をポスティングリストとして持ちます。ターム辞書がハッシュなら期待O(1)、探索木ならターム数Tに対してO(log T)で、目的のリストが見つかります。実際のリストには、文書IDだけでなく、出現頻度、位置、オフセットも入ることがあります。

クエリもトークン化したら、ブーリアン検索ではポスティングリストを集合として処理します。cat AND satなら、2つのリストの積集合なので、D1だけが残ります。リストは文書IDでソート済みなので、2つのポインタで同時に進めればO(n+m)です。

cat OR satなら和集合になり、どちらかのタームを含むドキュメントがすべて候補になります。AND条件が複数あるときは、最も短いポスティングリストから処理します。中間結果を小さく保つことが、クエリ最適化の基本です。

ブーリアン検索は一致するかどうかだけを返します。実際には、結果に順位が必要です。TF、つまり出現頻度は、あるタームが文書内に何回出たかを数えます。IDFは、全文書数Nを、そのタームを含む文書数dfで割った値の常用対数です。TF-IDFは、この出現頻度と希少性を掛け合わせ、複数タームなら合算します。

ただしTF-IDFでは、100回出たタームは1回のときの100倍のスコアになりますが、関連度も100倍とは限りません。BM25は、TFが増えても効果が飽和するようにし、長い文書の有利さも補正します。飽和を決めるk1は一般に1.2から2.0、Luceneのデフォルトは1.2、長さ補正のbは一般に0.75です。

実用では、ポスティングリストはソート済みの文書IDなので、差分符号化と可変長バイトで圧縮できます。大規模検索ではインデックスをシャードに分け、クエリを全シャードへscatterし、結果をgatherして集約します。Luceneは内部で、セグメント化、スキップリスト、ブロック符号化により、インデックスの読み書きを最適化しています。

一瞬で返る検索は、転置インデックス、集合演算、ランキングが組み合わさって実現しています。記事では、転置インデックスの構築と検索、TF-IDFの計算を、ステップごとに試せるデモがあります。

検索エンジンの全体像

収集ドキュメントテキスト解析トークン化インデックス構築クエリー処理ランキングスコア計算結果返却レスポンス

検索エンジンの処理は、ドキュメントの収集から結果の返却まで大きく 6 つのステージに分かれる。この記事では、そのうちテキスト解析、インデックス構築、クエリー処理、ランキングを扱う。

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

検索エンジンは、ドキュメントを受け取るとまずテキスト解析で生のテキストを検索可能な単位（トークン）に変換する。

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

このパイプラインは次の 4 つの処理からなる。

1. 文字正規化

Unicode 正規化や、大文字から小文字への変換を行う。これで "The" と "the" が同じトークンになる。

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

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

3. ストップワード除去

"the"、"is"、"on" のように出現頻度が高く、ドキュメントを区別する情報の少ない単語を除去する。インデックスが小さくなり、検索精度も上げられる。

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

"running" → "run"、"cats" → "cat" のように、単語を原形に戻す。語形が違っても同じ語として一致するので、検索のリコール（再現率）が上がる。

転置インデックス — 単語からドキュメントを引く

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

素朴に全文検索を実装すると、各ドキュメントを先頭から走査してキーワードを探すことになる。NN 個のドキュメントに対して計算量は 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]

インデックスに登録された各単語（ターム）に紐づくドキュメント ID のリストをポスティングリスト（Posting List）と呼ぶ。ハッシュベースのターム辞書なら、あるキーワードのポスティングリストを期待 O(1)O(1) で見つけられる（TT 個のタームを持つ木/FST 型の辞書では O(log⁡T)O(\log T)）。実際のクエリー時間の大半は、見つけたポスティングリストの読み出しと結合にかかる。

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

次のデモでは、3 つのドキュメントから転置インデックスを構築し、検索クエリーを実行するまでを 1 ステップずつ追える。

転置インデックスの構築と検索

3つのドキュメントから転置インデックスを1ステップずつ構築し、それを使って "cat" と "sat" の両方を含むドキュメントを探します。

ドキュメント

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

3つのドキュメント D1〜D3 から転置インデックスを構築します。

1 / 15

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

実際の検索エンジンでは、ポスティングリストにドキュメント ID 以外の情報も持たせることが多い。

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

位置情報を含むインデックスをポジショナルインデックスと呼ぶ。単語の位置が分かるので、"cat sat" のようなフレーズ検索ができる。

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

クエリーをドキュメントと同じ手順でトークン化したら、転置インデックスで該当するドキュメントを探す。最も基本的なモデルがブーリアン検索だ。

AND (積集合)cat →D1D2sat →D1D3∩D1OR (和集合)cat →D1D2sat →D1D3∪D1D2D3ID 順に並んだリストのマージO(n + m)n, m: 各リストの長さNOT (補集合)例: "cat NOT dog" → {D1,D2} \ {D2,D3} = {D1}

AND（積集合）

"cat AND sat" は、cat と sat のポスティングリストの積集合（intersection）を求める。どちらのリストもドキュメント ID でソート済みなので、2 つのポインターで両リストを先頭からたどるマージにより、O(n+m)O(n + m)（nn、mm は各リストの長さ）で処理できる。

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 "algorithm" → 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 が高い。少数のドキュメントにしか出てこない単語ほど、ドキュメントを区別する手がかりになる。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" について、3つのドキュメントの TF-IDF スコアを1ステップずつ計算し、順位を付けます。

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

3つのドキュメント（N=3、ストップワード除去済み）について、クエリー "cat mat" に対する TF-IDF スコアを計算します。

1 / 7

BM25: TF-IDF の改良

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

BM25（Best Matching 25）は TF-IDF を改良したスコアで、多くの検索エンジンで使われている（Lucene では 6.0 以降のデフォルト）。

IDFBM25(t)=log⁡ ⁣(1+N−df(t)+0.5df(t)+0.5)\text{IDF}_{\text{BM25}}(t) = \log\!\left(1 + \frac{N - \text{df}(t) + 0.5}{\text{df}(t) + 0.5}\right) BM25(t,d)=IDFBM25(t)⋅TF(t,d)⋅(k1+1)TF(t,d)+k1⋅(1−b+b⋅∣d∣avgdl)\text{BM25}(t, d) = \text{IDF}_{\text{BM25}}(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 つある。∣d∣|d| はドキュメント dd の長さ（ターム数）、avgdl\text{avgdl} は全ドキュメントの平均の長さだ。

  • k1k_1（一般に 1.2〜2.0、Lucene のデフォルトは 1.2）: TF の飽和を制御する。K=k1⋅(1−b+b⋅∣d∣avgdl)K = k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right) とおくと、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）して最終ランキングを作る。Elasticsearch などもこの scatter-gather 方式を使っている。

Apache Lucene と Elasticsearch

Apache Lucene は Java で書かれた転置インデックスベースの全文検索ライブラリーで、この分野の事実上の標準だ。内部では次のような最適化が行われている。

  • セグメント化: インデックスを不変のセグメントに分割し、書き込みと読み取りを並行して進められるようにする
  • スキップリスト: ポスティングリスト内を飛ばし読みして、積集合の計算などを速くする
  • ブロック符号化: ポスティングリストをブロック単位で符号化し、SIMD で高速に処理する

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

まとめ

転置インデックスは「ターム → ポスティングリスト」の対応を持ち、ターム辞書の引き当てはハッシュなら期待 O(1)O(1)、木/FST なら O(log⁡T)O(\log T) で済む。ブーリアン検索は、ソート済みのポスティングリスト同士の集合演算でクエリーを処理する。TF-IDF と BM25 は、タームの出現頻度と、そのタームを含むドキュメントの少なさを組み合わせて関連度を計算し、結果に順位を付ける。

検索ボックスにキーワードを入れてすぐに結果が返ってくる裏では、こうした転置インデックスの参照とスコア計算が行われている。

参考文献