algorithm - textos - Distancia entre Hamming y Levenshtein

levenshtein algorithm java

Question

Para el problema en el que estoy trabajando, encontrar distancias entre dos secuencias para determinar su similitud, el orden de las secuencias es muy importante. Sin embargo, las secuencias que tengo no son todas de la misma longitud, así que relleno cualquier cadena deficiente con puntos vacíos de manera que ambas secuencias tengan la misma longitud para satisfacer el requisito de distancia de Hamming. ¿Hay algún problema importante conmigo haciendo esto, ya que lo único que me importa es el número de transposiciones (no inserciones o eliminaciones como lo hace Levenshtein)?

Descubrí que la distancia de Hamming es mucho, mucho más rápida que Levenshtein como una métrica de distancia para secuencias de mayor longitud. ¿Cuándo se debe usar la distancia de Levenshtein (o los derivados de la distancia de Levenshtein) en lugar de la distancia mucho más económica de Hamming? La distancia de Hamming puede considerarse el límite superior para posibles distancias de Levenshtein entre dos secuencias, por lo que si estoy comparando las dos secuencias para una métrica de similaridad ordenada en lugar del número mínimo absoluto de movimientos para hacer coincidir las secuencias, no hay una aparente razón por la que elegir Levenshtein sobre Hamming como una métrica, ¿verdad?

Answer 1

Esa pregunta realmente depende de los tipos de secuencias que coincida y el resultado que desee.

Si no es un problema que "1234567890" y "0123456789" se consideran totalmente diferentes, de hecho, la distancia de Hamming está bien.