什么是高频使用的最快Levenshtein算法？

Question

什么是高频使用的最快Levenshtein算法？

6

为了一个客户端搜索工具，我需要找到一个单词与数百万个其他单词之间的Levenshtein距离。用户应该能够将大约20个单词的短文本与一本书进行比较。用户可以通过在书中查找文本的最具特征性的单词的位置来完成此操作。“查找位置”并不意味着寻找完全匹配，而是像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;
    }

这样会快很多，我已经尽力了。我将继续寻找其他想法并尝试一些新的方法。

- Marco de Wit

4

你是否熟悉这个线程：https://dev59.com/Gmct5IYBdhLWcg3wqfL9？ - Jan.J

是的，我是，但是levDist（'knowledge'，'configured'）给了我8，而我预期的是9。所以我不确定。 - Marco de Wit

@MarcodeWit：被接受的答案中的评论解释了那里的代码执行Damerau-Levensthein，这为您的单词提供了8。 - Bergi

@Bergi 在删除 Damerau 转置后，我的算法在 Firefox 上的速度提高了六倍以上。我想主要是因为缓存的原因。 - Marco de Wit

虽然我不知道如何使算法本身更快，但我建议你尝试使用Web Workers来并行化任务。它们听起来是解决你问题的理想方案，并且可以避免冻结用户界面。 - Cesar Canassa

1个回答

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

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

- Bergi · Accepted Answer

由于您一遍又一遍地比较相同的单词，因此使用部分应用和缓存可以略微提高性能：

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

我也稍微改变了循环的方式来使它更加线性。

不确定是否能够提高速度，但你可以省略其中一个数组——你不需要交替地读/写它们：

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

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