kaerukeywordをC言語で実装しなおしました。
https://github.com/tsukasaoishi/kaerukeyword
キーワード検索ライブラリKaerukeywordのバージョン1.1.2をアップしました。
kaerukeywordは、登録されたキーワードを与えられた文中から素早く検索できるライブラリです。はてなダイアリーのキーワード自動リンクのような用途に使うことができます。このブログのキーワードリンクはkaerukeywordで実現されています。
もともとRubyのハッシュを使ってtrieを構築していたのを、C言語で書き直しました。もちろんRubyのクラスのまま、インターフェースも変わっていないので、今までのコードを変更する必要はありません。
インストールはとりあえず以下のようにしてください。githubがgemの構築サービスをとめているためです..orz。もしかしたらgemcutterで公開するかもしれません。
wget http://www.kaeruspoon.net/kaerukeyword-1.1.2.gem
sudo gem install kaerukeyword-1.1.2.gem
使い方
require 'rubygems'
require 'kaerukeyword'
keywords = KaeruKeyword.new(["Ruby", "Rails"])
keywords << "Tsukasa"
keywords.search("I Love Ruby") #=> ["Ruby"]
262380語のキーワードを登録し、8789文字の文字列から検索するテストを実施してみました。検索は1000回繰り返しています。
以前のバージョン(1.0.2)
[キーワード登録]
user system total real
total: 8.970000 3.320000 12.290000 ( 12.289984)
avg: 0.000034 0.000013 0.000047 ( 0.000047)
[検索]
user system total real
total: 19.920000 0.610000 20.530000 ( 20.529973)
avg: 0.019920 0.000610 0.020530 ( 0.020530)
今回のバージョン(1.1.2)
[キーワード登録]
user system total real
total: 1.080000 0.320000 1.400000 ( 1.399998)
avg: 0.000004 0.000001 0.000005 ( 0.000005)
[検索]
user system total real
total: 3.500000 0.020000 3.520000 ( 3.519995)
avg: 0.003500 0.000020 0.003520 ( 0.003520)
262380語のキーワード登録が12.29秒から1.40秒に、8789文字の文字列からのキーワード検索は0.02秒から0.0035秒になっていて、大幅な高速化が実現しています。
また、メモリの消費量も約208Mバイトから56Mバイトになっていて、省メモリ化となっています。
個人レベルで使用するツールから、仕事でも使えるレベルにはなってきたのではないでしょうか。
今後は、検索結果にキーワードの出現位置情報を含めたり、キーワードごとのID値の設定を可能にしたり、AhoCorasick法の採用による検索速度のさらなる高速化や、double arrayを使ってさらに省メモリ化を実現したりといったことを実装する予定でいます。AhoCorasick法やdouble arrayを使うと、trie構築後のキーワードの登録がけっこう大変なので、このあたりは選択できるようにするつもりです。