修改Levenshtein距离算法不计算所有距离

Question

我正在进行模糊搜索实现,作为实现的一部分,我们使用的是Apache的StringUtils.getLevenshteinDistance.目前,我们正在寻找模糊搜索的特定最大平均响应时间.经过各种改进和一些剖析后,花费最多时间的地方是计算Levenshtein距离.它占搜索字符串总时间的大约80-90%三个字母或更多.

现在,我知道在这里可以做些什么有一些限制,但我已经读过以前的SO问题和LD的维基百科链接,如果有人愿意将阈值限制在设定的最大距离,这可能有助于遏制花在算法上的时间,但我不确定如何准确地做到这一点.

如果我们仅对距离感兴趣,如果它小于阈值k,那么在矩阵中计算宽度为2k + 1的对角条纹就足够了.这样,算法可以在O(kl)时间内运行,其中l是最短字符串的长度.[3]

下面你将看到StringUtils的原始LH代码.之后是我的修改.我试图基本上计算设定长度与i,j对角线的距离(因此,在我的例子中,i,j对角线上方和下方的两个对角线).但是,这是不正确的,因为我已经这样做了.例如,在最高的对角线上,它总是会直接在上面选择单元格值,这将是0.如果有人能告诉我如何使这个功能如我所描述的那样,或者如何使它成为如此的一般建议, 这将不胜感激.

public static int getLevenshteinDistance(String s, String t) {
        if (s == null || t == null) {
            throw new IllegalArgumentException("Strings must not be null");
        }

        int n = s.length(); // length of s
        int m = t.length(); // length of t

        if (n == 0) {
            return m;
        } else if (m == 0) {
            return n;
        }

        if (n > m) {
            // swap the input strings to consume less memory
            String tmp = s;
            s = t;
            t = tmp;
            n = m;
            m = t.length();
        }

        int p[] = new int[n+1]; //'previous' cost array, horizontally
        int d[] = new int[n+1]; // cost array, horizontally
        int _d[]; //placeholder to assist in swapping p and d

        // indexes into strings s and t
        int i; // iterates through s
        int j; // iterates through t

        char t_j; // jth character of t

        int cost; // cost

        for (i = 0; i<=n; i++) {
            p[i] = i;
        }

        for (j = 1; j<=m; j++) {
            t_j = t.charAt(j-1);
            d[0] = j;

            for (i=1; i<=n; i++) {
                cost = s.charAt(i-1)==t_j ? 0 : 1;
                // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
                d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);
            }

            // copy current distance counts to 'previous row' distance counts
            _d = p;
            p = d;
            d = _d;
        }

        // our last action in the above loop was to switch d and p, so p now 
        // actually has the most recent cost counts
        return p[n];
    }

我的修改(仅限于for循环):

  for (j = 1; j<=m; j++) {
        t_j = t.charAt(j-1);
        d[0] = j;

        int k = Math.max(j-2, 1);
        for (i = k; i <= Math.min(j+2, n); i++) {
            cost = s.charAt(i-1)==t_j ? 0 : 1;
            // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
            d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);
        }

        // copy current distance counts to 'previous row' distance counts
        _d = p;
        p = d;
        d = _d;
    }

Answer 1

我已经写了约莱文斯坦自动机,这是之前做这样的检查在O(n)的时间,单程这里.源代码示例使用Python,但解释应该是有用的,参考文章提供了更多详细信息.

Answer 2

实现窗口的问题是处理每行中第一个条目左侧和最后一个条目上方的值。

一种方法是将您最初填写的值从 1 而不是 0 开始，然后忽略您遇到的任何 0。您必须从最终答案中减去 1。

另一种方法是用高值填充第一个和最后一个上方的条目，这样最小检查永远不会选择它们。这就是我前几天不得不实施它时选择的方式：

public static int levenshtein(String s, String t, int threshold) {
    int slen = s.length();
    int tlen = t.length();

    // swap so the smaller string is t; this reduces the memory usage
    // of our buffers
    if(tlen > slen) {
        String stmp = s;
        s = t;
        t = stmp;
        int itmp = slen;
        slen = tlen;
        tlen = itmp;
    }

    // p is the previous and d is the current distance array; dtmp is used in swaps
    int[] p = new int[tlen + 1];
    int[] d = new int[tlen + 1];
    int[] dtmp;

    // the values necessary for our threshold are written; the ones after
    // must be filled with large integers since the tailing member of the threshold 
    // window in the bottom array will run min across them
    int n = 0;
    for(; n < Math.min(p.length, threshold + 1); ++n)
        p[n] = n;
    Arrays.fill(p, n, p.length, Integer.MAX_VALUE);
    Arrays.fill(d, Integer.MAX_VALUE);

    // this is the core of the Levenshtein edit distance algorithm
    // instead of actually building the matrix, two arrays are swapped back and forth
    // the threshold limits the amount of entries that need to be computed if we're 
    // looking for a match within a set distance
    for(int row = 1; row < s.length()+1; ++row) {
        char schar = s.charAt(row-1);
        d[0] = row;

        // set up our threshold window
        int min = Math.max(1, row - threshold);
        int max = Math.min(d.length, row + threshold + 1);

        // since we're reusing arrays, we need to be sure to wipe the value left of the
        // starting index; we don't have to worry about the value above the ending index
        // as the arrays were initially filled with large integers and we progress to the right
        if(min > 1)
            d[min-1] = Integer.MAX_VALUE;

        for(int col = min; col < max; ++col) {
            if(schar == t.charAt(col-1))
                d[col] = p[col-1];
            else 
                // min of: diagonal, left, up
                d[col] = Math.min(p[col-1], Math.min(d[col-1], p[col])) + 1;
        }
        // swap our arrays
        dtmp = p;
        p = d;
        d = dtmp;
    }

        if(p[tlen] == Integer.MAX_VALUE)
            return -1;
    return p[tlen];
}