Идеи реализации
Пред. Глава 36. Близость последовательностей След.

Идеи реализации

Процесс поиска LCS двух строк представим как их посимвольное сопоставление. Если первые символы строк одинаковы, один из них, безусловно, должен войти в LCS. В этом случае одинаковые первые символы отбрасываются (и добавляются в единственном экземпляре в LCS), и сопоставление продолжается со следующих символов. Если же символы различны, перед продолжением сопоставления какой-то из них должен быть выброшен (увы, пока неизвестно, какой именно).

Чтобы сделать процесс сопоставления наглядным, запишем символы первого слова по горизонтали, а второго — по вертикали. Выбрасывание очередного символа из первого слова изобразим стрелкой, направленной вправо (остриё стрелки находится в той же колонке, что и выбрасываемый символ). Когда символ выбрасывается из второго слова, рисуем стрелку, направленную вниз (в этом случае конец стрелки находится в той же строке, что и символ). Чтобы сделать возможным выбрасывание самого первого символа, добавим дополнительные ряд и столбец сверху и слева в получившуюся таблицу.

Кроме этого отметим в таблице те места, где символы на горизонтали и вертикали совпадают. Это как раз те символы, которые могли бы войти в LCS. В эти точки направим стрелки, идущие по диагонали, сверху вниз слева направо. Такие стрелки обозначают выбрасывание совпадающих символов из обеих строк с одновременным добавлением выброшенного в LCS. Результат представлен на рисунке 36.2. «Поиск LCS двух строк».

Рисунок 36.2. Поиск LCS двух строк

Теперь переходим к самому главному. Процесс поиска общей подпоследовательности можно представить как путь по стрелкам на полученном рисунке из верхнего левого угла в нижний правый. Ясно, что чем больше на пути встретится диагональных стрелок (и, соответственно, отмеченных красным точек совпадения), тем длиннее получится общая подпоследовательность.

Конструкциям, подобным изображённой на рисунке, посвящён важный раздел дискретной математики — теория графов. Граф состоит из двух множеств — множества вершин V и множества рёбер E. Каждое ребро представляет собой пару вершин. Очень часто вершины графа изображают на рисунке точками, а рёбра — дугами, соединяющими пару вершин. Если граф обладает дополнительными свойствами, он награждается соответствующими эпитетами. Так, в нашем случае пары вершин соединаются не просто дугами, а стрелками. Это значит, что ребро является не просто парой вершин, а упорядрченной парой. Такой граф называется ориентированным. Если же упорядоченными являются только некоторые рёбра, граф называют смешанным.

Таким образом, наша задача свелась к поиску наилучшего маршрута в ориентированном графе на рисунке 36.2. «Поиск LCS двух строк». Наилучшим считается тот, который пройдёт через наибольшее число диагональных рёбер. Можно вообразить пешехода, идущего через каменные джунгли Манхэттена, расчерченные на одинаковые кварталы сетью горизонтально и вертикально направленных дорог (стрит и авеню), причём некоторые кварталы можно срезать по диагонали.

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

Наличие переходов по диагонали делает задачу по-настоящему содержательной. Они искажают манхэттенское расстояние. Если переход по вертикали или горизонтали «стоит» одну условную единицу, то диагональный не стоит ничего.

Похожей задаче, связанной с поиском наилучшего пути в графе, посвящена глава 25. «Путь с максимальной суммой в числовом треугольнике». Там в качестве графа выступал числовой треугольник, а пути прокладывались от вершины к основанию вниз влево или вниз вправо. За каждый переход назначалась премия, равная числу, в который этот переход ведёт. Требовался путь, сулящий наибольшую премию, или, вернее, даже не сам путь, а эта премия.

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

Кстати, а сколько же всего путей в нашем графе, соединяющих точки старта и финиша? Уж не перебрать ли их все, чтобы найти наилучший?

В качестве небольшого комбинаторного упражнения подсчитаем количество путей в прямоугольнике, разбитом на квадраты, и имеющим размеры h квадратов по горизонтали и v по вертикали. Пока мы никак не не учитываем возможность диагональных переходов. Тогда стоимость каждого пути одинакова и равна сумме длин строк — это как раз полупериметр прямоугольника, охватывающего граф, это манхэттенская длина пути. Ясно, что учёт диагональных переходов разве что увеличат это число, так что мы получим оценку снизу для трудоёмкости решения задачи методом полного перебора всех вариантов.

Каждый путь может быть закодирован как последовательность букв H и V, которые соответственно символизируют шаг вправо и шаг вниз. В последовательности должно содержаться ровно h букв H и ровно v букв V. Все такие последовательности и нужно подсчитать.

Первую букву V можно расположить, очевидно, h + v способами. Для второй будет уже на одну возможность меньше, то есть h + v − 1 . Для самой последней останется лишь h + v − v + 1 = h + 1 вариант. На оставшиеся места расставим буквы H.

Итак, подсчёт приводит, казалось бы, к выражению h + v ⁢ h + v − 1 ⁢ … ⁢ h + 1 = h + v ! h ! .

Однако немного смущает то, что результат меняется при замене h на v и наоборот. Правильны ли наши выводы? Нет.

Дело в том, что каждую расстановку букв V мы подсчитали несколько раз. К примеру, первую V ставим на третье место, а вторую — на пятое. А затем первую на пятое а вторую на третье. Оба случая будут подсчитаны. В итоге наши подсчёты учитывают порядок расстановки букв V по их местам, что нам совсем не нужно. Правильный результат получится, если выражение разделить на количество перестановок букв V, то есть на v ! . В итоге получаем h + v ! h ! ⁢ v ! путей.

Да это же знакомое нам выражение для C h + v h = C h + v v количества сочетаний из h + v по h (или, что то же самое, по v)!

А теперь предлагаем вашему вниманию более изящное рассуждение. Обозначим количество последовательностей длины l, в которой v букв V и h = l − v букв H, как P ⁡ l v .

На первое место в последовательности можно поставить или H, или V. Если H, то дальше путь продолжается в прямоугольнике размером h − 1 × v , для чего имеется P ⁡ l − 1 v способов. Аналогично, если на первом месте окажется V, для продолжения пути будет P ⁡ l − 1 v − 1 возможностей.

Таким образом, получаем соотношение P ⁡ l v = P ⁡ l − 1 v + P ⁡ l − 1 v − 1 . Учтём также очевидные равенства P ⁡ l 0 = P ⁡ l l = 1 (последовательность, состоящая из одинаковых букв, единственна). Вот теперь трудно не узнать соотношения для элементов треугольника Паскаля, которому мы посвящали главу 10. Полученное равенство выражает тот факт, что число, стоящее в числовом треугольнике в l-ой строке, равно сумме чисел, расположенных слева и справа от него на одну строчку выше. Дополнительные равенства говорят о том, что числовой треугольник обрамлён слева и справа едииницами. В общем, P ⁡ l v = C l v = l ! v ! ⁢ l − v ! = h + v ! h ! ⁢ v ! . Мы другим способом пришли к той же самой формуле.

Для нашего примера со словами туманы и мутанты получается 1716 возможных путей. Перебрать их — задача, вполне посильная для современных вычислительных машин. Для двух слов, в каждом из которых по двенадцати букв, получается уже 2704156 вариантов. Хоть это и не астрономическое число, такой перебор уже будет некоторым испытанием. Но не будем забывать, что задача определения близости последовательностей не ограничивается только лишь словами, это могут быть последовательности строк файлов. При сравнении двух файлов с сотней строк в каждом количество путей (мы грубо прикинули в уме) будет порядка 10 59 . Это очень много, так что уже знакомый нам метод грубой силы и в этот раз покажет свою несостоятельность.

В основе рекурсивного подхода к решению лежат очень простые соображения. Обозначим LCS последовательностей X и Y как lcs ⁡ X Y . Пусть Z 1 — самый первый элемент последовательности Z, а Z ′ — последовательность, получаемая отбрасыванием первого элемента в последовательности Z. Для пустой последовательности введём обозначение E.

В принципе эти очевидные правила дают рекурсивный алгоритм вычисления LCS двух последовательностей, который либо сразу даёт ответ, либо сводится к вычислению LCS двух последовательностей, из которых хотя бы одна короче исходной. Нас сейчас занимает вычисление не самой LCS, а её длины. Обозначим как Z длину последовательности Z. Тогда легко написать формулу вычисления длины: lcs ⁡ X Y = 0 при X = E или Y = E , 1 + lcs ⁡ X ′ Y ′ при X 1 = Y 1 , max ⁡ lcs ⁡ X ′ Y lcs ⁡ X Y ′ иначе.

Для вычисления расстояния Левенштейна между последовательностями X и Y (обозначим его как lev ⁡ X Y ) также можно написать рекурсивные формулы. Нужно лишь заметить, что lev ⁡ X Y = X + Y − 2 ⁢ lcs ⁡ X Y . Тогда lcs ⁡ X Y = 1 2 ⁢ X + Y − lev ⁡ X Y . С учётом этого получаем lev ⁡ X Y = X + Y при X = E или Y = E , lev ⁡ X ′ Y ′ при X 1 = Y 1 , 1 + min ⁡ lev ⁡ X ′ Y lev ⁡ X Y ′ иначе.

Описанное здесь рекурсивное решение безнадёжно плохо. Единственным, пожалуй, его достоинством является простота алгоритма. Для последовательностей X и Y, не имеющих общих элементов, рекурсивная процедура, посвящённая вычислению длины LCS, вызывает сама себя дважды, если только X ′ или Y ′ не пусты.

Можно, конечно, подумать, что растущее в геометрической прогрессии число рекурсивных вызовов совершенно необходимо. Однако посмотрим, что происходит, если X 1 ≠ Y 1 , X 2 ≠ Y 1 , X 1 ≠ Y 2 . Мы изобразили на диаграмме каскад рекурсивных вызовов для строк X и Y: X Y ↓ ↘ X ′ Y X Y ′ ↓ ↘ ↓ ↘ X ″ Y X ′ Y ′ X ′ Y ′ X Y ″ Уже во втором поколении обнаруживаются два вызова с одинаковым набором параметров (выделены цветом). Для последовательностей, не имеющих общих элементов, количество таких избыточных вызовов будет катастрофически расти. Это явление нам знакомо по главе 9. «Числа Фибоначчи», и для борьбы с ним хорошо себя зарекомендовала мемоизация.

Есть целый класс подобных задач, и для их решения разработаны методы, известные под собирательным названием «динамическое программирование». Сразу оговоримся, что слово «программирование» здесь не связано напрямую с программированием вычислительных машин. Осуществлять динамическое программирование можно и на бумаге, если в наличии достаточно терпения, и, конечно, бумаги. И тем не менее вычислительная техника очень уместна при динамическом программировании — его методы хорошо алгоритмизуются.

Перечислим общие черты задач, в решении которых применяется динамическое программирование:

Очевидно, все эти признаки присутствуют в нашей задаче.

Для демонстрации метода динамического программирования введём обозначения. Пусть X и Y — сравниваемые строки. Обозначим как X i и Y j соответственно i-й и j-й символы этих строк. Отметим, что для нас будет удобно вести нумерацию символов, начиная с единицы. С удовольствием воспользуемся прямоугольной структурой графа и введём прямоугольную систему координат с началом в верхнем левом углу прямоугольника и с осями, направленными вправо и вверх. Каждая вершина графа получит координаты i j , где 0 ⩽ i ⩽ X , 0 ⩽ j ⩽ Y , а X и Y — длины строк X и Y.

Обозначим как W i j наименьший возможный штраф среди всех путей, соединяющий вершину 0 0 с вершиной i j . Наша цель — найти значение W X Y , а также путь, приводящий к такому наименьшему штрафу.

Величину W i j будем рассматривать как функцию, зависящую от двух целых неотрицательных чисел i, j. Это так называемая функция Беллмана — важное действующее лицо в динамическом программировании.

Постараемся прояснить роль функции Беллмана не только в нашей задаче, но и вообще в динамическом программировании. Как мы уже упоминали, поиск решения задачи динамического программирования разбит на отдельные шаги. Как правило, перед очередным шагом имеется выбор, от которого зависит, получим ли мы решение задачи или нет. Каждый сделанный шаг приводит процесс поиска решения в то или иное состояние. Часто в одно и то же состояние можно попасть разными путями (сделав разные последовательности шагов). При этом каждый из таких путей имеет свою цену, то есть свой вклад в целевую функцию. Примем для определённости, что в задаче динамического программирования нужно минимизировать целевую функцию (если, напротив, нужно максимизировать, просто поменяем знак у целевой функции). Функция Беллмана зависит от состояния поиска решения. Это минимальная цена попадания в данное состояние, где минимум берётся по всевозможным путям, ведущим в это состояние.

Мы надеемся, что читатель не запутался и не смешивает две различные функции — целевую и Беллмана. Целевая функция зависит от пути, ведущего из начального состояния в конечное, её область определения — множество таких путей. В то же время область определения функции Беллмана — множество всех состояний, включая начальное и конечное.

Пора применить новые знания к решению нашей задачи. Займёмся вычислением функции Беллмана. Состояниями процесса поиска решения будут служить вершины прямоугольного графа, каждой из которых, напомним, отвечает пара координат i j . Путь начинается в начале координат — верхнем левом углу. Вполне естественно положить W 0 0 = 0 , поскольку самый дешёвый путь из верхнего левого угла в него же обойдётся бесплатно. Ясно также, что W i 0 = i и W 0 j = j , так как путь в любую вершину на верхней или левой стороне прямоугольника стоит столько, сколько шагов соответственно вправо или вниз придётся сделать.

У всех остальных вершин графа есть соседние вершины сверху и слева, а в некоторые, кроме того, можно попасть по диагонали. Если в вершину i j можно попасть только сверху и слева, значением W i j будет минимум из значений W сверху и слева, увеличенный на единицу, то есть W i j = min ⁡ W i j − 1 + 1 W i − 1 j + 1 = min ⁡ W i j − 1 W i − 1 j + 1 (добавочная единица — это плата за горизонтальный или вертикальный переход). Если имеется ещё и диагональ, ведущая в данную вершину, формула немного усложнится: W i j = min ⁡ W i j − 1 + 1 W i − 1 j + 1 W i − 1 j − 1 .

Вот теперь, заполнив верхний и левый ряды значениями функции Беллмана, можем вычислять функцию по формулам и в остальных вершинах. Результат представлен на рисунке 36.3. «Функция Беллмана в задаче поиска LCS». Изобретатель динамического программирования R. E. Bellman, безусловно, порадовался бы за нас.

Рисунок 36.3. Функция Беллмана в задаче поиска LCS

Истинной целью всех этих вычислений является единственное значение W X Y (значение функции Беллмана в правом нижнем углу графа). Но для получения результата пришлось вычислять значения функции во всех без исключения вершинах графа.

Найденное значение 5 говорит о том, что степень различия двух слов равна 5 13 , а степень сходства — 8 13 . Длина LCS, как и было обещано, равна 13 − 5 2 = 4 . Это в точности то наибольшее количество диагоналей, которое можно встретить на пути из верхнего левого в нижний правый угол (напомним, что каждая пройденная диагональ соответствует общему элементу двух последовательностей).

Функция Беллмана позволяет найти не только длину LCS, но и саму наибольшую общую подпоследовательность. Для этого нужно вместе с вычислением значения функции в вершине запоминать тот самый дешёвый шаг, который ведёт в эту вершину. По окончании вычислений следует пройти все отмеченные шаги в обратной последовательности. Иными словами, стартуя из нижнего правого угла, нужно шагать в ту из соседних вершин (сверху, слева, или, быть может, сверху слева по диагонали), где значение функции Беллмана меньше всего отличается от значения в данной вершине.

Описанный алгоритм решения задачи о нахождении LCS двух последовательностей, основанный на динамическом программировании, называется алгоритмом Вагнера — Фишера.

Для полноты изложения мы должны упомянуть алгоритм, открытый Юджином Майерсом и описанный в статье An O ⁡ N ⁢ D Difference Algorithm and Its Variations. Собственно говоря, эта статья и вдохновила нас на написание данной главы.

Сложность алгоритма Майерса приблизительно пропорциональна сумме длин последовательностей, а не произведению, как в алгоритме Вагнера — Фишера. То же самое можно сказать и об используемой алгоритмом памяти. Похоже, это наилучший из известных алгоритмов для решения нашей задачи.

В библиотечном модуле String::Similarity процедура similarity как раз реализует алгоритм Майерса. Процедура ради эффективности запрограммирована на языке C. Сам модуль не входит в дистрибутив Perl и должен быть установлен отдельно.

Пред. Наверх След.
Глава 36. Близость последовательностей Начало Разработка
Информатика-54© А. Н. Швец