レーベンシュタイン距離
レーベンシュタイン距離を計算する際は、一般的に動的計画法によるアルゴリズムが用いられる。長さ n {\displaystyle n} と長さ m {\displaystyle m} の文字列間の距離を求めるには ( n + 1 ) ( m + 1 ) {\displaystyle (n+1)(m+1)} の二次元行列が使われ、計算時間は O ( m n ) {\displaystyle O(mn)} と非常に効率がよい。
このアルゴリズムの要諦は、
1文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、1文字削った文字列との距離から1文字加えた文字列との距離を求めることができる
長さ 0 {\displaystyle 0} の文字列と長さ L {\displaystyle L} の文字列の距離は L {\displaystyle L} である
の2点から帰納的に求めることができるという点である。
以下に、文字数 lenStr1 の文字列 str1 と、文字数 lenStr2 の 文字列 str2 間のレーベンシュタイン距離を求める擬似コードを示す。このコードにおいて d[i1,i2] には、str1 の i1 文字目までの文字列と str2 の i2 文字目までの文字列の間のレーベンシュタイン距離が格納される。