La optimización de algoritmo de Jaro-Winkler

Question

Tengo este código para el algoritmo Jaro-Winkler tomado de este página web. Necesito funcionar con 150.000 veces para obtener la distancia entre las diferencias. Se tarda mucho tiempo, ya que funciona en el dispositivo móvil Android.

¿Se puede optimizarse más?

public class Jaro {
    /**
     * gets the similarity of the two strings using Jaro distance.
     *
     * @param string1 the first input string
     * @param string2 the second input string
     * @return a value between 0-1 of the similarity
     */
    public float getSimilarity(final String string1, final String string2) {

        //get half the length of the string rounded up - (this is the distance used for acceptable transpositions)
        final int halflen = ((Math.min(string1.length(), string2.length())) / 2) + ((Math.min(string1.length(), string2.length())) % 2);

        //get common characters
        final StringBuffer common1 = getCommonCharacters(string1, string2, halflen);
        final StringBuffer common2 = getCommonCharacters(string2, string1, halflen);

        //check for zero in common
        if (common1.length() == 0 || common2.length() == 0) {
            return 0.0f;
        }

        //check for same length common strings returning 0.0f is not the same
        if (common1.length() != common2.length()) {
            return 0.0f;
        }

        //get the number of transpositions
        int transpositions = 0;
        int n=common1.length();
        for (int i = 0; i < n; i++) {
            if (common1.charAt(i) != common2.charAt(i))
                transpositions++;
        }
        transpositions /= 2.0f;

        //calculate jaro metric
        return (common1.length() / ((float) string1.length()) +
                common2.length() / ((float) string2.length()) +
                (common1.length() - transpositions) / ((float) common1.length())) / 3.0f;
    }

    /**
     * returns a string buffer of characters from string1 within string2 if they are of a given
     * distance seperation from the position in string1.
     *
     * @param string1
     * @param string2
     * @param distanceSep
     * @return a string buffer of characters from string1 within string2 if they are of a given
     *         distance seperation from the position in string1
     */
    private static StringBuffer getCommonCharacters(final String string1, final String string2, final int distanceSep) {
        //create a return buffer of characters
        final StringBuffer returnCommons = new StringBuffer();
        //create a copy of string2 for processing
        final StringBuffer copy = new StringBuffer(string2);
        //iterate over string1
        int n=string1.length();
        int m=string2.length();
        for (int i = 0; i < n; i++) {
            final char ch = string1.charAt(i);
            //set boolean for quick loop exit if found
            boolean foundIt = false;
            //compare char with range of characters to either side

            for (int j = Math.max(0, i - distanceSep); !foundIt && j < Math.min(i + distanceSep, m - 1); j++) {
                //check if found
                if (copy.charAt(j) == ch) {
                    foundIt = true;
                    //append character found
                    returnCommons.append(ch);
                    //alter copied string2 for processing
                    copy.setCharAt(j, (char)0);
                }
            }
        }
        return returnCommons;
    }
}

He mencionado que en todo el proceso que hago simplemente instancia de la secuencia de comandos, por lo que sólo una vez

jaro= new Jaro();

Si va a ejemplos de prueba y que así no romper el guión, le resultará aquí , en otro hilo para el pitón optimización

Answer 1

Sí, pero no van a disfrutar de ella. Vuelva a colocar todos esos StringBuffers newed con arrays de char que se asignan en el constructor y nunca más, utilizando índices enteros para realizar un seguimiento de lo que hay en ellos.

Este pendiente de los Comunes-Lang parche le dará algo del sabor .

Answer 2

Sé que esta pregunta probablemente ha sido resuelto por algún tiempo, pero me gustaría hacer un comentario sobre el mismo algoritmo. Al comparar una cadena contra sí misma, la respuesta resulta ser 1 / | cadena | apagado. Al comparar los valores ligeramente diferentes, los valores también resultan ser más baja.

La solución a esto es para ajustar 'm-1' a 'm' en el interior para-declaración dentro del método getCommonCharacters. Después, el código funciona como un encanto:)

http://en.wikipedia.org/wiki/Jaro%E2 % 80% 93Winkler_distance , así como para algunos ejemplos.

Answer 3

1. Trate de evitar los dos bucles anidados en el bucle getCommonCharacters.
   Sugerencia en cuanto a cómo: almacenar todos los caracteres en la cadena más pequeña en un mapa de algún tipo (Java tiene algunos), donde la clave es el carácter y el valor es la posición, de esa manera todavía se puede calcular la distancia, ya sea que esté son en común. Yo no entiendo muy bien el algoritmo, pero creo que esto es factible.
2. A excepción de que Y la respuesta de bmargulies, realmente no veo optimizaciones adicionales más allá de cosas como los bits etc. Si esto es realmente crítica, considere volver a escribir esta porción en C?

Answer 4

No sé mucho acerca de Android y cómo funciona con bases de datos. WP7 tiene (tendrá :)) SQL CE. El siguiente paso sería típicamente al trabajo con sus datos. Añadir longitudes de cadena y limitar sus comparaciones. Añadir índices en ambas columnas y ordenar por longitud y luego por valor. El índice de la longitud se debe ordenar también. Lo tenía ejecuta en un servidor viejo con 150 000 términos médicos me dan sugerencias y corrección ortográfica en menos de 0,5 segundos, los usuarios podrían apenas notarlo, especialmente si se ejecuta en un hilo separado.

Me refería a blog acerca de ello durante mucho tiempo (como 2 años :)) porque hay una necesidad. Pero finalmente me las arreglo para escribir unas palabras sobre ella y dar algunos consejos. Por favor, echa un vistazo aquí:

ISolvable.blogspot.com

A pesar de que es para la plataforma de Microsoft, sigue los principios generales son los mismos.

Answer 5

Sí, esto se puede hacer mucho más rápido. Por un lado, no es necesario en absoluto los StringBuffers. Por otra parte, no es necesario un circuito separado para contar transposiciones.

Se puede encontrar mi aplicación aquí , y debería ser mucho más rápido. Está bajo licencia Apache 2.0.

Answer 6

En lugar de regresar a los caracteres comunes utilizando el método GetCommonCharacters, utilizar un par de matrices para mantener a los partidos, de manera similar a la versión C aquí https://github.com/miguelvps/c/blob/master/jarowinkler.c

/*Calculate matching characters*/
for (i = 0; i < al; i++) {
    for (j = max(i - range, 0), l = min(i + range + 1, sl); j < l; j++) {
        if (a[i] == s[j] && !sflags[j]) {
            sflags[j] = 1;
            aflags[i] = 1;
            m++;
            break;
        }
    }
}

Otra optimización es comprobar la validez de calcular una máscara de bits para cada cadena. Usando esa información, compruebe si está presente en la segunda el carácter actual en la primera cuerda. Esto se puede hacer usando operaciones bit a bit eficiente.

Esto saltará el cálculo de la max / min y un bucle de caracteres que faltan.