Levenshtein Automata ってずいぶん簡単に作れるんだなあと思ったので、ついでにベンチマークもとってみた。

以下のgistは、ランダムな文字列を100個生成して、"levenshtein"という文字との編集距離が2個以下か否かを、オートマトンを使う方法と距離関数を真面目に使う方法でそれぞれ判定させたもの。距離関数ははてなおやさんとこのコピペした。

動かした結果。

0.131075143814
1.49535894394

距離関数の方は枝刈りしてないってのもあると思うけど、オートマトンの方が11倍ほど速い。

ちなみに元のブログエントリで本当に面白いのはLevenshtein Automataの構築法ではなくてその後の話なので、興味がある方は読んでみるといいと思う。