Ottimizzazione dell'algoritmo di Jaro-Winkler

Question

Ho preso questo codice per l'algoritmo Jaro-Winkler Questo sito web.Devo correre 150.000 volte per ottenere la distanza tra le differenze.Ci vuole molto tempo, poiché utilizzo un dispositivo mobile Android.

Può essere ottimizzato di più?

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

Dico che nell'intero processo creo solo un'istanza della sceneggiatura, quindi solo una volta

jaro= new Jaro();

Se hai intenzione di testare e hai bisogno di esempi per non interrompere la sceneggiatura, lo troverai Qui, in un altro thread per l'ottimizzazione di Python

Answer 1

Sì, ma non ti piacerà.Sostituiscili tutti newed StringBuffer con array di caratteri allocati nel costruttore e mai più, utilizzando indici interi per tenere traccia di cosa c'è dentro.

Questa patch Commons-Lang in sospeso ti darà un po' di sapore.

Answer 2

So che probabilmente questa domanda è stata risolta da tempo, ma vorrei commentare l'algoritmo stesso.Quando si confronta una stringa contro se stessa, la risposta risulta essere 1/| String | spento.Confrontando valori leggermente diversi, anche i valori risultano inferiori.

La soluzione a questo è modificare 'm-1' in 'm' nell'istruzione for interna all'interno del metodo getCommonCharacters.Il codice quindi funziona a meraviglia :)

Vedere http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance anche per alcuni esempi.

Answer 3

1. Cerca di evitare i due cicli nidificati nel ciclo getCommonCharacters.
   Suggerimento su come:memorizza tutti i caratteri nella stringa più piccola in una mappa di qualche tipo (Java ne ha alcuni), dove la chiave è il carattere e il valore è la posizione, in questo modo puoi comunque calcolare la distanza, se sono in comune.Non capisco bene l'algoritmo, ma penso che sia fattibile.
2. A parte questo e la risposta di bmargulies, non vedo davvero ulteriori ottimizzazioni oltre a cose come bit ecc.Se questo è davvero fondamentale, valuta la possibilità di riscrivere questa parte in C?

Answer 4

Non so molto di Android e di come funziona con i database.WP7 ha (avrà :)) SQL CE.Il passaggio successivo sarebbe in genere quello di lavorare con i tuoi dati.Aggiungi lunghezze di stringa e limita i confronti.Aggiungi indici su entrambe le colonne e ordina per lunghezza e quindi per valore.Anche l'indice sulla lunghezza dovrebbe essere ordinato.L'ho fatto funzionare su un vecchio server con 150.000 termini medici che mi fornivano suggerimenti e controllo ortografico in meno di 0,5 secondi, gli utenti riuscivano a malapena a notarlo, soprattutto se in esecuzione su un thread separato.

Avevo intenzione di parlarne nel blog per molto tempo (tipo 2 anni :)) perché ce n'è bisogno.Ma finalmente riesco a scrivere qualche parola a riguardo e a fornire alcuni consigli.Per favore controlla qui:

ISolvable.blogspot.com

Sebbene sia per la piattaforma Microsoft, i principi generali sono gli stessi.

Answer 5

Sì, questo può essere fatto molto più velocemente.Per prima cosa, non hai affatto bisogno degli StringBuffer.Inoltre, non è necessario un ciclo separato per contare le trasposizioni.

Potete trovare la mia implementazione qui, e dovrebbe essere molto più veloce.È sotto licenza Apache 2.0.

Answer 6

Invece di restituire i caratteri comuni utilizzando il metodo GetCommonCharacters, utilizza un paio di array per mantenere le corrispondenze, in modo simile alla versione C qui 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;
        }
    }
}

Un'altra ottimizzazione consiste nel precalcolare una maschera di bit per ogni stringa.Usandolo, controlla se il carattere corrente sulla prima stringa è presente sulla seconda.Questo può essere fatto utilizzando operazioni bit a bit efficienti.

Ciò salterà il calcolo del massimo/minimo e il loop per i caratteri mancanti.