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