Поиск в строках, массивах, последовательностях.

Общие подпоследовательности, дистанция.

Обозначения.

Cтрока x длины |x| = m записывается как x₁x₂ ... x_m, где x_i представляет i-й символ x.

Подстрока x_ix_i+1 ... x_j строки x, где i<=j<=m, будет обозначаться x(i,j). В случае, когда i>j, обращенная подстрока обозначается так x_R(i,j).

Обычно x будет обозначать искомый образец, а y – текстовую строку; |x| = m, |y| = m и, конечно, m<=n.

Пример:

x = trismegistus
|x| = 12
x(7,10) = gist
x_R(7,4) = gems

Расстояния между строками.

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

Здесь и далее, d - метрика.

При обработке строк, однако, символы не всегда уместно считать числами, несмотря на то, что коды символов являются ими. Кроме того, часто требуется сравнивать строки разной длины. Поэтому для сравнения строк обычно используют метрики, оценивающие максимальную стоимость преобразования одной строки в другую. В общем случае, операциям редактирования, используемым в этом преобразовании, а именно замене символов, их вставке и удалению, можно назначить разные цены. Последние две операции иногда объединяют в одну и называют вставуд (indel; от insertion и deletion).

Расстояние Хемминга [Hamming, 1982] между двумя строками одинаковой длины определяется как число позиций, в которых символы не совпадают. Это эквивалентно минимальной цене преобразования первой строки во вторую в случае, когда разрешена только операция замены с единичным весом. Если допускается сравнение строк разной длины, то, как правило, требуются также вставка и удаление.

Если придать им тот же вес, что и замене, минимальная общая цена преобразования будет равна одной из метрик, предложенных Левенштейном [Levenstein, 1965]. Другая метрика равна минимальной цене преобразования в случае, когда разрешены только вставка и удаление. Это эквивалентно назначению цены 1 удалению и вставке, и 2 замене, так как последнюю можно заменить парой вставка-удаление. Первую из этих метрик мы ниже называем расстоянием Левенштейна, а вторую – расстоянием редактирования.

Задача о расстоянии между строками.

В задаче поиска различий между файлами x и y через x_i обозначим i-ю строку x, а через y_j – j-ю строку y. В этом случае требуется определить минимальную последовательность операций редактирования, преобразующую x в y.

Задача о наибольшей общей подпоследовательности.

Напомню, что подпоследовательность строки получается путем исключения из нее нуля или более символов, не обязательно смежных. Общая подпоследовательность двух строк – это строка, являющаяся подпоследовательностью каждой из них. Самая длинная из таких строк называется, понятное дело, самой длинной общей подпоследовательностью.

Итак, задача состоит в том, чтобы для данных строк x и y (|x|, |y| > 0) найти |lcs(x,y)|, где lcs(x,y) – самая длинная общая подпоследовательность (longest common subsequence) x и y. Как правило, требуется найти не только длину lcs(x,y), но и саму эту последовательность.

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

Более углубленное изучение вопроса.

Метод динамического программирования Вагнера и Фишера прост в реализации, однако требует квадратичных затрат времени и памяти.

Его идея состоит в том, чтобы последовательно оценивать расстояния между все более длинными префиксами строк – до получения окончательного результата. Промежуточные результаты вычисляются итеративно и хранятся в массиве длины (m+1) * (n+1), что приводит к времени и памяти O(mn). Метод Вагнера и Фишера позволяет вычислить lcs прямо по заполненному массиву расстояний. Алгоритм вычисления расстояния Левенштейна, естественно, представлен.

Поэтому для больших приложений предпочтительна версия Хиршберга с линейным временем.

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

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

Подход к выделению lcs двух строк эквивалентен определению самого длинного монотонно возрастающего пути на графе, составленном из узлов (i,j), таких, что x_i = y_i. В то время как описанным методам всегда требуется квадратичное время, время этого алгоритма для строк одинаковой длины – всего лишь O((r+n) * log(n)), где r – общее число упорядоченных пар позиций, в которых символы двух строк совпадают. В худшем случае может понадобиться сравнивать каждый элемент x с каждым символом y, что приводит к n² таких упорядоченных пар и сложности O(n² * log(n)). Однако, во многих приложениях, например, в задаче поиска различий в файлах, где каждую строку файла естественно считать атомом, можно ожидать, что r будет близко к n, а это дает эффективность O(n * log(n)) – существенное улучшение по сравнению с процедурами, требующими квадратичного времени.

Алгоритм Машека и Патерсона – единственный из известных алгоритмов, которому в худшем случае требуется субквадратичное время.

Этому методу, однако, требуется, чтобы алфавит был конечным, а ценовые веса – целыми множителями фиксированного действительного числа. Алгоритм использует метод 'четырех русских' [Арлазаров, Диниц, Кронрод и Фараджев, 1970], его время в худшем случае равно O(n²/log n) – для строк равной длины. Основная идея этого метода состоит в разбиении матрицы расстояний на совокупность подматриц. Их нижние и правые края можно затем вычислить по аналогичным краям подматриц, примыкающих к текущей сверху и слева, и соответствующим подстрокам x и y, с помощью предварительно вычисленной таблицы. Хотя асимптотически этот алгоритм быстрее обычного динамического программирования, Машек и Патерсон [Masek, Patterson, 1983) указывают, что его следует использовать только для длинных строк; например, при вычислении расстояния редактирования между двумя бинарными строками он становится по-настоящему быстрым, только когда длины строк превосходят 262418.

В случае, когда две сравниваемые строки похожи, то есть когда d мало, хорош метод Укконена.

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

Параллельный метод^{English pdf} поиска lcs: если есть две строки с длинами m и n: m<=n, то на mn процессорах он выполняется O(logm) операций, а в более оптимальном случае - за O(log²m) при mn/log²m процессорах.

Вверх по странице, к оглавлению и навигации