Изучение разностного алгоритма Майерса: часть 2
ОГЛАВЛЕНИЕ
Данная статья изучает детализацию линейного пространства, описанную Евгением У. Майерсом в его статье "Разностный алгоритм O(ND) и его вариации".
• Скачать двоичные файлы учебного приложения - 23.89 Кб
• Скачать исходники учебного приложения - 35.52 Кб
Введение
Это вторая часть статьи о разностном алгоритме Майерса, требующая понимания базового жадного алгоритма, описанного в части I.
В загрузках имеется учебное приложение. Оно отображает графическое представление разных стадий алгоритма. Рекомендуется использовать его во время чтения данной статьи, чтобы лучше понять алгоритм. Диаграммы в этой статье являются снимками экрана приложения.
Обратный алгоритм
Базовый алгоритм также может работать обратно, то есть работать от (N,M) обратно до (0, 0). Единственное отличие заключается в том, что сдвиги начинаются в удалении / вставке / совпадении, а не кончаются в них. Ниже показано решение примера, но работающее обратно.
Рисунок 1: Обратное решение
Как видно из диаграммы, решение отличается от первого, сгенерированного путем работы вперед, но имеет такие же длины LCS и SES. Это совершенно правильно, потому что вообще может быть много эквивалентных решений, и алгоритм просто выбирает первое найденное решение.
Дельта: Поскольку длины последовательностей A и B могут различаться, k линии прямого и обратного алгоритмов могут различаться. Полезно выделить эту разницу в переменную delta = N - M. В примере N = 7 и M = 6, что дает дельта = 1. Это смещение от прямых k линий до обратных k линий. Можно сказать, что прямые пути сконцентрированы вокруг k = 0, а обратные пути сконцентрированы вокруг k = delta.
Средняя змея
Совпадение
Можно одновременно прогнать прямой и обратный алгоритмы для последовательных значений D. При каком-то значении D две змеи совпадут на какой-то k линии. Статья доказывает, что одна из этих змей является частью решения. Так как она будет находиться где-то посередине, она называется средней змеей.
Средняя змея для примера выделена розовым на этой диаграмме:
Рисунок 2: Средняя змея
Средняя змея полезна, потому что делит задачу на две части, которые затем можно решить отдельно и рекурсивно.
Средняя змея линейна в пространстве, потому что только последние V векторов должны храниться, давая O (D). Пока этот линейный алгоритм все еще является O ((N+M) D).
Помогает то, что средняя змея должна быть найдена с D, равным половине D из прямого и обратного алгоритмов. Отсюда следует, что по мере того как D возрастает, требуемое время достигает половины времени, требуемого базовым алгоритмам.
Ниже приведен имеющийся пока псевдокод:
for d = 0 to ( N + M + 1 ) / 2
{
for k = -d to d step 2
{
вычислить самый дальний прямой и обратный пути достижения
если есть совпадение, имеем среднюю змею
}
}
Нечетная и четная дельты
Каждая разность – горизонтальное удаление или вертикальная вставка – является сдвигом от одной k линии к ее соседней линии. Поскольку дельта является разностью между серединами прямого и обратного алгоритмов, известно, какие значения d надо проверять на среднюю змею.
Для нечетной дельты надо искать совпадение прямых путей с разностями d и обратных путей с разностями d - 1.
Эта диаграмма показывает, что для дельты = 3 совпадение происходит, когда прямая d равна 2 и обратная d равна 1:
Рисунок 3: Нечетная дельта
Аналогично для четной дельты совпадения будут, когда прямой и обратный пути имеют одинаковое число разностей.
Следующая диаграмма показывает, что для дельта = 2 совпадение происходит, когда прямая и обратная разности равны 2:
Рисунок 4: Четная дельта
Алгоритм
Ниже приведен полный псевдокод для отыскания средней змеи:
delta = N - M
for d = 0 to ( N + M + 1 ) / 2
{
for k = -d to d step 2
{
вычислить самый дальний прямой путь достижения на линии k
если delta нечетна и ( k >= delta - ( d - 1 ) и k <= delta + ( d - 1 ) )
если совпадение с обратным [ d - 1 ] на линии k
=> найдена средняя змея и SES длины 2D - 1
}
for k = -d to d step 2
{
вычислить самый дальний обратный путь достижения на линии k
если дельта четна и (k >= -d - delta и k <= d - delta)
если совпадение с прямым [ d ] на линии k
=> найдена средняя змея и SES длины 2D
}
}
Замечание: Граничные проверки k служат для исключения невозможных совпадений.
Рекурсивное решение
Алгоритм
Надо обернуть алгоритм средней змеи в рекурсивный метод. По сути, надо найти среднюю змею, а затем решить прямоугольники, оставшиеся вверху слева и внизу справа. Есть пара пограничных случаев, объясненных далее. было добавлено решение для 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 лет после его публикации.