目次

第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
• 文書のタイトルと本文を取り出す
• 状態を把握する
• 文書データベースを構築する