Изучение разностного алгоритма Майерса: часть 1

В данной статье предоставляется изучение разностного алгоритма Майерса

•    Скачать двоичные файлы учебного приложения - 23.8 Кб
•    Скачать исходники двоичного приложения - 35.5 Кб

Оглавление

• Введение
• Краткая информация
• Определения
• Файл A и файл B
• Кратчайший скрипт редактирования (SES)
• Длиннейшая общая подпоследовательность (LCS)
• Примеры последовательностей
• График редактирования
• Змеи
• k линии
• d кривые
• Жадный алгоритм
• График редактирования
• Алгоритм
• Пример при d = 3
• Реализация
• Решение
• Вывод

Введение

Данная статья изучает базовый жадный разностный алгоритм, описанный Евгением У. Майерсом  в своей статье "Разностный алгоритм O(ND) и его варианты". Она была опубликована в журнале "Алгоритмика" в ноябре 1986. В своей статье Майерс расширяет базовый алгоритм "измельчением линейного пространства". Это требует полного понимания базового алгоритма, описанного в данной статье. Он разобран в части второй данной темы.

В загрузках доступно учебное приложение. Оно отображает графическое представление разных стадий алгоритма. Рекомендуется использовать приложение во время чтения статьи, чтобы понять алгоритм. Графики в статье являются снимками экрана приложения.

Данная статья использует посимвольную разность, но алгоритм может применяться для любого типа данных, имеющего оператор равенства.

Краткая информация

Я начал изучение разностных алгоритмов для конкурса, проведенного Code Project, в августе 2009. Чем больше я узнавал об алгоритмах Майерса, тем красивей они мне казались. Я рекомендую подробно их изучить. Бесспорно, мне понравилось изучать и реализовывать их.

Я написал эту статью, потому что на базе исходной статьи на понимание и реализацию алгоритма мне потребовалась неделя. Вы можете прочитать эту статью меньше чем за час и в общих чертах понять работу Майерса. Я попытался объяснить основные принципы и теорию без дачи доказательств. Они есть в статье Майерса.

Определения

Файл A и файл B

Разностный алгоритм принимает два файла на вход. Первый, обычно более ранний, - файл A, а второй - файл B. Алгоритм генерирует инструкции для превращения файла A в файл B.

Кратчайший скрипт редактирования (SES)

Алгоритм находит кратчайший скрипт редактирования, превращающий файл A в файл B. SES содержит лишь два типа команд: удаления из файла A и вставки в файл B.

Длиннейшая общая подпоследовательность (LCS)

Отыскание SES равноценно отысканию длиннейшей общей подпоследовательности двух файлов. LCS – длиннейший список символов, который может быть сгенерирован из обоих файлов путем удаления ряда символов. LCS отличается от длиннейшей общей подстроки, которая должна быть непрерывной.

Для любых двух файлов может быть несколько LCS. Например, заданы последовательности "ABC" и "ACB", есть две LCS длиной 2: "AB" и "AC". LCS непосредственно соответствует SES, поэтому действительно может быть несколько SES одинаковой длины для любых двух файлов. Алгоритм возвращает первый же найденный LCS / SES, который поэтому может не быть уникальным.

Примеры последовательностей

Эта статья использует тот же пример, что и статья Майерса. Файл A содержит "ABCABBA", и файл B содержит "CBABAC". Они представлены в виде двух символьных массивов: A[] и B[].

Длина A[] равна N, а длина B[] равна M.

График редактирования

Это график редактирования для примера. Массив A расположен вдоль оси x вверху. Массив B расположен вдоль оси y, читаясь сверху вниз.

 

Рисунок 1.: График редактирования примера

Решение – кратчайший путь от левого верхнего угла (0, 0) до правого нижнего угла (7, 6).

Всегда можно сдвинуть один символ горизонтально или вертикально. Горизонтальный сдвиг (вправо) означает удаление из файла A, а вертикальный сдвиг (вниз) означает вставку в файл B. Если есть совпадающий символ, то также можно сдвинуть по диагонали, заканчивая в совпадении.

(Решением являются трассировка(и)/ Решением являются трассировки?, включающие в себя большинство диагоналей. LCS является диагональю в трассировке, а SES является горизонтальными и вертикальными сдвигами в ней. Для примера, LCS имеет длину 4 символа, а SES имеет длину 5 различий.)

Змеи

Статья слегка неоднозначна, но я понимаю «змею» как одиночное удаление или вставку, за которым следует ноль или больше диагоналей.

Например, есть две змеи, начинающиеся в верхнем левом углу (0, 0). Одна идет прямо до (1, 0) и останавливается. Другая опускается до (0, 1) и останавливается. Следующая змея от (0, 1) опускается до (0, 2) и затем идет по диагонали до (2, 4). Эти точки называются начальной, средней и конечной соответственно.

k линии

Можно строить линии, начинающиеся в точках на оси x и оси y и параллельные диагоналям. Они называются k линиями и несут пользу. Линия, начинающаяся в (0, 0), определяется как k = 0. k увеличивается линейно вправо и уменьшается сверху вниз. То есть k линия через (1, 0) имеет k = 1, а k линия через (0, 1) имеет k = -1.

По сути, эти линии представлены уравнением: y = x - k. Это тоже полезно, так как надо хранить лишь значение x для конкретной точки на заданной k линии, чтобы вычислить значение y.

d кривые

Разность представлена горизонтальным или вертикальным сдвигом на графике редактирования. Непрерывная серия змей имеет значение d, являющееся количеством разностей в данной трассировке, независимое от количества диагоналей в ней. Можно создать d кривую, соединяющую конечные точки всех трассировок с заданным значением d.

Жадный алгоритм

Разберем базовый жадный алгоритм без измельчения линейного пространства.

Рисунок 2.  Опережающее жадное решение

График редактирования

График выглядит пугающе, но разберем его по порядку.
•    k линии: Коричневые линии - k линии для нечетных значений k. Желтые линии - k линии для четных значений k.
•    змеи: Синие линии - змеи. Красные змеи показывают трассировку решения.
•    d кривые: Светло-голубые линии – кривые разностей. Например, три конечные точки на линии, помеченной '2', все имеют ровно 2 горизонтальных или вертикальных сдвига.