全文検索エンジンの仕組み - 転置インデックスとBM25を実装して確かめる

検索ボックスに「転置インデックス」と打ち込むと、数千万件の文書から関連する順に並んだ結果が数十ミリ秒で返ってきます。この裏側にあるのが転置インデックスというデータ構造と、BM25 というスコアリング関数です。この記事では、Python で最小の転置インデックスを実際に組み立て、BM25 のスコアを手で計算し、posting list の圧縮率や LIKE との速度差を自分の手元で実測しながら、全文検索エンジンの中身を順に開けていきます。

一次ソースは Apache Lucene の公式 javadoc、PostgreSQL / MySQL / SQLite の公式ドキュメント、Elastic 公式です。数値やバージョンは確認できたものだけを書き、確認できなかったものは「未確認」と明示します。

なお、テキストの中からパターンを走査する文字列検索アルゴリズム入門（KMP・Boyer-Moore）と、値から行を引くデータベースインデックス入門（B-tree）は、この記事とは別レイヤの話です。本記事は「語から文書を引く索引」に絞ります。

LIKE では届かない領域

まず、なぜ LIKE '%キーワード%' ではダメなのかを押さえます。PostgreSQL 公式ドキュメントは、LIKE や正規表現による検索の欠点を3つ挙げています。

1. 言語的な処理がない。satisfy で検索したときに satisfies を含む文書を取りこぼす（原文では「Regular expressions are not sufficient because they cannot easily handle derived words」）
2. 順位付け（ranking）がない。数千件ヒットしたときに、どれが「良い」結果なのか並べられない
3. 索引が効かないので遅い。検索のたびに全文書を処理することになる

全文検索エンジンは、この3つをそれぞれ「アナライザ」「スコアリング」「転置インデックス」で解決する仕組み、と捉えると全体像が掴みやすくなります。

転置インデックスの構造

文書から語へ、を、語から文書へ

普通の文書集合は「文書 ID を引くと本文が出てくる」順方向の対応です。これをひっくり返して「語を引くと、その語を含む文書 ID の並びが出てくる」ようにしたものが転置インデックス（inverted index）です。

順方向:  doc1 -> [全文, 検索, エンジン, 転置, インデックス]
         doc2 -> [転置, インデックス, 単語, 文書]
 
転置:    全文       -> [1]
         検索       -> [1]
         転置       -> [1, 2]
         インデックス -> [1, 2]
         単語       -> [2]

語（term）を引くキーにするので、辞書部の作りが重要になります。Lucene の辞書部（.tim / .tip）は FST ベースの構造で、前方一致をたどれるため補完（サジェスト）もここから作れます。この「共通接頭辞を共有して引く」発想はトライ木入門と地続きです。

posting list に何を入れるか

語ごとにぶら下がる文書 ID の並びを posting list（転置リスト）と呼びます。ここに何を持たせるかで、できる検索が決まります。

Lucene の索引ファイルもこの区分そのままで、頻度は .doc、位置は .pos、文字オフセットなどの追加メタデータは .pay に分かれて格納されます。「使わない情報は索引しない」がサイズと速度の第一の設計判断になります。

Python で最小の転置インデックスを作る

実際に組んでみます。日本語なので、ここではトークナイズに文字 bigram（2文字ずつずらして切る）を使います。標準ライブラリだけで動きます。

import math
from collections import defaultdict
 
docs = {
    1: "全文検索エンジンは転置インデックスで検索する",
    2: "転置インデックスは単語から文書IDを引く",
    3: "検索エンジンの検索は速い。検索は転置インデックスのおかげ",
    4: "データベースのインデックスはB-treeを使う",
    5: "形態素解析とN-gramは日本語の全文検索で使い分ける",
}
 
def bigrams(text):
    t = text.lower()
    return [t[i:i+2] for i in range(len(t) - 1)]
 
# 転置インデックス: token -> 文書ID -> 出現位置のリスト
index = defaultdict(lambda: defaultdict(list))
doclen = {}
for did, text in docs.items():
    toks = bigrams(text)
    doclen[did] = len(toks)
    for pos, tok in enumerate(toks):
        index[tok][did].append(pos)
 
N = len(docs)
avgdl = sum(doclen.values()) / N
 
def tfidf(query_tokens):
    scores = defaultdict(float)
    for q in query_tokens:
        post = index.get(q)
        if not post:
            continue
        idf = math.log(N / len(post))
        for did, positions in post.items():
            scores[did] += (1 + math.log(len(positions))) * idf
    return scores
 
def bm25(query_tokens, k1=1.2, b=0.75):
    scores = defaultdict(float)
    for q in query_tokens:
        post = index.get(q)
        if not post:
            continue
        df = len(post)
        idf = math.log(1 + (N - df + 0.5) / (df + 0.5))   # Lucene BM25Similarity と同じ形
        for did, positions in post.items():
            tf = len(positions)
            dl = doclen[did]
            scores[did] += idf * (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * dl / avgdl))
    return scores

転置インデックス で検索したときの実行結果です。

N = 5  avgdl = 23.0
doclen = {1: 21, 2: 19, 3: 27, 4: 22, 5: 26}
 
query bigrams = ['転置', '置イ', 'イン', 'ンデ', 'デッ', 'ック', 'クス']
posting list of '転置' -> {1: [9], 2: [0], 3: [16]}
posting list of 'イン' -> {1: [11], 2: [2], 3: [18], 4: [7]}
 
 doc  len   TF-IDF     BM25
   1   21    2.137    2.609
   2   19    2.137    2.709
   3   27    2.137    2.349
   4   22    1.116    1.464
   5   26    0.000    0.000
 
TF-IDF order: [1, 2, 3, 4]
BM25   order: [2, 1, 3, 4]

注目してほしいのは、TF-IDF では doc1・doc2・doc3 が完全に同点（2.137）なのに対し、BM25 は短い doc2 を1位に押し上げている点です。この差がどこから来るのかを次に見ます。

アナライザ: 検索の品質はここで決まる

上のコードでは bigrams() という関数ひとつでトークン化しましたが、実際のエンジンではこの前処理をアナライザと呼び、3つの部品に分けます。Elasticsearch 公式ドキュメントの定義が最も明快です。

原文 "The Foxes Jumped!"
  -- character filter -->  "The Foxes Jumped!"
  -- tokenizer -------->  ["The", "Foxes", "Jumped"]
  -- lowercase filter -->  ["the", "foxes", "jumped"]
  -- stopword filter -->  ["foxes", "jumped"]
  -- stemmer ---------->  ["fox", "jump"]

ここで最も重要な原則があります。索引時と検索時で同じアナライザを通すことです。索引側で jumped を jump に正規化しているのに、検索側で jumped のまま引けばヒットしません。「なぜかヒットしない」の原因の多くは、索引時と検索時のアナライザ不一致です。

ただし例外もあります。後述する kuromoji の search モードのように索引時だけ複合語を分解する、あるいは同義語展開を検索時だけ行う、といった意図的な非対称は実務でよく使われます。「揃えるのが原則、ずらすなら理由を説明できること」が指針です。

スコアリング: TF-IDF から BM25 へ

TF-IDF の考え方と限界

TF-IDF は「その文書に何回出るか（TF）」と「その語が世の中でどれくらい珍しいか（IDF）」の積です。素朴で強力ですが、2つ弱点があります。

• TF が青天井。同じ語が100回出る文書は、10回出る文書より本当に10倍関連が深いのか
• 文書長を考慮しない。長い文書はどの語も多く含みがちなので、素の TF では不当に有利になる

BM25 はこの2つに、それぞれ k1（飽和）と b（文書長正規化）というパラメータで対処します。

BM25 の式

BM25 は Robertson らの Okapi システムに由来し、確率的関連性フレームワークから導かれた式です。Stanford の教科書 "Introduction to Information Retrieval" が示す形を、プレーンテキストで書くとこうなります。

score(D, Q) = SUM over q in Q of:
 
    IDF(q) * ( tf * (k1 + 1) ) / ( tf + k1 * (1 - b + b * dl / avgdl) )
 
  tf    : 文書 D における語 q の出現回数
  dl    : 文書 D の長さ（トークン数）
  avgdl : コレクション全体の平均文書長
  k1    : TF の飽和を決める定数
  b     : 文書長正規化の強さを決める定数（0 から 1）

同教科書は「experiments have shown reasonable values are to set k1 and k3 to a value between 1.2 and 2 and b = 0.75」と述べ、b = 1 は「文書長で完全に正規化する」、b = 0 は「文書長正規化なし」に対応するとしています。

k1 は「何回目から効かなくなるか」を決める

k1 の効果を実際に計算してみます。

import math
k1, b = 1.2, 0.75
def tf_part(tf, dl, avgdl):
    return (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * dl / avgdl))
 
for tf in [1, 2, 3, 5, 10, 20, 50, 100]:
    print(tf, round(1 + math.log(tf), 3), round(tf_part(tf, 100, 100), 3))

 tf  TF-IDF風 1+log(tf)   BM25 tf項
  1              1.000      1.000
  2              1.693      1.375
  3              2.099      1.571
  5              2.609      1.774
 10              3.303      1.964
 20              3.996      2.075
 50              4.912      2.148
100              5.605      2.174
 
上限 = k1 + 1 = 2.2

tf を100倍にしても TF 項は 2.174 までしか伸びません。式を見れば分かるとおり、tf を無限大に飛ばすと TF 項は k1 + 1 に収束します。つまり BM25 の TF 項には天井があり、その天井の高さを k1 が決めているということです。キーワードを本文に連打する古典的なスパムが効かないのは、この飽和のおかげです。

k1 = 0 にすると TF 項は常に 1 になり、「語が含まれるか否か」だけを見るバイナリモデルに退化します。逆に k1 を大きくすると生の TF に近づきます。

b は文書長のペナルティを決める

   dl   BM25 tf項
   25      1.872
   50      1.760
  100      1.571
  200      1.294
  400      0.957

平均の4倍の長さの文書は、同じ3回の出現でもスコアが約4割減ります。「長い文書にたまたま3回出た」より「短い文書に3回出た」ほうが強い証拠だ、という直感を式にしたものです。b を 0 にすればこの列は全部 1.571 で並びます。

先ほどの実測で BM25 が doc2 を1位にしたのは、doc2 の長さが 19 と平均 23.0 より短かったからです。

Lucene の実装はどこが違うか

理論式と実装式には差があります。Apache Lucene の BM25Similarity javadoc（10.1.0）を確認すると、既定値と IDF の定義が明記されています。

idf = log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5))

ソース（BM25Similarity.java）でも Math.log(1 + (docCount - docFreq + 0.5D) / (docFreq + 0.5D)) と実装されています。教科書式の RSJ 重みは log((N - df + 0.5) / (df + 0.5)) ですが、これは df が N の半分を超えると負になるという困った性質を持ちます。Lucene は対数の中身に 1 + を足すことで、IDF が常に 0 以上になるようにしています。

確認できた Lucene の実装上の要点をまとめます。

最後の「文書長を1バイトに丸める」は実務上けっこう重要です。Lucene は dl を正確な整数では持たず、SmallFloat で1バイトに量子化した norm として保存します。索引サイズのために精度を捨てる設計判断で、スコアの微差が理論値とずれる原因にもなります。

Elasticsearch も既定値は同じで、公式ブログ "Practical BM25" は「By default, k1 has a value of 1.2 in Elasticsearch」「By default, b has a value of 0.75」と明記しています。SQLite の FTS5 に至っては公式ドキュメントに「k1 and b are both constants, hard-coded at 1.2 and 0.75 respectively」とあり、変更する手段がありません。

posting list を圧縮する

転置インデックスの容量の大半は posting list です。ここには「昇順に並んだ文書 ID の列」という強い性質があるので、専用の圧縮が効きます。

• delta encoding（差分符号化）: [3, 17, 41, 42, 900] を [3, 14, 24, 1, 858] にする。文書数が多くても差分は小さい
• VByte（可変長整数）: 1バイトあたり7ビットのデータと1ビットの終端フラグ。127以下なら1バイトで収まる

この2つを組み合わせるとどれくらい減るのか、実測しました。

def vbyte(n):
    out = bytearray()
    while True:
        b = n & 0x7F
        n >>= 7
        if n:
            out.append(b)
        else:
            out.append(b | 0x80)   # 最終バイトに終端ビットを立てる
            return bytes(out)
 
def encode(ids, delta):
    buf = bytearray()
    prev = 0
    for d in ids:
        buf += vbyte(d - prev if delta else d)
        if delta:
            prev = d
    return bytes(buf)

1000万文書のコレクションから、文書頻度 df を変えてランダムに posting list を作り、固定4バイト表現と比較した結果です。

低頻度語 df=1万     固定4B=   40000  VByte= 37865 (94.7%)  delta+VByte=  18803 (47.0%)  bits/doc=15.04
中頻度語 df=10万    固定4B=  400000  VByte=378934 (94.7%)  delta+VByte= 127691 (31.9%)  bits/doc=10.22
高頻度語 df=100万   固定4B= 4000000  VByte=3787920 (94.7%)  delta+VByte=1000002 (25.0%)  bits/doc= 8.00
超高頻度語 df=500万 固定4B=20000000  VByte=18942823 (94.7%)  delta+VByte=5000000 (25.0%)  bits/doc= 8.00

読み取れることが3つあります。

• VByte 単体はほぼ無力（94.7%）。文書 ID が大きいので結局4バイト近く必要になる
• delta を挟むと一気に効く。df が大きい（＝差分が小さい）ほど効き、高頻度語では1文書あたり 8 ビット、つまり1バイトまで縮む
• 圧縮率は語の頻度に依存する。低頻度語は差分が大きいので 47% 止まり

「よく出る語ほどよく縮む」という性質は、posting list が長い＝走査コストが高い語ほど I/O が減ることを意味していて、都合が良い方向に働きます。圧縮全般の考え方はデータ圧縮入門にまとめています。

Lucene のセグメント構造と近リアルタイム検索

転置インデックスは「作るのは重いが引くのは速い」構造です。ではドキュメントを1件追加するたびに作り直すのか、という問題を Lucene はセグメントで解きます。

Lucene 公式ドキュメントの記述を確認すると、設計が明快です。

• インデックスは複数のセグメントから成り、「Each segment is a fully independent index, which could be searched separately」
• 「Segments are immutable; updates and deletions may only create new segments and do not modify existing ones」
• 削除は物理削除ではなく、「some may be deleted, but their docids are retained until the segment is merged」
• ライタは「merges groups of smaller segments into single larger ones in order to maintain an index that is efficient to search, and to reclaim dead space left behind by deleted (and updated) documents」

つまり、書き込みは常に新しい小さなセグメントの追記で、削除は墓標（tombstone）、実際の掃除はマージ時にまとめて行う、というログ構造的な設計です。B-tree がページを in-place で更新していくデータベースインデックスとは、更新モデルが根本的に違います。

この設計の帰結が近リアルタイム検索（NRT）です。書き込んだ文書は、新しいセグメントが作られてリーダから見えるようになるまで検索できません。Elasticsearch でこの操作を refresh と呼び、index.refresh_interval の既定値は公式ドキュメントで 1s（Serverless では 5s）と定められています。「インデックスした直後に検索しても出てこない」という定番のハマりどころは、仕様どおりの挙動です。

さらに公式は「shards that haven't seen search traffic for at least index.search.idle.after seconds will not receive background refreshes until they receive a search request」とも述べており、検索が来ていないシャードは定期リフレッシュ自体が止まります。バルクインポート時に refresh_interval を -1 にして投入後に戻す、というチューニングはこの仕組みを利用したものです。

日本語の壁: 形態素解析とN-gram

英語は空白で切れば単語になりますが、日本語は切れ目がありません。ここが日本語全文検索の最大の分岐点です。文字そのものの扱いについては文字コードとUTF-8入門も参照してください。

形態素解析

辞書と品詞体系を使って、文を意味のある単位に分割します。

• MeCab: 日本語形態素解析の事実上の標準実装。多くのツールがバックエンドに使う
• Kuromoji: Java 実装。Lucene に analysis-kuromoji として同梱される。JapaneseTokenizer の javadoc には「This tokenizer uses a rolling Viterbi search to find the least cost segmentation (path) of the incoming characters」とあり、既定モードは「Currently this is JapaneseTokenizer.Mode.SEARCH」
• Sudachi: WorksApplications 製。公式 README によれば3つの分割モードを持つ

Sudachi の分割モードは、公式 README の例が分かりやすいです。

A モードは再現率（取りこぼしの少なさ）、C モードは適合率（余計なヒットの少なさ）に寄ります。実務では複数モードの結果を同時に索引に入れることもあります。

Elasticsearch の kuromoji_tokenizer も同じ思想で、公式ドキュメントによれば search モードは「a decompounding process for long nouns, also including the full compound token as a synonym」を行い、関西国際空港 を 関西, 関西国際空港, 国際, 空港 に展開します。長い複合語を分解しつつ元の語も残すことで、両方の検索にヒットさせる作りです。

N-gram（bigram）

辞書を使わず、機械的に N 文字ずつ切ります。MySQL の ngram パーサの公式ドキュメントによれば、abcd は ngram_token_size が 2 のとき ab, bc, cd に分割されます。

bigram の誤ヒットを実測する

bigram の「多い誤ヒット」を具体的に見ます。有名な例が「京都」と「東京都」です。

docs = {1: "東京都に住んでいます", 2: "京都に旅行に行きました", 3: "京都府と東京都"}
# 各文書を bigram で索引し、位置つき posting list を作る（コードは前掲と同じ）

query='京都'  bigrams=['京都']
  AND検索（位置を見ない）: [1, 2, 3]
  フレーズ検索（位置を見る）: [(1, [1]), (2, [0]), (3, [0, 5])]
    doc1: 東京都に住んでいます
    doc2: 京都に旅行に行きました
    doc3: 京都府と東京都
 
query='東京都'  bigrams=['東京', '京都']
  AND検索（位置を見ない）: [1, 3]
  フレーズ検索（位置を見る）: [(1, [0]), (3, [4])]

「京都」で検索すると、doc1「東京都に住んでいます」がヒットします。しかもこれは位置情報を使ったフレーズ検索でも消えません。bigram 索引にとって「京都」は「東京都」の部分文字列として実在するからです。形態素解析であれば 東京都 は 東京都（あるいは 東京 / 都）としてトークン化されるので、この誤ヒットは起きません。

逆に、形態素解析は辞書にない新語で取りこぼします。「両方入れて OR で引く」（Elasticsearch なら multi_field で形態素フィールドと N-gram フィールドを併置し、形態素側のスコアを高くする）が、実務でよく採られる折衷案です。

フレーズ検索: 位置情報の出番

上の実行結果で使った「フレーズ検索」は、posting list に持たせた出現位置を使います。原理は単純です。

1. 各トークンの posting list から、共通して現れる文書を求める（AND）
2. その文書の中で、トークン t_i の位置 p が
   すべての i について (p + i) を含むかを調べる
3. 条件を満たす p があれば、そこがフレーズの開始位置

つまり位置の集合に対して、オフセットをずらした共通部分を取るだけです。近接検索（「AとBが5語以内」）は、この差が完全一致でなく閾値以内かを見るように緩めたものです。計算量は posting list の長さに比例するので、O(1) ではありません。計算量の考え方の観点では、フレーズ検索が単純な AND より重いのは避けられません。

PostgreSQL でも同じ仕組みが tsvector の位置情報として実装されていて、公式ドキュメントは制限を明記しています。位置の値は「greater than 0 and no more than 16,383」、<N>（FOLLOWED BY）演算子の距離は「cannot be more than 16,384」、そして「no more than 256 positions per lexeme」です。長文で同じ語が257回以上出ると、それ以降の位置は記録されません。

RDB の全文検索とどう違うか

「Elasticsearch を建てるほどでもない」ケースのために、主要な RDB の全文検索機能を公式ドキュメントで確認します。

PostgreSQL

tsvector（正規化済みレキシムの集合）と tsquery（検索式）、@@ 演算子、そして GIN / GiST 索引の組み合わせです。

• 索引: 公式は GIN を推奨。GIN は語ごとに posting list を持つ本物の転置索引。GiST はロッシーで「the index might produce false matches, and it is necessary to check the actual table row to eliminate such false matches」
• ランキング: ts_rank は「Ranks vectors based on the frequency of their matching lexemes」、ts_rank_cd は Clarke らのカバー密度（cover density）ランキングで、語同士の近さを考慮する。ts_rank_cd は位置情報を要求し、位置が剥がされた tsvector では 0 を返す
• 重み: setweight() で A から D のラベルを付け、既定の重み配列 {0.1, 0.2, 0.4, 1.0}（D, C, B, A の順）で「タイトルは本文より重い」を表現できる
• 正規化オプション: 文書長で割るかどうかはビットフラグで選ぶ。既定の 0 は文書長を無視する

ここが BM25 との一番大きな違いです。PostgreSQL の既定ランキングは文書長正規化も TF 飽和もしません。BM25 相当が欲しければ normalization を明示するか、外部エンジンを検討することになります。

日本語については、PGroonga 公式が「PostgreSQL はアルファベットと数値だけを使った言語の全文検索だけをサポートしています。これは、日本語や中国語などはサポートしていないということです」と述べているとおり、素の PostgreSQL では実用になりません。選択肢は次のとおりです。

• pg_bigm: 2-gram インデックスを提供する拡張。GitHub の README には「full text search capability in PostgreSQL」「2-gram (bigram) index for faster full text search」とある。標準の pg_trgm は3-gram なので、2文字語の多い日本語には向かない
• PGroonga: Groonga をバックエンドに使う拡張。全言語対応で、JSON 内のテキスト値の全文検索もできる

MySQL（InnoDB FULLTEXT）

InnoDB の FULLTEXT INDEX は、日本語では ngram パーサを使うことになります。公式ドキュメントで確認できた点です。

• ngram_token_size の既定は 2、範囲は 1 から 10。読み取り専用変数なので起動オプションか設定ファイルでしか変えられず、変更後は索引の再構築が必要
• ngram パーサ使用時は innodb_ft_min_token_size / innodb_ft_max_token_size / ft_min_word_len / ft_max_word_len がすべて無視される
• ストップワードの扱いが独特で、「トークンがストップワードを含むと除外される」。a,b は a, と ,b に分割され、, がストップワードなら両方消える
• ワイルドカード検索で、プレフィックスが ngram_token_size より長い場合は ngram フレーズに変換され、ワイルドカード演算子は無視される（abc* は ab bc になる）

よく誤解されるのが50%閾値です。公式ドキュメントの記述は「For MyISAM search indexes, the 50% threshold for natural language searches is determined by the particular weighting scheme chosen」であり、MyISAM の話です。InnoDB の全文検索について 50%閾値の記述は見当たりませんでした。「MySQL の全文検索は半分以上の行に出る語を無視する」という知識は、InnoDB では当てはまらないと考えてよさそうです。なお ngram パーサ使用時は innodb_ft_min_token_size 自体が無視されるため、既定値（3）も関係ありません。

SQLite FTS5

仮想テーブルとして全文索引を持つモジュールです。既定トークナイザは unicode61 で、これは日本語を切れません。日本語には trigram トークナイザを使います。ランキングは組み込みの bm25() 補助関数です。

LIKE と FTS5 を実測比較する

手元で比べました。筆者環境（macOS 26.5 / Apple Silicon arm64 / Python 3.14.7 / SQLite 3.53.4）での実測です。20万行、1行あたり日本語の語を8個から16個ランダム連結した合成データで、FTS5 は tokenize='trigram' を指定しています。

con.execute("CREATE VIRTUAL TABLE fts USING fts5(body, content='docs', "
            "content_rowid='id', tokenize='trigram')")
con.execute("INSERT INTO fts(fts) VALUES('rebuild')")
 
# LIKE 側
con.execute("SELECT count(*) FROM docs WHERE body LIKE ?", (f"%{w}%",))
# FTS5 側
con.execute("SELECT count(*) FROM fts WHERE fts MATCH ?", (f'"{w}"',))

sqlite3 3.53.4
行数=200000  本体=37.3MB  FTS5索引込み=74.7MB  索引構築=4.50s
 
語             LIKE %..% (ms)   FTS5 MATCH (ms)      倍率     hits
浮動小数点誤差            132.7               0.1   1086x       20
形態素解析               142.6              20.6      7x    76885
転置インデックス            151.2              56.7      3x    77096
全文検索                143.3              19.4      7x    76836
 
FTS5 の bm25() でランキング（値が小さいほど良い一致）
  rowid= 170000  bm25=-10.2946
  rowid= 130000  bm25=-10.1317

この結果は素直で、示唆に富みます。

• レアな語（20万行中20件）では1000倍以上速い。転置インデックスの本領はここ
• ヒット数が多い語（約38%の行にヒット）では3倍から7倍程度。posting list を全部読むコストが支配的になり、優位性は縮む
• 索引のコストは軽くない。本体 37.3MB に対して FTS5 索引込みで 74.7MB、つまり索引が本体とほぼ同サイズ（trigram トークナイザは1文字ずつずらして3-gram を作るのでトークン数が多い）
• LIKE '%...%' の時間はヒット数にほぼ依存しない（130ms 台から150ms 台）。これは常に全行スキャンしているから

この「選択性が高いほど索引が効く」という原則は、B-tree でもまったく同じでした。実行計画の読み方は実行計画とJOINアルゴリズムにまとめています。

使い分けの指針

ここまでを踏まえた現実的な判断軸です。

エンジンを別立てにするとデータ同期（インデクシングパイプライン）という新しい問題が増えます。「DB 内で完結する拡張で足りるか」を先に検討するのが安全です。逆に、スコアリングを本気で調整したい、同義語辞書を運用したい、ファセットや集計が要る、という段階になったら Lucene 系のほうが総コストは下がります。

なお、検索結果の後続ページを返す設計はページネーション設計の話と直結します。スコア順の deep pagination は転置インデックスにとっても重い操作です。

まとめ

• アナライザ（character filter / tokenizer / token filter）は索引時と検索時で揃えるのが原則。ずらすなら理由を説明できること
• 転置インデックスは「語から文書 ID 列を引く」構造。posting list に何を持たせるか（ID / tf / 位置 / オフセット）で、できる検索とサイズが決まる
• BM25 は TF-IDF の2つの弱点を k1（TF の飽和・上限は k1 + 1）と b（文書長正規化）で補正する。Lucene・Elasticsearch・SQLite FTS5 のいずれも既定は k1 = 1.2 / b = 0.75
• Lucene の IDF は対数の中に 1 + を入れて非負化されており、文書長は1バイトに量子化されて保存される
• posting list は delta encoding が本質。実測では高頻度語で1文書あたり8ビットまで縮んだ（VByte 単体では 94.7% にしかならない）
• Lucene のセグメントは不変。更新は新セグメント、削除は墓標、掃除はマージ。この設計の帰結が近リアルタイム検索（Elasticsearch の refresh_interval 既定 1s）
• 日本語は形態素解析（誤ヒットが少ない・未知語に弱い）と N-gram（誤ヒットが多い・取りこぼさない）のトレードオフ。実測でも bigram 索引は「京都」で「東京都」を拾った
• PostgreSQL の既定ランキングは文書長正規化をしない（normalization 既定は 0）。MySQL の 50%閾値は MyISAM の話で InnoDB には該当する記述がない
• SQLite FTS5 の実測では、レア語で1000倍以上、低選択性の語では3倍から7倍。索引サイズは本体とほぼ同等だった

参考リンク

• BM25Similarity (Lucene 10.1.0 core API)
• org.apache.lucene.index パッケージ概要（セグメントと不変性）
• lucene101 コーデックの索引ファイル形式
• JapaneseTokenizer (Lucene kuromoji)
• Elasticsearch: Anatomy of an analyzer
• Elasticsearch: Index modules（refresh_interval）
• Elasticsearch: Near real-time search
• Elasticsearch: kuromoji_tokenizer
• PostgreSQL: Introduction to Text Search
• PostgreSQL: Controlling Text Search（ts_rank / ts_rank_cd）
• PostgreSQL: GIN and GiST Index Types
• PostgreSQL: Limitations
• MySQL 8.4: ngram Full-Text Parser
• MySQL 8.4: Fine-Tuning MySQL Full-Text Search
• SQLite FTS5
• Sudachi（分割モード A / B / C）
• pg_bigm
• PGroonga 概要
• Introduction to Information Retrieval: Okapi BM25
• Robertson & Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond (PDF)