Distancia de Hamming vs Levenshtein Distancia

Question

Para el problema que estoy trabajando, la búsqueda de distancias entre dos secuencias para determinar su similitud, orden de la secuencia es muy importante. Sin embargo, las secuencias que tengo no son todos de la misma longitud, por lo que la almohadilla de I cualquier cadena deficientes con puntos vacíos de tal manera que ambas secuencias son de la misma longitud con el fin de satisfacer el requisito de distancia de Hamming. ¿Hay algún problema importante con que yo haga esto, ya que todo lo que importa es el número de transposiciones (no inserciones o deleciones como Levenshtein hace)?

He encontrado que la distancia de Hamming es mucho, mucho más rápido que Levenshtein como una distancia métrica para las secuencias de mayor longitud. ¿Cuándo se debe utilizar Levenshtein distancia (o derivados de la distancia Levenshtein) en lugar de la distancia de Hamming mucho más barato? Distancia de Hamming puede ser considerado como el límite superior para posibles distancias levenshtein entre dos secuencias, por lo que si estoy comparando las dos secuencias para una similitud orden sesgada métrica en lugar del número mínimo absoluto de movimientos para que coincida con las secuencias, no hay una aparente razón para elegir Levenshtein sobre Hamming como métrica, ¿verdad?

Answer 1

Esa pregunta realmente depende de los tipos de secuencias que son coincidentes, y qué resultado que desea.

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

Answer 2

Además de la respuesta Johan derecha, el relleno puede ser problemático.

Por ejemplo, cuando se compara a 123 123456 es diferente si la almohadilla ya sea al final de la cadena o en el inicio de la cadena. La similitud de ___123 con 123456 es 0, pero la similitud de 123___ con 123456 es 3.