inverted-index(転置インデックスと TF-IDF / BM25)
全文検索のたびに全文書を頭から走査すると、文書数×文書長の時間がかかる。検索エンジンは逆向きの表を先に作る。文書→語ではなく、語→文書リスト(転置インデックス)だ。検索は語で表を引き、リストを突き合わせるだけで済む。関連度は、その文書での出現回数(TF)と語の珍しさ(IDF)の掛け算が土台で、BM25 は TF に飽和を入れ文書長で割り引いた実戦版になる。
この章で作るもの
Elasticsearch も Lucene も、データベースの全文検索も、根っこは同じ 1 つのデータ構造でできている。転置インデックスだ。「この語を含む文書はどれか」に即答するために、文書を取り込む時点で語→文書リストの表を作っておく。検索時には文書本文へ一切触れない。
この章は 3 段で組む。索引の構築(トークン化と語→ポスティングリストの表)、ブール検索(AND は積・OR は和)、そしてランキング(TF-IDF と BM25)だ。ブール検索は「含むか」しか答えられないが、実際の検索で欲しいのは「どれが上位か」で、そこを TF と IDF の掛け算が担う。
文書 転置インデックス(語 → ポスティングリスト)
doc0: "quick brown fox" quick → [doc0, doc1]
doc1: "quick brown dog" ──▶ brown → [doc0, doc1]
doc2: "lazy cat" fox → [doc0]
dog → [doc1]
lazy → [doc2] 検索 "quick dog":
cat → [doc2] [doc0,doc1] ∩ [doc1] = [doc1]順に見ていく。
- 索引 = 語→文書リスト: 取り込み時に表を作り、検索時は本文を読まない。前処理に払って検索を速くする
- ブール検索 = 集合演算: AND はポスティングリストの積(昇順マージ走査)、OR は和
- ランキング = TF × IDF: よく出る語(TF)×珍しい語(IDF)。BM25 は TF の飽和と文書長正規化を足した実戦版
① 索引を作る: トークン化とポスティングリスト
まず文書を語に割る。英数字の連なりを 1 語とし、小文字に揃える(Quick と quick を同じ語にする):
// Posting は 1 つの語が 1 つの文書に現れた記録。TF(その文書内の出現回数)を持つ。
type Posting struct {
DocID int
TF int
}
// Index は転置インデックス。語 → ポスティングリスト(その語を含む文書と出現回数の列)。
type Index struct {
postings map[string][]Posting
docLen []int // 文書ごとの語数(ランキングで使う)
docs []string
}
// Tokenize は文書を語の列に割る。英数字の連なりを 1 語とし、小文字に揃える。
// 実物はステミング(walked→walk)やストップワード除去もするが、ここでは省く。
func Tokenize(text string) []string {
var tokens []string
var cur strings.Builder
flush := func() {
if cur.Len() > 0 {
tokens = append(tokens, strings.ToLower(cur.String()))
cur.Reset()
}
}
for _, r := range text {
if unicode.IsLetter(r) || unicode.IsDigit(r) {
cur.WriteRune(r)
} else {
flush()
}
}
flush()
return tokens
}
// Build は文書集合から転置インデックスを作る。各文書をトークン化し、
// 語ごとに「どの文書に何回現れたか」を記録する。DocID は与えた順の添字。
func Build(docs []string) *Index {
idx := &Index{postings: map[string][]Posting{}, docs: docs}
for id, doc := range docs {
tokens := Tokenize(doc)
idx.docLen = append(idx.docLen, len(tokens))
tf := map[string]int{}
for _, t := range tokens {
tf[t]++
}
terms := make([]string, 0, len(tf))
for t := range tf {
terms = append(terms, t)
}
sort.Strings(terms) // 決定的に(マップ順に依存しない)
for _, t := range terms {
idx.postings[t] = append(idx.postings[t], Posting{DocID: id, TF: tf[t]})
}
}
return idx
}
// Postings は語のポスティングリスト(DocID 昇順)。無ければ nil。
func (idx *Index) Postings(term string) []Posting {
return idx.postings[strings.ToLower(term)]
}
// NumDocs は文書数。DocLen は文書の語数。Doc は元の文書。
func (idx *Index) NumDocs() int { return len(idx.docs) }
func (idx *Index) DocLen(id int) int { return idx.docLen[id] }
func (idx *Index) Doc(id int) string { return idx.docs[id] }
// DF は語を含む文書数(document frequency)。ランキングの材料になる。
func (idx *Index) DF(term string) int { return len(idx.Postings(term)) }Build が取り込みの本体だ。文書ごとに語の出現回数(TF)を数え、語→Posting{DocID, TF} の列として蓄える。ポスティングリストは DocID 昇順になる(文書を順に取り込むから)。この昇順が、次のブール検索で効いてくる。TF をここで数えておくのは、後のランキングの材料になるからだ。
② ブール検索: リストの積と和
「quick と dog の両方を含む文書」は、2 本のポスティングリストの積(intersection)だ。両方とも DocID 昇順なので、2 本のカーソルを進めるマージ走査で線形に交差できる:
// SearchAND は全ての語を含む文書を返す。ポスティングリストの積(intersection)。
// 各リストは DocID 昇順なので、マージ走査で線形に交差できる——ここが転置インデックスの
// 検索が速い理由で、文書本文には一切触れない。
func (idx *Index) SearchAND(terms ...string) []int {
if len(terms) == 0 {
return nil
}
result := docIDs(idx.Postings(terms[0]))
for _, t := range terms[1:] {
result = intersect(result, docIDs(idx.Postings(t)))
if len(result) == 0 {
return nil // 早期終了: 積がもう空
}
}
return result
}
// SearchOR はいずれかの語を含む文書を返す。ポスティングリストの和(union)。
func (idx *Index) SearchOR(terms ...string) []int {
seen := map[int]bool{}
for _, t := range terms {
for _, p := range idx.Postings(t) {
seen[p.DocID] = true
}
}
out := make([]int, 0, len(seen))
for id := range seen {
out = append(out, id)
}
sort.Ints(out)
return out
}
func docIDs(ps []Posting) []int {
out := make([]int, len(ps))
for i, p := range ps {
out[i] = p.DocID
}
return out
}
// intersect は昇順リスト 2 本のマージ走査。両方に現れる ID だけ残す。
func intersect(a, b []int) []int {
var out []int
i, j := 0, 0
for i < len(a) && j < len(b) {
switch {
case a[i] == b[j]:
out = append(out, a[i])
i++
j++
case a[i] < b[j]:
i++
default:
j++
}
}
return out
}intersect が要になる。ソート済みリスト同士なら、全体を舐め直さずに共通要素を拾える(btree 編や skip-list 編と同じ「順序を保つと速い」の応用)。SearchAND は積が空になった時点で打ち切る。頻度の低い語から交差すれば、さらに早く絞れる(実務の最適化)。ここまで文書本文には一度も触れていない。
③ ランキング: TF-IDF から BM25 へ
ブール検索は「含む/含まない」しか言えない。1 万件ヒットしたとき、どれを上に出すか。土台になるのが 2 つの頻度だ。TF(term frequency)はその文書内の出現回数で、「何度も出る語はその文書にとって重要」を表す。IDF(inverse document frequency)は語の珍しさで、どの文書にも出る語(the や です)は判別に役立たないから小さく、珍しい語ほど大きくする:
// IDF は語の珍しさ。log(N / df)。全文書に出る語は 0 に近づき、珍しい語ほど大きい。
func (idx *Index) IDF(term string) float64 {
df := idx.DF(term)
if df == 0 {
return 0
}
return math.Log(float64(idx.NumDocs()) / float64(df))
}
// SearchTFIDF はクエリの各語について TF × IDF を文書ごとに足し込み、スコア降順で返す。
// ポスティングリストを走査するだけで、全文書を見ない(スコアが付くのは語を含む文書だけ)。
func (idx *Index) SearchTFIDF(terms ...string) []Hit {
scores := map[int]float64{}
for _, t := range terms {
idf := idx.IDF(t)
for _, p := range idx.Postings(t) {
scores[p.DocID] += float64(p.TF) * idf
}
}
return sortHits(scores)
}TF-IDF はこの 2 つの積を語ごとに足すだけだが、素朴すぎる点が 2 つある。TF が線形に効くので、同じ語を 100 回書いた文書が 100 倍のスコアになる(スパムに弱い)。そして文書の長さを見ないので、長い文書ほど有利になる。BM25 はこの 2 点を直した式だ:
// BM25 のパラメータ。k1 は TF の飽和の強さ(大きいほど TF が効き続ける)、
// b は文書長正規化の強さ(1 で完全正規化、0 で無視)。1.2 / 0.75 が定番の既定値。
const (
k1 = 1.2
b = 0.75
)
// SearchBM25 は BM25 でスコアづけする。TF-IDF との違いは 2 つ。
//
// 1. TF の飽和: TF-IDF は出現 100 回なら 100 倍効くが、BM25 は tf/(tf+k1) の形で頭打ちに
// なる。「2 回出る」と「100 回出る」の差は、「0 回」と「2 回」の差より小さい。
// 2. 文書長の正規化: 長い文書は偶然どんな語でも含みやすい。平均文書長との比で TF を
// 割り引き、短い文書での出現を相対的に重く見る。
//
// IDF も +0.5 平滑化入りの形を使う(BM25 の標準形)。
func (idx *Index) SearchBM25(terms ...string) []Hit {
n := float64(idx.NumDocs())
if n == 0 {
return nil
}
var totalLen float64
for i := 0; i < idx.NumDocs(); i++ {
totalLen += float64(idx.DocLen(i))
}
avgLen := totalLen / n
scores := map[int]float64{}
for _, t := range terms {
df := float64(idx.DF(t))
if df == 0 {
continue
}
idf := math.Log(1 + (n-df+0.5)/(df+0.5))
for _, p := range idx.Postings(t) {
tf := float64(p.TF)
norm := 1 - b + b*float64(idx.DocLen(p.DocID))/avgLen
scores[p.DocID] += idf * (tf * (k1 + 1)) / (tf + k1*norm)
}
}
return sortHits(scores)
}tf/(tf + k1·norm) の形が TF の飽和を作る。出現 0 回と 2 回の差は大きく、2 回と 100 回の差は小さい。norm は文書長を平均で割った正規化で、短い文書での 1 回は長い文書での 1 回より重く数える。k1=1.2, b=0.75 は広く使われる既定値だ。この 2 つの補正だけで、BM25 は数十年たった今も全文検索ランキングの標準であり続けている。
動かす
下のデモは、この転置インデックスをそのままブラウザで動かしている。5 つの文書に対しクエリを選ぶと、上段に各語のポスティングリスト、下段に検索結果が出る。AND / OR / BM25 を切り替えると、同じクエリでも結果の絞り方と並び方が変わる。dog を 3 回含む文書が BM25 の先頭に来ること、そしてそのスコアが 3 倍にはなっていない(飽和)ことを見てほしい。
AND: 全語のポスティングリストの積。どちらのリストも DocID 昇順なので、マージ走査で線形に交差できる。文書本文は読んでいない
索引を先に作っておくので、検索は「語で表を引いてリストを突き合わせる」だけで済む。 文書が何万件あっても、走査するのはクエリ語のポスティングリストだけだ。順位づけは TF(その文書に何回出るか)と IDF(その語がどれだけ珍しいか)の掛け算が土台で、BM25 は TF に飽和を入れ、文書の長さで割り引いた実戦版になる。
設計の観点: 検索エンジンの土台
- なぜ前処理に払うのか: 検索は読み込みより桁違いに多く実行される。取り込み時に索引を作るコストを払えば、検索が語の表引き + リスト走査になる。書き込み時に働いて読み込みを速くする、という btree 編や wal 編と同じ非対称の張り方
- AND の実行順: 積は「短いリストから」処理すると速い。df の小さい(珍しい)語から交差すれば、途中結果が小さく保たれる。クエリオプティマイザの最小版
- TF-IDF の弱点と BM25: TF の線形性(繰り返しスパム)と文書長の無視。BM25 は飽和と長さ正規化で直す。Lucene/Elasticsearch は既定のスコアラを TF-IDF から BM25 に切り替えた(Lucene 6, 2016)
- 索引の更新: 追記される文書にどう追従するか。実務はセグメント方式(新しい文書は小さな索引に貯め、裏でマージ)を採る。ログ構造KV 編の memtable + コンパクションと同じ構図
- 転置インデックスの外: 完全一致でなく意味で探すなら、語の表ではなく埋め込みベクトルの近傍探索(ベクトル検索)になる。実務の検索は BM25 とベクトル検索のハイブリッドが増えている
メリット・デメリットと実例
| 方式 | 検索速度 | 前処理 | 得意 | 実例 |
|---|---|---|---|---|
| 全文走査(grep) | 遅(文書数×長さ) | 不要 | 一度きりの検索 | grep、ログの ad-hoc 検索 |
| 転置インデックス | 速(語の表引き) | 索引構築 | 繰り返し検索・ランキング | Lucene、Elasticsearch、DB の全文検索 |
| ベクトル検索 | 中(近傍探索) | 埋め込み計算 | 意味の類似 | FAISS、各種ベクトルDB |
裏どり:
- Lucene / Elasticsearch / Solr: 転置インデックスの代表実装。セグメント方式で更新を吸収し、スコアラは BM25 が既定(Lucene 6 で TF-IDF から交代)
- PostgreSQL の GIN インデックス:
tsvectorの全文検索を支えるのは汎用転置インデックス(GIN)。RDB の中にも同じ構造が入っている - BM25 の由来: Robertson らの確率的検索モデル(Okapi BM25, 1994)。TREC での実績を経て事実上の標準になった
- ハイブリッド検索: BM25(語の一致)とベクトル検索(意味の近さ)を組み合わせ、RRF などで順位を融合するのが近年の定番構成
簡略化したこと
- ステミング・ストップワードなし: walked→walk の正規化や the の除去はしない。トークン化は英数字の分割と小文字化のみ
- フレーズ検索なし: "quick dog" の隣接検索には語の出現位置(ポジション)が要る。ここでは TF まで
- セグメント・更新なし: 索引は一括構築のみ。追記・削除・マージは扱わない
- 圧縮なし: 実務のポスティングリストは差分 + 可変長整数で圧縮する(rpc 編の varint と同じ技法)
- 日本語の分かち書きなし: 空白の無い言語には形態素解析や n-gram が要る。英語トークンに絞る
参考資料
- Manning, Raghavan, Schütze, Introduction to Information Retrieval(無料公開) — 転置インデックスとランキングの教科書
- Robertson & Zaragoza, "The Probabilistic Relevance Framework: BM25 and Beyond" — BM25 の背景
- btree 編(順序を保つ索引)・ログ構造KV 編(セグメント + マージの構図)と合わせて読むと索引設計が繋がる
- 実装: search/invertedindex