Последовательное приближенное сравнение строк: различия между версиями
Irina (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показаны 34 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Сравнение строк, допускающее ошибки или | Сравнение строк, допускающее ошибки или различия; неточное сравнение строк; полуглобальное или полулокальное сходство последовательностей | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть даны ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math> и ''строка | Пусть даны ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math> и ''строка шаблона'' <math>P = p_1 p_2 ... p_m</math>, представляющие собой последовательности над алфавитом <math>\Sigma</math> размера <math>\sigma</math>, а также ''функция расстояния'' между строками d и ''порог'' k. Задача ''приближенного сравнения строк'' (approximate string matching, ASM) заключается в нахождении всех текстовых позиций, завершающих так называемое ''приблизительное вхождение'' P в T; иначе говоря, в вычислении множества <math>\{ j, \exist i, 1 \le i \le j, d(P, t_i ... t_j) \le k \}</math>. В последовательной версии задачи T, P и k уже заданы, при этом алгоритм может быть настроен для конкретного d. | ||
| Строка 9: | Строка 9: | ||
Популярным обобщением всех вышеперечисленных вариантов является ''взвешенное расстояние редактирования'', при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа c обозначим за <math>w(c \to | Популярным обобщением всех вышеперечисленных вариантов является ''взвешенное расстояние редактирования'', при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа c обозначим за <math>w(c \to \epsilon)</math>, вес операции вставки c – за <math>w(\epsilon \to c)</math>, вес операции замены c на <math>c' \ne c</math> за <math>w(c \to c')</math>. Предполагается, что <math>w(c \to c) = 0</math> и что выполняется неравенство треугольника, то есть <math>w(x \to y) + w(y \to z) \ge w(x \to z)</math> для любых <math>x, y, z \in \Sigma \cup \{ \epsilon \}</math>. Поскольку расстояние теперь может быть асимметричным, примем за d(A, B) стоимость преобразования A в B. Разумеется, любой результат, полученный для метрики взвешенного расстояния редактирования, применим к расстояниям редактирования, Хэмминга и indel-расстоянию (которые далее будут называться ''расстояниями редактирования с единичной стоимостью''), однако другие редукции не являются тривиальными. | ||
Далее рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из <math>\Sigma</math>. Для простоты и практичности будем далее полагать m = o(n). | |||
== Основные результаты == | == Основные результаты == | ||
Первое и наиболее универсальное решение этой задачи [13] строится на процессе вычисления взвешенного расстояния редактирования. Пусть <math>A = a_1 a_2 ... a_m</math> и <math>B = b_1 b_2 ... b_n</math> – две строки, а <math>C[0 ... m, 0 ... n]</math> – матрица, такая, что <math>C[i, j] = d(a_1 ... a_i, b_1 ... b_j)</math>. Тогда имеет место <math>C[0, 0] = 0</math> и | |||
<math>C[i, j] = min (C[i - 1, j] + w(a_i \to \epsilon), C[i, j - 1] + w(\epsilon \to b_j), C[i - 1, j - 1] + w(a_i \to b_j))</math>, | |||
предполагая, что <math>C[i, -1] = C[-1, j] = \infty</math>. Вычисление матрицы требует 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]). Существует решение с временем выполнения <math>O(n + mn / log_{\sigma} \; n)</math> в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования. Более того, время составляет <math>O(n + mnh / log \; n)</math>, где <math>0 \le h \le log \; \sigma</math> – энтропия T.''' | |||
Этот весьма общий результат имеет место также для вычисления взвешенного расстояния редактирования и локального сходства (см. раздел «Применение»). Для случая расстояния редактирования и использования RAM-модели с единичной стоимостью можно получить лучший результат. С одной стороны, можно применить «[https://en.wikipedia.org/wiki/Method_of_Four_Russians| метод четырех русских]», который предварительно вычисляет все возможные блоки (подматрицы C) размера <math>t \times t</math> для <math>t = O(log_{\sigma} \; n)</math> и затем поблочно вычисляет матрицу C [9]. С другой стороны, каждую ячейку матрицы C можно представить при помощи константного числа бит (поскольку она может отличаться от соседних ячеек на ± 1) таким образом, чтобы можно было хранить и обрабатывать несколько ячеек при помощи одного машинного слова [10]. Эта техника называется ''битовым параллелизмом'' и предполагает использование машинных слов длиной <math>\Theta (log \; n)</math> бит. | |||
'''Теорема 3 (Масек и Паттерсон, 1980 [9]; Майерс, 1999 [10]). Существуют решения с временем выполнения <math>O(n + mn / log_{\sigma} n)^2)</math> и <math>O(n + mn /log \; n)</math> в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования.''' | |||
Оба показателя сложности имеют место также для indel-расстояния, но не для расстояния Хэмминга. | |||
Для расстояний редактирования с единичной стоимостью сложность может зависеть от k, а не от m, поскольку для нетривиальных задач k < m и обычно k составляет небольшую часть m (или даже k = o(m)). Классическая техника [8] вычисляет матрицу С путем обработки за константное время диагоналей <math>C[i + d, j + d], 0 \le d \le s</math>, вдоль которых значения ячеек не изменяются. Это можно сделать при помощи предварительной обработки суффиксных деревьев T и P для ответа на запросы о самых низких общих предках. | |||
'''Теорема 4 (Ландау и Вишкин, 1989 [8]). Существует решение с временем выполнения O(kn) в наихудшем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.''' | |||
Также существуют другие решения, дающие лучший результат для небольших k и требующие <math>O(n(1 + k^4/m))</math> времени [4]. Для случая расстояния Хэмминга можно получить лучший результат при использовании сверток [1]. | |||
'''Теорема 5 (Амир и др,. 2004 [1]). Существует решение с временем выполнения <math>O(n \sqrt{k \; log \; k)}</math> и <math>O(n(1 + k^3/m)log \; k)</math> в наихудшем случае для задачи ASM с использованием расстояния Хэмминга.''' | |||
Последний результат для расстояния редактирования [4] демонстрирует время O(n) в случае, если k достаточно мало <math>(k = O(m^{1/4)})</math>. Можно также получить время O(n) для расстояний редактирования с единичной стоимостью за счет добавления экспоненциального дополнительного члена в m или k. Количество разных столбцов в матрице C не зависит от n, так что переход от любого возможного столбца к следующему может быть предварительно вычислен при помощи конечного автомата. | |||
'''Теорема 6 (Укконен, 1985 [14]). Существует решение с временем выполнения <math>O(n + m \; min(3^m, m(2 m \sigma)^k))</math> в наихудшем случае для задачи ASM с использованием расстояния редактирования.''' | |||
Аналогичный результат имеет место для расстояния Хэмминга и indel-расстояния, для которых экспоненциальный член слегка сокращается в силу свойств этих метрик. | |||
Сложность задачи ASM в наихудшем случае, разумеется, составляет <math>\Omega(n)</math>, однако неизвестно, может ли она быть достигнута для любых значений m и k. Впрочем, сложность этой задачи в среднем случае известна. | |||
'''Теорема 7 (Чанг и Марр, 1994 [3]). Существует решение с временем выполнения <math>\Theta(n(k + log_{\sigma} m)/m)</math> в среднем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.''' | |||
Нетрудно доказать нижнюю границу как расширение границы Яо для точного сравнения строк [15]. Нижняя граница была достигнута в той же статье [3] для <math>k/m < 1/3 - O(1 / \sqrt{\sigma})</math>. Позднее она была улучшена до <math>k/m < 1/2 - O(1 / \sqrt{\sigma})</math> [6] с использованием несколько отличающейся идеи. Данный подход заключается в предварительном вычислении минимального расстояния для сопоставления любой возможной текстовой подстроки (блока) длины <math>O(log_{\sigma} m)</math> в P. Затем текстовое окно поблочно сканируется в обратном направлении с добавлением этих заранее вычисленных минимальных расстояний. Если до окончания сканирования всего окна они превышают значение k, тогда никакое вхождение P с k ошибками не может содержать отсканированные блоки, и окно можно безопасно сдвинуть поверх отсканированных блоков, продвигаясь по T. Это пример алгоритма ''фильтрации'', который отбрасывает большинство текстовых областей и применяет алгоритм ASM только к тем областям, которые не могут быть отброшены. | |||
'''Теорема 8 (Фредриксон и Наварро, 2004 [6]). Существует оптимальное в среднем решение для задачи ASM с использованием расстояния редактирования для любого <math>k/m \le \frac{1 - e / \sqrt{\sigma}}{2 - e / \sqrt{\sigma}} = 1/2 - O(1 / \sqrt{\sigma})</math>''' | |||
Данный результат дословно применим и к indel-расстоянию. Для расстояния Хэмминга достигается та же сложность, однако граница на k/m улучшается до <math>1 - 1 / \sigma</math>. Отметим, что при достижении предельного значения k/m средняя сложность уже составляет <math>\Theta(n)</math>. Неясно, для какого предела k/m можно получить среднее линейное время выполнения. | |||
== Применение == | |||
Эта задача широко применяется в вычислительной биологии (для сравнения последовательностей ДНК и белков, восстановления после ошибок экспериментов, с целью выявления точек мутаций или прогнозирования сходства в структуре или функции), для текстового информационного поиска (для восстановления после ошибок транскрипции, набора или автоматического распознавания), обработки сигналов (для восстановления после ошибок при передаче и искажений) и в некоторых других областях. Подробнее об этом см. обсуждение в работе [11]. | |||
Существует немало расширений задачи ASM, особенно в вычислительной биологии. К примеру, можно заменить полные подстроки другими (''обобщенное расстояние редактирования''), поменять символы в строке (''сравнение строк с заменами или транспозициями''), выполнить обращение подстрок (''расстояние обращений''), присвоить переменную стоимость операциям вставки и удаления в случае их группировки (''сходство со штрафами за пропуски'') или искать любую пару подстрок обеих строк, обладающую достаточным сходством (''локальное сходство''). Примеры можно найти в книге Гусфилда [7], где рассматривается множество родственных задач. | |||
== Открытые вопросы == | |||
Сложность задачи в наихудшем случае не вполне понятна. Для расстояния редактирования с единичной стоимостью она составляет <math>\Theta(n)</math> в случае, если <math>m = O(min(log \; n, (log_{\sigma} n)^2))</math> или <math>k = O(min(m^{1/4},log_{m \sigma} n))</math>. Для взвешенного расстояния редактирования сложность составляет <math>\Theta(n)</math> в случае <math>m = O(log_{\sigma} n)</math>. Неизвестно также, вплоть до какого значения k/m можно получить среднее время <math>O(n)</math>; до настоящего момента его удавалось получить для <math>k/m = 1/2 - O(1 / \sqrt{\sigma})</math>. | |||
== Экспериментальные результаты == | |||
Исчерпывающий обзор материалов по данному вопросу [11] включает множество экспериментов. На сегодняшний день самыми быстрыми алгоритмами для расстояния редактирования на практике являются алгоритмы фильтрации [6, 12] в сочетании с битово-параллельными алгоритмами для проверки областей-кандидатов [2, 10]. Эти алгоритмы фильтрации хорошо работают для достаточно малых значений k/m, в противном случае битово-параллельные алгоритмы следует использовать автономно. Алгоритмы фильтрации легко допускают расширение с целью поддержки поиска по нескольким шаблонам одновременно. | |||
== Ссылка на код == | |||
Эффективное решение задачи ASM обеспечивают такие хорошо известные пакеты, как agrep (http://webglimpse.net/download.html, поддиректория верхнего уровня agrep/) и nrgrep (http://www.dcc.uchile.cl/~gnavarro/software). | |||
== См. также == | |||
* [[Приближенное сравнение регулярных выражений]] – более сложный случай, где P может быть регулярным выражением | |||
* [[Индексированное приближенное сравнение строк]] относится к случаю, при котором возможна предварительная обработка текста | |||
* [[Локальное выравнивание (с вогнутыми штрафами за пропуски)]] относится к более сложной схеме с весами, используемой в вычислительной биологии | |||
* [[Последовательное точное сравнение строк]] – упрощенная версия, в которой ошибки не допускаются | |||
== Литература == | |||
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) | |||
[[Категория: Совместное определение связанных терминов]] | |||
Текущая версия от 11:18, 7 декабря 2024
Ключевые слова и синонимы
Сравнение строк, допускающее ошибки или различия; неточное сравнение строк; полуглобальное или полулокальное сходство последовательностей
Постановка задачи
Пусть даны текстовая строка [math]\displaystyle{ T = t_1 t_2 ... t_n }[/math] и строка шаблона [math]\displaystyle{ P = p_1 p_2 ... p_m }[/math], представляющие собой последовательности над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math], а также функция расстояния между строками d и порог k. Задача приближенного сравнения строк (approximate string matching, ASM) заключается в нахождении всех текстовых позиций, завершающих так называемое приблизительное вхождение P в T; иначе говоря, в вычислении множества [math]\displaystyle{ \{ j, \exist i, 1 \le i \le j, d(P, t_i ... t_j) \le k \} }[/math]. В последовательной версии задачи T, P и k уже заданы, при этом алгоритм может быть настроен для конкретного d.
Решения этой задачи заметно различаются в зависимости от используемой метрики расстояния d. Далее будет использоваться очень популярная метрика, называемая расстоянием Левенштейна или расстоянием редактирования и определяемая как минимальное количество операций вставки символа, удаления символа и замены одного символа на другой, необходимых для преобразования одной строки в другую. Также будет уделено внимание другим распространенным вариантам, таким как indel-расстояние, в котором допускаются только вставки и удаления и которое является двойственным к нахождению самой длинной общей подпоследовательности lcs (d(A, B) = |A| + |B| - 2 • lcs(A, B)), а также расстояние Хэмминга, в котором рассматриваются только замены.
Популярным обобщением всех вышеперечисленных вариантов является взвешенное расстояние редактирования, при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа c обозначим за [math]\displaystyle{ w(c \to \epsilon) }[/math], вес операции вставки c – за [math]\displaystyle{ w(\epsilon \to c) }[/math], вес операции замены c на [math]\displaystyle{ c' \ne c }[/math] за [math]\displaystyle{ w(c \to c') }[/math]. Предполагается, что [math]\displaystyle{ w(c \to c) = 0 }[/math] и что выполняется неравенство треугольника, то есть [math]\displaystyle{ w(x \to y) + w(y \to z) \ge w(x \to z) }[/math] для любых [math]\displaystyle{ x, y, z \in \Sigma \cup \{ \epsilon \} }[/math]. Поскольку расстояние теперь может быть асимметричным, примем за d(A, B) стоимость преобразования A в B. Разумеется, любой результат, полученный для метрики взвешенного расстояния редактирования, применим к расстояниям редактирования, Хэмминга и indel-расстоянию (которые далее будут называться расстояниями редактирования с единичной стоимостью), однако другие редукции не являются тривиальными.
Далее рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из [math]\displaystyle{ \Sigma }[/math]. Для простоты и практичности будем далее полагать m = o(n).
Основные результаты
Первое и наиболее универсальное решение этой задачи [13] строится на процессе вычисления взвешенного расстояния редактирования. Пусть [math]\displaystyle{ A = a_1 a_2 ... a_m }[/math] и [math]\displaystyle{ B = b_1 b_2 ... b_n }[/math] – две строки, а [math]\displaystyle{ C[0 ... m, 0 ... n] }[/math] – матрица, такая, что [math]\displaystyle{ C[i, j] = d(a_1 ... a_i, b_1 ... b_j) }[/math]. Тогда имеет место [math]\displaystyle{ C[0, 0] = 0 }[/math] и
[math]\displaystyle{ C[i, j] = min (C[i - 1, j] + w(a_i \to \epsilon), C[i, j - 1] + w(\epsilon \to b_j), C[i - 1, j - 1] + w(a_i \to b_j)) }[/math],
предполагая, что [math]\displaystyle{ C[i, -1] = C[-1, j] = \infty }[/math]. Вычисление матрицы требует 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]). Существует решение с временем выполнения [math]\displaystyle{ O(n + mn / log_{\sigma} \; n) }[/math] в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования. Более того, время составляет [math]\displaystyle{ O(n + mnh / log \; n) }[/math], где [math]\displaystyle{ 0 \le h \le log \; \sigma }[/math] – энтропия T.
Этот весьма общий результат имеет место также для вычисления взвешенного расстояния редактирования и локального сходства (см. раздел «Применение»). Для случая расстояния редактирования и использования RAM-модели с единичной стоимостью можно получить лучший результат. С одной стороны, можно применить «метод четырех русских», который предварительно вычисляет все возможные блоки (подматрицы C) размера [math]\displaystyle{ t \times t }[/math] для [math]\displaystyle{ t = O(log_{\sigma} \; n) }[/math] и затем поблочно вычисляет матрицу C [9]. С другой стороны, каждую ячейку матрицы C можно представить при помощи константного числа бит (поскольку она может отличаться от соседних ячеек на ± 1) таким образом, чтобы можно было хранить и обрабатывать несколько ячеек при помощи одного машинного слова [10]. Эта техника называется битовым параллелизмом и предполагает использование машинных слов длиной [math]\displaystyle{ \Theta (log \; n) }[/math] бит.
Теорема 3 (Масек и Паттерсон, 1980 [9]; Майерс, 1999 [10]). Существуют решения с временем выполнения [math]\displaystyle{ O(n + mn / log_{\sigma} n)^2) }[/math] и [math]\displaystyle{ O(n + mn /log \; n) }[/math] в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования.
Оба показателя сложности имеют место также для indel-расстояния, но не для расстояния Хэмминга.
Для расстояний редактирования с единичной стоимостью сложность может зависеть от k, а не от m, поскольку для нетривиальных задач k < m и обычно k составляет небольшую часть m (или даже k = o(m)). Классическая техника [8] вычисляет матрицу С путем обработки за константное время диагоналей [math]\displaystyle{ C[i + d, j + d], 0 \le d \le s }[/math], вдоль которых значения ячеек не изменяются. Это можно сделать при помощи предварительной обработки суффиксных деревьев T и P для ответа на запросы о самых низких общих предках.
Теорема 4 (Ландау и Вишкин, 1989 [8]). Существует решение с временем выполнения O(kn) в наихудшем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.
Также существуют другие решения, дающие лучший результат для небольших k и требующие [math]\displaystyle{ O(n(1 + k^4/m)) }[/math] времени [4]. Для случая расстояния Хэмминга можно получить лучший результат при использовании сверток [1].
Теорема 5 (Амир и др,. 2004 [1]). Существует решение с временем выполнения [math]\displaystyle{ O(n \sqrt{k \; log \; k)} }[/math] и [math]\displaystyle{ O(n(1 + k^3/m)log \; k) }[/math] в наихудшем случае для задачи ASM с использованием расстояния Хэмминга.
Последний результат для расстояния редактирования [4] демонстрирует время O(n) в случае, если k достаточно мало [math]\displaystyle{ (k = O(m^{1/4)}) }[/math]. Можно также получить время O(n) для расстояний редактирования с единичной стоимостью за счет добавления экспоненциального дополнительного члена в m или k. Количество разных столбцов в матрице C не зависит от n, так что переход от любого возможного столбца к следующему может быть предварительно вычислен при помощи конечного автомата.
Теорема 6 (Укконен, 1985 [14]). Существует решение с временем выполнения [math]\displaystyle{ O(n + m \; min(3^m, m(2 m \sigma)^k)) }[/math] в наихудшем случае для задачи ASM с использованием расстояния редактирования.
Аналогичный результат имеет место для расстояния Хэмминга и indel-расстояния, для которых экспоненциальный член слегка сокращается в силу свойств этих метрик.
Сложность задачи ASM в наихудшем случае, разумеется, составляет [math]\displaystyle{ \Omega(n) }[/math], однако неизвестно, может ли она быть достигнута для любых значений m и k. Впрочем, сложность этой задачи в среднем случае известна.
Теорема 7 (Чанг и Марр, 1994 [3]). Существует решение с временем выполнения [math]\displaystyle{ \Theta(n(k + log_{\sigma} m)/m) }[/math] в среднем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.
Нетрудно доказать нижнюю границу как расширение границы Яо для точного сравнения строк [15]. Нижняя граница была достигнута в той же статье [3] для [math]\displaystyle{ k/m \lt 1/3 - O(1 / \sqrt{\sigma}) }[/math]. Позднее она была улучшена до [math]\displaystyle{ k/m \lt 1/2 - O(1 / \sqrt{\sigma}) }[/math] [6] с использованием несколько отличающейся идеи. Данный подход заключается в предварительном вычислении минимального расстояния для сопоставления любой возможной текстовой подстроки (блока) длины [math]\displaystyle{ O(log_{\sigma} m) }[/math] в P. Затем текстовое окно поблочно сканируется в обратном направлении с добавлением этих заранее вычисленных минимальных расстояний. Если до окончания сканирования всего окна они превышают значение k, тогда никакое вхождение P с k ошибками не может содержать отсканированные блоки, и окно можно безопасно сдвинуть поверх отсканированных блоков, продвигаясь по T. Это пример алгоритма фильтрации, который отбрасывает большинство текстовых областей и применяет алгоритм ASM только к тем областям, которые не могут быть отброшены.
Теорема 8 (Фредриксон и Наварро, 2004 [6]). Существует оптимальное в среднем решение для задачи ASM с использованием расстояния редактирования для любого [math]\displaystyle{ k/m \le \frac{1 - e / \sqrt{\sigma}}{2 - e / \sqrt{\sigma}} = 1/2 - O(1 / \sqrt{\sigma}) }[/math]
Данный результат дословно применим и к indel-расстоянию. Для расстояния Хэмминга достигается та же сложность, однако граница на k/m улучшается до [math]\displaystyle{ 1 - 1 / \sigma }[/math]. Отметим, что при достижении предельного значения k/m средняя сложность уже составляет [math]\displaystyle{ \Theta(n) }[/math]. Неясно, для какого предела k/m можно получить среднее линейное время выполнения.
Применение
Эта задача широко применяется в вычислительной биологии (для сравнения последовательностей ДНК и белков, восстановления после ошибок экспериментов, с целью выявления точек мутаций или прогнозирования сходства в структуре или функции), для текстового информационного поиска (для восстановления после ошибок транскрипции, набора или автоматического распознавания), обработки сигналов (для восстановления после ошибок при передаче и искажений) и в некоторых других областях. Подробнее об этом см. обсуждение в работе [11].
Существует немало расширений задачи ASM, особенно в вычислительной биологии. К примеру, можно заменить полные подстроки другими (обобщенное расстояние редактирования), поменять символы в строке (сравнение строк с заменами или транспозициями), выполнить обращение подстрок (расстояние обращений), присвоить переменную стоимость операциям вставки и удаления в случае их группировки (сходство со штрафами за пропуски) или искать любую пару подстрок обеих строк, обладающую достаточным сходством (локальное сходство). Примеры можно найти в книге Гусфилда [7], где рассматривается множество родственных задач.
Открытые вопросы
Сложность задачи в наихудшем случае не вполне понятна. Для расстояния редактирования с единичной стоимостью она составляет [math]\displaystyle{ \Theta(n) }[/math] в случае, если [math]\displaystyle{ m = O(min(log \; n, (log_{\sigma} n)^2)) }[/math] или [math]\displaystyle{ k = O(min(m^{1/4},log_{m \sigma} n)) }[/math]. Для взвешенного расстояния редактирования сложность составляет [math]\displaystyle{ \Theta(n) }[/math] в случае [math]\displaystyle{ m = O(log_{\sigma} n) }[/math]. Неизвестно также, вплоть до какого значения k/m можно получить среднее время [math]\displaystyle{ O(n) }[/math]; до настоящего момента его удавалось получить для [math]\displaystyle{ k/m = 1/2 - O(1 / \sqrt{\sigma}) }[/math].
Экспериментальные результаты
Исчерпывающий обзор материалов по данному вопросу [11] включает множество экспериментов. На сегодняшний день самыми быстрыми алгоритмами для расстояния редактирования на практике являются алгоритмы фильтрации [6, 12] в сочетании с битово-параллельными алгоритмами для проверки областей-кандидатов [2, 10]. Эти алгоритмы фильтрации хорошо работают для достаточно малых значений k/m, в противном случае битово-параллельные алгоритмы следует использовать автономно. Алгоритмы фильтрации легко допускают расширение с целью поддержки поиска по нескольким шаблонам одновременно.
Ссылка на код
Эффективное решение задачи ASM обеспечивают такие хорошо известные пакеты, как agrep (http://webglimpse.net/download.html, поддиректория верхнего уровня agrep/) и nrgrep (http://www.dcc.uchile.cl/~gnavarro/software).
См. также
- Приближенное сравнение регулярных выражений – более сложный случай, где P может быть регулярным выражением
- Индексированное приближенное сравнение строк относится к случаю, при котором возможна предварительная обработка текста
- Локальное выравнивание (с вогнутыми штрафами за пропуски) относится к более сложной схеме с весами, используемой в вычислительной биологии
- Последовательное точное сравнение строк – упрощенная версия, в которой ошибки не допускаются
Литература
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)