[Algorithm] Расстояние Хэмминг против Левенштейна


Answers

Question

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

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