転置インデックス
転置インデックス(てんちインデックス、Inverted index)とは、全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造をいう。転置索引、転置ファイル、逆引き索引などとも呼ばれる。
ここに次のようなテキストがある。 T 0 = {\displaystyle T_{0}=} "it is what it is", T 1 = {\displaystyle T_{1}=} "what is it", T 2 = {\displaystyle T_{2}=} "it is a banana"
ここから得られる転置インデックスは次のようなものである。
"what", "is" そして "it" といった語に対して単語検索をかけてみると、次のような集合が得られる。
{ 0 , 1 } ∩ { 0 , 1 , 2 } ∩ { 0 , 1 , 2 } = { 0 , 1 } {\displaystyle \{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}}
同じテキストから文書番号と単語の出現位置まで含んだ完全な転置インデックスをつくると次のようになる。
文書番号と同様に、単語出現位置はゼロを基点とする。 "banana": {(2, 3)} というのは"banana"という単語が3番目の文書に現れ( T 2 {\displaystyle T_{2}} ) 、その文書中の4番目の単語(position 3)という意味である。
"what is it" というフレーズ検索を実行すれば、全ての文字列を含む文書0と文書1がヒットすることになる。しかし単語が連続して(句=フレーズとして)現れるのは文書1だけということが分かる。