Изучение разностного алгоритма Майерса: часть 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.