Алгоритм Ландау-Вишкина (k различий)

Чтобы решить задачу [math]k[/math] различий, матрицу расстояний [2] надо преобразовать таким образом, чтобы [math]d_[/math] представлял минимальное расстояние между [math]x(0, i-1)[/math] и любой подстрокой [math]y[/math] , заканчивающейся символом [math]y_j[/math] . Для этого достаточно ввести условие:

[math]d_ = 0, 0 \lt j \lt n[/math]

так как минимальное расстояние между [math]\varepsilon[/math] и любой подстрокой y равно [math]0[/math] .

Оставшуюся часть матрицы вычислим с использованием цен редактирования расстояния Левенштейна и рекуррентного соотношения для [math]d_[/math] :

Теперь каждое значение, не превосходящее [math]k[/math] , в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше [math]k[/math] отличий от образца.

Рассмотрим этот подход к решению задачи на примере: пусть

Построим матрицу расстояний для этого случая:

j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 i a c e a b p c q d e a b c r 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 a 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 2 b 2 1 1 2 1 0 1 2 2 2 2 1 0 1 2 3 c 3 2 1 2 2 1 1 1 2 3 3 2 1 3 1 4 d 4 3 2 2 3 2 2 2 2 2 3 3 2 1 1 5 e 5 4 3 2 3 3 3 3 3 3 2 3 3 2 2

Последняя строка матрицы показывает, что вхождения образца с точностью до [math]2[/math] отличий, заканчиваются в позициях [math]3[/math] , [math]10[/math] , [math]13[/math] и [math]14[/math] . Соответствующими подстроками являются [math]ace[/math] , [math]abpcqde[/math] , [math]abc[/math] и [math]abcr[/math] .

Алгоритм [ править ]

Пронумеруем диагонали матрицы расстояния целыми числами [math]p \in [-m, n][/math] , таким образом, чтобы диагональ [math]p[/math] состояла из элементов [math](i, j)[/math] , у которых [math]j - i = p[/math] . Пусть [math]r_[/math] представляет наибольшую строку [math]i[/math] , у которой [math]d_ = q[/math] и [math](i, j)[/math] лежит на диагонали [math]p[/math] . Таким образом, [math]q[/math] — это минимальное число различий между [math]x(0, r_-1)[/math] и любой подстрокой текста, заканчивающейся [math]y_[/math] . Значение [math]m[/math] в строке [math]r_[/math] , для [math]q \lt k[/math] , указывает, что в тексте имеется вхождение образца с точностью до [math]k[/math] отличий, заканчивающееся в [math]y_[/math] . Таким образом, чтобы решить задачу [math]k[/math] различий, достаточно вычислить значения [math]r_[/math] для [math]q \lt k[/math] .

Рассмотрим алгоритм вычисления [math]r_[/math] .

Алгоритм вычисляет значения [math]r_[/math] на [math]n+k+1[/math] диагоналях. Для каждой диагонали переменной строки [math]r[/math] можно присвоить не больше [math]m[/math] различных значений, что приводит к времени вычислений [math]O(mn)[/math] . Рассмотрим как можно ускорить решение этой задачи, используя другие методы.

На этапе предварительной обработки, с помощью алгоритма Укконена строится суффиксное дерево строки [math]yx[/math] , где [math]\#[/math] и [math]\$[/math] — символы, не принадлежащие алфавиту, над которыми построены строки [math]x[/math] и [math]y[/math] . Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алгоритм можно преобразовать так, что он будет выполняться за время [math]O(n\log)[/math] , где [math]\sigma[/math] — число различающихся символов образца. Стадия предварительной обработки требует время [math]O(n)[/math] и [math]O(n\log)[/math] для постоянного и неограниченного алфавитов, соответственно.

В приведенном выше алгоритме перед циклом [math]\mathrm[/math] для диагонали [math]p[/math] , переменной [math]r[/math] было присвоено такое значение, что [math]x(0, r - 1)[/math] сопоставляется с точностью до [math]k[/math] различий с некоторой подстрокой текста, заканчивающейся [math]y_[/math] . Тогда функция цикла [math]\mathrm[/math] находит максимальное значение для которого [math]x(r+1, r+h) = y(r+p+1, r+p+h)[/math] . Обозначим это значение как [math]h[/math] . Это эквивалентно нахождению длины самого длинного общего префикса суффиксов [math]x(r+1, m)\$[/math] и [math]y(r+p+1,n)x[/math] предварительно вычисленной конкатенированной строки. Символ [math]\#[/math] используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как [math]y[/math] , так и [math]x[/math] . Обозначим [math]lca(r,p)[/math] как самый низкий общий предок в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение [math]h[/math] задается [math]length(lca(r,p))[/math] .

Суффиксное дерево имеет [math]O(n)[/math] узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам [math]lca[/math] требуется преобразование дерева, проводимое за линейное время. Значения [math]r_[/math] вычисляются на [math]n+k+1[/math] диагоналях. Более того, для каждой диагонали надо вычислить [math]k+1[/math] таких значений, что в общей сложности дает [math]O(kn)[/math] запросов. Таким образом, общее время работы алгоритма k различий составляет [math]O(kn)[/math] для алфавитов фиксированного размера, и [math]O(n \cdot \log + kn)[/math] для неограниченных алфавитов.

В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до [math]O(\log+k)[/math] , при использовании одновременно [math]n[/math] процессоров. Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос [math]lca[/math] за [math]O(1)[/math] .