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

现在，我知道这里可以做的事情有一些限制，但是我已经阅读了之前的SO问题和LD的Wikipedia链接，如果有人愿意将阈值限制为设置的最大距离，则可以帮助限制在算法上花费的时间，但是我不确定如何准确地做到这一点。

如果我们仅对距离小于阈值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;
    }