Optimierung von Jaro-Winkler-Algorithmus

Question

Ich habe diesen Code für Jaro-Winkler-Algorithmus genommen von dieser Website. Ich brauche 150.000 Mal zu laufen Abstand zwischen Unterschieden zu bekommen. Es dauert eine lange Zeit, da ich auf einem Android-Mobilgerät ausgeführt werden.

Kann es optimiert mehr werden?

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

ich erwähnt, dass im gesamten Prozess, den ich gerade Instanz des Skripts machen, so nur einmal

jaro= new Jaro();

Wenn Sie auf Test und Notwendigkeit Beispiele werden so das Skript nicht brechen, werden Sie feststellen, es

War es hilfreich?

einreichen

Lösung

Ja, aber gehen Sie nicht, es zu genießen. Ersetzen Sie alle jenen newed Stringbuffers mit char-Arrays, die im Konstruktor zugewiesen werden und nie wieder, Integer-Indizes verwenden, um zu verfolgen, was in ihnen.

Diese anhängige Commons-Lang-Patch werden Sie etwas von dem Geschmack geben .

Answer 1

Ja, aber gehen Sie nicht, es zu genießen. Ersetzen Sie alle jenen newed Stringbuffers mit char-Arrays, die im Konstruktor zugewiesen werden und nie wieder, Integer-Indizes verwenden, um zu verfolgen, was in ihnen.

Diese anhängige Commons-Lang-Patch werden Sie etwas von dem Geschmack geben .

Answer 2

Ich weiß, diese Frage wahrscheinlich für einige Zeit gelöst ist, aber ich würde auf dem Algorithmus einen Kommentar abgibt selbst. Wenn eine Zeichenfolge gegen sich selbst zu vergleichen, stellt sich die Frage 1 sein out / | string | aus. Wenn etwas andere Werte zu vergleichen, werden die Werte auch geringer aus.

Die Lösung hierfür ist ‚m-1‘ bis ‚m‘ in der inneren for-Anweisung innerhalb des getCommonCharacters Verfahrens einzustellen. Der Code funktioniert dann wie ein Zauber:)

Siehe http://en.wikipedia.org/wiki/Jaro%E2 % 80% 93Winkler_distance auch für einige Beispiele.

Answer 3

1. Versuchen Sie, die zwei verschachtelten Schleifen in der getCommonCharacters Schleife zu vermeiden.
   Vorschlag, wie: Speichern Sie alle Zeichen in der kleineren Zeichenfolge in einer Karte von einer Art (Java hat ein paar), wo der Schlüssel ist der Charakter und der Wert ist die Position, auf diese Weise Sie noch die Entfernung berechnen kann, ob sie gemeinsam sind. Ich verstehe nicht ganz, den Algorithmus verstehen, aber ich denke, das ist machbar.
2. Mit Ausnahme, dass und bmargulies Antwort, ich sehe nicht wirklich weitere Optimierungen über Sachen wie Bits usw. Wenn das wirklich kritisch ist, denken Sie daran Umschreiben diesen Teil in C?

Answer 4

Ich weiß nicht viel über Android und wie funktioniert es mit Datenbanken. WP7 hat (haben :)) SQL CE. Der nächste Schritt wäre typischerweise mit Ihren Daten an der Arbeit. In Stringlängen und Ihre Vergleiche begrenzen. In Indizes auf beiden Spalten und sortieren nach Länge und dann von Wert. Der Index auf Länge sollte auch sortiert werden. Ich hatte es mit 150 000 medizinischen Begriffen auf einen alten Server läuft mir Anregungen zu geben und die Überprüfung buchstabiert in weniger als 0,5 Sekunden, Benutzer konnten kaum bemerken, vor allem, wenn auf einem separaten Thread ausgeführt wird.

Ich wollte über sie für eine lange Zeit (wie 2 Jahre :)) zum Blog, weil es notwendig ist. Aber ich schaffe schließlich einige Worte darüber zu schreiben und ein paar Tipps zu geben. Bitte überprüfen Sie es heraus hier:

ISolvable.blogspot.com

Auch wenn es für die Microsoft-Plattform ist, sind nach wie vor allgemeine Grundsätze gleich.

Answer 5

Ja, kann dies viel schneller gemacht werden. Für eine Sache, brauchen Sie nicht die Stringbuffers überhaupt. Zum anderen brauchen Sie keinen separaten Schleife Umstellungen zu zählen.

Hier finden Sie meine Implementierung hier , und es sollte viel schneller sein. Es ist unter der Apache 2.0-Lizenz.

Answer 6

Statt das gemeinsame Zeichen mit GetCommonCharacters Methode zurückkehren, verwenden Sie ein Paar von Arrays, die Spielen zu halten, ähnlich wie bei der C-Version hier 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;
        }
    }
}

Eine weitere Optimierung ist eine Bitmaske für jede Saite im Voraus zu berechnen. Verwenden, die prüfen, ob das aktuelle Zeichen der ersten Zeichenfolge auf dem zweiten vorhanden ist. Dies kann mit Hilfe effizienter bitweise Operationen durchgeführt werden.

Dies wird überspringen Berechnung des max / min und Looping für Zeichen fehlen.