Алгоритм Ландау-Вишкина (k различий)
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Задача: |
По заданному слову | найти в тексте или словаре все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом возможных различий.
В данном случае под различием подразумевается расстояние Левенштейна — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Например, при запросе
и , найти слова , , и так далее.Содержание
Описание задачи с точки зрения динамического программирования
Алгоритм 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 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до
, при использовании одновременно процессоров. Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос за .