libkkc update week two

libkkc 0.1.6, libkkc-data 0.1.6, ibus-kkc 1.5.6 をそれぞれリリースしました。
変更点は以下の通りです。

最近のパソコンは高速なので、通常の日本語入力では問題ありませんが、ibus-kkc で長い文章を入力すると、たまにもたつくことがありました。試しに3000文を変換するベンチマークをとってみると、

real user system
libkkc 0.1.5 282.17 279.95 0.07
Anthy 133.92 132.19 0.58

Anthy に2倍以上の差をつけられています。

gprof でプロファイルをとってみると、言語モデルから 2-gram を引く処理が全体の 67% を占めています。libkkc は この論文 の SORTED と呼ばれるタイプの索引を使っており、検索は二分探索なので、要素が多いとそれなりに時間がかかります。

高速化の手始めに、検索に使われるキーの傾向を調べてみると、3-gram のコストを求めるのに直近の検索キーを何度も検索していることがわかりました。そこで、直前に使われたキーと値のペアを一組だけ記憶しておくようにすると、これだけで 30% ほど速くなりました。

また、検索の成功・失敗の回数を数えてみると 95% 失敗しています。これは ブルームフィルタであらかじめ失敗判定をしてやれば大幅に高速化できそうに思えたのですが、そこまで思惑通りには行かず、20% ほどの速度向上にとどまりました。ハッシュの計算 (murmur hash 3 を利用) が悪いのかな?

というわけで、もう一度ベンチマークをとってみると、

real user system
libkkc 0.1.6 130.11 129.15 0.05
libkkc 0.1.5 282.17 279.95 0.07
Anthy 133.92 132.19 0.58

Anthy と同じくらいにはなりました。

Leave a Reply

Your email address will not be published. Required fields are marked *