levenshtein

レーベンシュタイン距離は、$str1 を $str2 に変換するために置換、挿入、削除 しなければならない最小の文字数として定義されます。アルゴリズムの複雑さは、 O(m*n) です。 ここで、n および m はそれぞれ $str1 および $str2 の長さです (O(max(n,m)**3) となる similar_text() よりは良いですが、 まだかなりの計算量です)。

上記の最も簡単な形式では、この関数はパラメータとして引数を二つだけとり、 $str1 から $str2 に変換する際に必要な 挿入、置換、削除演算の数のみを計算します。