La modificación de una función de distancia Levenshtein para calcular la distancia entre dos conjuntos de coordenadas xy?

Question

He estado tratando de trabajar en la modificación de una función Levenshtein Distancia para que pueda encontrar la distancia entre dos líneas o conjuntos de coordenadas XY (en otras palabras, cómo similares o diferentes son las líneas, no su distancia geométrica) . Estoy corriendo en algunos problemas sin embargo. Yo entiendo cómo se toma el valor anterior para obtener el costo borrado, y el otro a la izquierda para conseguir Además, durante la sustitución, pero estoy tratando de utilizar la distancia euchlidian, y no está funcionando para mí.

Si usted podría señalar lo que estoy haciendo mal, que sería impresionante.

Este es el código correspondiente en 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]);
        }
    }
}

Resultado de muestra:

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

Si he entendido bien su pregunta, entonces usted debe eliminar por completo el código para calcular la distancia euclidiana entre dos puntos!

En primer lugar, deseo reiterar su pregunta:

Hay dos conjuntos de puntos, por ejemplo.

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

Intenta calcular una distancia levenshtein entre esos dos conjuntos. Sustituyes "letras" con "puntos".

Hasta este punto, tiene sentido. Basta con sustituir las "letras" en el algoritmo levenshtein con puntos y ya está!

Pero ha cometido un error: El algoritmo original de Levenshtein no calcula las distancias entre dos letras , como por ejemplo distancia (a, b) = 1 o la distancia (a, d) = 3.

Se ha intentado extender el algoritmo con una cosa así (función de distancia euclidiana () usando). Pero algoritmo levenshtein no es para este tipo de cosas. Y si usted tiene una mirada cercana a ella, se verá, que no va a funcionar (los valores de la matriz tienen un significado, y cada iteración del bucle utiliza los valores en la matriz que se calcula en una iteración anterior).

Levenshtein distancia es una distancia de edición, no hay distancia geométrica. Se ha intentado modificar, de manera que se calcula una mezcla de edición y la distancia geométrica. Esta mezcla no tiene sentido, es inútil y el mal, en mi humilde opinión.

Conclusión

Para calcular el levenshtein distancia de dos conjuntos de coordenadas xy , se deben sustituir los euclidianDistance () con una simple comparación de igualdad (a[0]==b[0] && a[1]==b[1]).

A continuación, el algoritmo levenshtein le dará una "distancia de edición".

Answer 2

¿No sería más inteligente para utilizar geometría para calcular la distancia entre dos líneas? O hay una razón específica que no desea usar eso.

Desde dos líneas siempre tienen un punto de intersección, a menos que estén paralelos (editar, gracias) , que es fácil de calcular la distancia más pequeña: eso es 0 o Insertar un poco de matemática, lo que puede se encuentran en Google

Answer 3

No entiendo por qué se usaría para este Levenshtein, parece que se podrían obtener resultados mucho mejores a partir de cálculos simples.

• Para encontrar la diferencia en el ángulo de las líneas, usted podría simplemente encontrar el ángulo para cada línea (arctg ((x_1-x_2) / (y1-y_2))) y restar ellos.
• Para encontrar la distancia media de las líneas, usted podría simplemente utilizar la fórmula de la distancia con el primer punto de cada línea y el segundo punto de cada línea y promediar las distancias entre sí.

Aparte de eso (a menos que sus líneas son en 3D), no hay nada más que realmente "comparar" con.

Quizás he entendido mal. ¿Está buscando para comparar los valores de cadena para las líneas?