Исследование алгоритмов расчета редакционного расстояния
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
случай, когда обе строки непусты.
Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
Две замены одного и того же символа - не оптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
Две замены разных символов можно менять местами.
Два стирания или две вставки можно менять местами.
Вставка символа с его последующим стиранием - не оптимально (можно их обе отменить).
Стирание и вставку разных символов можно менять местами.
Вставка символа с его последующей заменой - не оптимально (излишняя замена).
Вставка символа и замена другого символа меняются местами.
Замена символа с его последующим стиранием - не оптимально (излишняя замена).
Стирание символа и замена другого символа меняются местами.
Пускай S1 кончается на символ a, S2 кончается на символ b. Есть три варианта:
1.Символ а, на который кончается S1, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ a, после чего превратили первые i ? 1 символов S1 в S2 (на что потребовалось операций), значит, всего потребовалось операций;
.Символ b, на который кончается S2, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили S1 в первые j ?1 символов S2, после чего добавили b. Аналогично предыдущему случаю, потребовалось D(i, j-1)+1 операций;
.Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального a, то чтобы сделать последним символом b, мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального a мы не добавляли. Самого финального a мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа - его замена. Заменять его 2 или больше раз не оптимально.
Значит:
1.Если a = b, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили операций.
.Если , мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить D(i-1, j-1) операций, значит, всего потребуется D(i-1, j-1)+1 операций.
2. Алгоритм Хиршберга
При рассмотрении массива расстояний из метода Вагнера-Фишера становится, очевидно, что при таком подходе требования к памяти равны O(M*N). Например, для сравнения файлов длиной в 105 строк потребуется около 40 гигабайт памяти. Чтобы избежать проблем с памятью при работе с длинными строками, Хиршберг разработал линейную относительно затрат памяти версию этого алгоритма.
.1 Структура алгоритма Хиршберга
Будем применять рекурсию для разбиения задачи на подзадачи, каждая из которых не потребует много памяти. Для дальнейших зарисовок возьмем какие-нибудь начальные значения строк:
= ACGTACGTACGT,= AGTACCTACCGT.
Переписать одну в другую на глаз не так очевидно. Буквы, кстати, выбраны не случайно - это азотистые основания (A,T,G,C), компоненты ДНК: метод оценки редакционного расстояния активно применяется в биологии для оценки мутаций. Тогда исходная не заполненная матрица будет выглядеть (именно выглядеть, хранить мы будем только необходимые данные) следующим образом:
Рисунок 2.1 - Матрица
В каждой клетке должно стоять значение редакционного расстояния. Поделим исходную задачу на подзадачу, поделив вторую строку на две равные (или почти равные) части, запомним место разбиения, и начнем заполнять матрицу ровно так же, как делали в Вагнера - Фишера:
Рисунок 2.2 - Матрица
При заполнении мы не будем хранить предыдущие столбцы, двигаясь слева направо, сверху вниз, по мере вычисления значений D(i, j) значения D(i-1, j) можно удалять:
Рисунок 2.3 - Заполнение матрицы
Аналогично, заполним правую часть разбиения. Здесь будем двигаться справа налево, сверху вниз.
Вот мы и встретились. Теперь можно получить часть решения общей задачи, совместив частные. Просуммируем получившиеся в левых и правых столбцах значения и выберем минимум.
Рисунок 2.4 - Подсчет матрицы
алгоритм редакционное предписание
Что означает это совмещение? Я попытался совместить первую строку с первой половиной второй строки, затем первую строку с второй половиной строки. Сумма позволяет получить количество операций изменения первой строки, чтобы привести ее к конкатенации первой и второй половины второй строки (то есть к второй строке) это значит что мы получили значение редакционного расстояния. Но, рано радоваться, ибо этого результата можно было достичь и проще (вышеописанный метод).
Однако, посмотрев на картинку под другим углом (буквально), мы получили еще один существенный факт: теперь мы знаем как разрезать первую строку на две половины, чтобы соответствующие пары дали нам редакционное расстояние: d (S11,S21) + d (S12,S22) = d (S1,S2). Строка (в матрице), в которой расположен минимум и есть искомое разбиение S1, и это разбиение отправляется в выдачу редакционного предписания.
Аналогично будем делить задачу уже для получившихся подстрок S11 и S21 (и вторую пару тоже