Расстояние хэминга против Левенштейна расстояние

Question

Для проблемы, над которой я работаю, найти расстояния между двумя последовательностями для определения их сходства, порядок последовательности очень важен. Тем не менее, последовательности, которые у меня есть, не являются одинаковой длиной, поэтому я накладываю любые дефицитные строки с пустыми точками, так что обе последовательности имеют одинаковую длину, чтобы удовлетворить требование расстояния в хмею. Есть ли какая -либо серьезная проблема со мной, так как все, что меня волнует, это количество транспозиций (не вставки или удаления, такие как Levenshtein)?

Я обнаружил, что расстояние в хэмминге намного, намного быстрее, чем Левенштейн в качестве метрики расстояния для последовательностей более длительной длины. Когда следует использовать расстояние Левенштейна (или производные расстояния Левенштейна) вместо гораздо более дешевого расстояния хэмминга? Расстояние хэмминга можно считать верхней границей для возможных расстояний Левенштейна между двумя последовательностями, поэтому, если я сравниваю две последовательности для метрики сходства, смещенного в порядке, а не абсолютного минимального количества движений, чтобы соответствовать последовательностям, нет очевидного Причина, по которой я могу выбрать Levenshtein из -за хэмминга в качестве метрики, не так ли?

Answer 1

Этот вопрос действительно зависит от типов последовательностей, которые вы соответствуете, и какой результат вы хотите.

Если это не проблема, что «1234567890» и «0123456789» считаются совершенно разными, действительно, расстояние в хмею - это нормально.

Answer 2

В дополнение к правильному ответу Йохана, заполнение может быть проблематичной.

Например, когда вы сравниваете 123 к 123456 Это по -другому, если вы прокладываете либо в конце строки, либо в начале строки. Сходство ___123 с 123456 равно 0, но сходство 123___ с 123456 3.