Bal4u : C/UVa - C言語・文字列照合 Archiveスパムメールの判定や、文字列のあいまい検索等では、文字列間の違いを効率よく判定するアルゴリズムが必要。ここではその紹介。 「文字列間の距離 (String Distance) とは、２つの文字列間の違いを測る尺度。文字を挿入したり、削除したり、置き換えたりして、２つの文字列を等しくするまでの最小の操作の数でもある。」 例えば、computer と commuter。 pをmに置き換える（あるいは逆、mをpにする）だけで、全く同じ文字列になるので、二つの文字列間の距離は１となる。操作なしでは同等にならないので、１が最小操作数でもあるわけだ。 例えば、sport と sort。 左のsportから s を削除すれば、右のsortになるし、右のsortにpを挿入すると左になる。したがって、文字列間の距離は１となる。 ＜文字列間距離ｄ の再帰的定義＞ d("", "") = 0 ← 空文
