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

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

Нетрудно доказать нижнюю границу как расширение границы Яо для точного сравнения строк [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 только к тем областям, которые не могут быть отброшены.

Эта задача широко применяется в вычислительной биологии (для сравнения последовательностей ДНК и белков, восстановления после ошибок экспериментов, а также для выявления точек мутаций или прогнозирования сходства в структуре или функции), для текстового информационного поиска (для восстановления после ошибок транскрипции, набора или автоматического распознавания), обработки сигналов (для восстановления после ошибок при передаче и искажений) и в некоторых других областях. Подробнее об этом см. обсуждение в работе [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, в противном случае битово-параллельные алгоритмы следует использовать автономно. Алгоритмы фильтрации легко допускают расширение с целью поддержки поиска по нескольким образцам одновременно.

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

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

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