Алгоритм Ландау-Вишкина (k несовпадений)
Постановка задачи: Дано число текст и образец , . Требуется найти все подстроки текста длины , с не более чем несовпадающими символами с образцом. Эту задачу решает алгоритм Ландау-Вишкина (k несовпадений) (англ.Landau-Vishkin Algorithm)
Алгоритм
Идея
При анализе используется двумерный массив несовпадений текста , содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его -й строке содержатся позиции в первых несовпадений между строками и . Таким образом, если , то , и это -е несовпадение между и , считая слева направо. Если число несовпадений с подстрокой меньше , то, начиная с , элементы -й строки равны значению по умолчанию .
Заметим, если , то подстрока отличается от образца не более, чем на символов, и, таким образом, является решением задачи.
Затем образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации с образцом сравнивается подстрока . - обозначим самую правую позицию в тексте, достигнутую за предыдущие итерации, то есть является максимальным из чисел , где . Если , в присваивается результат работы , которая находит количество несовпадений между и . Если не превышает , вызывается процедура , которая сравнивает подстроки и , где изменяется таблица текстовых несовпадений. Переменная будет рассмотрена ниже.
|
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)
|
Процедура extend
Рассмотрим процедуру подробнее. Она сравнивает подстроки и , в случае несовпадения увеличивается и таблица текстовых несовпадений обновляется. Это происходит пока либо не будет найдено несовпадений (учитывая несовпадения, которые были найдены раньше на -ой итерации), либо не будет достигнуто с не больше чем несовпадениями, то есть найдено вхождение образца, начинающееся с .
|
extend(i, j, b)
while (b < k + 1) and (j - i < m)
j++
if y[j] != x[j-1]
b++
tm[i][b] = j - i
|
Процедура merge
Рассмотрим процедуру подробнее. Она находит количество несовпадений между и и устанавливает b равным найденному числу, при этом используется полученная ранее информация. Введем - это строка таблицы несовпадений, в которой есть информация о несовпадениях, полученных при совмещении начала образца и . содержит текущий номер самой правой из проверенных на настоящий момент позиций текста. Поэтому при обработки подстроки начинающейся с , можно учитывать информацию в -ой строке , которая содержит информацию о сопоставлении образца с . Подходящими значениями из таблицы несовпадений являются, таким образом, , где – это наименьшее из целых чисел, для которых . Однако, следует учитывать тот факт, что эти несовпадения соответствуют началу образца, который был выровнен с , в то время как текущая позиция образца выровнена с – разница в мест.
Также в алгоритме используется двумерный массив несовпадений образца , генерируемой на стадии предварительной обработки образца. В нем содержатся позиции несовпадения образца с самим собой при различных сдвигах, аналогично , то есть в -ой строке содержатся позиции внутри первых несовпадений между подстроками и . Таким образом, если , то , и это -е несовпадение между и слева направо. Если число несовпадений между этими строками меньше , то, начиная с , элементы -й строки равны , значению по умолчанию. Построение будет подробнее рассмотрено позднее.
Таким образом, для интерес представляет строка таблицы несовпадений образца, причем используются значения , где – самое правое несовпадение в , такое, что , так как требуются только несовпадения в подстроке .
Чтобы использовать упомянутую информацию в процедуре , рассмотрим в тексте позицию , находящуюся в диапазоне, . Рассмотрим следующие условия для позиции :
Условие A: когда символы и совмещены, позиция в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть , и это несовпадение номер , где , то есть .
Условие B: для двух копий образца, со сдвигом относительно друг друга , совмещенных с текстом так, что их начальные символы лежат, соответственно, над и , позиция соответствует несовпадению между двумя образцам, то есть . Это -е несовпадение при этом сдвиге, где , то есть = .
Вспомним, что нас интересует, совпадает ли символ текста в позиции с соответствующими символом образца, когда совмещен с , то есть верно ли, что . Рассмотрим этот вопрос при разных комбинациях указанных выше условий.
Случай 1: !A and !B: То есть, и , откуда . Нет необходимости сравнивать символ текста с символом образца, так как ясно, что в этой позиции они совпадают.
Случай 2: (A and !B) or (!A and B): В любом случае (если лишь условие истинно, то и , откуда , с другой стороны, если выполнено только условие , то и , и опять, ). Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом образца, так как известно, что они не совпадают.
Случай 3: A and B: В этом случае мы ничего не можем сказать о том, совпадают ли символы и , поэтому их надо сравнить.
Возвращаемся к процедуре merge. В случае 2, или если в случае 3 выявлено несовпадение символов, необходимо увеличить количество несовпадений символов на единицу и обновить . Соответствующими значениями таблицы для являются и . Переменные и в начале устанавливаются равными индексам первых элементов этих двух массивов, соответственно, и последовательно увеличиваются.
Условия окончания работы процедуры следующие:
- Если , то для случая, когда образец расположен относительно текста так, что совмещен с , обнаружено несовпадение, поэтому из процедуры можно выйти.
- Bспомним, что самая правая из интересующих нас позиций в , а именно, , равна , если , поэтому будет уже использовано для предыдущего значения , а именно, , и поэтому позиция должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры.
- Процедуру можно прервать, если и . Если выполняется вторая часть этого условия, то равняется , и соответствует суммам для последующих значений вплоть до . В этом случае процедура может быть прервана, если выполняется также первая часть приведенного условия, так как она указывает, что позиция текста фактически пропущена.
Остается показать, что число позиций несовпадений в таблице несовпадений образца достаточно для того, чтобы нашла все, или, если их больше , первые несовпадений для . Это можно показать следующим образом. Условие A выполняется не больше чем для позиции текста в диапазоне . Условие B выполняется для некоторого неизвестного числа позиций в этом же интервале. Строка в таблице несовпадений образца, , содержит не больше чем позиций несовпадений между двумя копиями образца, с соответствующим сдвигом . Если , то таблица содержит все позиции несовпадения образца самим с собой, у которых условие B выполняется для позиций текста в интервале . С другой стороны, если , то таблица может дать позиций текста в диапазоне , для которых выполняется условие B. Поскольку , в диапазоне имеется до позиций текста, для которых выполняется условие A. Таким образом, в худшем случае может быть позиций, для которых имеет место случай 3, и которые требуется сравнить напрямую. Остается по крайней мере позиций, удовлетворяющих условию B, но не условию A (случай 2), что является достаточным, чтобы заключить, что для данного положения образца относительно текста имеется не меньше несовпадений между текстом и образцом.
|
merge(i, r, j, b)
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 // Случай 3
I + PM[I - R, U] = R + TM[R, V]
if x[ pm[i-r][u] ] != y[ i+pm[i-r][u] ]
b++
tm[i][b] = pm[i - r][u]
u++
v++
|
Построение pm
Теперь осталось только обратиться к вычислению таблицы несовпадений образца на стадии предварительных вычислений. Не теряя общности, можно предположить, что является некоторой степенью . В алгоритме предварительной обработки используется разбиение множества из строк на следующие подмножеств:
Алгоритм состоит из этапов. На этапе , где , вычисляются строки в множестве , где множество – это .
Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста. Рассмотрим алгоритм для этапа . На стадии входами для алгоритма анализа образца являются подстроки образца и , которые трактуются здесь, соответственно, как образец и текст, и массив , содержащий выходы предыдущих стадий. Выходы стадии вводятся в pm. За исключением стадии , на которой находят до несовпадений, на стадии для каждой строки требуется найти до несовпадений, а не до , как в алгоритме анализа текста.
|
pm[...][1...min{, }] = m+1 r = j = for i = to b = 0 if i < j merge(I, R, J, B) if b < min{} r = i extend(i, j, b)
|
Оценка работы
Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур и , каждая из итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время . Общее число операций, выполняемых процедурой во время вызовов равно , так как она проверяет каждый символ текста не больше одного раза. Процедура при каждом вызове обрабатывает массив и , которые в сумме имеют элементов. Время работы можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное . Таким образом, можно видеть, что общее время анализа текста составляет .
Рассмотрим построение Используя аргументы, аналогичные применявшимся при проверке корректности процедуры merge, можно показать, что для нахождения требуемого количества несовпадений на стадии s требуется позиций, для которых выполняется условие 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 |
| tm | 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 |
