Определение последовательности правок, которая дает расстояние Левенштейна

Question

Я делаю некоторую работу, используя расстояние Левенштейна (редактирование), используя динамическое программирование. Я думаю, что понимаю алгоритм Вагнера-Фишера, чтобы сделать это эффективно. Тем не менее, не похоже, что алгоритм является конструктивным. Если я вычислю, что расстояние редактирования между двумя строками составляет, например, 10, то я также хотел бы определить конкретную последовательность из 10 правок, которая превращает одно в другое. Это тоже можно сделать эффективно? Если так, то как?

Answer 1

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

Чтобы найти правки, вы должны передать полученную матрицу в обратном направлении. Начать с ячейки результата, (m,n),

• Если значение ячейки (m-1, n-1) То же самое, чем символы в этих местах одинаковы, редактирование не требуется.
• Если значение ячейки (m-1, n-1) меньше, чем найти ячейку (и) из{(m-1, n-1), (m-1, n), (m, n-1)} с наименьшим значением. Положение ячейки (я) с наименьшим значением определяет, выполняется ли замена, удаление или вставка. Если больше ячеек с наименьшим значением, то большее количество последовательностей правок может дать минимальное расстояние. Если вам нужна только одна последовательность, выберите любую из них.

Сделайте ту же проверку, пока путь не достигнет ячейки (0,0),

Путь проверок определяет правки, выполненные в обратном порядке.

Answer 2

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

Вот как я это реализовал, и он отлично работает:

1. Начать в клетке (m, n)
2. Проверьте ячейки (m - 1, n - 1), (m - 1, n) а также (m, n - 1) и определите, какой из них содержит наименьшее значение.
   • Если это (m - 1, n) тогда у вас есть удаление. декремент m одним.
   • Если это (m, n - 1) тогда у вас есть вставка. декремент n одним.
   • Если это (m - 1, n - 1) тогда у вас есть либо
     • замена, если (m - 1, n - 1) < (m, n), декремент m а также n одним.
     • нет операции, если (m - 1, n - 1) == (m, n), декремент m а также n одним.

Если какой-либо поиск ячейки вызовет отрицательные индексы, просто пропустите их. Если вы приедете в камеру (0, 0) все готово Вы создадите список правок в обратном порядке.