Алгоритм Ландау-Вишкина (k несовпадений)
Постановка задачи: дано число текст и образец , . Требуется найти все подстроки текста длины , с не более чем несовпадающими символами с образцом. Эту задачу решает алгоритм Ландау-Вишкина (k несовпадений) (англ.Landau-Vishkin Algorithm)
Алгоритм
Идея
При анализе используется двумерный массив несовпадений текста , содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его -й строке содержатся позиции в первых несовпадений между строками и . Таким образом, если , то , и это -е несовпадение между и , считая слева направо. Если число несовпадений с подстрокой меньше , то, начиная с , элементы -й строки равны значению по умолчанию . (См. пример).
Заметим, если , то подстрока отличается от образца не более, чем на символов, и, таким образом, является решением задачи.
Затем образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации с образцом сравнивается подстрока . Пусть — это самая правая позиция в тексте, достигнутая за предыдущие итерации, то есть является максимальным из чисел , где . Если , в присваивается результат работы , которая находит количество несовпадений между и . Если не превышает , вызывается процедура , которая сравнивает подстроки и , где изменяется таблица текстовых несовпадений. Переменная будет рассмотрена ниже.
|
int[][] algorithmLandauViskin(y : string, x : string)
n = y.length
m = x.length
tm[0...n - m][1...k + 1] = m + 1 // инициализация
r = 0
j = 0
for i = 0 to n - m
b = 0
if i < j
b = merge(i, r, j)
if b < k + 1
r = i
extend(i, j, b)
return tm
|
Процедура extend
Рассмотрим процедуру подробнее. Она сравнивает подстроки и , в случае несовпадения увеличивается и таблица текстовых несовпадений обновляется. Это происходит пока либо не будет найдено несовпадений (учитывая несовпадения, которые были найдены раньше на -ой итерации), либо не будет достигнуто с не больше чем несовпадениями, то есть найдено вхождение образца, начинающееся с .
|
void extend(i : int, j : int, b : int)
while (b < k + 1) and (j - i < m)
j++
if y[j] x[j-1]
b++
tm[i][b] = j - i
|
Процедура merge
Рассмотрим процедуру подробнее. Она находит количество несовпадений между и и устанавливает равным найденному числу, при этом используется полученная ранее информация. Введем — это строка таблицы несовпадений, в которой есть информация о несовпадениях, полученных при совмещении начала образца и . Текущий номер самой правой из проверенных на настоящий момент позиции текста равен . Поэтому при обработки подстроки начинающейся с , можно учитывать информацию в -ой строке , которая содержит информацию о сопоставлении образца с . Подходящими значениями из таблицы несовпадений являются, таким образом, , где — это наименьшее из целых чисел, для которых . Однако, следует учитывать тот факт, что эти несовпадения соответствуют началу образца, который был выровнен с , в то время как текущая позиция образца выровнена с — разница в мест.
Также в алгоритме используется двумерный массив несовпадений образца , генерируемой на стадии предварительной обработки образца. В нем содержатся позиции несовпадения образца с самим собой при различных сдвигах, аналогично , то ест—ь в -ой строке содержатся позиции внутри первых несовпадений между подстроками и . Таким образом, если , то , и это -е несовпадение между и слева направо. Если число несовпадений между этими строками меньше , то, начиная с , элементы -й строки равны , значению по умолчанию. Построение будет подробнее рассмотрено позднее.
Таким образом, для интерес представляет строка таблицы несовпадений образца, причем используются значения , где — самое правое несовпадение в , такое, что , так как требуются только несовпадения в подстроке .
Чтобы использовать упомянутую информацию в процедуре , рассмотрим в тексте позицию , находящуюся в диапазоне, . Рассмотрим следующие условия для позиции :
Условие A: когда символы и совмещены, позиция в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть , и это несовпадение номер , где , то есть .
Условие B: для двух копий образца, со сдвигом относительно друг друга , совмещенных с текстом так, что их начальные символы лежат, соответственно, над и , позиция соответствует несовпадению между двумя образцам, то есть . Это -е несовпадение при этом сдвиге, где , то есть .
Вспомним, что нас интересует, совпадает ли символ текста в позиции с соответствующими символом образца, когда совмещен с , то есть верно ли, что . Рассмотрим этот вопрос при разных комбинациях указанных выше условий.
Случай 1: !A and !B: То есть, и , откуда . Нет необходимости сравнивать символ текста с символом образца, так как ясно, что в этой позиции они совпадают.
Случай 2: (A and !B) or (!A and B): В любом случае (если лишь условие A истинно, то и , откуда , с другой стороны, если выполнено только условие B, то и , и опять, ). Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом образца, так как известно, что они не совпадают.
Случай 3: A and B: В этом случае мы ничего не можем сказать о том, совпадают ли символы и , поэтому их надо сравнить.
Возвращаемся к процедуре . В случае 2, или если в случае 3 выявлено несовпадение символов, необходимо увеличить количество несовпадений символов на единицу и обновить . Соответствующими значениями таблицы для являются и . Переменные и в начале устанавливаются равными индексам первых элементов этих двух массивов, соответственно, и последовательно увеличиваются.
Условия окончания работы процедуры следующие:
- Если , то для случая, когда образец расположен относительно текста так, что совмещен с , обнаружено несовпадение, поэтому из процедуры можно выйти.
- Bспомним, что самая правая из интересующих нас позиций в , а именно, , равна , если , поэтому будет уже использовано для предыдущего значения , а именно, , и поэтому позиция должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры.
- Процедуру можно прервать, если и . Если выполняется вторая часть этого условия, то равняется , и соответствует суммам для последующих значений вплоть до . В этом случае процедура может быть прервана, если выполняется также первая часть приведенного условия, так как она указывает, что позиция текста фактически пропущена.
Остается показать, что число позиций несовпадений в таблице несовпадений образца достаточно для того, чтобы нашла все, или, если их больше , первые несовпадений для . Это можно показать следующим образом. Условие A выполняется не больше чем для позиции текста в диапазоне . Условие B выполняется для некоторого неизвестного числа позиций в этом же интервале. Строка в таблице несовпадений образца, , содержит не больше чем позиций несовпадений между двумя копиями образца, с соответствующим сдвигом . Если , то таблица содержит все позиции несовпадения образца самим с собой, у которых условие B выполняется для позиций текста в интервале . С другой стороны, если , то таблица может дать позиций текста в диапазоне , для которых выполняется условие B. Поскольку , в диапазоне имеется до позиций текста, для которых выполняется условие A. Таким образом, в худшем случае может быть позиций, для которых имеет место случай 3, и которые требуется сравнить напрямую. Остается по крайней мере позиций, удовлетворяющих условию B, но не условию A (случай 2), что является достаточным, чтобы заключить, что для данного положения образца относительно текста имеется не меньше несовпадений между текстом и образцом.
|
int merge(i : int, r : int, j : int) u = 1 v = q while (b < k + 1) and (v < k + 2) and (i + pm[i - r][u] < j or tm[r][v] m + 1) if i + pm[i - r][u] > r + tm[r][v] // Случай 2, условие A b++ tm[i][b] = tm[r][v] - (i - r) v++ else if i + pm[i - r][u] < r + tm[r][v] // Случай 2, условие B b++ tm[i][b] = pm[i - r][u] u++ else if i + pm[i - r][u] = r + tm[r][v] // Случай 3 if x[pm[i - r][u]] y[i + pm[i - r][u]] b++ tm[i][b] = pm[i - r][u] u++ v++ return b
|
Построение pm
Теперь осталось только обратиться к вычислению таблицы несовпадений образца на стадии предварительных вычислений. Не теряя общности, можно предположить, что является некоторой степенью . В алгоритме предварительной обработки используется разбиение множества из строк на следующие подмножеств:
Алгоритм состоит из этапов. На этапе , где , вычисляются строки в множестве , где множество — это .
Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста. Рассмотрим алгоритм для этапа . На стадии входами для алгоритма анализа образца являются подстроки образца и , которые трактуются здесь, соответственно, как образец и текст, и массив , содержащий выходы предыдущих стадий. Выходы стадии вводятся в . За исключением стадии , на которой находят до несовпадений, на стадии для каждой строки требуется найти до несовпадений, а не до , как в алгоритме анализа текста.
|
void precalcPm () pm[...][1...min{, }] = m + 1 r = j = for i = to b = 0 if i < j b = merge(i, r, j) if b < min{} r = i extend(i, j, b)
|
Оценка сложности
Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур и , каждая из итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время . Общее число операций, выполняемых процедурой во время вызовов равно , так как она проверяет каждый символ текста не больше одного раза. Процедура при каждом вызове обрабатывает массив и , которые в сумме имеют элементов. Время работы можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное . Таким образом, можно видеть, что общее время анализа текста составляет .
Рассмотрим построение . Используя аргументы, аналогичные применявшимся при проверке корректности процедуры , можно показать, что для нахождения требуемого количества несовпадений на стадии требуется позиций, для которых выполняется условие B, и в особом случае, а именно, на стадии , требуется таких позиций.
На каждой стадии из стадий анализа образца цикл производит итераций . Если не считать время работы процедур и , каждая итерация требует фиксированного времени. Для всех итераций на шаге процедуре требуется время . Ранее было показано, что время работы пропорционально числу искомых несовпадений. Таким образом, каждый вызов занимает время , что равно . Таким образом, общее время для стадии равно = . Проведя суммирование по всем стадиям, получаем общее время счета . Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны .
Пример
Пусть , , .
| tm | 1 | 2 | 3 | x[1..m] | y[i+1..i+m] |
| 0 | 2 | 3 | 4 | tram | thet |
| 1 | 1 | 2 | 3 | tram | hetr |
| 2 | 1 | 2 | 3 | tram | etri |
| 3 | 3 | 4 | 5 | tram | trip |
| 4 | 1 | 2 | 3 | tram | ripp |
| 5 | 1 | 2 | 3 | tram | ippe |
| 6 | 1 | 2 | 3 | tram | pped |
| 7 | 1 | 2 | 3 | tram | pedt |
| 8 | 1 | 2 | 3 | tram | edtr |
| 9 | 1 | 2 | 3 | tram | dtra |
| 10 | 4 | 5 | 5 | tram | trap |
| pm | 1 | 2 | 3 | 4 | 5 | x[1..m-i] | x[i+1..m] |
| 1 | 1 | 2 | 3 | 5 | 5 | tra | ram |
| 2 | 1 | 2 | 5 | 5 | 5 | tr | am |
| 3 | 1 | 5 | 5 | 5 | 5 | t | m |
