読者です 読者をやめる 読者になる 読者になる

1日で作る全文検索エンジン - Building a full-text search engine in "ONE" day -

最近、「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業者がゴミのようだ!」と思ったのは、ここだけの話です。