Метод динамического программирования Вагнера и Фишера прост в реализации, однако требует квадратичных затрат времени и памяти.
Его идея состоит в том, чтобы последовательно оценивать расстояния между все более длинными префиксами строк - до получения окончательного результата. Промежуточные результаты вычисляются итеративно и хранятся в массиве длины (m+1) * (n+1), что приводит к времени и памяти O(mn). Метод Вагнера и Фишера позволяет вычислить lcs прямо по заполненному массиву расстояний. Алгоритм вычисления расстояния Левенштейна, естественно, представлен.
Поэтому для больших приложений предпочтительна версия Хиршберга с линейным временем.
В его методе итеративно вычисляются длины lcs последовательно увеличивающихся префиксов строк, а не расстояния между ними. Экономия памяти происходит за счет того, что в каждый заданный момент времени в памяти хранятся только две строки массива, требуемого динамическому программированию. Потеря остальной части массива, однако, приводит к более сложному методу выделения lcs двух строк. Предлагается рекурсивно делить пополам первую строку и получать две lcs - для каждой половины и подходящей подстроки второй строки. Рекурсия раскручивается до тех пор, пока, в конце концов, выделение lcs не станет тривиальным. Окончательная lcs полных строк после этого получается простой конкатенацией кусков строк, полученных во время рекурсии.
Однако, алгоритм Ханта-Шиманского во многих приложениях имеет значительно более высокую эффективность, которая достигается ценой того, что в худшем случае временная сложность становится больше квадратичной.
Подход к выделению lcs двух строк эквивалентен определению самого длинного монотонно возрастающего пути на графе, составленном из узлов (i,j), таких, что xi = yi. В то время как описанным методам всегда требуется квадратичное время, время этого алгоритма для строк одинаковой длины - всего лишь O((r+n) * log(n)), где r - общее число упорядоченных пар позиций, в которых символы двух строк совпадают. В худшем случае может понадобиться сравнивать каждый элемент x с каждым символом y, что приводит к n2 таких упорядоченных пар и сложности O(n2 * log(n)). Однако, во многих приложениях, например, в задаче поиска различий в файлах, где каждую строку файла естественно считать атомом, можно ожидать, что r будет близко к n, а это дает эффективность O(n * log(n)) - существенное улучшение по сравнению с процедурами, требующими квадратичного времени.
Алгоритм Машека и Патерсона - единственный из известных алгоритмов, которому в худшем случае требуется субквадратичное время.
Этому методу, однако, требуется, чтобы алфавит был конечным, а ценовые веса - целыми множителями фиксированного действительного числа. Алгоритм использует метод 'четырех русских' [Арлазаров, Диниц, Кронрод и Фараджев, 1970], его время в худшем случае равно O(n2/log n) - для строк равной длины. Основная идея этого метода состоит в разбиении матрицы расстояний на совокупность подматриц. Их нижние и правые края можно затем вычислить по аналогичным краям подматриц, примыкающих к текущей сверху и слева, и соответствующим подстрокам x и y, с помощью предварительно вычисленной таблицы. Хотя асимптотически этот алгоритм быстрее обычного динамического программирования, Машек и Патерсон [Masek, Patterson, 1983) указывают, что его следует использовать только для длинных строк; например, при вычислении расстояния редактирования между двумя бинарными строками он становится по-настоящему быстрым, только когда длины строк превосходят 262418.
В случае, когда две сравниваемые строки похожи, то есть когда d мало, хорош метод Укконена.
В основе его метода лежит поиск пути минимальной цены на графе, который составлен из вершин матрицы расстояний, а также горизонтальных, вертикальных и диагональных ребер, соответствующих связям между смежными узлами. Требуемый путь начинается в (0, 0) и заканчивается в (m, n).
В этом разделе :
8 Метод динамического программирования Вагнера и Фишера
В методе динамического программирования последовательно, по предыдущим значениям, вычисляются расстояния между все более и более длинными префиксами двух строк - до получения окончательного результата. Опишем этот процесс более подробно.
8 Алгоритм Хиршберга
Цель Хиршберга состояла в том, чтобы найти lcs(x,y) для строк x и y. Поэтому вместо расстояний между строками определялись длины самых длинных общих подпоследовательностей у все более и более длинных префиксов. Обозначим их как li,j.
8 Алгоритм Ханта-Шиманского
Метод выделения lcs для двух входных строк x и y Ханта и Шиманского (Hunt, Szymanski) эквивалентен нахождению максимального монотонно возрастающего пути в графе, состоящего из точек (i, j), таких, что xi = yj. Мы опишем этот метод, а затем проиллюстрируем его примером.
8 Алгоритм Машека и Патерсона
Машек и Патерсон применили к процедуре вычисления расстояния между строками Вагнера и Фишера подход `четырех русских` (Арлазарова, Диница, Кронрода и Фараджева) и получили алгоритм, выполняющийся за время O(n2/log n).
| |
*
Обратная связь