概要

転置インデックス は、全文検索において、対象となる文書群から単語の位置情報を格納するための索引構造。

理論

$N$ 個の文章の集合 $D = {d_1,d_2,d_3,\cdots,d_N}$ と、それらに含まれる単語全ての集合 $W = {w_1,w_2,w_3,\cdots,w_M}$ を考える。

各文章ごとに含まれる単語を並べていくと、以下のような行列が得られる（単語が1度でも文章に出現する場合を1、出現しない場合を0で表現）。

d1: [w1, w2, w3, w4, w5]
d2: [w1, w2, w6, w7]
d3: [w4, w6, w8]
d4: [w2, w3, w4, w6, w8]

--->

    w1 w2 w3 w4 w5 w6 w7 w8
d1   1  1  1  1  1  0  0  0
d2   1  1  0  0  0  1  1  0
d3   0  0  0  1  0  1  0  1
d4   0  1  1  1  0  1  0  1

特定の文章 $d_i$ に対応する行を参照すれば、その文章に含まれる単語リストが得られる。

次に、この行列の転置行列を考える。

    d1 d2 d3 d4
w1   1  1  0  0
w2   1  1  0  1
w3   1  0  0  1
w4   1  0  1  1
w5   1  0  0  0
w6   0  1  1  1
w7   0  1  0  0
w8   0  0  1  1

先程の行列とは逆に、特定の単語 $w_i$ に対応する行を参照することで、その単語を含む文章のリストが得られる。

→ つまり、検索キーワード $w_i$ を含む文章の一覧を検索するシステムに使える。

このように単語 ID をキーとして、その単語を含む文章一覧（ポスティングリスト）を並べたものを 転置インデックス と呼ぶ。

現実的には、1つの文章に使われる単語は全単語 $W$ のうちのほんの一部に過ぎないので、上の例のように転置インデックスの行列に1が多数並ぶようなことはない（ほとんど値が0の疎な行列になる）。
なので、メモリ容量節約および検索速度改善のため、転置インデックスの実態としては以下のような Map 構造が用いられることが多い。

w1: [d1, d2]
w2: [d1, d2, d4]
w3: [d1, d4]
w4: [d1, d3, d4]
w5: [d1]
w6: [d2, d3, d4]
w7: [d2]
w8: [d3, d4]

例えば上の転置インデックスでクエリが $w_2, w_6$ の AND 検索（指定された全ての単語が存在するドキュメントを探す）を行う場合、以下の手順で検索結果を求められる。

  1. $w_2$ のポスティングリスト $d_1,d_2,d_4$
  2. $w_2$ のポスティングリスト $d_2,d_3,d_4$
  3. 1,2の積集合を取って、検索結果は $d_2, d_4$

実装

キーワード数を変えて処理時間を計測：

AND 検索 OR 検索
and-search or-search