『検索エンジン自作入門』

https://gyazo.com/f9c76bc2dfd216ff4e65a1c8397c1cbc

2014/9/25

第1章

p.30~

少し後で読み返したい

第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

文書のタイトルと本文を取り出す

状態を把握する

文書データベースを構築する