Изучение разностного алгоритма Майерса: часть 2 - Рекурсивное решение

Рекурсивное решение

Алгоритм

Надо обернуть алгоритм средней змеи в рекурсивный метод. По сути, надо найти среднюю змею, а затем решить прямоугольники, оставшиеся вверху слева и внизу справа. Есть пара пограничных случаев, объясненных далее. было добавлено решение для SES, поскольку статья оставляет это ' в качестве упражнения' и только находит LCS.

Сравнить( A, N, B, M )
{
  если ( M == 0 && N > 0 ) добавить N удалений к SES
  если ( N == 0 && M > 0 ) добавить M вставок к SES
  если ( N == 0 || M == 0 ) вернуться
  
  вычислить среднюю змею
  
  допустим, она находится от ( x, y ) до ( u, v ) с суммарными разностями D
  
  если ( D > 1 )
  {
    Сравнить( A[ 1 .. x ], x, B[ 1 .. y ], y ) // верхний левый
    
    Добавить среднюю змею к результатам
    
    Сравнить( A[ u + 1 .. N ], N - u, B[ v + 1 .. M ], M - v ) // нижний правый
  }
  иначе если ( D == 1 ) // должна быть прямая змея
  {
    Добавить диагональ d = 0 к результатам
    Добавить среднюю змею к результатам
  }
  иначе если ( D == 0 ) // должна быть обратная змея
  {
    Добавить среднюю змею к результатам
  }
}

Общий случай понятен. Изучим два пограничных случая.

Пограничный случай: D == 0

Если алгоритм средней змеи находит решение с D = 0, то две последовательности одинаковы. Это означает, что дельта равна нулю, то есть четна. Следовательно, средняя змея является обратной змеей, которая просто совпадает (диагонали). Остается лишь добавить эту змею к результатам.

Диаграмма ниже показывает общий вид данного пограничного случая:

Рисунок 5: Решение с D = 0

Пограничный случай: D == 1

Если алгоритм средней змеи находит решение с D = 1, то есть ровно одна вставка или удаление. Это значит, что дельта равна 1 или -1, то есть нечетна, а значит, средняя змея является прямой змеей.

Можно закончить решение для данного случая, вычислив диагональ d = 0 и добавив ее к результатам вместе со средней змеей.

Диаграмма ниже показывает общий вид данного пограничного случая:

Рисунок 6: Решение с D = 1

Вывод

Алгоритм средней змеи является шедевром искусства. Он также допускает описанное рекурсивное решение и делает алгоритм параллельным. Его реализация оставлена в качестве упражнения.

Есть другие очевидные оптимизации, меняющие место, более дешевое в современных компьютерах, на выигрыш во времени. Однако данный алгоритм так хорошо сбалансирован, что все еще используется *nix программой diff спустя более 20 лет после его публикации.