2007-06-04 追記 ruby-pytstはこちら → yatsu.info : ruby-pytstをRubyForgeに登録

きまぐれ日記: はてなキーワードを高速に付与

はてなキーワード付与の速度問題は、LesserWikiの速度問題と同じっぽい :)

で、僕が考えたのもAho-Corasick法(AC法)だったが、自分でアルゴリズムを書くのが面倒だったので、pytstというPython用TSTライブラリをRubyに移植してみた(とりあえずruby-tstと名付けた)。 名前のとおり、Trie構造はTST(Ternary Search Trie)を使用している。

pytstはC++で実装されていて、SWIGでPython対応しているが、ruby-tstはCで書き直した。

/usr/share/dict/wordsの23万語をキーワードにして、Google Newsの記事中の単語を一括置換してみたところ、かなり速いパフォーマンスを発揮した。

TST構造はRubyのハッシュのようにも使用できる。

t = TST.new
t[:test] = "TEST"
p t[:test]

検索する場合は

require 'tst'

t = TST.new

t["abc"] = "abc"
t["abcdef"] = "abcdef"
t["abcdefgh"] = "abcdefgh"
t["01"] = "01"
t["02"] = "02"

%w[abc 01 abc01 abc---01 abcdef---abc--01--abcdef--abc].each do |str|
  t.scan(str) {|s, d, v| print "('#{s}' #{d} '#{v}') "}
  puts
end

これを実行すると、こうなる。

('abc' 3 'abc') 
('01' 2 '01') 
('abc' 3 'abc') ('01' 2 '01') 
('abc' 3 'abc') ('---' -3 '') ('01' 2 '01') 
('abcdef' 6 'abcdef') ('---' -3 '') ('abc' 3 'abc') ('--' -2 '') ('01' 2 '01')
  ('--' -2 '') ('abcdef' 6 'abcdef') ('--' -2 '') ('abc' 3 'abc')

ブロックを受け取って一括置換してくれるreplaceメソッドもあるが、面倒なので(そればっかりだな)省略。

Marshalにも対応したが、Rubyの型を使ってmarshal_dump, marshal_load対応したためか、遅い。

その他の問題点は、ときどき落ちること（w
メモリ破壊していると思われ……。

２週間ほどほったらかしにしているので、そろそろ修正して公開したいところ。

AC法については北研二、津田和彦、獅々堀正幹『情報検索アルゴリズム』、TSTについてはセジウィック『アルゴリズムC・新版』(旧版には載っていないので注意)がわかりやすい。