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

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

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

Популярным обобщением всех вышеперечисленных вариантов является ''взвешенное расстояние редактирования'', при котором операциям присваиваются положительные вещественные веса, а расстояние является минимальной суммой весов последовательности операций, преобразующих одну строку в другую. Вес операции удаления символа c обозначим за <math>w(c \to e)</math>, вес операции вставки c – за <math>w( \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).

<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 с использованием расстояния редактирования с единичной стоимостью.'''