例えば以下の2つの文字を比べた場合です。
あした
あたし
2つ目のポジションの「し」を削除し、3つ目のポジションに「た」を挿入するという2回のアクションで文字列を一致させられます。
これは、以下の文字列を比べた場合と同じコストです。
あした
あたい
1つ目のパターンの方は、3つとも全て同じ文字が使われているというのに、文字列の近さは同じと判定されてしまうわけです。
レーベンシュタイン距離は「挿入」「削除」「置換」の3パターンしかサポートしていません。
これを解決するには「し」と「た」を「並べ替える」という処理が必要になります。
この処理を追加サポートしているのが、「Damerau-Levenshtein」（カタカナ表記ではなんと書けばいいのだろう）。並べ替え処理は、英語版Wikipediaでは、「transposition」（転移？）と書いてありました。
http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
この処理をサポートすることによって、単純に文字の前後を打ち間違えただけの誤字を判断する精度は高くなります。
コードもレーベンシュタイン距離のそれに2行ほど足すだけで済む、実に単純なものです。以下はJavascriptで書いたサンプルコード。
/** Damerau-Levenshtein距離測定 */
function damerauLevenshteinDistance( str1, str2 ) {
var x = str1.length;
var y = str2.length;
var d = [];
for( var i = 0; i <= x; i++ ) {
d[i] = [];
d[i][0] = i;
}
for( var i = 0; i <= y; i++ ) {
d[0][i] = i;
}
for( var i = 1; i <= x; i++ ) {
for( var j = 1; j <= y; j++ ) {
var cost = str1[i - 1] == str2[j - 1] ? 0 : 1;
d[i][j] = Math.min( d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost );
// 以下のboldの部分が追加になった
if( i > 1 && j > 1
&& str1[i - 1] == str2[j - 2]
&& str1[i - 2] == str2[j - 1] )
d[i][j] = Math.min( d[i][j], d[i-2][j-2] + cost );
}
}
return d[x][y];
}
但し、Wikipedianの記事にも書いてありますが、この記述では思った通りに動かないケースも有ります。
こちら
らっこ
上記のケースの場合、2つ目の文字を置換した上で、1つ目と3つ目の文字を入れ替えれば、2回の行為で文字列を一致させられますが、Damerau-Levenshteinでの解は「3」になります。
文字列の類似を判定するロジックは他にもJaro-Winkler距離がいい感じだったり、目的によってはダイス係数もけっこうイケるんじゃないかなぁと思ったりと、いろいろな手法があるようで。
しかし残念ながら、私はそれらの特徴や最適な使い道については今ひとつ分かっていません。。。
勉強せねば。