Javascriptでレーベンシュタイン距離の実演

レーベンシュタイン距離は、2つの文字列の間にどの程度の差があるかを算出します。
具体的には、2つの文字を同一にするには、挿入・置換・削除を何回行えば良いか最小回数を算出します。

※IE8、FF3.6、Chrome4で動作を確認しています。IE7以下では動作しません。
※このスクリプトはイメージです。ほとんどテストしてないのでバグってたらすいません。

---

サンプル

テキストボックスに文字列を入力してボタンを押すと、2つの文字列の距離が出力されます。






レーベンシュタイン距離は、下記に出力されるような手順で入れ替えた際のコストを算出します。


レーベンシュタイン距離は、下記に出力されるようなテーブルを作成して、最小コストを割り出しています。
↓ 削除     → 挿入     斜め(1増) 置換

---

単純なコード

function levenshteinDistance( 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; 
    } 

    var cost = 0; 
    for( var i = 1; i <= x; i++ ) { 
        for( var j = 1; j <= y; j++ ) { 
            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 ); 
        }
    }
    return d[x][y];
}