全文検索の内部：逆引きインデックスとスコアリング(BM25)

転置インデックスの二層構造

全文検索の基礎は 全文検索 で触れた 転置インデックス（inverted index） ですが、その内部は単純な「語 → 文書一覧」の表ではありません。実装は二つの層に分かれます。

• term dictionary（辞書）: 索引対象の全語（term）をソート済みで保持し、各語からポスティングリストの位置へポインタを持つ。語の数は文書数より遥かに少なく、ここを引いて目的の語に到達する。
• posting list（ポスティングリスト）: 各語ごとに、その語を含む文書 ID（doc id）を 昇順に並べた列。多くの場合さらに語の出現頻度や出現位置を併せ持つ。

term dictionary は、Lucene では FST（有限状態トランスデューサ）で圧縮され、共通接頭辞を共有して数百万語でもメモリに載るよう設計されます。検索はまず辞書で語を引き、得たオフセットからポスティングリストを読む、という二段で進みます。

ポスティングリストと差分圧縮

ポスティングリストは doc id の昇順列なので、値そのものではなく 隣との差（delta） を記録すると小さくできます。

元の doc id 列 : 5, 9, 13, 28, 31
delta 符号化   : 5, 4,  4, 15,  3   ← 前の値との差だけを保存

差は元の値より小さいため、可変長整数（VByte）や PForDelta、Roaring Bitmap といった手法で少ビットに詰められます。索引が小さいほどキャッシュに載りやすく、I/O も減るため、圧縮は速度のためにも効きます。複数語の AND 検索は、各語のポスティングリスト（いずれも昇順）を同時に前進させる マージ結合 で交差を求めます。a AND b なら両方に出る doc id だけを残す処理です。

スキップリストでマージを加速

単純なマージは両リストを端から舐めるため、片方が極端に短いと無駄が出ます。たとえば 稀な語 AND ありふれた語 では、ありふれた語の長大なリストを一件ずつ進めるのは非効率です。そこで各ポスティングリストに スキップリスト（skip list） を重ねます。

一定間隔ごとに「この先 K 件先の doc id とその格納位置」を記録しておき、目標の doc id がまだ先なら途中を読み飛ばします。スキップ間隔を sqrt(リスト長) 程度に取ると、交差判定が線形から準線形に改善します。

TF-IDF：頻度と希少性の積

ヒットした文書をどの順に並べるか、それが スコアリング です。古典的な指標が TF-IDF で、二つの直感を掛け合わせます。

• TF（term frequency）: 文書 d 中で語 t が多く出るほど、その語に関連が深い。
• IDF（inverse document frequency）: 多くの文書に出る語（「の」「する」等）は識別力が低く、稀な語ほど重い。

idf(t) = log( N / df(t) )      N=総文書数, df(t)=t を含む文書数
score(d, q) = Σ_(t∈q) tf(t,d) × idf(t)

df が大きい（ありふれた）語ほど idf は 0 に近づき、スコアへの寄与が小さくなります。これにより「珍しい検索語の一致」が「ありふれた語の一致」より高く評価されます。

BM25：飽和と文書長の正規化

TF-IDF には二つの弱点があります。TF が線形なので語が 100 回出る文書が 10 回の文書より単純に 10 倍重くなること、そして長い文書ほど語が増えて不当に有利になることです。これを補正したのが BM25（Best Matching 25） で、現代の検索エンジンの事実上の標準です。

score(d,q) = Σ_(t∈q) idf(t) ×
             ( tf(t,d) × (k1 + 1) ) /
             ( tf(t,d) + k1 × (1 - b + b × |d| / avgdl) )

  k1   : TF の飽和を制御 (一般に 1.2〜2.0)
  b    : 文書長正規化の強さ (0〜1、既定 0.75)
  |d|  : 文書 d の長さ(語数)
  avgdl: 全文書の平均長

要点は二つです。第一に、分母に tf を含む形のため TF は 飽和 します。語が増えるほどスコアは伸びますが頭打ちになり、k1 がその曲がり具合を決めます。第二に、b による 文書長正規化 で、平均より長い文書（|d| / avgdl が 1 より大きい）はスコアが割り引かれます。b=0 なら長さを無視、b=1 なら完全に正規化します。

位置情報とフレーズ・近接検索

AND 検索は語の共起しか見ないため、"機械 学習" というフレーズを「機械」と「学習」が離れて出る文書とは区別できません。フレーズ検索や近接検索を実現するには、ポスティングリストに doc id・頻度だけでなく 語の出現位置（position） を持たせます。

term "学習" の posting:
  doc 7 : freq=3, positions=[12, 45, 88]
  doc 9 : freq=1, positions=[5]

フレーズ "機械 学習" は、両語のポスティングを取り、同じ文書内で「機械」の位置 p の直後 p+1 に「学習」があるかを位置リストの突き合わせで確認します。近接検索（NEAR/3 等）は、その位置差が指定値以下かを判定するだけです。位置を持つ索引（positional index）は doc id だけの索引よりサイズが増えますが、フレーズ・近接という重要な検索を可能にします。

索引としての位置づけ

転置インデックスは B+Tree インデックス と同じ「索引」ですが、向く問題が異なります。B+Tree は値の順序と範囲に強く一意制約や主キーに使われ、転置インデックスは「語を含むか」の集合演算とスコア順位付けに特化します。

転置インデックスのもう一つの工夫は、存在しない語の問い合わせを早く弾く前段フィルタです。語が辞書になければポスティングを読むまでもなく空集合と分かり、確率的に存在を判定する ブルームフィルタ が併用されることもあります。スコア順 top-k だけ欲しい場合は、BM25 の上限を見積もって低スコア文書を打ち切る WAND/Block-Max WAND といった枝刈りで、ポスティング全走査を避けます。索引を引いて クエリ最適化 と同じく「読まずに済ませる」のが、全文検索を速くする一貫した発想です。