javascript - 索引字典的编辑距离

Question

我目前在使用已实现的模糊字符串匹配器时遇到问题。我希望能够使用 Javascript 在不到一秒左右的时间内快速确定 10,000 个短语列表中的哪些短语与字典中 200,000 个短语中的任何一个的编辑距离为 2 或更小。这些短语平均每个大约 15 个字符。我不关心有多少场比赛，甚至比赛是什么，只关心是否有比赛。我可以事先对字典中我想要的单词进行任何索引，但对其他单词则没有。

我的主要方法是使用 BK 树。对所有 10,000 个单词进行分类通常需要大约 130-140 秒，因此比我希望的要低大约两个数量级。能够在 Javascript 中快速对短语进行分类是否现实？如果是这样，我应该使用什么技术，是否有比 BK 树更快的方法来解决此类问题？

Answer 1

我会建议我的 Levenshtein 实现，因为它是我见过的最快的。

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;
            }
        }
    };
})();