Последовательное приближенное сравнение строк: различия между версиями

Пусть даны ''текстовая строка'' <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.

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

<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.

Этот весьма общий результат имеет место также для вычисления взвешенного расстояния редактирования и локального сходства (см. раздел «Применение»). Для случая расстояния редактирования и использования RAM-модели с единичной стоимостью можно получить лучший результат. С одной стороны, можно применить «метод четырех русских», который предварительно вычисляет все возможные блоки (подматрицы C) размера <math>t \times t</math> для <math>t = O(log_{\sigma} \; n)</math> и затем поблочно вычисляет матрицу [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 с использованием взвешенного расстояния редактирования.'''

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

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

'''Теорема 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>(log_{\sigma} \; m)</math> в P. Затем текстовое окно поблочно сканируется в обратном направлении с добавлением этим заранее вычисленных минимальных расстояний. Если до окончания сканирования всего окна они превышают значение k, тогда никакое вхождение P с k ошибками не может содержать отсканированный блок и окно можно безопасно сдвинуть поверх отсканированных блоков, продвигаясь по T. Это пример алгоритма ''фильтрации'', который отбрасывает большинство текстовых областей и применяет алгоритм ASM только к тем областям, которые не могут быть отброшены.

Данный результат дословно применим и к indel-расстоянию. Для расстояния Хэмминга достигается та же сложность, однако граница на k/m улучшается до <math>1 - 1 / \sqrt{\sigma}</math>. Отметим, что при достижении предельного значения k/m средняя сложность уже составляет <math>\Theta(n)</math>. Неясно, для какого предела k/m можно получить среднее линейное время выполнения.

Эта задача широко применяется в вычислительной биологии (для сравнения последовательностей ДНК и белков, восстановления после ошибок экспериментов, а также для выявления точек мутаций или прогнозирования сходства в структуре или функции), для текстового информационного поиска (для восстановления после ошибок транскрипции, набора, typing или автоматического распознавания), обработки сигналов (для восстановления после ошибок при передаче и искажений) и в некоторых других областях. Подробнее об этом см. обсуждение в работе [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 можно получить среднее время O(n); до настоящего момента его удавалось получить для <math>k/m = 1/2 - O(1 / \sqrt{\sigma})</math>.

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

* [[Приближенное сравнение регулярных выражений – более сложный случай, где P может быть регулярным выражением]]

* [[Индексированное приближенное сравнение строк относится к случаю, при котором возможна предварительная обработка текста]]

* [[Локальное выравнивание (с вогнутыми штрафами за пропуски) относится к более сложной схеме с весами]]

* [[Последовательное точное сравнение строк – упрощенная версия, в которой ошибки не допускаются]]