転置インデックス
Inverted index
その単語がどのページで使われいるかを表す表
本の索引みたいなやつ
用語
文書
Document
インデックスを用いる際の単位
本ならページ、サイトなら1ページ、メールなら1通など
文書を一意に特定する情報
本ならページ、サイトならURLとか？、メールならメールID?とか
ポスティング
文書と文書IDを対応付ける情報
p.1とかp.2とか
各単語におけるポスティングの集合
ここに含まれる全てのポスティングのドキュメント中にその単語が含まれている
「p.1, p.2」とか
転値リスト
ポスティングリストの集合
単語レベルの転値リスト
Word-level inverted list
その単語がどの文書に存在するかだけでなく、その中の場所の情報も含む転置リスト
「こんにちは」が何ページにあるかだけでなく、何ページの何文字目にあるかなどもわかる
利用用途
そのポジションの場所によって検索結果のスコアの優劣を付けたりして使ったり。
複数単語の検索のときに、フレーズを検索するときに使える
ポジションが隣り合っているかどうかを知るために使える
単に文書の中に「hello」と「world」があればよいでのはなく、「hello world」というフレーズを探したい
日本語の場合
各単語が空白で区切られていないので、以下のような手段を用いて単語ごとに区切る必要がある
作り方
まず全文書を単語に分解する
各単語がどのページで使われいるかを表す表を作る
a
| 私 | は | 元気 | おにぎり | です | アンパンマン | はすける | わっしょい | |
| p.1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| p.2 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| p.3 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
↑この表を転置した表を作る
この際にキーワードをあいうえお順、アルファベット順にソートする
b
| p.1 | p.2 | p.3 | |
| アンパンマン | 0 | 1 | 1 |
| おにぎり | 0 | 1 | 0 |
| 元気 | 1 | 0 | 0 |
| 私 | 1 | 0 | 0 |
| です | 0 | 1 | 0 |
| は | 1 | 0 | 0 |
| はすける | 0 | 0 | 1 |
| わっしょい | 1 | 1 | 0 |
これこんな感じにする↓と完成
よく見る索引だ
c
| アンパンマン | p.2, p.3 |
| おにぎり | p.2 |
| 元気 | p.1 |
| 私 | p.1 |
| です | p.2 |
| は | p.1 |
| はすける | p.3 |
| わっしょい | p.1, p.2 |
辞書の実装
メモリ上にあるか、二次記憶装置上にあるかで少し形を変える必要がある
転置リストの実装
各ポスティングリストを二次記憶装置の連続した領域に格納する
なんで？