レーベンシュタイン距離を求めてみた。(JS) | Codetter（こーどったー）

function LevensHtein(str_1, str_2)
{
    if(str_1 === str_2) return 0;
    var len_1 = 1 + str_1.length, i = len_1,
        len_2 = 1 + str_2.length, j = len_2,
        dists = function (dim_1, dim_2)
        {
            var i = 0,
                retTable = new Array(dim_1);
            for(; dim_1--;)
            {
                retTable[dim_1] = new Array(dim_2);
                for(i = dim_2; i--;) retTable[dim_1][i] = 0;
            }
            return retTable;
        }(len_1, len_2);
    for(; i--;) dists[i][0] = i;
    for(; j--;) dists[0][j] = j;
    for(i = 0; ++i < len_1;)
    {
        for(j = 0; ++j < len_2;)
        {
            dists[i][j] = Math.min(
                1 + dists[i - 1][j    ],
                1 + dists[i    ][j - 1],
                    dists[i - 1][j - 1] + (str_1[i - 1] === str_2[j - 1] ? 0 : 1));
        }
    }
    return dists[len_1 - 1][len_2 - 1];
}

/* minimum: function LevensHtein(s,t){if(s==t)return 0;var l=1+s.length,i=l,m=1+t.length,j=m,d=function(d,e){var i=0,r=new Array(d);for(;d--;){r[d]=new Array(e);for(i=e;i--;)r[d][i]=0}return r}(l,m);for(;i--;)d[i][0]=i;for(;j--;)d[0][j]=j;for(i=0;++i<l;){for(j=0;++j<m;){d[i][j]=Math.min(1+d[i-1][j],1+d[i][j-1],d[i-1][j-1]+(s[i-1]==t[j-1]?0:1))}}return d[l-1][m-1]} */