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

書籍の概要

この本の概要

まいにち使っている検索エンジンがどうやって動いているか,知っていますか?
本書では,小さな検索エンジンを作りながら,ソースコードレベルで検索エンジンのしくみを解説。
Yahoo!Japanの検索エンジン開発チームを経て2008年度上期未踏IT人材発掘・育成事業において高性能分散型検索エンジンの開発によりスーパークリエータに認定された山田浩之氏と,全文検索エンジンSenna/Groongaの開発に携わってきた末永匡氏による,オンリーワンの1冊です。

こんな方におすすめ

  • 検索エンジンのしくみや実装に興味のある方

著者の一言

本書は,GoogleやYahoo!などのウェブ検索サービスの裏側の検索エンジンというシステムに焦点を当て,その内部のメカニズムを明らかにしていきます。まず第1章で,検索エンジンの基礎および原理をしっかり学んでいただき,第2章以降で,サンプル検索エンジンのソースコードを用いて検索エンジンの開発を体験していただきます。このような原理と実践のバランスにより,読者のみなさんが検索エンジンの仕組みをより深く理解することを目指しています。

原理と全体の構成および監修は企業や大学で検索エンジンの研究開発をしてきた山田が担当し,実践および運用におけるポイントはオープンソース検索エンジンSenna/Groongaの開発者であり実際に多数の検索サービスの運用経験を持つ末永さんが担当することにより,このようなバランスを実現することできました。

本書によりみなさんが得た知識や経験が,画期的なソフトウェアやサービスを生み出す1つのきっかけとなれば幸いです。

この書籍に関連する記事があります!

検索エンジンは「使う」よりも「作る」ほうがおもしろい!
GoogleやYahoo!などを使わない日はないくらい,検索エンジンは私たちに欠かせない存在となりました。

目次

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

著者プロフィール

山田浩之(やまだひろゆき)

はじめに,第1章,第5章1節,Appendix 1,全体監修を担当。
日本アイ・ビー・エム株式会社を経て,ヤフー株式会社にて分散型全文検索エンジンの研究開発に従事。2008年上期未踏IT人材発掘・育成事業において高性能分散型検索エンジンの開発によりスーパークリエータに認定。現在は東京大学生産技術研究所にて高性能並列データベースの研究開発に従事。博士(情報理工学)。


末永匡(すえなが たすく)

サンプル検索エンジンwiserの作成,第2章から第7章,Appendix 2,おわりにを担当。
Tombo, Inc./株式会社wktk 所属。長崎県出身。Web上では「グニャラくん」のハンドルネームで活動。
ブログ検索サービスの担当となり,はじめて検索エンジンに触れる。オープンソース検索エンジンSennaへのパッチ投稿をきっかけに,検索エンジンSenna/groongaの開発に携わる。
中央集権的ではない,より自由でアナーキーなアプリケーションプラットフォームを夢見て,日々奮闘中。