転置インデックス

Inverted index

その単語がどのページで使われいるかを表す表

本の索引みたいなやつ

用語

文書

Document

インデックスを用いる際の単位

本ならページ、サイトなら1ページ、メールなら1通など

文書を一意に特定する情報

本ならページ、サイトならURLとか？、メールならメールID?とか

ポスティング

文書と文書IDを対応付ける情報

p.1とかp.2とか

各単語におけるポスティングの集合

ここに含まれる全てのポスティングのドキュメント中にその単語が含まれている

「p.1, p.2」とか

転値リスト

ポスティングリストの集合

単語レベルの転値リスト

Word-level inverted list

その単語がどの文書に存在するかだけでなく、その中の場所の情報も含む転置リスト

「こんにちは」が何ページにあるかだけでなく、何ページの何文字目にあるかなどもわかる

利用用途

そのポジションの場所によって検索結果のスコアの優劣を付けたりして使ったり。

複数単語の検索のときに、フレーズを検索するときに使える

ポジションが隣り合っているかどうかを知るために使える

単に文書の中に「hello」と「world」があればよいでのはなく、「hello world」というフレーズを探したい

日本語の場合

各単語が空白で区切られていないので、以下のような手段を用いて単語ごとに区切る必要がある

作り方

まず全文書を単語に分解する

各単語がどのページで使われいるかを表す表を作る

table: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

↑この表を転置した表を作る

この際にキーワードをあいうえお順、アルファベット順にソートする

table: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

これこんな感じにする↓と完成

table:c

アンパンマン p.2, p.3

おにぎり p.2

元気 p.1

私 p.1

です p.2

は p.1

はすける p.3

わっしょい p.1, p.2

辞書の実装

メモリ上にあるか、二次記憶装置上にあるかで少し形を変える必要がある

転置リストの実装

各ポスティングリストを二次記憶装置の連続した領域に格納する

なんで？