はてなキーワードを高速に付与

sennaのsen_symクラスは、common prefix searchが可能です。この機能を使って(今更なのですが)Dartsと同じ手法ではてなキーワードを高速に付与するプログラムを作ってみました。

以下のような特徴があります。

任意のタイミングで付与対象のキーワードをインデックスに追加／削除できる
インデックスの作成／更新が高速
キーワード付与が高速

http://d.hatena.ne.jp/images/keyword/keywordlistの内容でインデックスを生成し、
350KB程度の日本語テキスト(EUC)にキーワードを付与した場合の処理速度を比較してみました。

Dartsを使ったインデックス作成
% time ./mkdarts keywordlist.sort keywordlist.da
2.010u 0.060s 0:02.74 75.5%	0+0k 0+0io 235pf+0w
sennaを使ったインデックス生成
% time ./hatenapo  keywordlist.pat ins < keywordlist.sort 
0.680u 0.030s 0:00.73 97.2%	0+0k 0+0io 2648pf+0w

Dartsを使ったキーワード付与
% time ./hatenakeyword < sample.txt > /dev/null
1.120u 0.060s 0:01.18 100.0%    0+0k 0+0io 211pf+0w
sennaを使ったキーワード付与
% time ./hatenapo keywordlist.pat sel < sample.txt > /dev/null
0.560u 0.010s 0:00.57 100.0%    0+0k 0+0io 2085pf+0w

sennaもなかなか高速なことがわかります。ただし、検索に失敗した場合hatenakeyword(Darts)では1byteずつシフトしているのに対してhatenapo(senna)では1文字ずつシフトしているので、その点hatenapoが有利になっています(検索回数が半分程度で済んでいる)。common prefix searchそのものはDartsの方が高速かもしれません。