toshiさんの レーベンシュタイン距離で文字列の類似度を高速に取得する | バグ取りの日々 に紹介されている3つのアルゴリズムで文字列の類似度を計算し、計算にかかる時間を測定した。
なお、比較した文字列は、水素エネルギーに関するニュース記事のタイトル(大量)であり、各々の類似度は小さい。
(1) 普通のレーベンシュタイン距離: 1568秒
(2) レーベンシュタイン距離（最適化 + 中断）
(2-1) 中断なし: 936秒
(2-2) 標準化したレーベンシュタイン距離が0.9以上である場合は、0.9までで比較を中断: 990秒
本来、計算時間は、(2-1)＞(2-2) になるが、測定結果はそうならなかった。この程度の誤差はある。
概ね (1)の1.7倍速である。
(3) WuらのO(NP)文字列差分検出アルゴリズム
1回目 1680秒
2回目 1550秒程度(正確な記録なし)
3回目 1757秒
概ね (1)の0.94倍速である。
比較する文字列同士の類似度が小さい場合、高速化されない。