Энергия ошибки

[lorovsky_anonymous]

Дано верное слово и ошибочное. Известен ли алгоритм с помощью которого можно посчитать сколько должно быть пропусков, лишних букв и замен чтобы верное слово превратилось в ошибочное и чтобы сумма таких мутаций была минимальной? Естественно тупой перебор всех мутаций верного слова не интересует.

[Munin]

Это называется "расстояние Хэмминга" (по Хэммингу, Hamming distance). Гуглите.

[venco]

Расстояние Хэмминга - это без вставок, а вам нужно расстояние Левенштейна (Levenshtein distance).

[vpb]

Как говорит Википедь, расстояние Левенштейна может быть найдено за квадратичное время. Статью из википедии я не смотрел, алгоритма соответствующего не знаю. Но из общих соображений мне кажется, что должен существовать какой-то менее сложный алгоритм, скажем сложности $O(N(d+1))$, где $N$ --- длина слова, а $d$ --- расстояние.

Квадратичные алгоритмы они хоть и полиномиальные, но все же квадратичная сложность --- это слишком долго. Для такого очевидного практического применения, как анализ геномов, квадратичные алгоритмы оказались бы неосуществимы. (Если, скажем, надо сравнить два генома порядка по $10^8$ оснований (не знаю сколько там на самом деле...), то потребовалось бы время порядка $10^{16}$, что нереалистично.

Поэтому я думаю, что в исследование этой задачи уже наверняка вложены немалые усилия, надо только порыть литературу.

[Утундрий]

Курить после слова "память".

[mihaild]

vpb в сообщении #1419519 писал(а):

Но из общих соображений мне кажется, что должен существовать какой-то менее сложный алгоритм, скажем сложности $O(N(d+1))$, где $N$ --- длина слова, а $d$ --- расстояние.

Да понятно какой - т.к. между словами, отличающиесемя по длине больше чем на $d$, расстояние больше $d$, достаточно в динамике по префиксу первого слова учитывать только $2d + 1$ вариантов префикса второго.

[lorovsky_anonymous]

venco в сообщении #1419493 писал(а):

расстояние Левенштейна (Levenshtein distance).

Кажется то что нужно. Спасибо.