転置インデックス

全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造をいう。転置索引、転置ファイル、逆引き索引などとも呼ばれる。

転置インデックスとは文書ごとに単語を探すのではなく、単語ごとにそれを含む文書を一覧抽出するために、上記のテーブルの行列を｢転置｣させたものである。

なるほど

単語Wから「Wを含む文書の一覧」が得られるようなデータ構造をつくる

grep型が都度すべての文書を検索するのに対して、インデックス型はその名の通り索引を用いて効率的に検索を行うことができるためです。

転置インデックスは後者のやり方

ポスティングリスト

辞書の各単語がどの文書に出現するかを保存したものです。 キーを単語、値を文書の配列とした連想配列をイメージするとわかりやすいかと思います。

これは理解はできる

検索を行う際は検索クエリに含まれる単語ごとにポスティングリストを取得し、その積集合を取ることで検索クエリに含まれる単語を含んだ文書を取得することができます。

そうなん？全くイメージわかねえ

が、例もあった

が、本質的にはハッシュっぽいね