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

Перейти к навигации Перейти к поиску
Строка 15: Строка 15:


== Основные результаты ==
== Основные результаты ==
Первое и наиболее универсальное решение этой задачи [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 с использованием расстояния редактирования с единичной стоимостью.
4430

правок

Навигация