Modificando uma função de distância de Levenshtein para calcular a distância entre dois conjuntos de coordenadas XY?

Question

Eu tenho tentado trabalhar para modificar uma função de distância de Levenshtein para que ela possa encontrar a distância entre duas linhas ou conjuntos de coordenadas XY (em outras palavras, quão semelhantes ou diferentes são as linhas, não sua distância geométrica). Estou tendo alguns problemas. Entendo como você aceita o valor acima para obter o custo da exclusão e o da esquerda para obter adição, mas durante a substituição, estou tentando usar a distância euchlidiana e não está funcionando para mim.

Se você pudesse apontar o que estou fazendo de errado, isso seria incrível.

Aqui está o código relevante em 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]);
        }
    }
}

Saída de amostra:

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

Se eu entendi sua pergunta corretamente, você deve remover completamente o código para calcular a distância euclidiana entre dois pontos!

Primeiro, deixe -me reafirmar sua pergunta:

Você tem dois conjuntos de pontos, por exemplo

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

Você tenta calcular uma distância de Levenshtein entre esses dois conjuntos. Você substitui "letras" por "pontos".

Até este ponto, faz sentido. Basta substituir as "letras" no algoritmo Levenshtein por pontos e você terminou!

Mas você cometeu um erro: o algoritmo original de Levenshtein não calcula distâncias entre duas letras, como por exemplo, distância (a, b) = 1 ou distância (a, d) = 3.

Você tentou estender o algoritmo com uma coisa dessas (usando a função euclidandandistance (). Mas o algoritmo Levenshtein não se destina a essas coisas. E se você der uma olhada de perto, verá que ele não funcionará (os valores na matriz têm um significado e cada iteração de loop usa valores na matriz que foram calculados em uma iteração anterior).

A distância de Levenshtein é uma distância de edição, sem distância geométrica. Você tentou alterá -lo, para que ele calcule uma mistura de edição e distância geométrica. Essa mistura não faz sentido, é inútil e errado, IMHO.

Conclusão

Para calcular o Distância de Levenshtein de dois conjuntos de coordenadas XY, você deve substituir sua euclidiandistance () por uma comparação simples de igualdade (a[0]==b[0] && a[1]==b[1]).

Em seguida, o algoritmo Levenshtein lhe dará uma "distância de edição".

Answer 2

Não seria mais inteligente usar geometria para calcular a distância entre duas linhas? Ou existe um motivo específico que você não gostaria de usar isso.

Como duas linhas sempre têm um ponto de interseção, a menos que sejam paralelas (Editar, obrigado), é fácil calcular a menor distância: isso é 0 ou Insira alguma matemática, que pode ser encontrada no Google!

Answer 3

Não entendo por que você usaria Levenshtein para isso, parece que você obteria resultados muito melhores de cálculos simples.

• Para encontrar a diferença no ângulo das linhas, você pode simplesmente encontrar o ângulo para cada linha (Arctan ((x_1-x2)/(y_1-y_2))) e subtrai-los.
• Para encontrar a distância média das linhas, você pode simplesmente usar a fórmula de distância com o primeiro ponto de cada linha e o segundo ponto de cada linha e calcular essas distâncias juntas.

Fora isso (a menos que suas linhas estejam em 3D), não há mais nada para "compará -las".

Talvez eu tenha entendido mal. Você está procurando comparar os valores da string para as linhas?