前回は、応用への道筋であるはてなキーワードリンクの実装についてまとめた。ここでは、大規模データ処理のノウハウ満載な全文検索技術について解説する。
１ 全文検索技術の応用範囲
はてなのデータで検索エンジンを作る
はてなで実際に運用している検索エンジンの概要からスタートし、その後検索エンジンを作っていく上で重要な要素の１つである転置インデックス（inverted index）について説明する。転置インデックスは、辞書（dictionary）と呼ばれる部分と、Postingsと呼ばれる部分の2つの基本要素によって構成されている。
はてなダイアリーの全文検索
はてなダイアリーの「含むブログ」機能では、検索システムを検索以外に応用している。含むブログは、はてなキーワードに含まれている言葉のみ検索できるシステムである。以前はRDBで処理していたがスケーラビリティ的に破綻したため、検索エンジンを実装した。機能を日付順に出力するというものに特化した仕様にすることで、高速化を図った。システムコアはC++で実装し、ThriftというライブラリでPerlと通信している。
はてなブックマークの全文検索
はてなブックマークの検索機能は、自分がブックマークしたサイトだけを対象とした全文検索エンジンである。ユーザごとに検索インデックスを作ることで、大規模データを小分けに検索することができる。コンパクトかつ簡単に実装することができ、自前実装で細かい要求に応えることができるのである。
２ 検索システムのアーキテクチャ
検索システムができるまで
検索システムができるまでには以下の6つのステージがある。ここでは特に3.インデクシングと4.検索について解説する。
- クロール（収集）
- 格納
- インデクシング（索引）
- 検索
- スコアリング
- 結果表示
検索エンジンいろいろ
- grep
- Namazu
- Hyper Estraier
- Apache Lucene
- Shunsaku
- Senna
- Sedue
- Lux
全文検索の種類
- grep型：grep、Shunsakuなど。検索対象を先頭からすべて読む、即時性に優れ、検索漏れもなく、並列化やクエリ拡張が容易である点が特徴
- Suffix型：Sedue。検索可能な形で検索対象全文を持つ。データ構造はTrie、Suffix Array、Suffix Treeなど。理論的には可能だが、情報量が大きく実装が難しい
- 転置インデックス型：主流（Google）。termとドキュメントを紐づける。バランスのよいアーキテクチャだが、即時性に優れず検索漏れがあるなどの欠点もある
３ 検索エンジンの内部構造
転置インデックスの構造
転置インデックスはtermとドキュメントの関連づけのこと。termはドキュメント中の単語で、termの集合がDictionaryである。つまり、転置インデックスの内部構造はDictionaryとPostingsからなる。termを含むドキュメントを即時に発見することができるのである。
Dictionaryの作り方
Dictionaryを作り方は、単語をtermとして扱うものとn-gramをtermとして扱うものがある。前者を行う方法には、辞書とAC法を使う方法と形態素解析を使う方法がある。例えば、辞書ははてなキーワードやWikipedia、形態素解析はMeCabなどが有名である。形態素解析の特徴は以下の6つである。
- 品詞を推定する
- 辞書を持っている
- 辞書にない単語も予測できる（ものもある）
- 単語の並びを考慮に入れる
- 単語の並びを機会学習する（場合もある）
- 辞書をカスタマイズできる
n-gramはテキストをn字ずつ切り出したもの。例えばabracadabraの3-gramだったら、abrとbraとrac…となる。クエリも同じルールで分割するが、誤った検索が行われないためにフィルタリングが行われる。フィルタリングは検索結果を走査して確認するもの。対象が大きいと計算量が大きくなるため、対象が小さければよい。再現率（Recall）と適合率（Precision）とは、検索の妥当性の評価基準である。前者が網羅的に返したか（正例の数/適合する総数）で、後者が正しいものを返したか（正例の数/返した総数）である。
Postingsの作り方
PostingsはIDを持っている配列のようなものである。その構成には大きく2つあり、出現位置も保持するものと文書IDのみ保持するものがある。前者はFull Inverted Indexと呼び、スニペット、スコアリング、フィルタリングが容易である。後者はInverted File Indexと呼び、サイズが小さく実装が容易である。ここでは後者について説明する。
Inverted File Indexはデータ構造が単純なため、文書IDの順をソートすることでVB Codeで圧縮することができる。そのためそこそこの圧縮率と高速展開性能を持つ。また、構造が左側にtermがあり、右側に圧縮されたPostings Listがあるため、key-valueストアに保存するのに向いている。
スコアリングについて補足
過去の検索の歴史の中で「ドキュメントの重要性」を考慮してランキングをつけたのはGoogleが初めて。それがPageRankであり、他にも様々なアルゴリズムを使ってランキングを決めている。TF/IDF（Term Frequency/Inverse Document Frequency：単語の出現頻度と逆出現頻度）といった指標もある。
最後に
全文検索技術の応用範囲、検索システムのアーキテクチャ、そして検索エンジンの内部構造について解説した。具体的には、はてなダイアリーの「含むブログ」機能、検索システムの6つの段階（クロール、格納、インデクシング、検索、スコアリング、結果表示）、転置インデックスの構造についてまとめた。
次回は、基本部分、作り込み、速度と精度の追求である全文検索エンジンの作成について解説する。
 |
[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB DB PRESS plusシリーズ) |
