前回は、大規模データ処理のノウハウの塊である全文検索技術についてまとめた。ここでは、基本部分、作り込み、速度と精度の追求である全文検索エンジンの作成について解説する。
１ [課題]はてなブックマーク全文検索を作る
課題内容
[課題]はてなブックマークに投稿された直近1万件のエントリを対象にした全文検索を作る。検索語を含むエントリを返す。返す内容はURL、タイトルを含むこと。スニペットも表示。投稿日付順にソート。これらに加え、進度に合わせて以下の2つ。
- 検索の作り込み：AND/OR検索に対応、カテゴリでの絞り込みに対応
- 速度と精度を追求：実用的な検索速度、検索漏れやfalse-positiveを回避
サンプルデータの形式とデータサイズ
- URLやタイトルなどエントリの基本データが10,000件分記録されているテキスト
- 各エントリの本文テキスト10,000ファイル
辞書の構成
Dictionary＋Postings
インタフェース
アプリケーションのインターフェースは以下の2つ。
- コマンドラインから起動
- 対話的なインターフェース
基本部分＋作り込み
作り込みは以下の3つ。
- 全文検索
- and、or検索
- カテゴリによる絞り込み
速度と精度で勝負
サンプルクエリに対する検索結果の上位5件を評価。検索時間と精度（false-positive：検索漏れ）。
２ 回答例と考え方
回答例
転置インデックスを作ってディスクに書き出すindexer.plと、そのインデックスをロードして対話プロンプトで検索するsearcher.plの2つのスクリプト（詳細は著書参照）。
indexer.plの実装
実行例は以下の2段階。
- 基本データファイル（10000entries.txt）と本文テキストのディレクトリを指定してインデクシング
- 同様に引数を与えて検索
searcerh.plの実装
入力で与えられたデータファイルを読み取りつつ、indexer.plで作ったインデクスファイルをロード。ロードされた転置インデックスは、そのままPerlのハッシュとして使える。
改善点
以下の4つが挙げられる。
- AND/OR検索を実装する
- searcher.plで検索語も分解する
- 形態素解析でなく、n-gram方式に変更してみる
- 転置インデックスに単語出現位置を記録して、スニペット表示に役立ててみる
最後に
はてなブックマークの全文検索機能を題材に、転置インデックス型の検索エンジンを作成した。検索エンジンの内部構造を見ると、Perlのハッシュのようなデータ構造で実現できる程度の簡単な構造になっていることがわかる。こういった基礎部分をもとに、Twitterのスケールアウト戦略といった応用も学んでいくことが望まれる。
次回は、大規模データ処理を支えるサーバ/インフラ入門について解説する。
 |
[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB DB PRESS plusシリーズ) |
