最近、「Introduction to Information Retrieval」というStanfordの大学院向け教科書のドラフトを読んでいます。id:naoyaあたりが勉強会で読んでいる教科書です。この教科書には、効率のいい全文検索システムを作るにはどうすればいいか、という(まさに)教科書的手法が網羅的に書いてあり、そのあたりに興味がある人には、非常に興味深く読めるお勧めの本です。
ただ、面白い面白いと言っているだけでは、エンジニアとしては価値半減ですので、GW中にrubyで一日かけて実装してみました。
さすがに実装は、一日で作ったものですから、非常に素朴です。マルチバイト文字はbi-gramで、シングルバイトはスペースなどの区切り記号で認識しています。インデックスは、rubyの処理系のHashやArrayで保持しており、外部にMarshallで書き出す、というものです。検索エンジン自体はdrubyで外部から検索ができるようになっており、数百ぐらいの文書なら、それなりに動いています。
コードは以下に晒してますので、よかったら見てみてください。
http://github.com/stanaka/one-day-fulltext-search/
全文検索エンジンの肝となる、事前準備のIndexingと検索の二つを軽く解説します。二つの機能ともTokenizeというクラスに実装してみました。まず、Indexingは以下の二つのメソッド(だけ)で実装しています。マルチバイトだったら、bi-gramでtokenをどんどん切り出していき、シングルバイトだったら区切り文字でtokenを切り出しています。切り出したtokenをハッシュに突っ込んでいます。
def add_token(token, docid, position) @tokens[token] ||= Hash.new @tokens[token][docid] ||= Array.new @tokens[token][docid].push position end def tokenize(str, docid) last_char = nil sb_word = nil position = 0 str.each_char do |char| position += 1 if char.mbchar? if sb_word add_token(sb_word, docid, position); sb_word = nil end add_token(last_char + char, docid, position) if last_char last_char = char else last_char = nil if char =~ /[!@\#\$\%^&*\(\)\[\]\s\'\"\;\:\.\,\/\\\|\~\>\<]/ then if sb_word add_token(sb_word, docid, position) sb_word = nil end else sb_word = '' unless sb_word sb_word += char end end end end
検索は、search, recuresive_search, merge_resultsの三つのメソッドで実装しています。searchで検索を受けつけ、マルチバイトの文字だったら、bi-gramで分割し各tokenをrecursive_searchで再帰的に検索し、merge_resultsで各tokenが連続していることを確認しながら、結果のANDを取得しています。シングルバイトだったら、単純にハッシュで引いた中身をそのまま返しています。
def merge_results(result_set, new_result, offset) new_result_set = Hash.new merged_keys = result_set.keys & new_result.keys merged_keys.each do |key| positions = result_set[key] & new_result[key].map {|v| v - offset} if positions.length > 0 new_result_set[key] = positions end end return new_result_set end def recursive_search(words, result_set = nil, offset = 0) word = words.shift if @tokens[word] if result_set then result_set = merge_results(result_set, @tokens[word], offset) else result_set = @tokens[word] end result_set = recursive_search(words, result_set, offset + 1) if words.length > 0 end return result_set end def search(word) results = Array.new result_set = nil if word.mbchar? && word.jlength > 2 then last_char = nil words = Array.new word.each_char do |char| words.push(last_char + char) if last_char last_char = char end result_set = recursive_search(words) else result_set = @tokens[word] end if result_set #pp result_set result_set.each do |docid, positions| results.push([docid, positions]) end end return results end
これだけのシンプルな実装で、ちゃんとそれなりに全文検索が動いています。gitリポジトリには、このクラスを使って、YAMLデータの中身をIndexingするfulltextsearch_indexing.rbと、drubyのサーバとして動作する全文検索エンジンfulltextsearch_server.rb、サーバに検索クエリを投げるfulltextsearch_client.rbがあります。
実際の動きを以下のサンプルデータで紹介してみます。ちなみに、bcount, scountは、それぞれブックマーク数、スター数のイメージです。
- url: http://example.com/1 content: これはFull Text Searchです。 bcount: 10 scount: 2 date: 2006-01-01 00:00:00 +09:00 - url: http://example.com/2 content: これはFull Text Searchかもしれません。 bcount: 0 scount: 0 date: 2007-01-01 00:00:00 +09:00 - url: http://example.com/3 content: Full Versionになるのは、いつのことでしょう bcount: 2 scount: 5 date: 2008-01-01 00:00:00 +09:00
このサンプルデータに対して検索してみると以下のような結果が得られます。検索順は、ブックマーク数、スター数、時間の経過の三つのパラメータからスコアを付けて、計算しています。
% ruby fulltextsearch_client.rb Full
[{:url=>"http://example.com/1",
:bcount=>10,
:scount=>2,
:content=>"これはFull Text Searchです。",
:date=>Sun Jan 01 00:00:00 +0900 2006},
{:url=>"http://example.com/3",
:bcount=>2,
:scount=>5,
:content=>"Full Versionになるのは、いつのことでしょう",
:date=>Tue Jan 01 00:00:00 +0900 2008},
{:url=>"http://example.com/2",
:bcount=>0,
:scount=>0,
:content=>"これはFull Text Searchかもしれません。",
:date=>Mon Jan 01 00:00:00 +0900 2007}]パラメータの重み付けは自由に変更でき、例えば、スター数を重視すると、以下のような結果が得られます。
stanaka@colinux% ruby fulltextsearch_client.rb Full 0 1 0
[{:url=>"http://example.com/3",
:bcount=>2,
:scount=>5,
:content=>"Full Versionになるのは、いつのことでしょう",
:date=>Tue Jan 01 00:00:00 +0900 2008},
{:url=>"http://example.com/1",
:bcount=>10,
:scount=>2,
:content=>"これはFull Text Searchです。",
:date=>Sun Jan 01 00:00:00 +0900 2006},
{:url=>"http://example.com/2",
:bcount=>0,
:scount=>0,
:content=>"これはFull Text Searchかもしれません。",
:date=>Mon Jan 01 00:00:00 +0900 2007}]ちなみに、日本語文字列でも、ちゃんと結果が得られます。
% ruby fulltextsearch_client.rb これは
[{:url=>"http://example.com/1",
:bcount=>10,
:scount=>2,
:content=>"これはFull Text Searchです。",
:date=>Sun Jan 01 00:00:00 +0900 2006},
{:url=>"http://example.com/2",
:bcount=>0,
:scount=>0,
:content=>"これはFull Text Searchかもしれません。",
:date=>Mon Jan 01 00:00:00 +0900 2007}]作ってみたところ、(素朴な)全文検索エンジンを作るのは簡単で、教科書を読んだだけで作ることができます。ただ、ここから億単位の文書を読みこませても十分に早いスケールする全文検索エンジンを作るのは、当たり前ですが、相当に大変だと思います。でも、地道にやれば十分手の届くところにある、と感じます。
ともあれ、検索順位のアルゴリズムを考えるのは楽しいです。今回はブックマーク数とスター数と、記事の投稿時間をパラメータとして使ってみました。全文検索でヒットした記事に、それらの三つのパラメータから重み付けをして順位を決め、検索結果を出すというのは、非常に興味深いです。
検索順位については、普段Google「様」がPageRankをベースとしたアルゴリズムで順位を決定しているものを見ているわけですが、はてなのデータを使えば、はてなブックマークやはてなスターによって日々蓄積されている、人為的なデータをベースとして順位を決定できます。実際、はてなダイアリーの記事を対象として、両者の検索結果を比較してみると、なかなか興味深いです。
検索エンジンを自前で持つ意味というのは、Google様の価値観とは異なる自分独自の価値観を持つことができ、かつ、それが有益な場合だと思います。実際、Googleの初期のころ他の検索エンジンを圧倒してきたのは、PageRankという価値観が圧倒的に支持されたからです。それに対抗できる価値観を持つことができたら、まだ新しい検索エンジンの存在価値が出てくると思います。
ちなみに、パラメータの重み付けを少し変える度に、検索結果順がころころ変わって、日々それに一喜一憂しているSEO業者の人は大変だなぁ、と思いました。「見ろ!SEO業者がゴミのようだ!」と思ったのは、ここだけの話です。
