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

Задача:

По заданному слову [math]x[0..m-1][/math] найти в тексте или словаре [math]y[0..n-1][/math] все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом [math]k[/math] возможных различий.

В данном случае под различием подразумевается расстояние Левенштейна — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.

Например, при запросе [math]abcdef[/math] и [math]k = 2[/math], найти слова [math]abcdeRf[/math], [math]abHdef[/math], [math]VbRdef[/math] и так далее.

Описание задачи с точки зрения динамического программирования

Алгоритм k различий Ландау-Вишкина основан на подходе, близком методу динамического программирования для вычисления расстояния между строками, который предложил Укконен. Перед тем, как перейти к этому алгоритму, рассмотрим метод динамического программирования и его адаптацию в стиле Укконена.

Пусть [math]d_{i,j}[/math] — расстояние между префиксами строк [math]x[/math] и [math]y[/math], длины которых равны, соответственно, [math]i[/math] и [math]j[/math], то есть [math]d_{i,j} = d(x(0,i-1), y(0,j-1))[/math]. Перед тем, как начать вычислять [math]d_{i,j}[/math], надо установить граничные значения массива. Что касается первого столбца массива, то значение [math]d_{i,0}[/math] равно сумме цен удаления первых [math]i[/math] символов [math]x[/math]. Аналогично, значения [math]d_{0,j}[/math] первой строки задаются суммой цен вставки первых [math]j[/math] символов [math]y[/math]. Таким образом:

[math]d_{0,0} = 0[/math]

[math]d_{i,0} = \sum\limits_{k = 1}^{i}{w(x_i, \varepsilon)}, для 1 \lt i \lt m[/math]

[math]d_{0,j} = \sum\limits_{k = 1}^{j}{w(\varepsilon, j_k)}, для 1 \lt j \lt n[/math]

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

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

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

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

[math]w(a,{\varepsilon}) = 1[/math]

[math]w({\varepsilon}, b) = 1[/math]

[math]w(a, b) = \left\{\begin{array}{llcl} 0&,\ a \ne b\\ 1&,\ a = b\\ \end{array}\right. [/math]

[math]d_{i,j} = \min(d_{i-1,j} + w(x_i,{\varepsilon}), d_{i,j-1} + w({\varepsilon}, y_j), d_{i-1,j-1} + w(x_i, y_i))[/math]

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

Пример

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

[math]x = abcde[/math],

[math]y = aceabpcqdeabcr[/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_{p,q}[/math] представляет наибольшую строку [math]i[/math], у которой [math]d_{i,j} = q[/math] и [math](i, j)[/math] лежит на диагонали [math]p[/math]. Таким образом, [math]q[/math] — это минимальное число различий между [math]x(0, r_{p,q}-1)[/math] и любой подстрокой текста, заканчивающейся [math]y_{r_{p,q}+p}[/math]. Значение [math]m[/math] в строке [math]r_{p,q}[/math], для [math]q \lt k[/math], указывает, что в тексте имеется вхождение образца с точностью до [math]k[/math] отличий, заканчивающееся в [math]y_{m+p}[/math]. Таким образом, чтобы решить задачу [math]k[/math] различий, достаточно вычислить значения [math]r_{p,q}[/math] для [math]q \lt k[/math].

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

int[] rpq(int n, int m, int k, char[] x, char[] y)
   for p = 0 to n
      r(p, -1) = -1
   for p = -(k + 1) to -1
      r(p, |p| - 1) = |p| - 1
      r(p, |p| - 2) = |p| - 2
   for q = -1 to k
      r(n + 1, q) = -1
   for q = 0 to k
     for p = -q to n
        r = max(r(p, q - 1) + 1, r(p - 1, q - 1), r(p + 1, q - 1) + 1)
        r = min(r, m)
        while r < m and r + p < n and x(r + 1) = y(r + 1 + p)
           r++
        r(p, q) = r
        if r(p, q) = m
           // имеется вхождение с k отличиями, заканчивающееся в y(p+m)
           res.add(y(p + m))
   return res

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

Предварительные вычисления

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

Модификация предыдущего алгоритма

В приведенном выше алгоритме перед циклом [math]while[/math] для диагонали [math]p[/math], переменной [math]r[/math] было присвоено такое значение, что [math]x(0, r - 1)[/math] сопоставляется с точностью до [math]k[/math] различий с некоторой подстрокой текста, заканчивающейся [math]y_{r+p}[/math]. Тогда функция цикла [math]\mathrm{while}[/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_{p,q}[/math] вычисляются на [math]n+k+1[/math] диагоналях. Более того, для каждой диагонали надо вычислить [math]k+1[/math] таких значений, что в общей сложности дает [math]O(k{\cdot}n)[/math] запросов. Таким образом, общее время работы алгоритма k различий составляет [math]O(k{\cdot}n)[/math] для алфавитов фиксированного размера, и [math]O(n \cdot \log{m} + k{\cdot}n)[/math] для неограниченных алфавитов.

Параллельная версия алгоритма

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

См. также

• Алгоритм Ландау-Вишкина (k несовпадений)

Источники информации

• algolist.manual.ru — алгоритм Ландау-Вишкина (k различий)
• Graham A. Stephen — String Searching Algorithms (Lecture Notes Series on Computing), ISBN 9810237030
• habrahabr.ru — Нечёткий поиск в тексте и словаре