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

Written on 05 Июля 2013.

Файл 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 горизонтальных или вертикальных сдвига.

Алгоритм

Алгоритм итеративный. Он вычисляет самые дальние пути достижения на каждой k линии для очередного d. Решение найдено, когда путь достигает правого нижнего угла. Это гарантированно является LCS / SES, так как уже были вычислены варианты с меньшим d. Максимальное значение d наблюдается при отсутствии совпадений, которое является N удалений + M вставок.

for ( int d = 0 ; d <= N + M ; d++ )

Внутри этого цикла мы должны найти самый дальний путь достижения для каждой k линии. Для заданного d единственные k линии, которые могут быть достигнуты, лежат в диапазоне [-d .. +d]. k = -d возможно, когда все сдвиги направлены вниз, и k = +d, когда сдвиги направлены вправо. Важное замечание по реализации заключается в том, что конечные точки для четного d расположены на четных k линиях, и наоборот. Поэтому внутренний цикл такой:

for ( int k = -d ; k <= d ; k += 2 )

Пропущенный кусок – способ отыскания самого дальнего пути достижения на заданной k линии.
Чтобы попасть на линию k, надо сдвинуться вниз от линии k + 1 или вправо от линии k - 1. Если мы сохраним самые дальние пути достижения от предыдущего d, то сможем выбрать сдвиг, который перебросит нас дальше всего вдоль линии k. Два пограничных случая: когда k = -d – в случае чего можно лишь двигаться вниз, и k = +d – когда можно двигаться лишь вправо.

Пример при d = 3

Разберем пример для d = 3, что значит k линии [-3, -1, 1, 3]. Для помощи конечные точки змей переписаны в виды таблицы ниже:

Рисунок 3. Таблица конечных точек

k = -3: Нельзя добраться до линии k = -4 при d = 2, поэтому надо сдвинуться вниз от линии k = -2. Сохраненный результат от предыдущего d = 2 дает начальную точку (2, 4). Сдвиг вниз дает среднюю точку (2, 5), и получаем диагональ, приводящую к (3, 6).

k = -1: Здесь есть два варианта. Можно двигаться вправо от k = -2 или вниз от k = 0. Результаты для предыдущего d = 2 гласят, что предыдущая точка на k = -2 есть (2, 4), а предыдущая точка на k = 0 есть (2, 2). Сдвиг вправо от k = -2 приводит к (3, 4), а сдвиг вниз от k = 0 приводит к (2, 3). Поэтому выбираем k = -2, так как это перебросит нас дальше вдоль линии k = -1. Снова получаем диагональ, поэтому змея является (2, 4) -> (3, 4) -> (4, 5).

k = 1: Снова есть два варианта. Можно двигаться вправо от k = 0 или вниз от k = 2. Предыдущими конечными точками являются (2, 2) и (3, 1), которые обе приводят к (3, 2). Произвольно решаем начать из точки с большим значением x, которая с диагональю дает змею (3, 1) -> (3, 2) -> (5, 4).

k = 3: Это другой пограничный случай. Линия k = 4 невозможна с d = 2, поэтому двигаемся вправо от k = 2. Предыдущий результат для k = 2 есть (3, 1), поэтому сдвиг вправо приводит к (4, 1). Снова получаем диагональ, дающую конечную точку в (5, 2).

Реализация

Как это реализовать? Есть два цикла, нужна структура данных.

Следует отметить, что решения для d(n) зависят только от решений для d(n - 1). Также помните, что для четных значений d мы находим конечные точки на четных k линиях, зависящих только от предыдущих конечных точек, которые все находятся на нечетных k линиях. Аналогично для нечетных значений d.

Поэтому используется массив по имени V с индексом k и координатой x конечной точки в качестве значения. Не надо хранить координату y, так как она вычисляется по заданным x и k: y = x - k. Также для заданного d, k находится в диапазоне [-d … d], являющи(е)хся индексами в V и ограничивающих(е) его размер.

Это хорошо работает, поскольку, когда d – четный, то конечные точки для четных индексов k вычисляются с использованием нечетных значений k, постоянных для этой итерации d. Аналогично для нечетных значений d.

Решение, двигаться вниз или вправо, чтобы дойти до заданной k линии, можно записать в виде булева выражения:

bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );

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

Также нужна заглушка для d = 0, поэтому задаем V [ 1 ] = 0. Это означает точку на линии k = 1, где x = 0. Следовательно, это точка (0, -1). Мы гарантированно двигаемся вниз от этой точки, дойдя до (0, 0), как требуется.

Основная реализация приведена ниже:

V[ 1 ] = 0;

for ( int d = 0 ; d <= N + M ; d++ )
{
  for ( int k = -d ; k <= d ; k += 2 )
  {
    // вниз или вправо?
    bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );

    int kPrev = down ? k + 1 : k - 1;

    // начальная точка
    int xStart = V[ kPrev ];
    int yStart = xStart - kPrev;

    // средняя точка
    int xMid = down ? xStart : xStart + 1;
    int yMid = xMid - k;

    // конечная точка
    int xEnd = xMid;
    int yEnd = yMid;

    // идти по диагонали
    int snake = 0;
    while ( xEnd < N && yEnd < M && A[ xEnd ] == B[ yEnd ] ) { xEnd++; yEnd++; snake++; }

    // сохранить конечную точку
    V[ k ] = xEnd;

    // проверить на решение
    if ( xEnd >= N && yEnd >= M ) /* решение найдено */
  }
}

Решение

Код выше находит первую змею, достигающую конца обеих последовательностей. Однако данные в V хранят лишь самую последнюю конечную точку для каждой k линии. Отыскание всех змей, ведущих к решению, требуют фиксации состояния V после каждой итерации d и затем движения обратно от dsolution до 0.

IList<V> Vs; // сохраненный V's проиндексирован на d
IList<Snake> snakes; // список для хранения решения

POINT p = new POINT( N, M ); // начинаем с конца

for ( int d = vs.Count - 1 ; p.X > 0 || p.Y > 0 ; d-- )
{
  var V = Vs[ d ];

  int k = p.X - p.Y;

  // конечная точка находится в V
  int xEnd = V[ k ];
  int yEnd = x - k;

  // вниз или вправо?
  bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );

  int kPrev = down ? k + 1 : k - 1;

  // начальная точка
  int xStart = V[ kPrev ];
  int yStart = xStart - kPrev;

  // средняя точка
  int xMid = down ? xStart : xStart + 1;
  int yMid = xMid - k;

  snakes.Insert( 0, new Snake( /* начальная, средняя и конечная точки */ ) );

  p.X = xStart;
  p.Y = yStart;
}

Следует отметить, что приведенный «жадный» алгоритм имеет сложность O( (N+M) D ) во времени и пространстве.

форум разработчиков