Быстрый алгоритм дистанции редактирования

Question

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

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

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

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

Спасибо заранее.

Answer 1

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

Рассмотрим I-й строки в DP-таблице.

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

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

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

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