Bayesian Setsによる関連文書検索システムStupa

都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。

Bayesian Setsとは

Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、

クエリ	出力
apple, banana	chocolate, strawberry, vanilla, cherry, ...
apple, macintosh	software, windows, mac, computer, ...

どちらのクエリにも"apple"という言葉が含まれていますが、1つ目のクエリは"banana"と一緒に検索しているため、果物のapple, bananaに関連するアイテムが得られていることが分かります。また2つ目のクエリでは"macintosh"と共に検索しているため、コンピュータ関連のアイテムが結果として得られています。このように入力されたアイテムと同じ概念の集合をオンデマンドに特定し、その集合中の他のアイテムを取得することができます。 Bayesian Setsについてより詳しくは、以下のページをご参照ください。

またBayesian Setsを使った他のシステムには連想検索エンジンReflexaがあり、はてなブックマークの関連エントリなどに使用されているようです。

関連文書検索システムStupa

Bayesian Setsを使用した関連文書検索システムとして、Stupa(ストゥーパ)というシステムを作成しました。昔アジアを旅行したときに見た仏塔(ストゥーパ)から取ったもので、特に検索には関係ありません。

StupaはBayesian Setsにより類似する文書を高精度に検索し、また転置インデックスを構築することで高速に検索を実行できます。登録された文書データや転置インデックスは圧縮して保持しているため、メモリの使用量も少なく実行できます。

stupa

例として日本語版Wikipediaから作成したデータ(約61万エントリ)を使用して、Stupaのコマンドラインツールで関連エントリを検索した結果を以下に示します。結果のリストには、関連するエントリの名前と関連度が1行1エントリで表示されます。

「トヨタ自動車」で検索

 
% bsmgr search /path/wikipedia.tsv
Read input documents ...
Query> トヨタ自動車
トヨタ・プリウス        62.243313
トヨタ・トヨエース      56.777371
トヨタ・コロナ  54.229831
張富士夫        53.586574
トヨタ・ハイラックス    51.514397
トヨタ・プロボックス    49.165956
トヨタ・パブリカ        49.076950
中村健也        47.865204
奥田碩  45.499038
特別仕様車      45.440519
...
(search time: 3.21ms)

「かめはめ波」と「ドラゴンボール」で検索

 
Query> かめはめ波       ドラゴンボール
かめはめ波      263.980312
トランクス (ドラゴンボール)     72.204788
ミスター・サタン        69.037348
ドラゴンボールのアニメオリジナルの登場人物      65.560679
ドラゴンボールZ 超悟空伝 -突激編-       62.634941
ベジット        62.190804
ドラゴンボールZ 燃えつきろ!!熱戦・烈戦・超激戦  54.983379
ダーブラ        53.873965
ギニュー特戦隊  51.688147
ドラゴンボールZ この世で一番強いヤツ    51.597809
...
(search time: 3.95ms)

上記は「トヨタ自動車」で検索した場合と、「かめはめ波」「ドラゴンボール」の2つで検索した場合の結果ですが、両方とも関連するエントリが取得できています。検索にかかった時間は3ミリ秒ほどと比較的高速に実行できていることも分かります。 Stupaは入力された文書データや転置インデックスをメモリ上で保持して動作するため、頻繁に文書の追加・削除が行われるようなリアルタイム性の高いアプリケーションでの利用を主に想定して開発しています。例えばTwitter上で、自分の発言に関連するTweetを即座に検索する、といったアプリケーションが作れるかもしれません（Twitterだと1発言あたりの文章が短すぎて精度が悪くなってしまうかもしれませんが）。またオプションで登録できる文書の最大数を指定すると、最大登録数を超えた場合に古い文書から削除していくようになるため、使用リソースを一定に抑えつつ、常に最新の文書から関連しているものを検索することができます。

Thriftによる検索サーバ

StupaにはC++ライブラリとコマンドラインツールが含まれているのですが、これ以外にThriftを使用した検索サーバも配布しています。Perlのクライアントも同梱されていますので、Webサービス等に実際に導入することも可能だと思います。 stupa-thrift

また現在クライアントはPerl実装しかないのですが、Thrift用のインタフェース定義ファイルがパッケージに含まれていますので、RubyやPythonなど他言語のクライアントを生成することも可能です。より詳しくはThriftのマニュアルをご参照下さい。

まとめ

関連文書検索システムStupaをご紹介させていただきました。StupaはBayesian Setsを使用して、高精度かつ高速に検索を実行することが可能です。今後はmixi上での応用を考えつつ、パフォーマンスの向上等を行っていきたいと思います。もしご興味がある方がいらっしゃいましたら、ぜひご利用下さい！