返回顶部

收藏

莱文斯坦(列文斯坦)距离

更多

莱文斯坦(列文斯坦)距离,可以用于

  1. 拼写检查
  2. 语音识别
  3. DNA分析
  4. 剽窃检测
function getResArray(a, b) {
    var alength = a.length+1, blength = b.length+1, ai=0, bi=0;
    var q = [], c;
    for ( ; ai < blength; ai++) {
        c = new Array;
        for (; bi < alength; bi++) {
            if (ai == 0) {
                c[bi] = bi;
            }
            if (bi == 0 && ai != 0) {
                c[0] = ai;
            }  else if(ai != 0) {
                c[bi] = 0;
            }
        }
        bi = 0;
        q[ai] = c;
    }
    return q;
}
function min(ma, mb ,mc) {
    var min = ma;
    return mb < mc ? (mb < min ? mb : min) : (mc < min ? mc : min); 
}
function levenshteinDistance(a , b) {    
    var alength = a.length, blength = b.length, i = 1, j =1, cost;
    var q = getResArray(a, b);
    for (; i <= alength; i++) {
        for (; j <= blength; j++) {
            if (a.charAt(i-1) == b.charAt(j-1)) {
                cost = 0;
            }
            else {
                cost = 1;
            }
            q[j][i] = min(q[j-1][i]+1, q[j][i-1]+1, q[j-1][i-1]+cost); 
        }
        j = 1;
    }
    return q[blength][alength];
}
console.log(levenshteinDistance("sdff", "sdf"));
//该片段来自于http://outofmemory.cn

标签:javascript,算法

收藏

0人收藏

支持

0

反对

0

发表评论