Hamming-Distanz vs.Die Levenshtein-Distanz

Question

Für das problem, an dem ich arbeite, finden Sie Entfernungen zwischen zwei Sequenzen zu ermitteln, Ihre ähnlichkeit, die Reihenfolge der Sequenz ist sehr wichtig.Aber die Sequenzen, die ich habe sind nicht alle die gleiche Länge, so dass ich pad fehlerhafter Zeichenfolgen mit leeren Punkte, so dass beide Sequenzen die gleiche Länge um den Hamming-Abstand Anforderung.Gibt es irgendein problem mit mir, dies zu tun, da alle ich Pflege über sind die Anzahl der Transpositionen (nicht Einfügungen oder Löschungen wie die Levenshtein-tut)?

Ich habe festgestellt, dass Hamming-Distanz ist viel, viel schneller, als Levenshtein-als Distanz-Metrik für die Sequenzen von mehr Länge.Wann sollte man verwenden Sie die Levenshtein-Distanz (oder Derivate des Levenshtein-Distanz) statt, die viel billiger Hamming-Distanz?Hamming-Distanz kann als die Obere Grenze für die mögliche Levenshtein-Abstand zwischen zwei Sequenzen, so dass, wenn ich den Vergleich der beiden Sequenzen für eine um-biased ähnlichkeit Metrik nicht die absolute minimale Anzahl von Zügen zu entsprechen, die Sequenzen haben, gibt es keinen ersichtlichen Grund für mich, warum ich die Levenshtein-über Hamming als eine Metrik, die ist es?

Answer 1

Diese Frage hängt wirklich davon ab, die Arten von Sequenzen, die Sie suchen, und was für ein Ergebnis Sie wollen.

Wenn es nicht ein problem, dass "1234567890" und "0123456789" sind als völlig verschiedene, ja Hamming-Distanz ist in Ordnung.

Answer 2

Zusätzlich zur richtigen Antwort von Johan kann die Polsterung problematisch sein.

Zum Beispiel, wenn Sie vergleichen 123 zu 123456 Es ist anders, wenn Sie entweder am Ende der Saite oder am Start der Zeichenfolge polieren. Die Ähnlichkeit von ___123 mit 123456 ist 0, aber die Ähnlichkeit von 123___ mit 123456 ist 3.