先行発売で、検索エンジン自作入門を購入しました。まだペラペラと眺めている状況ですが、これが非常に面白いです。
「検索エンジン自作入門」は、集めた文章をいかに整理するかをテーマとして扱っている本です。整理するという意味は、検索エンジンを利用するというライフハック的な意味ではありません。整理する為の検索エンジン自体を自分で作ることで理解するという、極めて硬派な本です。
「検索エンジン自作入門」とは？
「検索エンジン自作入門」は、未踏IT人材発掘・育成事業にスーパークリエータに認定された山田浩之氏と、Senna/groongaの開発者の末永匡氏の共著です。検索エンジンについて語らせたら、日本でこれ以上の人たちはいないだろうという組み合わせです。ということで、内容は非常に濃いのですが、難しい内容を解りやすく解説されています。
一方で、扱っている内容は非常にマニアックです。下に目次付けておくので見て頂きたいのですが、紙面の5割以上が転置インデックス（Inverted index）についてです。つまり１つのアルゴリズムについて、100ページ以上を割いていることになります。こんな有難い本は、なかなかないですね。
そして、それを学ぶ為に、必要最小限の機能を実装した検索エンジン「wiser」を開発し、ダウンロードできるようにしているという力の入れっぷりです。この本を大学の授業なので、1年間通して教えたらかなり面白いのではないでしょうか？
転置インデックスは、検索エンジンの肝
検索エンジン本に関わらず、ここまで転置インデックスの話しかしていません。では何故「検索エンジン」についての本の中身が、転置インデックスになるのでしょう？それは、検索エンジンの肝が全文検索であり、全文検索の実装の1つが転置インデックスであるためです。
転置インデックスの概念は、書籍の索引と同じです。目的のページに早く辿り着く為の方法です。それをコンピュータが実行できるようにしているのが、転置インデックスです。リレーショナル・データベースにも、検索を早くする為に幾つかインデックスがありますが、基本的には一緒ですね。文章に対して比較的適しているのが、転置インデックスです。また転置インデックスの中身の技術については、RDBMSのインデックスと同じものを使っているものもあります。
以前、Mecabの開発者の工藤拓さんの講演を聞いていたところ、「Double Array TRIEのの実装が、Mecabだ」といった趣旨のことを話されていました。その一言が非常に印象的でした。もちろんDouble Array TRIEだけが、Mecabを構成している要素ではないでしょう。しかし、どの技術がMecabの本質的な特徴かと突き詰めたら、Double Array TRIEだということと理解しました。プロダクトの優位性を決定づけるものが何か、考えさせられたものです。
転置インデックスを知ると、何が嬉しいの？
実際のところ、9割のITエンジニアにとっては、転置インデックスなんて自分に関係ないというと思います。私も、詳しく調べて使っていた時がありましたが、直接的に関係していたのは一時期だけです。
では、何の役にたつのか？検索エンジンであったり転置インデックスは、わりと根源的な技術の1つです。システムを設計する上で、こういった知識があるかないかで、自ずと結果が違ってきます。
また、毎年いろいろなプロダクトやサービスが出てきますが、どういった仕組みで作られているか理解できると、その製品の将来性が解ります。技術の引き出しをつくる為にも、こういった要素技術を抑えておく必要があります。
検索エンジン自作入門と、Rubyによるクローラー開発技法。或いは感想
自著の宣伝になりますが、最近「
Rubyによるクローラー開発技法」という本を書きました。この本のテーマは、いかに文章やデータを集めるかです。文章やデータを集めているだけなので、次はどうするのというのが出てきています。本の中ではあまり書けませんでしたが、その次の技術としては、文章を整理する為の検索エンジンや、データマイニング、あるいは可視化などで、情報を整理して活用することがあります。
そんな意味で、ちょうど良いタイミングで良い本が出たなぁと思います。また、少し前に「
手を動かしながら学ぶ ビジネスに活かすデータマイニング」という本も出ています。データを集めて検索したり分析したりの学習の敷居が、ずいぶん低くなって楽しいなぁと思います。ぜひぜひ、一緒に読んで頂ければと思います。
2014/9/25追記
Kindle版も出ている模様です。ちょっと待てば良かったｗ
See Also:
『Rubyによるクローラー開発技法』を書きました 
Rubyによるクローラー開発技法の目次 
検索エンジン自作入門の目次
第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
文書のタイトルと本文を取り出す
状態を把握する
文書データベースを構築する
