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

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

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

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

Пусть даны текстовая строка [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 e) }[/math], вес операции вставки c – за [math]\displaystyle{ w( \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] строится на процессе вычисления взвешенного расстояния редактирования. Пусть A = a1 a 2.. am и B = b1 b 2.. bn – две строки, А C[0 … m, 0 … n] – матрица, такая, что C[i, j] = d(a1 … ai, b1 … bj). Тогда имеет место C[0;0] = 0 и bj)) =min(C[i- 1;j] + w(ai -+e), C[i,j + w( -> bj); C[i - 1; j - 1] + w(a, предполагая, что C[i; — 1] = C[—l,j] = 1. Вычисление матрицы требует времени O(mn), а d(A; B) = C[m; n]. Для решения задачи приближенного сравнения строк примем A = P и B = T и положим C[0; j] = 0 для всех j, так что вышеприведенная формула будет использоваться только для i > 0.

Теорема 1 (Селлерс, 1980 [ ]). Существует решение с временем выполнения 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 [ ]). Существует решение с временем выполнения O(n + mn/\ogcr n) в наихудшем случае для задачи ASM с использованием взвешенного расстояния редактирования. Более того, время составляет O(n + mnh/log n), где 0 < h < logcr – энтропия T.

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

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

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

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

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

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

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

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

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

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

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