什么是最频繁使用的levenshtein算法

Question

对于客户端搜索工具,我需要找到一个单词的Levenshtein距离以及数百万个其他单词.用户应该能够将大约二十个单词的短文与一本书进行比较.用户可以通过查找书中文本的最具特征的单词的位置来做到这一点."寻找位置"并不意味着寻找完全匹配,但几乎与levenshtein匹配.我从已经可用的实现开始,但我需要更快的速度.我最终得到了这个:

var rowA = new Uint16Array(1e6);
var rowB = new Uint16Array(1e6);
function levenshtein(s1, s2) {
    var s1_len = s1.length, s2_len = s2.length, i1, i2 = 0, a, b, c, c2, i = 0;
    if (s1_len === 0)
        return s2_len;
    if (s2_len === 0)
        return s1_len;
    while (i < s1_len)
        rowA[i] = ++i;
    while (i2 < s2_len) {
        c2 = s2[i2];
        a = i2;
        ++i2;
        b = i2;
        for (i1 = 0; i1 < s1_len; ++i1) {
            c = a + (s1[i1] !== c2 );
            a = rowA[i1];
            b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
            rowB[i1] = b;
        }
        if (i2 === s2_len)
            return b;
        c2 = s2[i2];
        a = i2;
        ++i2;
        b = i2;
        for (i1 = 0; i1 < s1_len; ++i1) {
            c = a + (s1[i1] !== c2 );
            a = rowB[i1];
            b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
            rowA[i1] = b;
        }
    }
    return b;
}

如您所见,我使用了将对象放置在函数之外以便重新使用它们的技术.我也稍微通过线性化循环来重复自己.会更快吗？我很好奇你的建议.

更新:在获得Bergi的提示之后,我更加想到了这个解决方案:

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

这又快得多.我无法挤出更多.我一直在寻找其他想法,并会尝试更多.

Answer 1

由于您一遍又一遍地与同一个单词进行比较，因此通过使用部分应用程序和缓存可以提高性能：

\n\n

function levenshtein(s1) {\n    var row0 = [], row1 = [], s1_len = s1.length;\n    if (s1_len === 0)\n        return function(s2) {\n            return s2.length;\n        };\n    return function(s2) {\n        var s2_len = s2.length, s1_idx, s2_idx = 0, a, b, c, c2, i = 0;\n        if (s2_len === 0)\n            return s1_len;\n        \xe2\x80\xa6\n        return b;\n    };\n}\n

\n\n

\n

我还通过稍微线性化循环来重复自己。

\n

\n\n

不确定它是否会变得更快，但您可以省略其中一个数组 - 您不需要以交替的方式读/写它们：

\n\n

function levenshtein(s1) {\n    var s1_len = s1.length, row = new Array(s1_len);\n    if (s1_len === 0)\n        return function(s2) {\n            return s2.length;\n        };\n    return function(s2) {\n        var s2_len = s2.length, s1_idx, s2_idx = 0, a, b, c, c2, i = 0;\n        if (s2_len === 0)\n            return s1_len;\n        while (i < s1_len)\n           row[i] = ++i;\n        while (s2_idx < s2_len) {\n            c2 = s2[s2_idx];\n            a = s2_idx;\n            ++s2_idx;\n            b = s2_idx;\n            for (s1_idx = 0; s1_idx < s1_len; ++s1_idx) {\n                c = a + (s1[s1_idx] === c2 ? 0 : 1);\n                a = row[s1_idx];\n                b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);\n                row[s1_idx] = b;\n            }\n        }\n        return b;\n    };\n}\n

\n\n

我认为如果不将数百万个单词放入专用数据结构（例如前缀特里树）中，就无法进行进一步的优化。

\n