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