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・新版』(旧版には載っていないので注意)がわかりやすい。
