Estoy trabajando en una implementación de búsqueda difusa y, como parte de la implementación, estamos utilizando StringUtils.getLevenshteinDistance de Apache. Por el momento, buscaremos un tiempo de respuesta promedio máximo máximo específico para nuestra búsqueda difusa. Después de varias mejoras y con algunos perfiles, el lugar donde se pasa la mayor parte del tiempo es calcular la distancia de Levenshtein. Ocupa aproximadamente el 80-90% del tiempo total en cadenas de búsqueda de tres letras o más.

Ahora, sé que hay algunas limitaciones en lo que se puede hacer aquí, pero he leído en preguntas SO anteriores y en el enlace de Wikipedia para LD que si uno está dispuesto a limitar el umbral a una distancia máxima establecida, eso podría ayudar a frenar el tiempo dedicado al algoritmo, pero no estoy seguro de cómo hacer esto exactamente.

Si solo estamos interesados en la distancia si es más pequeña que un umbral k, entonces es suficiente calcular una franja diagonal de ancho 2k + 1 en la matriz. De esta manera, el algoritmo puede ejecutarse en tiempo O (kl), donde l es la longitud de la cadena más corta. [3]

A continuación, verá el código LH original de StringUtils. Después de eso es mi modificación. Básicamente estoy tratando de calcular las distancias de una longitud establecida desde la diagonal i, j (en mi ejemplo, dos diagonales por encima y por debajo de la diagonal i, j). Sin embargo, esto no puede ser correcto como lo he hecho. Por ejemplo, en la diagonal más alta, siempre va a elegir el valor de la celda directamente arriba, que será 0. Si alguien pudiera mostrarme cómo hacer que esto funcione como he descrito, o algún consejo general sobre cómo hacerlo , podria ser muy apreciado.

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];
    }

Mis modificaciones (solo para los bucles 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;
    }