最快通用的Levenshtein Javascript实现

Question

最快通用的Levenshtein Javascript实现

8

我正在寻找一款适用于JavaScript的优秀通用Levenshtein实现。它必须快速，并且适用于短字符串和长字符串。它还应该被多次使用（因此需要缓存）。最重要的是它计算简单的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;
            }
        }
    };
})();

现在我有两个问题：

这段代码能否更快？我知道通过编写每个循环的第一次迭代，可以获得约20％的速度提升。

这段代码是否适合作为通用代码，例如用于库中的使用？

- Marco de Wit

请查看以下问题：https://dev59.com/Gmct5IYBdhLWcg3wqfL9 同时，这是关于编程的内容。 - James Westgate

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gustf · Accepted Answer

我们在工作中进行了一个有趣的竞赛，比赛内容是制作最快的Levenshtein实现。我想出了一种更快的方法。首先，我必须说这并不容易，因为你的解决方案是“out there”中最快的。 :)

这个实现经过node.js测试，我的基准测试结果表明，在小文本（随机单词大小为2-10个字符）上，这个实现速度比其他实现快约15%，而在较长的文本（长度为30+，包含随机字符）上则快两倍以上。

注意：我删除了所有实现的数组缓存。

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

如果初始缓存内部循环的s.charCodeAt(y)在Uint32Array中，对于较长的文本，它的速度几乎可以提高3倍。使用Uint16Array作为距离成本数组似乎也有益于较长的文本。以下是该解决方案的代码：

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;
    var p = new Uint16Array(n);
    var u = new Uint32Array(n);
    for (y = 0; y < n;) {
        u[y] = s.charCodeAt(y);
        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++) {
            a = p[y];
            if (a < c || b < c) {
                c = (a > b ? b + 1 : a + 1);
            }
            else {
                if (e1 !== u[y]) {
                    c++;
                }
            }

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

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

            if (d < g || h < g) {
                g = (d > h ? h + 1 : d + 1);
            }
            else {
                if (e4 !== u[y]) {
                    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 !== u[y]) {
                    d = c + 1;
                }
                else {
                    d = c;
                }
            }
            p[y] = d;
            c = a;
        }
        h = d;
    }

    return h;
}

所有基准测试结果均来自我的测试，测试数据可能与您的测试数据不同。

我认为此解决方案与您的解决方案（以及其他一些快速解决方案）的两个主要区别是：

1. 如果不必要，内部循环不总是进行字符比较。 2. 在莱文斯坦“矩阵”中，外部循环中每次处理4行进行“循环展开”排序。这是一个重大的性能优势。

请参见http://jsperf.com/levenshtein-distance/24。

我会在找到时间时将此解决方案放在github上 :)

更新：最终，我将解决方案放在了github上https://github.com/gustf/js-levenshtein。它有点被修改/优化，但它是相同的基本算法。