Последовательное приближенное сравнение строк

Материал из WEGA
Перейти к навигации Перейти к поиску

Ключевые слова и синонимы

Сравнение строк, допускающее ошибки или различия; неточное сравнение строк; полуглобальное или полулокальное сходство последовательностей

Постановка задачи

Пусть даны текстовая строка T=t1t2...tn и строка шаблона P=p1p2...pm, представляющие собой последовательности над алфавитом Σ размера σ, а также функция расстояния между строками d и порог k. Задача приближенного сравнения строк (approximate string matching, ASM) заключается в нахождении всех текстовых позиций, завершающих так называемое приблизительное вхождение P в T; иначе говоря, в вычислении множества {j,i,1ij,d(P,ti...tj)k}. В последовательной версии задачи T, P и k уже заданы, при этом алгоритм может быть настроен для конкретного d.


Решения этой задачи заметно различаются в зависимости от используемой метрики расстояния d. Далее будет использоваться очень популярная метрика, называемая расстоянием Левенштейна или расстоянием редактирования и определяемая как минимальное количество операций вставки символа, удаления символа и замены одного символа на другой, необходимых для преобразования одной строки в другую. Также будет уделено внимание другим распространенным вариантам, таким как indel-расстояние, в котором допускаются только вставки и удаления и которое является двойственным к нахождению самой длинной общей подпоследовательности lcs (d(A, B) = |A| + |B| - 2 • lcs(A, B)), а также расстояние Хэмминга, в котором рассматриваются только замены.


Популярным обобщением всех вышеперечисленных вариантов является взвешенное расстояние редактирования, при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа c обозначим за w(cϵ), вес операции вставки c – за w(ϵc), вес операции замены c на cc за w(cc). Предполагается, что w(cc)=0 и что выполняется неравенство треугольника, то есть w(xy)+w(yz)w(xz) для любых x,y,zΣ{ϵ}. Поскольку расстояние теперь может быть асимметричным, примем за d(A, B) стоимость преобразования A в B. Разумеется, любой результат, полученный для метрики взвешенного расстояния редактирования, применим к расстояниям редактирования, Хэмминга и indel-расстоянию (которые далее будут называться расстояниями редактирования с единичной стоимостью), однако другие редукции не являются тривиальными.


Далее рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из Σ. Для простоты и практичности будем далее полагать m = o(n).

Основные результаты

Первое и наиболее универсальное решение этой задачи [13] строится на процессе вычисления взвешенного расстояния редактирования. Пусть A=a1a2...am и B=b1b2...bn – две строки, а C[0...m,0...n] – матрица, такая, что C[i,j]=d(a1...ai,b1...bj). Тогда имеет место C[0,0]=0 и

C[i,j]=min(C[i1,j]+w(aiϵ),C[i,j1]+w(ϵbj),C[i1,j1]+w(aibj)),

предполагая, что C[i,1]=C[1,j]=. Вычисление матрицы требует O(mn) времени; d(A, B) = C[m, n]. Для решения задачи приближенного сравнения строк примем A = P и B = T и положим C[0, j] = 0 для всех j, так что вышеприведенная формула будет использоваться только для i > 0.


Теорема 1 (Селлерс, 1980 [13]). Существует решение с временем выполнения O(mn) в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования.


Алгоритм требует O(m) памяти, если заметить, что матрицу C можно вычислять по столбцам и что для вычисления столбца j требуется только столбец j – 1. Как было показано, из этого тотчас же следует, что поиск среди расстояний редактирования с единичной стоимостью также может быть выполнен за время O(mn). В этих случаях очень легко вычислить только часть матрицы C, чтобы получить алгоритмы со средним временем O(kn) [14].


Для вычисления взвешенного расстояния редактирования существуют алгоритмы с меньшей сложностью в наихудшем случае. Применяя разбор Лемпеля-Зива к P и T, можно выявить области матрицы C, соответствующие подстрокам P и T, которые могут быть вычислены из предыдущих областей, соответствующих аналогичным подстрокам P и T [5].


Теорема 2 (Крочмор и др., 2003 [5]). Существует решение с временем выполнения O(n+mn/logσn) в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования. Более того, время составляет O(n+mnh/logn), где 0hlogσ – энтропия T.


Этот весьма общий результат имеет место также для вычисления взвешенного расстояния редактирования и локального сходства (см. раздел «Применение»). Для случая расстояния редактирования и использования RAM-модели с единичной стоимостью можно получить лучший результат. С одной стороны, можно применить «метод четырех русских», который предварительно вычисляет все возможные блоки (подматрицы C) размера t×t для t=O(logσn) и затем поблочно вычисляет матрицу C [9]. С другой стороны, каждую ячейку матрицы C можно представить при помощи константного числа бит (поскольку она может отличаться от соседних ячеек на ± 1) таким образом, чтобы можно было хранить и обрабатывать несколько ячеек при помощи одного машинного слова [10]. Эта техника называется битовым параллелизмом и предполагает использование машинных слов длиной Θ(logn) бит.


Теорема 3 (Масек и Паттерсон, 1980 [9]; Майерс, 1999 [10]). Существуют решения с временем выполнения O(n+mn/logσn)2) и O(n+mn/logn) в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования.


Оба показателя сложности имеют место также для indel-расстояния, но не для расстояния Хэмминга.


Для расстояний редактирования с единичной стоимостью сложность может зависеть от k, а не от m, поскольку для нетривиальных задач k < m и обычно k составляет небольшую часть m (или даже k = o(m)). Классическая техника [8] вычисляет матрицу С путем обработки за константное время диагоналей C[i+d,j+d],0ds, вдоль которых значения ячеек не изменяются. Это можно сделать при помощи предварительной обработки суффиксных деревьев T и P для ответа на запросы о самых низких общих предках.


Теорема 4 (Ландау и Вишкин, 1989 [8]). Существует решение с временем выполнения O(kn) в наихудшем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.


Также существуют другие решения, дающие лучший результат для небольших k и требующие O(n(1+k4/m)) времени [4]. Для случая расстояния Хэмминга можно получить лучший результат при использовании сверток [1].


Теорема 5 (Амир и др,. 2004 [1]). Существует решение с временем выполнения O(nklogk) и O(n(1+k3/m)logk) в наихудшем случае для задачи ASM с использованием расстояния Хэмминга.


Последний результат для расстояния редактирования [4] демонстрирует время O(n) в случае, если k достаточно мало (k=O(m1/4)). Можно также получить время O(n) для расстояний редактирования с единичной стоимостью за счет добавления экспоненциального дополнительного члена в m или k. Количество разных столбцов в матрице C не зависит от n, так что переход от любого возможного столбца к следующему может быть предварительно вычислен при помощи конечного автомата.


Теорема 6 (Укконен, 1985 [14]). Существует решение с временем выполнения O(n+mmin(3m,m(2mσ)k)) в наихудшем случае для задачи ASM с использованием расстояния редактирования.


Аналогичный результат имеет место для расстояния Хэмминга и indel-расстояния, для которых экспоненциальный член слегка сокращается в силу свойств этих метрик.


Сложность задачи ASM в наихудшем случае, разумеется, составляет Ω(n), однако неизвестно, может ли она быть достигнута для любых значений m и k. Впрочем, сложность этой задачи в среднем случае известна.


Теорема 7 (Чанг и Марр, 1994 [3]). Существует решение с временем выполнения Θ(n(k+logσm)/m) в среднем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.


Нетрудно доказать нижнюю границу как расширение границы Яо для точного сравнения строк [15]. Нижняя граница была достигнута в той же статье [3] для k/m<1/3O(1/σ). Позднее она была улучшена до k/m<1/2O(1/σ) [6] с использованием несколько отличающейся идеи. Данный подход заключается в предварительном вычислении минимального расстояния для сопоставления любой возможной текстовой подстроки (блока) длины O(logσm) в P. Затем текстовое окно поблочно сканируется в обратном направлении с добавлением этих заранее вычисленных минимальных расстояний. Если до окончания сканирования всего окна они превышают значение k, тогда никакое вхождение P с k ошибками не может содержать отсканированные блоки, и окно можно безопасно сдвинуть поверх отсканированных блоков, продвигаясь по T. Это пример алгоритма фильтрации, который отбрасывает большинство текстовых областей и применяет алгоритм ASM только к тем областям, которые не могут быть отброшены.


Теорема 8 (Фредриксон и Наварро, 2004 [6]). Существует оптимальное в среднем решение для задачи ASM с использованием расстояния редактирования для любого k/m1e/σ2e/σ=1/2O(1/σ)


Данный результат дословно применим и к indel-расстоянию. Для расстояния Хэмминга достигается та же сложность, однако граница на k/m улучшается до 11/σ. Отметим, что при достижении предельного значения k/m средняя сложность уже составляет Θ(n). Неясно, для какого предела k/m можно получить среднее линейное время выполнения.

Применение

Эта задача широко применяется в вычислительной биологии (для сравнения последовательностей ДНК и белков, восстановления после ошибок экспериментов, с целью выявления точек мутаций или прогнозирования сходства в структуре или функции), для текстового информационного поиска (для восстановления после ошибок транскрипции, набора или автоматического распознавания), обработки сигналов (для восстановления после ошибок при передаче и искажений) и в некоторых других областях. Подробнее об этом см. обсуждение в работе [11].


Существует немало расширений задачи ASM, особенно в вычислительной биологии. К примеру, можно заменить полные подстроки другими (обобщенное расстояние редактирования), поменять символы в строке (сравнение строк с заменами или транспозициями), выполнить обращение подстрок (расстояние обращений), присвоить переменную стоимость операциям вставки и удаления в случае их группировки (сходство со штрафами за пропуски) или искать любую пару подстрок обеих строк, обладающую достаточным сходством (локальное сходство). Примеры можно найти в книге Гусфилда [7], где рассматривается множество родственных задач.

Открытые вопросы

Сложность задачи в наихудшем случае не вполне понятна. Для расстояния редактирования с единичной стоимостью она составляет Θ(n) в случае, если m=O(min(logn,(logσn)2)) или k=O(min(m1/4,logmσn)). Для взвешенного расстояния редактирования сложность составляет Θ(n) в случае m=O(logσn). Неизвестно также, вплоть до какого значения k/m можно получить среднее время O(n); до настоящего момента его удавалось получить для k/m=1/2O(1/σ).

Экспериментальные результаты

Исчерпывающий обзор материалов по данному вопросу [11] включает множество экспериментов. На сегодняшний день самыми быстрыми алгоритмами для расстояния редактирования на практике являются алгоритмы фильтрации [6, 12] в сочетании с битово-параллельными алгоритмами для проверки областей-кандидатов [2, 10]. Эти алгоритмы фильтрации хорошо работают для достаточно малых значений k/m, в противном случае битово-параллельные алгоритмы следует использовать автономно. Алгоритмы фильтрации легко допускают расширение с целью поддержки поиска по нескольким шаблонам одновременно.

Ссылка на код

Эффективное решение задачи ASM обеспечивают такие хорошо известные пакеты, как agrep (http://webglimpse.net/download.html, поддиректория верхнего уровня agrep/) и nrgrep (http://www.dcc.uchile.cl/~gnavarro/software).

См. также

Литература

1. Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. J. Algorithms 50(2), 257-275 (2004)

2. Baeza-Yates, R., Navarro, G.: Faster approximate string matching. Algorithmica 23(2), 127-158 (1999)

3. Chang, W., Marr, T.: Approximate string matching and local similarity. In: Proc. 5th Annual Symposium on Combinatorial Pattern Matching (CPM'94). LNCS, vol. 807, pp. 259-273. Springer, Berlin, Germany (1994)

4. Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. SIAM J. Comput. 31 (6), 1761 -1782 (2002)

5. Crochemore, M., Landau, G., Ziv-Ukelson, M.: A subquadratic sequence alignment algorithm for unrestricted scoring matrices. SIAM J. Comput. 32(6), 1654-1673 (2003)

6. Fredriksson, K., Navarro, G.: Average-optimal single and multiple approximate string matching. ACM J. Exp. Algorithms 9(1.4)(2004)

7. Gusfield, D.: Algorithms on strings, trees and sequences. Cambridge University Press, Cambridge (1997)

8. Landau, G., Vishkin, U.: Fast parallel and serial approximate string matching. J. Algorithms 10,157-169 (1989)

9. Masek, W., Paterson, M.: A faster algorithm for computing string edit distances. J. Comput. Syst. Sci.20,18-31 (1980)

10. Myers, G.: A fast bit-vector algorithm for approximate string matching based on dynamic progamming. J. ACM 46(3), 395-415(1999)

11. Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. 33(1), 31-88(2001)

12. Navarro, G., Baeza-Yates, R.: Very fast and simple approximate string matching. Inf. Proc. Lett. 72,65-70 (1999)

13. Sellers, P.: The theory and computation of evolutionary distances: pattern recognition. J. Algorithms 1, 359-373 (1980)

14. Ukkonen, E.: Finding approximate patterns in strings. J. Algorithms 6,132-137 (1985)

15. Yao, A.: The complexity of pattern matching for a random string. SIAM J. Comput. 8,368-387 (1979)