転置インデックス

検索エンジンの実装などに使われる、索引構造のこと。書籍の末尾には索引として、ある単語がどのページに含まれて居るかを列挙しているページがあるが、それを計算機上で実現するものを指す。

例えば、文書が1,000文書あったとして、各文書には固有の番号(文書ID)が付与されているとする。この1,000文書すべてから単語を抽出し、各単語が含まれる文書IDを記録していく。例として、以下のような構造ができあがる

Pearl   1, 2, 304 ...
Perl    1, 5, 10, 12, 15 ...
Python  5, 10, 32 ...

上記は "Pearl" という単語が文書ID1, 2, 304 ... の文書に含まれるという意である。この構造を、何かしらのデータ構造で表現したものが転置インデックスである。

転置インデックスでは、単語さえ決まればそれに紐付く文書IDはすぐに探すことができるため、情報検索分野で広く利用される