# Gemfile gem 'regexp_trie'
これははてなキーワードやWikipediaのリンクのように、ある程度の量のテキストに対して大量のキーワードをマッチさせるときに、最適化した正規表現を生成するライブラリです。
はてなキーワード*1をとあるブログエントリ*2にマッチさせるための簡単なベンチマークもあります。
結果:
$ 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() と完全には一致しないので公平なベンチマークではありません。
参考文献
- 404 Blog Not Found:TRIE-Optimized Regexp (2005年)
- 404 Blog Not Found:perl - Regexp::Assembleのススメ (2007年)
- 404 Blog Not Found:perl - 自動で /a|b|c/ を /[abc]/ にしてくれたら... (2007年)
- これによると、2007年くらいにPerlの正規表現エンジンにTRIEによる最適化が入ったようですね
- Rubyで正規表現を中途半端に最適化する - Qiita (2015年)
Regexp.union()との互換性について、コメント欄を参照のこと
*1:http://developer.hatena.ne.jp/ja/documents/keyword/misc/catalog
*2:id:dankogai に敬意を表して、Regexp::Trieのオリジナル作者である氏がRegexp::Trieのプロトタイプを紹介するエントリにしました。
