スパムメールの判定や、文字列のあいまい検索等では、文字列間の違いを効率よく判定するアルゴリズムが必要。ここではその紹介。
「文字列間の距離 (String Distance) とは、２つの文字列間の違いを測る尺度。文字を挿入したり、削除したり、置き換えたりして、２つの文字列を等しくするまでの最小の操作の数でもある。」
例えば、computer と commuter。 pをmに置き換える（あるいは逆、mをpにする）だけで、全く同じ文字列になるので、二つの文字列間の距離は１となる。操作なしでは同等にならないので、１が最小操作数でもあるわけだ。
例えば、sport と sort。 左のsportから s を削除すれば、右のsortになるし、右のsortにpを挿入すると左になる。したがって、文字列間の距離は１となる。
＜文字列間距離ｄ の再帰的定義＞
d(“”, “”) = 0 ← 空文字列間の距離
d(s, “”) = d(“”, s) = |s| ← 文字列の長さ（文字数）
d(s1+ch1, s2+ch2) ← ch1, ch2 はそれぞれの文字列の最後の文字
= min( d(s1, s2) + (if ch1=ch2 then 0 else 1),
← そのまま、または ch1とch2との置換
d(s1+ch1, s2) + 1, ← ch1 を s1 に挿入 （あるいは s2 から ch2削除）
d(s1, s2+ch2) + 1 ) ← ch1 を s1 から削除 （あるいは s2 に ch2挿入）
つまり、文字列 s1 と s2 との距離は、個々の文字を、等しい場合はそのまま、異なる場合は文字置換・挿入・削除（それぞれで距離を１つ縮める）操作の最小回数によって算出できる。
以下はそのC言語プログラム。作業用配列の大きさは動的に書いてあるが、古いCコンパイラだと十分大きなサイズに直して下さい。
/*
引数： str1, str2、比較したい文字列２つ
関数値： str1とstr2との文字列間の距離。0以上の整数。
*/
int string_distance(char *str1, char *str2)
{
int i, j;
int len1 = strlen(str1);
int len2 = strlen(str2);
char M[len1+1][len2+1];
if (len1 == 0) return len2;
if (len2 == 0) return len1;
for (j = 0; j <= len1; j++) M[j][0] = j;
for (i = 0; i <= len2; i++) M[0][i] = i;
for (j = 1; j <= len1; j++) {
for (i = 1; i <= len2; i++) {
int d, min;
d = (str1[j-1] != str2[i-1]);
/* or
d = (str1[j-1] == str2[i-1]) ? 0 : 1;
*/
min = M[j-1][i ] + 1;
if (min > M[j ][i-1] + 1) min = M[j ][i-1] + 1;
if (min > M[j-1][i-1] + d) min = M[j-1][i-1] + d;
M[j][i] = min;
}
}
return M[len1][len2];
}
計算量は明らかに O(|s1|*|s2|)。 s1とs2の長さが等しく N と考えるなら、 O(N2) となる。
この文字列間距離はかならず実現できる操作（文字の挿入・削除・置換のみ）を表すもの。実際の操作では、以下のようなアルゴリズムを考えることもできる（最終結果と最小手間数が判っているので、意味のない操作だが、プログラムをつくる練習材料にはなる）。ほかには、再帰的プログラムによる方法もある。
基準・比較対象（target） viagra ← s1
操作したい文字列 v1a_gra ← s2
先頭からの各文字 s1[i] と s2[i] に対し、
s1[i] と s2[i] が等しい場合、操作しない
異なる場合、挿入・削除・置換の操作で得られた３つの文字列について、それぞれのs1との文字列間距離を計算し、最小なる操作を選べばよい。
s1、s2 文字列の長さをNとすると、それぞれの文字について、文字列間距離を計算する手間がかかるので、全体的に計算量はO（N3） である。
＜練習問題＞
164 String Computer
526 String Distance and Transform Process