転置インデックス
一般的な見解としては、各文書に連続してアクセスする際に、その都度、直接単語一覧を作成して格納していくことが手っ取り早い方法だろう。文書ごとに単語リストを格納していくと出来上がるのは我々がよく知るところの、いわゆる「索引」になる。この時点では文書あたりの単語リストであり、単語あたりの文書リストではないので転置索引(逆引き索引)ではなく正引き索引といえるだろう。以下がその例である。(検索エンジンによっては大きく構造が異なる場合もある)
転置インデックスの基本的な概念はテーブルに対して「単語Xはどの文書にあるか」といったクエリの応答速度を最適化するということである。
上記のテーブルに対するクエリだと、一覧中の各項目を逐一チェックして、各項目について単語が存在するかどうかを確認しなければならないアルゴリズムとなる。転置インデックスとは文書ごとに単語を探すのではなく、単語ごとにそれを含む文書を一覧抽出するために、上記のテーブルの行列を「転置」させたものである。
同じ例で、転置インデックスは次のようになるだろう。
こうすることで、単語を含む文書を見付けるために、アルゴリズムは転置インデックスの単語IDにジャンプし、文書一覧を見付けてくることが出来る。これによって検索応答時間の大幅な短縮がなされることとなる。