転置インデックス

出典: フリー百科事典『ウィキペディア（Wikipedia）』

転置インデックス（てんちいんでっくす、Inverted index）とは、全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造をいう。転置索引、逆引き索引、転置ファイル(Inverted file)などとも呼ばる。

[編集] 概要

転置インデックスは検索エンジンでもっともよく利用されるデータ構造である。検索キーが単語(文字列)であり、連想配列の値が位置情報である場合、ハッシュテーブルの形態を取ることもある。

転置インデックスには大きく分けて2通りの手法がある。レコード単位転置インデックス(record level inverted index; 転置ファイルインデックスとも呼ばれる)は単語と、その単語を含む全ての文書をリストとして備えている。単語単位インデックス(word level inverted index; 完全転置インデックスとも呼ばれる) は、単語を含む全ての文書の他に、その単語が文書中のどこに現れるかという位置情報まで含んでいる。単語単位転置インデックスの実装手法にも幾通りかある。最も単純なものは全ての文書IDとその保存位置情報をペアで格納したものである。レコード単位転置インデックスはディスク容量の節約にはなるが、その分、機能性も乏しいものとなってしまう。（普通検索エンジンで行うような）単語検索は可能だが、（検索クエリで引用符でくくるような）フレーズ検索はできない。

[編集] 例

ここに次のようなテキストがある。 $T 0 =$ "it is what it is", $T 1 =$ "what is it", $T 2 =$ "it is a banana"

ここから得られる転置インデックスは次のようなものである。

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

"what", "is" そして "it" といった語に対して単語検索をかけてみると、次のような集合が得られる。

$\{0,1\} \cap \{0,1,2\} \cap \{0,1,2\} = \{0,1\}$ .

同じテキストから文書番号と単語の出現位置まで含んだ完全な転置インデックスをつくると次のようになる。

文書番号と同様に、単語出現位置はゼロを基点とする。 "banana": {(2, 3)} というのは"banana"という単語が3番目の文書に現れ( $T 2$ ) 、その文書中の4番目の単語(position 3)という意味である。

"a":      {(2, 2)}
"banana": {(2, 3)}
"is":     {(0, 1), (0, 4), (1, 1), (2, 1)}
"it":     {(0, 0), (0, 3), (1, 2), (2, 0)} 
"what":   {(0, 2), (1, 0)}

"what is it" というフレーズ検索を実行すれば、全ての文字列を含む文書0と文書1がヒットすることになる。しかし単語が連続して（句＝フレーズとして）現れるのは文書1だけということが分かる。

[編集] 転置インデックスの有用性

検索エンジンを設計するとき、転置インデックスの必要性を考え、エンジンのアルゴリズム、その動作ステップを考慮することは重要なことである。たとえば、コーパスを使った手法で索引ファイルを作成することを考えてみる。アルゴリズムの手始めは、最初の文書をチェックして、単語ごとに分割することである。処理の最後に、文書中に現れる全ての単語の一覧とその出現位置をリストアップする。むろん、同じ単語は複数回にわたって出現する。したがって出現位置情報も1つだけとは限らなくなる。位置情報とは単語が文書中のどこに位置しているかであり、単語の出現に先立って現れた文字数をカウントすることだといえよう。たとえば、ある文書に最初に現れた単語は、文書中の最初の文字を含んでおり、すなわち位置情報は｢0｣であるといえる。2番目の単語は5文字目に出現するとする。したがって位置情報も｢5｣となる。

表形式にすると、次のようなものになるだろう。

単語ID	単語	位置情報
1	dog	1,20,500,etc
2	cat	10,45,3445,etc

1つの文書だけでなく、コーパスを用いているので、各文書に現れる全ての単語を格納するのに、より大きなリストが必要となってくる。ここが検索エンジン設計者の見解が異なるところであり、すべての検索エンジンが同じ設計になっていない理由の1つである。

一般的な見解としては、各文書に連続してアクセスする際に、その都度、直接単語一覧を作成して格納していくことが手っ取り早い方法だろう。文書ごとに単語リストを格納していくと出来上がるのは我々がよく知るところの、いわゆる「索引」になる。この時点では文書あたりの単語リストであり、単語あたりの文書リストではないので転置索引（逆引き索引）ではなく正引き索引といえるだろう。以下がその例である。（検索エンジンによっては大きく構造が異なる場合もある）

文書ID	含まれる単語IDと位置
1	(1 at 1,20,500) (2 at 10,45,3445)
2	(1 at 3, 50, 60) (2 at 100, 120, 130,..)
3	etc

転置インデックスの基本的な概念はテーブルに対して「単語Xはどの文書にあるか」といったクエリの応答速度を最適化するということである。

上記のテーブルに対するクエリだと、一覧中の各項目を逐一チェックして、各項目について単語が存在するかどうかを確認しなければならないアルゴリズムとなる。転置インデックスとは文書ごとに単語を探すのではなく、単語ごとにそれを含む文書を一覧抽出するために、上記のテーブルの行列を｢転置｣させたものである。

同じ例で、転置インデックスは次のようになるだろう。

単語ID	該当文書ID
1	1,3,4,5
2	2,3,4
3	etc

こうすることで、単語を含む文書を見付けるために、アルゴリズムは転置インデックスの単語IDにジャンプし、文書一覧を見付けてくることが出来る。これによって検索応答時間の大幅な短縮がなされることとなる。

[編集] 参考文献

Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 560–563 of section 6.5: Retrieval on Secondary Keys.
Justin Zobel, Alistair Moffat and Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing. ACM Transactions on Database Systems (TODS), Volume 23, Issue 4 (December 1998), Pages: 453 - 490.