はじめに
前回までで、検索エンジンの基本となる仕組みの大枠は説明しました。
今回は、復習を兼ねてこれまでの連載全体を見ていき、検索エンジンを作る上で説明が足りなかった部分を補足していこうと思います。本連載では実際のコードはあまり載せられませんが、ぜひこの際に簡単な検索エンジンを作ってみることをお勧めします。
全体の構成
第2回で紹介した検索エンジンの構成をもう一度見てみましょう。
図1 検索エンジンの構成
検索エンジンは索引とその索引を構築する部分、そしてその索引を検索する部分の3つに分けられることを説明しました。本連載では、索引に関しては第3～6回、構築方法に関しては第7回、そして検索方法に関しては前回の第8回でそれぞれ説明してきました。各項目をとても足早に説明してきましたが、一応全部の要素がカバーされていますので、これまでの知識を使って簡単な検索エンジンを作ることはできてしまいます。
以下、実際に簡易検索エンジンを作るにあたって、それぞれのコンポーネントについて必要な知識をもう少し補足していきます。
転置索引
全文検索における最も普及した索引構造が転置索引でした。転置索引は辞書と転置リストからなり、辞書には文書に出現したタームが検索しやすい用に格納され、そのタームがどの文書のどこに出現するかという情報が転置リスト（ポスティングリスト）に格納されています。
第5回では、辞書と転置リストの実装について説明しました。
実際に作る場合、ディスクベースの辞書の場合はB+木が良いと思いますが、実装する際はOracle Berkeley DBやTokyo Cabinet、また私が開発しているLux IOなどの既存のライブラリを使うことをお勧めします。
また転置リストの実装ですが、第5回で説明したように、ファイルシステム上の1つのファイルとして実装し、辞書に各タームのポスティングリストのオフセットを保存させるか、オフセットの管理が面倒な場合は、1ポスティングリストを1ファイルとして実装し、辞書に各ポスティングリストのファイル名を保存しても良いでしょう（※1）。
さらに簡単にするには、ポスティングリストの中身は、TFありの文書レベルとし（第4回参照）、その他の統計値は保存しない方法もあります（第8回参照）。また、日本語の文書を対象とする場合は、形態素解析エンジンのライブラリが必要となりますが、広く使われていて高速なMeCabをお勧めします。英語の文書を対象とし、タームの抽出は文を空白で区切るだけでも、動作を理解するだけなら十分でしょう。
索引の構築
第7回で説明した2つの構築方法のいずれかを使うのが良いと思いますが、Merge-based Inversionでは、メモリ上で辞書と転置リストを構築し、ある程度溜まったらディスクに書き出すという操作を繰り返し、最後にそれらをマルチウェイでマージする方法でした。メモリ上の辞書は、既存の木構造のライブラリなどが利用できます。また、マルチウェイマージでは、各ウェイから一番小さい(または大きい)要素を取り出すのにヒープ構造が有効になります。
Sort-based Inversionを実装する場合は、ExternalSortの部分をUNIX,Linuxのsortコマンドにより行うことにより、実際に記述するコード量が少なくなりそうです。
第7回では転置索引の構築方法のみを述べましたが、実際にはユーザに提示するスニペットと呼ばれる短い文章のために、文書の全文または一部を保存しておきます。文書IDに対して文書の内容を保存するので、第5回の図2で紹介したようなデータ構造やハッシュデータベースなどを使うことができます。
索引の検索
ユーザから入力されたクエリはそのまま文字列として渡ってきます。まずは、そのクエリを索引構築時に文書に対して行うのと同じようにタームに分割します。その後、そのぞれのタームを辞書に引き当てて各ポスティングリストを取得し、各ポスティング（文書）とクエリの関連度をアキュムレータに溜めていくという手順が検索処理でした（第7回のリスト3）。
どのような関連度を計算するかで、統計値をどこまで含むかは変わってきますが、TFだけを保存していた場合は、TFの多い順で関連度を計算しランキングをすることもできます。文書が長ければ高いスコアが得られてしまうのであまり現実的ではありませんが、これも全体の動作を理解するためであれば十分でしょう。その場合は第8回で紹介したリスト3のアルゴリズムを使って、アキュムレータにはTF値を足して行くことになります。
上位K件を取得する場合はヒープ（によるpriority queue）の利用が効率的です。言語によってはヒープ構造が用意されているのでそれを利用するか、効率をあまり考えずにクイックソートで全件をソートして上位を取り出しても良いと思います。
また、構築の部分で文書の内容が保存されている場合は、上位K件の文書IDから文書の内容を取得して、そこからスニペットを生成し、最終的にユーザに結果を提示します。
全体のまとめ
全体の処理のまとめを図2に示します。
図2 検索エンジンの概念
図1の各コンポーネントの処理をもう少し詳細に書いてみました。よくわからないところがあったら各回の記事をもう1回読んでみてください。
まとめ
今まで学んできたことを、簡単にではありますが体系的に復習しました。
転置索引は非常にシンプルな構造なので、理解するのは難しくないと思います。しかし、頭で理解するのと実際に作れるのには雲泥の差があると思います。実用的かどうかなどは考えずにとりあえず簡単なものを作ってみることで、検索エンジンの細かい仕組みが見えてくると思います。
次回からは、少しだけ高度な話題や近年の話題について触れていく予定です。
