まさ@ブログ書き込み中

まさ@ブログ書き込み中

まさの旅、英語、プログラミング、プライベートについて、色々記録しています。

『大規模サービス技術入門』の中盤をまとめる(2)

 

おはようございます、東京に向かっているまさです。

 

昨日『大規模サービス技術入門』の中盤の回(第6回~第10回)のうち、データ圧縮やアルゴリズムについて少しお話しました。

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)

 

 

 

今回は残りの回のまとめとして、全文検索技術(第9回)についてまとめていきたいと思います。

 

ちなみに、第10回はその全文検索技術の実装についてでしたがPerlによる実装だったため軽く読み飛ばしましたので、実装についてはまとめません。

 

 

はてな全文検索技術

本書でははてなダイアリーはてなブックマーク全文検索について例が挙げられていました。

 

はてなダイアリーでは、はてなダイアリーの全文を検索の対象とし、はてなキーワードで検索できるようにしています。

 

これは以前はRDB(Relational Data Base)にキーワードとブログを関連づけていたのですが、レコード数が多くなるとスケーラビリティ的に破綻してしまったそうです。

 

そこで、サービスに特化した仕様を盛り込んだ検索エンジンを採用しました。

 

はてなブックマークでは検索エンジンの機能的にスニペットを出せるようにしているのではてなダイアリーとは違うデータ構造ですが、これも検索エンジンを別途つくることによってRDBに全データを保存するよりも効率的に対応しています。

 

具体的には、ユーザーがブックマークを追加するタイミングに合わせて、各ユーザーごとに検索インデックスを用意してそれを更新しているようです。

 

 

検索システムのアーキテクチャ

全文検索をするためには、以下の工程を踏まえなければなりません。

  1. クロール・・・検索する対象のドキュメントを持ってくること
  2. 格納・・・そのドキュメントを保存すること
  3. インデクシング・・・取ってきたドキュメントからインデックスを構築すること
  4. 検索
  5. スコアリング・・・検索結果の表示順を決めること
  6. 結果表示

 

それぞれの工程に課題があり、解決策があるようですが、ここでは3番の「インデクシング」と4番の「検索」についてまとめます。

 

このインデクシングと検索を実行する検索エンジンシステムは有名なもので、オープンソースで公開されているものもあるみたいです。

 

色々ある全文検索システムですが、そのアーキテクチャとして大きくgrep型」「Suffix型」「転値インデックス型」の3つがあるようです。

 

grep

grep型は検索対象のドキュメントを先頭から全部読んでいくという一番単純なアーキテクチャ

利点として、即時性が良い(ドキュメントが更新されてもすぐに検索できる)、検索漏れがない、並列化*やクエリ拡張がしやすいことが挙げられます。

*並列化=長いドキュメントを分割して並列してみたり、複数の検索語を一気に検索したりすること

 

Suffix型

ドキュメントを検索可能な形で持って、すべてメモリ上に載せるアーキテクチャ。以前紹介したTrieもこれ。転値インデックス型はドキュメント全体を持つわけではないので、その点において両者は異なります。

 

これは理論的には可能と言われていますが、情報量が大きくなり、実装が難しいみたいです。

 

転値インデックス型

簡単にいうと、単語(term)とドキュメントを関連づけたもの。

 

特徴として、転値インデックス方式はドキュメントとは別に転値インデックスをつくらなければなりません。

 

インデックスを前処理でつくらなければならないんですね。そのため、grepのようにドキュメントが更新されたら検索結果も変わる・・・とはいきません。

 

したがって、即時性には優れていません。また、実装方法によっては検索漏れが生まれてしまうそうな(詳しくは後述)。

 

一方、転値インデックスは圧縮してコンパクトに持つこともできるし、大規模化もしやすく、それなりの工数で実装できるという利点があって、実システムの多くがこのアーキテクチャを採用しているそうです。

 

 

転値インデックスの構造

転地インデックスの内部構造は大きくDictionaryPostingsの二つに分かれています。

 

Dictionaryはtermと呼ばれるドキュメントの中の単語の集まりで、そのtermに対応するPostingsがあります。転値インデックスとはtermを含むドキュメントを即時に発見しくみなのです。

 

Dictionaryの作り方

Dictionary(termの集まり)をつくるには、もちろんですがtermをどうやって選ぶかという問題があります。

 

一つは、言語の単語をtermとして扱う方法、もう一つは単語ではなくn-gramという手法で文字を適当な単位で区切ってtermとして扱う方法があります。

 

単語をtermとして扱う場合、辞書とAC法を使って実現する方法や、形態素解析を使う方法があります。

 

形態素解析を使う方法というのは、特に「分かち書き」の機能を使ってテキストを名詞や副詞などに分割しそれらをtermとして扱います。

 

検索漏れ

先ほど様々な検索システムのアーキテクチャをまとめた際に、転値インデックス型の懸念事項として検索漏れが生じてしまうかもしれない、という風に書きました。

 

これはつまり、形態素形態素解析の結果として分割された単語)をtermとしたときに起こりうる問題です。

 

本書では「Gears of War」というゲームを調べる際に間違って「Gear 発売日」としてしまうと、Metal Gearメタルギア)の発売日が出てきてしまうという例がありました。

 

つまり「Gears」という長いtermで「Gears of War」のドキュメント(Posting)は紐づけられてしまうので、「Gear」では引っかからないのですね。

 

これに対しては考え方によって許容すべきかどうかが分かれますね。「GearとGearsは別なんだから、Gear 発売日ではメタルギアの発売日が出るべきだ」という考え方もあれば「GearはGearsの部分語なんだから、Gears of Warがヒットすべきだ」という考え方もあります。

 

また、日本語の活用、例えば「ググる」で検索した場合「ググれ」や「ググって」が入っているドキュメントも結果表示したい場合、活用された単語は全部同じものと考えなければなりません。その場合は形態素解析によって語幹をつかんでおいてtermとするのも手です。

 

n-gram分割の問題とフィルタリング

n-gramとはあるテキストをn字ずつで切り出したものです。

 

「まさのブログ」の場合、2-gramであれば「まさ」「さの」「のブ」「ブロ」「ログ」のように分割していきます。ポイントは、文字の区切りは1文字ずつずらしながら行われるという点です。

 

しかし、n-gram分割には問題点があります。例えば「東京都」という言葉を2-gramで分割する場合「東京」と「京都」というtermが作られてしまい、「東京都」で検索をしているのに「東京タワーと京都タワー」といったテキストが入ったドキュメントが検索結果として表示されてしまいます

 

そのため、それを避けるために「東京都」というワードが検索結果の中に入ってるかどうか走査する(フィルタリングを行う)のが一般的ですが、検索結果が多ければ多いほどその分計算量が増えてしまいます。

 

 

再現率と適合率

検索の妥当性の評価基準の一つに「再現率」と「適合率」というものがあります。

 

「再現率」とはどれだけの量(結果)を返すことができているかを表すもので、「適合率」とは検索結果で返したもののうち、きちんと妥当なものを返せているかどうかを表すものです。

 

この二つはトレードオフとなっています。

 

例えば「まさのブログ」という検索をかけた際に、それに対応するドキュメントを多く返すことができればできるほど、再現率は高いと言えるでしょう。

 

しかし検索結果の中には、本来求められていないものが入っていることがありますね。このようなミスは検索結果が多ければ多いほど増えてしまいます。

 

よって、再現率が高ければ高いほど、適合率は低くなってしまう。再現率が低く、例えば検索結果が一つしかなくていいなら、一番妥当なやつを出せばいいわけですから、適合率は高くなります。

 

検索の妥当性を示す再現率と適合率は、それぞれ「網羅的に返したか」「正しいものを返したか」を表し、それぞれはトレードオフの関係です。

 

 

以上で『大規模サービス技術入門』の中盤のまとめを終わります。

ではまた。