logo标签列表

用JavaScript以最佳性能按“Levenshtein距离”对数组进行排序

javascriptjquerysortinglevenshtein-distance
55

我有一个随机的 JavaScript 名称数组...

[@larry,@nicholas,@notch] 等等。

它们都以 @ 符号开头。我想按 Levenshtein 距离对它们进行排序，这样列表顶部的名称与搜索词最接近。目前，我有一些 JavaScript 代码，使用 jQuery 的 .grep() 方法，结合键盘按下时输入的搜索词，对其使用 JavaScript 的 .match() 方法：

(代码自首次发布以来已编辑)

limitArr = $.grep(imTheCallback, function(n){
    return n.match(searchy.toLowerCase())
});
modArr = limitArr.sort(levenshtein(searchy.toLowerCase(), 50))
if (modArr[0].substr(0, 1) == '@') {
    if (atRes.childred('div').length < 6) {
        modArr.forEach(function(i){
            atRes.append('<div class="oneResult">' + i + '</div>');
        });
    }
} else if (modArr[0].substr(0, 1) == '#') {
    if (tagRes.children('div').length < 6) {
        modArr.forEach(function(i){
            tagRes.append('<div class="oneResult">' + i + '</div>');
        });
    }
}

$('.oneResult:first-child').addClass('active');

$('.oneResult').click(function(){
    window.location.href = 'http://hashtag.ly/' + $(this).html();
});

这段代码还有一些if语句用于检测数组中是否包含“#”或“@”符号，忽略它们。其中imTheCallback是名字的数组，可以是“#”或“@”符号，而modArr是已排序的数组。然后，每次将元素添加到.atResults和.tagResults中，以此基于输入的搜索词形成一个名称列表。

我还有Levenshtein距离算法:

var levenshtein = function(min, split) {
    // Levenshtein Algorithm Revisited - WebReflection
    try {
        split = !("0")[0]
    } catch(i) {
        split = true
    };

    return function(a, b) {
        if (a == b)
            return 0;
        if (!a.length || !b.length)
            return b.length || a.length;
        if (split) {
            a = a.split("");
            b = b.split("")
        };
        var len1 = a.length + 1,
            len2 = b.length + 1,
            I = 0,
            i = 0,
            d = [[0]],
            c, j, J;
        while (++i < len2)
            d[0][i] = i;
        i = 0;
        while (++i < len1) {
            J = j = 0;
            c = a[I];
            d[i] = [i];
            while(++j < len2) {
                d[i][j] = min(d[I][j] + 1, d[i][J] + 1, d[I][J] + (c != b[J]));
                ++J;
            };
            ++I;
        };
        return d[len1 - 1][len2 - 1];
    }
}(Math.min, false);

我该如何将算法（或类似的算法）应用到我的现有代码中，以便在不影响性能的情况下对其进行排序？

更新：

现在我正在使用James Westgate的Lev Dist函数。它的速度非常快。因此性能问题已得到解决，现在的问题是如何将其与源代码一起使用...

modArr = limitArr.sort(function(a, b){
    levDist(a, searchy)
    levDist(b, searchy)
});

我的问题是关于如何使用.sort()方法的普遍理解。感谢您的帮助。

谢谢！

2
如果这是一个数组，为什么要使用 for..in 进行迭代？这也会迭代 length 属性（或任何其他非索引属性，如果您定义了这样的属性），以及继承的可枚举属性（如果您的其他代码尝试填充 ES5 数组方法，则可能存在）。您可以使用本地的 .forEach 或 jQuery 的 $.each 来迭代数组。 - Šime Vidas
1
modArr = limitArr.sort(function(a,b){ return levDist(b,searchy) - levDist(a,searchy); });modArr = limitArr.sort（function（a，b）{ 返回levDist（b，searchy） - levDist（a，searchy）; }）; - James Westgate
1
@JamesWestgate 再次挺身而出。 （注意：这将按相似度升序排序，这可能不是您想要的顺序；要按相似度降序排序，请使用 function(a,b){ return levDist(a, searchy) - levDist(b,searchy); }。） - Jordan Gray
2
是的，根据数组的大小，您可能希望缓存结果，因为它可能会多次执行相同的计算。只需要一个简单的关联数组就可以解决问题。 - James Westgate
你可以将要搜索的名称按长度分组放入桶中。这样，您可以减少要检查的术语数量，因为您只需要检查与搜索术语+-限制相同长度的桶。通过这种方式，您可以在我的jsperf算法版本中删除限制检查。 - James Westgate
显示剩余5条评论
7个回答
115

我几年前写了一个内联拼写检查器，并实现了Levenshtein算法 - 由于它是内联的并且为IE8设计，因此我进行了大量的性能优化。

var levDist = function(s, t) {
    var d = []; //2d matrix

    // Step 1
    var n = s.length;
    var m = t.length;

    if (n == 0) return m;
    if (m == 0) return n;

    //Create an array of arrays in javascript (a descending loop is quicker)
    for (var i = n; i >= 0; i--) d[i] = [];

    // Step 2
    for (var i = n; i >= 0; i--) d[i][0] = i;
    for (var j = m; j >= 0; j--) d[0][j] = j;

    // Step 3
    for (var i = 1; i <= n; i++) {
        var s_i = s.charAt(i - 1);

        // Step 4
        for (var j = 1; j <= m; j++) {

            //Check the jagged ld total so far
            if (i == j && d[i][j] > 4) return n;

            var t_j = t.charAt(j - 1);
            var cost = (s_i == t_j) ? 0 : 1; // Step 5

            //Calculate the minimum
            var mi = d[i - 1][j] + 1;
            var b = d[i][j - 1] + 1;
            var c = d[i - 1][j - 1] + cost;

            if (b < mi) mi = b;
            if (c < mi) mi = c;

            d[i][j] = mi; // Step 6

            //Damerau transposition
            if (i > 1 && j > 1 && s_i == t.charAt(j - 2) && s.charAt(i - 2) == t_j) {
                d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
            }
        }
    }

    // Step 7
    return d[n][m];
}
2
我还没有仔细查看代码，但我已经进行了快速测试，并且可以证实这比原始帖子中的算法要快得多。干得好！ - Jordan Gray
2
有一件小事：我注意到你计算的是Damerau-Levenshtein距离，而不仅仅是Levenshtein距离。如果你删掉转置测试，这将更接近于OP想要的，并且运行速度会更快。 :) - Jordan Gray
5
有趣的事实是，var关键字确实有实际用途，而不仅仅是重置按钮。 - AlienWebguy
3
谢谢！这是我在网上见过的唯一一个表现良好的函数。其他函数在处理长字符串时变得非常缓慢，而这个函数真是太棒了。干得好！鼓掌 - alt
2
如果您设置了一个限制，并且去掉DT，那么性能会飞快。http://jsperf.com/levenshtein-distance/2注意：我的原始实现有按字母顺序排序的项目桶，然后每个字母也有一个按长度分组的桶，这样我就可以仅比较相同长度或长度达到限制的项目而无需在算法内部进行检查。 - James Westgate
显示剩余17条评论
13

我想给出这个解决方案：

var levenshtein = (function() {
        var row2 = [];
        return function(s1, s2) {
            if (s1 === s2) {
                return 0;
            } else {
                var s1_len = s1.length, s2_len = s2.length;
                if (s1_len && s2_len) {
                    var i1 = 0, i2 = 0, a, b, c, c2, row = row2;
                    while (i1 < s1_len)
                        row[i1] = ++i1;
                    while (i2 < s2_len) {
                        c2 = s2.charCodeAt(i2);
                        a = i2;
                        ++i2;
                        b = i2;
                        for (i1 = 0; i1 < s1_len; ++i1) {
                            c = a + (s1.charCodeAt(i1) === c2 ? 0 : 1);
                            a = row[i1];
                            b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
                            row[i1] = b;
                        }
                    }
                    return b;
                } else {
                    return s1_len + s2_len;
                }
            }
        };
})();

另请参阅http://jsperf.com/levenshtein-distance/12

通过消除一些数组的使用，获得了最大的速度提升。

6

更新时间：http://jsperf.com/levenshtein-distance/5

新版本的优化性能已经超越所有其他基准测试。作者专门追求了Chromium/Firefox的性能，因为没有IE8/9/10测试环境，但是进行的优化应该适用于大多数浏览器。

Levenshtein距离算法

用于执行Levenshtein距离的矩阵可以重复使用。这是一个明显的优化目标（但要注意，这现在对字符串长度有限制（除非您动态调整矩阵大小））。

jsPerf Revision 5中未探索的优化选项是记忆化。根据您对Levenshtein距离的使用方式，这可能会有很大帮助，但由于其特定于实现的性质而被省略。

// Cache the matrix. Note this implementation is limited to
// strings of 64 char or less. This could be altered to update
// dynamically, or a larger value could be used.
var matrix = [];
for (var i = 0; i < 64; i++) {
    matrix[i] = [i];
    matrix[i].length = 64;
}
for (var i = 0; i < 64; i++) {
    matrix[0][i] = i;
}

// Functional implementation of Levenshtein Distance.
String.levenshteinDistance = function(__this, that, limit) {
    var thisLength = __this.length, thatLength = that.length;

    if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
    if (thisLength === 0) return thatLength;
    if (thatLength === 0) return thisLength;

    // Calculate matrix.
    var this_i, that_j, cost, min, t;
    for (i = 1; i <= thisLength; ++i) {
        this_i = __this[i-1];

        for (j = 1; j <= thatLength; ++j) {
            // Check the jagged ld total so far
            if (i === j && matrix[i][j] > 4) return thisLength;

            that_j = that[j-1];
            cost = (this_i === that_j) ? 0 : 1;  // Chars already match, no ++op to count.
            // Calculate the minimum (much faster than Math.min(...)).
            min    = matrix[i - 1][j    ] + 1;                      // Deletion.
            if ((t = matrix[i    ][j - 1] + 1   ) < min) min = t;   // Insertion.
            if ((t = matrix[i - 1][j - 1] + cost) < min) min = t;   // Substitution.

            matrix[i][j] = min; // Update matrix.
        }
    }

    return matrix[thisLength][thatLength];
};

达梅劳-勒文斯坦距离

jsperf.com/damerau-levenshtein-distance

达梅劳-勒文斯坦距离是对勒文斯坦距离进行一些小修改，以包括置换。几乎没有什么可以优化的余地。

// Damerau transposition.
if (i > 1 && j > 1 && this_i === that[j-2] && this[i-2] === that_j
&& (t = matrix[i-2][j-2]+cost) < matrix[i][j]) matrix[i][j] = t;

排序算法

回答的第二部分是选择适当的排序函数。我将很快上传优化后的排序函数到http://jsperf.com/sort。

欢迎来到Stack Overflow！感谢您的帖子！请勿在帖子中使用签名/标语。您的用户框已经算作了您的签名，您可以使用个人资料来发布任何关于自己的信息。有关签名/标语的常见问题解答 - Andrew Barber
嗨！抱歉，我的错误...我以为stackoverflow会在“匿名”或“访客”下发布我的消息...我看到它创建了一个伪帐户...我想我会完全注册。 - TheSpanishInquisition
1
你好，你所包含的原型方法肯定会更慢，因此我无法看到它们在这些测试中的相关性。 - StuR
4
我实现了一个非常高效的莱文斯坦距离计算方法，如果你还需要的话。
function levenshtein(s, t) {
    if (s === t) {
        return 0;
    }
    var n = s.length, m = t.length;
    if (n === 0 || m === 0) {
        return n + m;
    }
    var x = 0, y, a, b, c, d, g, h, k;
    var p = new Array(n);
    for (y = 0; y < n;) {
        p[y] = ++y;
    }

    for (; (x + 3) < m; x += 4) {
        var e1 = t.charCodeAt(x);
        var e2 = t.charCodeAt(x + 1);
        var e3 = t.charCodeAt(x + 2);
        var e4 = t.charCodeAt(x + 3);
        c = x;
        b = x + 1;
        d = x + 2;
        g = x + 3;
        h = x + 4;
        for (y = 0; y < n; y++) {
            k = s.charCodeAt(y);
            a = p[y];
            if (a < c || b < c) {
                c = (a > b ? b + 1 : a + 1);
            }
            else {
                if (e1 !== k) {
                    c++;
                }
            }

            if (c < b || d < b) {
                b = (c > d ? d + 1 : c + 1);
            }
            else {
                if (e2 !== k) {
                    b++;
                }
            }

            if (b < d || g < d) {
                d = (b > g ? g + 1 : b + 1);
            }
            else {
                if (e3 !== k) {
                    d++;
                }
            }

            if (d < g || h < g) {
                g = (d > h ? h + 1 : d + 1);
            }
            else {
                if (e4 !== k) {
                    g++;
                }
            }
            p[y] = h = g;
            g = d;
            d = b;
            b = c;
            c = a;
        }
    }

    for (; x < m;) {
        var e = t.charCodeAt(x);
        c = x;
        d = ++x;
        for (y = 0; y < n; y++) {
            a = p[y];
            if (a < c || d < c) {
                d = (a > d ? d + 1 : a + 1);
            }
            else {
                if (e !== s.charCodeAt(y)) {
                    d = c + 1;
                }
                else {
                    d = c;
                }
            }
            p[y] = d;
            c = a;
        }
        h = d;
    }

    return h;
}

这是我对一个类似的SO问题的回答：最快通用的Levenshtein Javascript实现 更新 上述版本的改进版现在已经发布在github/npm上，详情请见https://github.com/gustf/js-levenshtein。
请查看参观一下和你的答案在另一个城堡里：什么时候一个答案不是一个答案。 - Drew
@Drew 谢谢，链接指向另一个类似的SO问题有点不清楚。我稍微修改了一下。一切都好了吗？ - gustf
1
一种思考方式是，如果您的网站链接不在那里，那是否就是一个答案。对于27来说，它超过了400行代码。所以不确定该说什么。不太容易把它放在这里。 - Drew
1
好的，我明白你的意思了。现在已经添加了实现，并进行了一些其他的改进。感谢您抽出时间来审查我的答案，我仍在学习 SO 的方式。 - gustf
2
显而易见的方法是将每个字符串映射到一个(距离, 字符串)对，然后对此列表进行排序，然后再删除距离部分。这样可以确保只需计算一次Levenstein距离。如果有重复的话可能需要先合并。
2

我建议使用更好的Levenshtein方法，例如@James Westgate答案中的方法。

话虽如此，在DOM操作中的开销通常很大。您可以改进jQuery的使用方式。

尽管上面的示例中循环较小，但将每个oneResult生成的html连接成单个字符串，并在循环结束时进行一次append，效率会更高。

您的选择器速度较慢。 $('.oneResult') 将搜索DOM中所有元素，并在旧版IE浏览器中测试其className。您可能需要考虑像atRes.find('.oneResult')这样的内容来定义搜索范围。

在添加click处理程序的情况下，我们可能需要更好地避免在每个keyup上设置处理程序。您可以通过在设置keyup处理程序的同一块中在atRest上设置一个单独的处理程序来利用事件委派：

atRest.on('click', '.oneResult', function(){
  window.location.href = 'http://hashtag.ly/' + $(this).html();
});

请查看http://api.jquery.com/on/了解更多信息。
我认为问题是关于Levenstein的，但是你的回答却是关于Jquery的。请考虑将您的回复修改为评论。 - Jack G
1
我刚刚写了一个新版本：http://jsperf.com/levenshtein-algorithms/16 
function levenshtein(a, b) {
  if (a === b) return 0;

  var aLen = a.length;
  var bLen = b.length;

  if (0 === aLen) return bLen;
  if (0 === bLen) return aLen;

  var len = aLen + 1;
  var v0 = new Array(len);
  var v1 = new Array(len);

  var i = 0;
  var j = 0;
  var c2, min, tmp;

  while (i < len) v0[i] = i++;

  while (j < bLen) {
    c2 = b.charAt(j++);
    v1[0] = j;
    i = 0;

    while (i < aLen) {
      min = v0[i] - (a.charAt(i) === c2 ? 1 : 0);
      if (v1[i] < min) min = v1[i];
      if (v0[++i] < min) min = v0[i];
      v1[i] = min + 1;
    }

    tmp = v0;
    v0 = v1;
    v1 = tmp;
  }
  return v0[aLen];
}

这个版本比其他版本更快。甚至可以在IE上使用 =)

好的，我已经去掉了“-1”。点击链接查看，@axrwkr。不过，至少应该在这里提一下... - icedwater
如果链接失效，那么这个答案的价值也会随之消失。我想代码应该在这里。 - mickmackusa
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接