Elasticsearchが裏でどのように動いているか理解できるようにするために、「検索エンジン自作入門」を読んだ。
この本を読んで、検索エンジンがやっていることを簡易的に知ることが出来た。少し理解するのは難しいが、具体的な例をコードレベルで見ることができる資料はなかなか無いので、非常に良い本であった。
2章以降からはコードを使って説明がされていくのだけど、そこからは理解が難しいかもしれない。しかし、それ以降を理解できなかったとしても、1章が端的に検索エンジンの仕組みについて書いてあるので、1章を読むだけでも価値があると思う。
自分の中では以下のものが参考になった。
- 検索エンジンは4つのコンポーネントからなる
- インデックス管理器
- インデックス検索器
- インデックス構築器
- 文書管理器
- 転置インデックスとは、{ 単語 -> [ docID & positions, docID & positions, ... ], ... } という集合で組み合わさっている
- 転置インデックス構築処理の流れ
- 転置インデックスからの検索処理の流れ
- 文書は単語数次元あるベクトルとみなす事もできるので、ベクトルの近さを見れば類似度が分かる
また以前転置インデックスについても書いたのでこちらも参考に。
読書メモ
- 検索エンジンは4つのコンポーネントで(図もあり) 207
- インデックス管理器
- インデックス検索器
- インデックス構築器
- 文書管理器
- 転置インデックスの仕組み 266, 341
- 単語 -> [ docID & positions, docID & positions, ... ]
- 転置インデックスからフレーズを探す 366
- 単語を全て含むものを検索し、さらに同一ドキュメントでpositionが隣同士
- 転置インデックスの辞書の実装 454
- 二文探索木やB+木
- 転置リスト(ポスティングリスト)の物理的レイアウト 506
- 転置インデックスを用いた検索処理の流れ 542
- 1. 検索クエリを構成する単語ごとに、ポスティングリストを取得
- 2. ブーリアン検索により、検索条件に該当する文書IDを取得
- 3-1. 検索条件に該当する文書とクエリの適合度を計算
- 3-2. 検索結果を並び替えるための属性値を取得
- 4. 適合度または並び替え用属性値の上位k件の文書を取得
- 検索クエリを構成する単語をポスティングリストの長さの昇順にソートすることで、比較回数を少なく出来る
- マージに基づくインデックス構築方法 655
- トークン抽出の流れ 849
- 転置インデックス構築処理の流れ 1124
- 転置インデックスからの検索処理の流れ 1161
- 検索クエリ「きょうは」というクエリで検索する例 1233
- マッチしているかどうかを判定する流れ 1247
- 類似文書検索 2087
- 動的なインデックス構築の基本的な戦略 2707
- インデックスをメモリ上のインデックスとディスク上のインデックスに分割して管理する
- 文書の追加による更新は、基本的にはメモリ上のインデックスに対して行う
- ただし、メモリ上のインデックスのサイズが事前に設定したメモリ容量の上限に達した場合は、メモリ上のインデックスをディスク上のインデックスに統合する
- インデックスのマージによる統合 2743
- Remerge戦略 ディスク上のインデックスを常に1つに
- No Merge戦略 マージを全く行わない
- Geometric Partitioning戦略 ディスク上を複数の大きさの異なるインデックスに分割し、小さいものをマージしていく
- XML Parserの種類 2864
- DOM Parser: 一気に読み込んでパース処理。要素の順序を気にせず操作を行える反面、メモリ使用量が多い
- SAX Parser: XMLを読み込みながら順次パース処理。メモリ使用量は少ないが、要素の順序を考慮する必要あり
