Optimisation de l'algorithme Jaro-Winkler

Question

J'ai ce code pour l'algorithme Jaro-Winkler provenant cette site . Je dois courir 150.000 fois pour obtenir la distance entre les différences. Il prend beaucoup de temps, que je lance sur un appareil mobile Android.

Peut-il être optimisé plus?

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

Je mentionne que, dans tout le processus que je fais par exemple juste du script, donc une seule fois

jaro= new Jaro();

Si vous allez tester et des exemples besoin afin de ne pas briser le script, vous trouverez

Était-ce utile?

Nous faire parvenir

La solution

Oui, mais vous ne vont pas en profiter. Remplacer tous les StringBuffers newed avec des tableaux char qui sont attribués dans le constructeur et jamais, en utilisant des indices entiers de garder une trace de ce qui est en eux.

Cette attente correctif Commons-Lang vous donnera un peu de la saveur .

Answer 1

Oui, mais vous ne vont pas en profiter. Remplacer tous les StringBuffers newed avec des tableaux char qui sont attribués dans le constructeur et jamais, en utilisant des indices entiers de garder une trace de ce qui est en eux.

Cette attente correctif Commons-Lang vous donnera un peu de la saveur .

Answer 2

Je sais que cette question a probablement été résolu depuis un certain temps, mais je voudrais commenter l'algorithme lui-même. Lorsque l'on compare une chaîne contre elle-même, la réponse se révèle être 1 / | chaîne | de. Lorsque l'on compare des valeurs légèrement différentes, les valeurs se tournent également être plus faible.

La solution est d'adapter « m-1 » à « m » dans la for-instruction interne à l'intérieur de la méthode getCommonCharacters. Le code fonctionne alors comme un charme:)

Voir http://en.wikipedia.org/wiki/Jaro%E2 % 80% 93Winkler_distance et quelques exemples.

Answer 3

1. Essayez d'éviter les deux boucles imbriquées dans la boucle de getCommonCharacters.
   Suggestion à faire: stocker tous les caractères dans la chaîne plus petite dans une carte de quelque sorte (java a quelques-uns), où la clé est le caractère et la valeur est la position, de cette façon vous pouvez calculer encore la distance, wether ils sont en commun. Je ne comprends pas tout à fait l'algorithme, mais je pense que cela est faisable.
2. Sauf pour cela et la réponse de bmargulies, je ne vois vraiment pas d'autres optimisations au-delà des choses comme des morceaux, etc. Si cela est vraiment critique, envisager de réécrire cette partie en C?

Answer 4

Je ne sais pas beaucoup sur Android et comment il fonctionne avec les bases de données. WP7 a (aura :)) SQL CE. L'étape suivante serait généralement de travailler avec vos données. Ajouter longueurs de chaîne et de limiter vos comparaisons. Ajouter des index sur les deux colonnes et trier par longueur et par valeur. L'indice de la longueur doit être triée ainsi. Je l'avais exécuté sur un ancien serveur avec 150 000 termes médicaux me donnant des suggestions et vérification orthographique en moins de 0,5 secondes, les utilisateurs peuvent remarquer à peine, surtout si vous travaillez sur un thread séparé.

Je voulais blog à ce sujet depuis longtemps (comme 2 ans :)) parce qu'il ya un besoin. Mais je parviens enfin à écrire quelques mots à ce sujet et donner quelques conseils. S'il vous plaît vérifier ici:

ISolvable.blogspot.com

Bien qu'il soit pour la plate-forme Microsoft, encore des principes généraux sont les mêmes.

Answer 5

Oui, cela peut être beaucoup plus rapide. D'une part, vous n'avez pas besoin StringBuffers du tout. D'autre part, vous n'avez pas besoin d'une boucle séparée pour compter transpositions.

Vous pouvez trouver ma mise en œuvre ici , et il devrait être beaucoup plus rapide. Il est sous licence Apache 2.0.

Answer 6

retour au lieu des caractères communs en utilisant la méthode de GetCommonCharacters, utilisez deux tableaux pour garder les matches, de façon similaire à la version C ici 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;
        }
    }
}

Une autre optimisation consiste à pré-calculer pour chaque chaîne bitmask. En utilisant cela, vérifiez si le caractère en cours sur la première chaîne est présente sur le second. Cela peut être fait en utilisant des opérations de manipulation de bits efficace.

Cela va sauter le calcul du max / min et en boucle pour les caractères manquants.