Алгоритм быстрого редактирования расстояния

Проблема: Я знаю тривиальное редактирование расстояния DP для формулировки и вычисления в O (mn) для 2 строк размером n и m соответственно. Но недавно я узнал, что если нам нужно только вычислить минимальное значение расстояния редактирования f, и оно ограничено | f |<= s, то мы можем вычислить его за O (min (m, n) + s ^ 2) или O (s * min (m, n)) [wikipedia] время.

Пожалуйста, объясните формулировку ДП, стоящую за этим, если это на основе ДП, или объясните алгоритм

Посмотрите на improved algorithm раздел
ссылка на сайт: http://en.wikipedia.org/wiki/Edit_distance .

еще одна ссылка об улучшенном алгоритме УККОНЕНА http://www.berghel.net/publications/asm/asm.php

Заранее спасибо.

3

Решение

Вы можете рассчитать расстояние редактирования за O (мин (n, м) * с), используя следующую простую идею:

Рассмотрим i-ую строку в DP-таблице.

Итак, если мы знаем, что ответ <= s, то нас вклинивают в ячейки с координатами (i, i — s), (i, i — s + 1), …, (i, i + s). Потому что в других клетках ответ строго больше, чем s.

Например, предположим, что мы знаем, что редактируем расстояние между «abacaba» и «baadba» меньше 3.

DP-таблица для этой строки

Таким образом, мы можем пропустить эритроциты, потому что они имеют значение больше, чем s.

Асимптотика алгоритма O (min (n, m) * s), поскольку мы вычисляем s клеток слева и справа от главной диагонали.

10

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector