全文検索エンジンについて学んでいたのだけど、転置インデックスのデータ構造という観点から見るといろいろ面白かったのでまとめてみる。
転置インデックスの具体的な構造
全文検索では、転置インデックス(Inverted index)という仕組みを使う。詳しくは第3回 転置索引とは何か？：検索エンジンはいかにして動くのか？｜gihyo.jp … 技術評論社 や、A first take at building an inverted index あたりを見たら良い。
もうちょっと具体的な構造が「検索エンジン自作入門」という本に書いてあったので、まとめてみると以下のようになる。
# 転置インデックス。トークンをキーとした連想配列で構築されている。 inverted_index = { "token1" => { docs_count => 3, # トークンが出現するドキュメント数 positions_count => 8, # トークンが出現する総回数 # 実際に出現するドキュメントや位置などを記録する配列。必ずdoc_id順などでソートされている。 postings => [ posting1, posting2, ... ], }, "token2" => { ... }, ... }; # postingsに入る一要素の例。 posting = { doc_id => 3, # tokenが出現するドキュメントのID positions => [ 2, 8, 10 ], # そのドキュメント中のどこに存在するか positions_count => 3, # tokenがそのドキュメント中に何回出現するか }
検索の流れ
この構造の転置インデックスを使うと、以下の流れで検索できる。
- 検索ワードをトークナイズする(例: 全文検索 -> 全文, 文検, 検索)
- トークンごとにinverted_indexからデータを取ってくる
- postingsを見てそのトークンが含まれるdoc_idを取得する
- 全てのトークンが含まれるドキュメントがマッチするドキュメントである
ただし上記のやり方だと、「全文検索」というワードを含むドキュメントではなくて、「全文」「文検」「検索」の全ての単語が含まれるドキュメントが検索される。
しかし、postingにpositionsも記録しているので、この情報を使えば「全文」「文検」「検索」が連続して出現するドキュメントを探すことができる。つまり、フレーズ検索も出来るようになっている。フレーズ検索については今日のElasticsearch学び Vol.3 - クエリ編 - $shibayu36->blog; にも書いた。
転置インデックスのmerge
転置インデックスの構造を眺めていると、mergeをしやすいというのも重要な特性だと感じた。
inverted_indexが二つ渡された時のmergeを考えてみると
- 両方に同じトークンが含まれたら単純にdocs_countを合計し、positions_countを合計し、postingsをmergeする
- postingsのmergeは後述
- トークンが片方にしか無かったら、そのままコピー
次にpostingsのmergeを考える。postingsはdoc_idでソートされた状態を維持してmergeしなければならない。特性上、両方のpostingsはdoc_idでソートされているので
- merged_postings = []する
- postings1の先頭とpostings2の先頭を見て、doc_idの小さい方を取り出し、merged_postingsに追加
- 繰り返し
という手順で、postingsのmergeが出来る。
転置インデックスをmergeできると何が嬉しいか
転置インデックスのmergeが使えると以下のようなことが出来る。
- 1ドキュメントをインデックスする時には、1ドキュメントのinverted_indexを作り、メモリ上のinverted_indexとmergeするという手順を使って、処理を簡素化出来る
- メモリ上のinverted_indexとストレージ上のinverted_indexをmerge出来る
- ストレージ上のinverted_index同士をmergeできる
これらを使えば
- 毎回ストレージにアクセスせずに、メモリ上にinverted_indexを作り、一定のタイミングでストレージ上とmergeするようにすれば、インデックス作成を高速化出来る
- 異なるファイルに保存しているinverted_indexをmerge出来る
ということが出来る。
これらの特性を眺めていると、elasticsearchが高速にインデックスできる理由や、分散して処理を行える理由がなんとなく見えてくる気がする。
