今日紹介するコードはここにおいてあります。 https://gist.github.com/aflc/6482587
編集距離（levenshtein距離）の計算方法で一番有名なのが動的計画法を使ったもので、これはWikipediaにも載っているお手軽でよく使われているものです。
しかし、この方法は結構時間がかかるので、他にも高速な手法がいくつか提案されています。
NOXさんのブログエントリを読んでいただくのが一番手っ取り早いのですが、ビットパラレル法というのが上手くハマると10倍以上高速です。
ここで紹介されている論文では64文字以上の比較ができないのですが、今回は
Heikki Hyyrö, "Explaining and extending the bit-parallel approximate string matching algorithm of Myers", 2001
という論文中で紹介されている、64文字以上への拡張を含めて実装してみました。
違いは、配列の境界をまたがる際にプラスの演算とビットシフトの演算に相当する部分を一個前の配列から伝搬させているだけです。
早速やってみた結果がこちら。
ベンチマークコードはNOXさんのコードを拝借しました。ありがとうございます。
まずは64文字以内の場合。
# g++ -O3
# gcc 4.9 のMac book Air 2011, core i5で計測
# str1 = "aaabcacbcacbbcabcbcacbcbabcbacbassssssssssssssssssssssssssssssss"
# str2 = "cvahavacabcbabcaabcbsdfsdfsfeoacbcababdfjsfasdasdabababababababa"
dp : 49
Time: 3.32257s (100000 times)
bp-map : 49
Time: 0.275121s (100000 times)
bp-256 : 49
Time: 0.068569s (100000 times)
bpv-map : 49
Time: 0.294881s (100000 times)
bpv-256 : 49
Time: 0.072087s (100000 times)
dp: 動的計画法
bp-map: ビットパラレル法で、かつパターンマッチ配列にstd::mapを使ったもの
bp-256: ビットパラレル法、かつパターンマッチ配列にchar[256]を使ったもの、すなわち一バイト文字列のみに対応
bpv-*: ビットパラレル方の拡張版
今回DP版の配列は固定長ではなく二重のstd::vector配列を採用しているためその分かなり遅くなってます。固定長配列に戻すと1.56279sでした。
bp-256とbpv-256の差はあまり無いので64文字以下の場合に拡張版を使っても遜色はなさそうです。
そして、例えば単語単位とか日本語とかで編集距離を出そうと思った場合にはmapを使うしか無いわけですが、とりあえずstd::mapだと４倍位遅くなってしまいました。
ただし、同じパターン文字列を使って順次距離を求めるような場合、パターンマッチ配列は一度だけ計算すればいいためほぼ無視出来る計算量です。今回のベンチマークでは毎回パターンマッチ配列を作成しています。
次に、文字数が増えた場合です。
# g++ -O3
# gcc 4.9 のMac book Air 2011, core i5で計測
# str1 = "aaabcacbcacsdvaabcbabcbacabccabbbcabcbcacbcbabcbacbassssssssssssssssssssssssssssssss"
# str2 = "cvahavacabcbabcaabcbsdfsdfsfeoasaacbabcabaacbcbaacbcbcababdfjsfasdasdabababababababa"
dp : 59
Time: 5.40564s (100000 times)
bpv-map : 59
Time: 0.378752s (100000 times)
bpv-256 : 59
Time: 0.135761s (100000 times)
文字数が増えても安定した速さです。bpvは64bit型配列２つ分（=128文字までOK）を使っています。相対的にbpv-mapが健闘しているという感じでしょうかね。実際はこんなに長い文字列で編集距離求めたりしないでしょうけど。
補足までにunordered_mapに変えると二倍くらい遅くなります。一般的にはunordered_mapの方が速いと思っていただけに意外な結果に。どなたか原因のわかる方教えて下さい。