Modifizieren eine Levenshtein Abstandsfunktion zu berechnen Abstand zwischen zwei Gruppen von x-y-Koordinaten?

Question

Ich habe eine Levenshtein Entfernung Funktion zur Arbeit versucht, so verändern, dass sie den Abstand zwischen zwei Linien zu finden, oder Sätze von xy-Koordinaten (in anderen Worten, wie ähnlich oder verschieden sind die Linien, nicht ihre geometrischen Abstand) . Ich laufe in einige allerdings Probleme. Ich bekomme, wie Sie den Wert nehmen über Löschung Kosten und die man nach links zu bekommen zusätzlich zu bekommen, aber während der Substitution Ich versuche euchlidian Abstand zu verwenden, und es funktioniert nicht für mich.

Wenn Sie darauf hinweisen könnten, was ich falsch mache, das wäre genial.

Hier ist der entsprechende Code in javascript:

padlock.dtw = {
    _deletionCost: 1,
    _insertionCost: 1,
    levenshtein: function(a,b){
        var l1 = a.length, l2 = b.length;
        if (Math.min(l1, l2) === 0) {
            return Math.max(l1, l2);
        }
        var i = 0, j = 0, d = [];
        for (i = 0 ; i <= l1 ; i++) {
            d[i] = [];
            d[i][0] = i;
        }
        for (j = 0 ; j <= l2 ; j++) {
            d[0][j] = j;
        }
        for (i = 1 ; i <= l1 ; i++) {
            for (j = 1 ; j <= l2 ; j++) {
                d[i][j] = Math.min(
                    d[i - 1][j] + this._deletionCost, /* deletion */
                    d[i][j - 1] + this._insertionCost, /* addition */
                    d[i - 1][j - 1] + (a[i - 1] === b[j - 1] ? 0 : this.euclideanDistance(a[i-1], b[j-1])) /* substitution, use euchlidean distance as cost */
                );
            }
        }
        this._debugPrintMatrix(d);
        return d[l1][l2];
    },
    euclideanDistance: function(a, b){
        var xd = a[0]-b[0];
        var yd = a[1]-b[1];
        return Math.abs(Math.sqrt(Math.pow(xd, 2) + Math.pow(yd, 2)));
    },
    _debugPrintMatrix: function(m){
        for(var i=0;i<m.length;i++){
            console.log.apply(this, m[i]);
        }
    }
}

Beispiel für die Ausgabe:

>>> padlock.dtw.levenshtein( [ [1,1], [0,9], [3,3], [4,4] ], [ [1,1], [2,2], [3,3], [4,4] ] )

Distance Matrix:
0 1 2                 3 4
1 0 1                 2 3
2 1 2                 3 4
3 2 2.414213562373095 2 3
4 3 3.414213562373095 3 2

Final Distance: 2

Answer 1

Wenn ich Ihre Frage richtig verstanden hat, dann sollten Sie vollständig den Code entfernen für euklidischen Abstand zwischen zwei Punkten Berechnung!

Lassen Sie mich zunächst neu formulieren Sie Ihre Frage:

Sie haben zwei Sätze von Punkten, z.

A = [ [1,1], [0,9], [3,3], [4,4] ]
B = [ [1,1], [2,2], [3,3], [4,4] ]

Sie versuchen, einen levenshtein Abstand zwischen diesen beiden Sätzen zu berechnen. Sie ersetzen „Buchstaben“ mit „Punkten“.

Bis zu diesem Punkt ist es sinnvoll. Ersetzen Sie einfach die „Buchstaben“ in levenshtein Algorithmus mit Punkten und Sie sind fertig!

Aber sind Sie einen Fehler: Der ursprünglichen Levenshtein Algorithmus nicht berechnen Abstände zwischen zwei Buchstaben , wie z.B. Abstand (a, b) = 1 oder Abstand (a, d) = 3 ist.

Sie haben versucht, den Algorithmus mit so etwas (mit Euklidischer Abstand () Funktion) zu verlängern. Aber levenshtein Algorithmus ist für solche Dinge nicht gemeint. Und wenn Sie einen genauen Blick auf sie haben, werden Sie sehen, dass es nicht Arbeit (die Werte in der Matrix, die eine Bedeutung haben, und jede Schleife Iteration verwendet Werte in der Matrix, die in einer vorherigen Iteration berechnet wurde).

Levenshtein-Distanz ist eine Edit-Distanz, kein geometrischer Abstand. Sie haben versucht, es zu ändern, so dass es eine Mischung aus bearbeiten und geometrischem Abstand berechnet. Diese Mischung macht keinen Sinn, es ist nutzlos und falsch, IMHO.

Fazit

Um den levenshtein Abstand von zwei Sätzen von x-y zu berechnen Koordinaten , sollten Sie Ihren euclidianDistance () mit einem einfachen Gleichheitsvergleich (a[0]==b[0] && a[1]==b[1]) ersetzen.

Dann wird der levenshtein Algorithmus gibt Ihnen eine "Edit-Distanz".

Answer 2

Wäre es nicht klüger sein geometrics zu verwenden, um den Abstand zwischen zwei Linien Berechnung? Oder gibt es einen bestimmten Grund, warum Sie würde nicht wollen, dass verwenden.

Da zwei Linien haben immer einen Schnittpunkt, es sei denn, sie sind parallel (edit, danke) , ist es einfach, den kleinsten Abstand zu berechnen: die 0 ist oder Einsatz einige Mathematik, die Dose werden auf google gefunden

Answer 3

Ich verstehe nicht, warum Sie Levenshtein dafür verwenden würde, scheint es, dass Sie viel bessere Ergebnisse von einfachen Berechnungen erhalten würde.

• Um die Differenz in Winkel der Linien zu finden, könnten Sie einfach den Winkel finden für jede Zeile (arctan ((x_1-x_2) / (y_1-y_2))) und subtrahieren sie.
• Um die mittlere Entfernung der Linien zu finden, geben Sie einfach die Entfernung Formel mit dem ersten Punkt jeder Zeile und dem zweiten Punkt jeder Zeile und im Durchschnitt zusammen diese Abstände nutzen könnten.

Anders als das (es sei denn, Ihre Linien in 3D sind), es gibt nichts anderes, um wirklich „vergleichen“, um sie mit.

Vielleicht habe ich falsch verstanden. Suchen Sie die Zeichenfolge-Werte für die Linien vergleichen?