Islands in the byte stream

Technical notes by a software engineer

PerlのRegexp::TrieをRubyに移植した

GitHub - gfx/ruby-regexp_trie: Optimized Regexp builder with Trie (a Ruby port of Perl's Regexp::Trie)

# Gemfile
gem 'regexp_trie'

これははてなキーワードやWikipediaのリンクのように、ある程度の量のテキストに対して大量のキーワードをマッチさせるときに、最適化した正規表現を生成するライブラリです。

はてなキーワード*1をとあるブログエントリ*2にマッチさせるための簡単なベンチマークもあります。

example/benchmark.rb

結果:

$ bundle exec example/benchmark.rb
(snip)
                           user     system      total        real
Regexp raw             4.270000   0.030000   4.300000 (  4.351108)
RegexpTrie             0.050000   0.000000   0.050000 (  0.047678)

このくらい速ければ、1リクエスト中に2~3回処理してなんとかなる程度、といえるでしょう。それでもキャッシュはしたほうがいいですが。

ただし、benchmark.rbを実行するとわかりますが、 Regexp.union() と完全には一致しないので公平なベンチマークではありません。

参考文献

*1:http://developer.hatena.ne.jp/ja/documents/keyword/misc/catalog

*2:id:dankogai に敬意を表して、Regexp::Trieのオリジナル作者である氏がRegexp::Trieのプロトタイプを紹介するエントリにしました。