moshimore Knowledge

アプリ開発・紹介とメモ書き、日々の日記。

検索エンジン自作入門

f:id:moshimore:20180124014849j:plain
もうかれこれ4年前の話、2014年に「検索エンジン自作入門」というが発売され、興味があったので買ってありました。
「入門」といっても中身はガチガチな技術的な話が書かれていて、サラリと理解できる内容ではありません。

どこから進めていこうか

年が明けて、1月も終わろうとしている今日、改めて読み直して、サンプルソースを動かしたいなと思います。

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏

以下、目次です。これに沿って紹介していきます。

第1章 検索エンジンはいかにして動くのか

1-1 検索エンジンの構成を理解する

検索エンジンとは
検索エンジンを構成するコンポーネント
検索エンジンに関連するコンポーネント

1-2 高速な全文検索を実現するインデックスの仕組み

全文検索の2つの方法
転置インデックスの仕組み
転置インデックスの作り方
転置インデックスで用いられる用語

1-3 転置インデックスを深く知る

転置インデックス=辞書+転置リスト
転置インデックスから単語を探す
転置リストに単語の位置情報を加える
転置インデックスからフレーズを探す

1-4 日本語文書から転置インデックスを作る

日本語の文を分割する方法
分割方法のトレードオフ

1-5 転置インデックスの実装

辞書の実装
転置リストの実装

1-6 転置インデックスを用いて検索する

ブーリアン検索
転置インデックス用いた検索処理の流れ
関連度の計算方法
情報検索における検索

1-7 転置インデックスを構築する

メモリを用いた転置インデックスの構築
二次記憶を用いた転置インデックスの構築
静的なインデックス構築と動的なインデックス構築

1-8 検索したい文書を用意する

データを集める
データを整形する

第2章 全文検索エンジンのサンプルを準備する

2-1 全文検索エンジンwiserの概要

wiserの構成
検索用の文書を用意する

2-2 wiserをセットアップする

wiserをビルドする
wiserを起動する
Wikipediaデータを展開する

2-3 wiserを動かす

転置インデックスを構築する
転置インデックスを用いて検索する
grepとwiserの実行速度を比較する

第3章 転置インデックスを作ろう

3-1 転置インデックスのおさらい

トークンを抽出する
トークンごとにポスティングリストを作る

3-2 転置インデックスを構築する

ストレージ上でポスティングリストを作る
ポスティングリストと転置リストのデータ構造
転置インデックスの構築手順をソースコードレベルで追う
ソースコードをより詳細に見る
コラム 要件に応じた検索エンジン(システム)の設計

第4章 検索しよう

4-1 検索処理のおおまかな流れ

検索処理の流れを把握する

4-2 転置インデックスを用いて検索を行う

検索処理をソースコードレベルで追う
関数split_query_to_tokens()の内部を読み解く
具体例を用いて検索処理の流れをより深く理解する
関数search_docs()の内部を読み解く
関数search_phrase()の内部を読み解く
コラム タグ検索はどのように実現されるか

第5章転置インデックスを圧縮しよう

5-1 圧縮の基本

転置インデックスにおける圧縮のメリット
コラム 圧縮の目的
転置インデックスの圧縮方法
転置リストの圧縮方法
なぜ圧縮できるのか

5-2 wiserにおける圧縮機能の実装

圧縮機能のソースコードの概要
圧縮しない場合の動作を見る
Golomb符号の概要を把握する
Golomb符号における符号化の処理を読み解く
Golomb符号における復号の処理を読み解く

第6章 wiserの改良やパラメータの調整に挑戦してみよう

6-1 検索処理を効率化する

改善のポイント
検索クエリを重複しないトークンに分割する

6-2 フレーズ検索をやめてみる

2文字の文字列を検索したときの挙動を調べる
3文字の文字列を検索したときの挙動を調べる

6-3 検索結果の出力順序を変更する

検索結果の並び替えの軸となる指標
検索結果を文書サイズの大きい順に出力する
コラム ランキングSPAM

6-4 1文字の検索クエリで検索できるようにする

特定の文字を接頭辞に持つトークンの一覧を取得する
検索して結果をマージする
コラム 類似文書検索を実現するには

6-5 転置インデックスの更新バッファ量を変えてみる

バッファサイズの違いによる効果の差を確認する
sarコマンドで負荷を調べる

6-6 英字アルファベットだけトークンの分割方法を変えてみる

英単語の検索で適合率が下がる問題を避けるには
インデックスの対象にする文字をどう判定しているか
トークンの分割を行う関数を修正する

6-7 圧縮の効果を確認する

Golomb符号の効果を見る
非圧縮時と圧縮時のインデックスサイズを比較する
コラム 全文検索エンジンの安易な利用を避ける

第7章 これからより深く学ぶために

7-1 wiserでは扱えなかったテーマ

転置インデックス以外の全文検索インデックス
大規模なデータを効率よく扱えるストレージ
キャッシュを利用した高速化
さまざな圧縮方法の利用
ランキングの改良
適合率と再現率の調整
検索結果の並び替え処理の負荷を減らす
並列処理
属性による絞り込みとの併用
ファセット検索
コラム レイテンシとスループット

7-2 全文検索エンジンGroongaでの工夫

トークンの部分一致検索による再現率の向上
メモリマップトファイルの利用
スニペット
コラム 広報活動の大切さ

7-3 利用者の意図を考慮した検索エンジンを目指して

ストップワードを導入する
形態素解析のミスに対処する
コラム ぎなた読み
組文字・全半角を扱う
ひらがな・カタカナを同一視するどうか判断する
表記のゆれを考慮する
検索クエリを正規化する
ブーリアン検索の解釈に気をつける
検索クエリを形態素解析器により適切に解析する
誤り訂正を行う
入力を補完する
関連する検索キーワードを提案する

7-4 文書の収集・抽出におけるポイント

クローラを作るうえで対処すべきポイント
テキストの抽出で対処すべきポイント

Appendix

A-1 高度な話題

近年の圧縮手法
動的なインデックス構築
インデックスの分散

A-2 wiserのテキスト抽出・保存処理

XMLを扱う2種類のAPI ~DOMとSAX
文書のタイトルと本文を取り出す
状態を把握する
文書データベースを構築する