Otimizando o algoritmo Jaro-Winkler

Question

Eu tenho esse código para o algoritmo de Jaro-Winkler isto local na rede Internet. Preciso correr 150.000 vezes para obter distância entre as diferenças. Demora muito tempo, enquanto eu corro em um dispositivo móvel Android.

Pode ser otimizado mais?

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

Menciono que em todo o processo eu faço apenas uma instância do script, então apenas uma vez

jaro= new Jaro();

Se você vai testar e precisar de exemplos, então não quebre o script, você o encontrará aqui, em outro tópico para otimização do Python

Answer 1

Sim, mas você não vai gostar. Substitua todos esses newEd StringBuffers com matrizes de char que são alocados no construtor e nunca mais, usando índices inteiros para acompanhar o que está neles.

Este patch pendente comuns-lançamentos dará a você um pouco do sabor.

Answer 2

Sei que essa pergunta provavelmente foi resolvida há algum tempo, mas gostaria de comentar sobre o próprio algoritmo. Ao comparar uma string contra si, a resposta acaba sendo 1/| string | desligado. Ao comparar valores ligeiramente diferentes, os valores também acabam sendo mais baixos.

A solução para isso é ajustar 'm-1' para 'm' no interior para a estatura dentro do método getCommOncharacters. O código então funciona como um charme :)

Ver http://en.wikipedia.org/wiki/jaro%E2%80%93winkler_distance também para alguns exemplos.

Answer 3

1. Tente evitar os dois loops aninhados no Loop GetCommincharacters.
   Sugestão sobre como: Armazene todos os chars na corda menor em um mapa de algum tipo (Java tem alguns), onde a chave é o personagem e o valor é a posição, para que você ainda possa calcular a distância, se eles são em comum. Não entendo muito bem o algoritmo, mas acho que isso é factível.
2. Exceto por isso e a resposta de BMargulies, eu realmente não vejo outras otimizações além de coisas como bits etc. Se isso for realmente crítico, considere reescrever essa parte em C?

Answer 4

Não sei muito sobre o Android e como funciona com bancos de dados. O WP7 tem (terá :)) SQL CE. O próximo passo seria normalmente trabalhar com seus dados. Adicione comprimentos de string e limite suas comparações. Adicione índices nas duas colunas e classifique por comprimento e depois por valor. O índice no comprimento também deve ser classificado. Eu tinha executado em um servidor antigo com 150.000 termos médicos, dando -me sugestões e verificação de ortografia em menos de 0,5 segundos, os usuários mal conseguiam perceber, especialmente se executando em um thread separado.

Eu pretendia escrever um blog sobre isso por um longo tempo (como 2 anos :)) porque há uma necessidade. Mas finalmente consigo escrever algumas palavras sobre isso e fornecer algumas dicas. Por favor, confira aqui:

Isolvable.blogspot.com

Embora seja para a plataforma Microsoft, os princípios gerais ainda são os mesmos.

Answer 5

Sim, isso pode ser feito muito mais rápido. Por um lado, você não precisa dos StringBuffers. Por outro lado, você não precisa de um loop separado para contar transposições.

Você pode encontrar minha implementação aqui, e deve ser muito mais rápido. Está sob licença Apache 2.0.

Answer 6

Em vez disso, devolvendo os caracteres comuns usando o método getCommincharacters, use algumas matrizes para manter as correspondências, da mesma forma que a versão C aqui 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;
        }
    }
}

Outra otimização é pré-calcular uma máscara de bits para cada string. Usando isso, verifique se o caractere atual na primeira string está presente no segundo. Isso pode ser feito usando operações eficientes Bitwise.

Isso pulará calculando o máximo/min e o loop para caracteres ausentes.