Алгоритм Ландау-Вишкина (k различий)
| Задача: |
| По заданному слову найти в тексте или словаре все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом возможных различий. |
В данном случае под различием подразумевается расстояние Левенштейна — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Например, при запросе и , найти слова , , и так далее.
Содержание
Описание задачи с точки зрения динамического программирования
Алгоритм k различий Ландау-Вишкина основан на подходе, близком методу динамического программирования для вычисления расстояния между строками, который предложил Укконен[1]. Перед тем, как перейти к этому алгоритму, рассмотрим метод динамического программирования и его адаптацию в стиле Укконена.
Пусть — расстояние между префиксами строк и , длины которых равны, соответственно, и , то есть . Перед тем, как начать вычислять , надо установить граничные значения массива. Что касается первого столбца массива, то значение равно сумме цен удаления первых символов . Аналогично, значения первой строки задаются суммой цен вставки первых символов . Таким образом:
Чтобы решить задачу различий, матрицу расстояний[2] надо преобразовать таким образом, чтобы представлял минимальное расстояние между и любой подстрокой , заканчивающейся символом . Для этого достаточно ввести условие:
так как минимальное расстояние между и любой подстрокой y равно .
Оставшуюся часть матрицы вычислим с использованием цен редактирования расстояния Левенштейна и рекуррентного соотношения для :
Теперь каждое значение, не превосходящее , в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше отличий от образца.
Пример
Рассмотрим этот подход к решению задачи на примере: пусть
,
.
Построим матрицу расстояний для этого случая:
| 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 |
Последняя строка матрицы показывает, что вхождения образца с точностью до отличий, заканчиваются в позициях , , и . Соответствующими подстроками являются , , и .
Алгоритм
Пронумеруем диагонали матрицы расстояния целыми числами , таким образом, чтобы диагональ состояла из элементов , у которых . Пусть представляет наибольшую строку , у которой и лежит на диагонали . Таким образом, — это минимальное число различий между и любой подстрокой текста, заканчивающейся . Значение в строке , для , указывает, что в тексте имеется вхождение образца с точностью до отличий, заканчивающееся в . Таким образом, чтобы решить задачу различий, достаточно вычислить значения для .
Рассмотрим алгоритм вычисления .
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
Алгоритм вычисляет значения на диагоналях. Для каждой диагонали переменной строки можно присвоить не больше различных значений, что приводит к времени вычислений . Рассмотрим как можно ускорить решение этой задачи, используя другие методы.
Предварительные вычисления
На этапе предварительной обработки, с помощью алгоритма Укконена строится суффиксное дерево строки , где и — символы, не принадлежащие алфавиту, над которыми построены строки и . Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алгоритм можно преобразовать так, что он будет выполняться за время , где — число различающихся символов образца. Стадия предварительной обработки требует время и для постоянного и неограниченного алфавитов, соответственно.
Модификация предыдущего алгоритма
В приведенном выше алгоритме перед циклом для диагонали , переменной было присвоено такое значение, что сопоставляется с точностью до различий с некоторой подстрокой текста, заканчивающейся . Тогда функция цикла находит максимальное значение для которого . Обозначим это значение как . Это эквивалентно нахождению длины самого длинного общего префикса суффиксов и предварительно вычисленной конкатенированной строки. Символ используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как , так и . Обозначим как самый низкий общий предок в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение задается .
Оценка времени работы
Суффиксное дерево имеет узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам требуется преобразование дерева, проводимое за линейное время. Значения вычисляются на диагоналях. Более того, для каждой диагонали надо вычислить таких значений, что в общей сложности дает запросов. Таким образом, общее время работы алгоритма k различий составляет для алфавитов фиксированного размера, и для неограниченных алфавитов.
Параллельная версия алгоритма
В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до , при использовании одновременно процессоров. Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос за .
