Изменение алгоритма расстояния Левенштейна, чтобы не вычислять все расстояния

Я работаю над реализацией нечеткого поиска, и как часть реализации мы используем StringUtils.getLevenshteinDistance от Apache. На данный момент мы стремимся к определенному максимальному среднему времени отклика для нашего нечеткого поиска. После различных улучшений и некоторого профилирования место, где тратится больше всего времени, - это вычисление расстояния Левенштейна. Примерно 80-90% общего времени занимает поиск строк из трех или более букв.

Теперь я знаю, что есть некоторые ограничения на то, что здесь можно сделать, но я ' Я читал предыдущие вопросы SO и ссылку на Википедию для LD, что, если кто-то хочет ограничить порог до установленного максимального расстояния, это может помочь сократить время, затрачиваемое на алгоритм, но я не уверен, как это сделать точно.

Если нас интересуют только расстояние, если оно меньше порог k, то достаточно вычислить диагональную полосу шириной 2k + 1 в матрице. Таким образом, алгоритм может быть запущен за время O (kl), где l - длина кратчайшего string. [3]

Ниже вы увидите исходный код LH из StringUtils. После этого идет моя модификация. Я пытаюсь в основном рассчитать расстояния заданной длины от диагонали 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;
    }