Изменения

Перейти к: навигация, поиск

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

119 байт добавлено, 20:58, 16 июня 2014
Нет описания правки
'''Постановка задачи:''' Дано дано число <tex>k > 0</tex> текст <tex>y[1...n]</tex> и образец <tex>x[1...m]</tex>, <tex>m < n</tex>. Требуется найти все подстроки текста длины <tex>m</tex>, с не более чем <tex>k</tex> несовпадающими символами с образцом. Эту задачу решает алгоритм Ландау-Вишкина (k несовпадений) (''англ.Landau-Vishkin Algorithm'')
==Алгоритм==
===Идея===
[[Файл:algLandauVishkin1.png|thumb|250px|right| В таблицу <tex>tm </tex> по номеру несовпадения записывается соответстующий индекс образца, то есть <tex>tm[i][1] = a</tex>, <tex>tm[i][2] = b</tex>, <tex>tm[i][3] = c</tex> и т . д.]]
При анализе используется двумерный массив несовпадений текста <tex>tm[0...n-m][1...k+1]</tex>, содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его <tex>i</tex>-й строке содержатся позиции в <tex>x</tex> первых <tex>k+1</tex> несовпадений между строками <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>. Таким образом, если <tex>tm[i][v] = s</tex>, то <tex>y[i+s] \neq x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x[1...m]</tex> и <tex>y[i+1...i+m]</tex>, считая слева направо. Если число <tex>d</tex> несовпадений <tex>x[1...m]</tex> с подстрокой <tex>y[i+1...i+m]</tex> меньше <tex>k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны значению по умолчанию <tex>m+1</tex>.
Заметим, если <tex>tm[i][k+1] = m+1</tex>, то подстрока <tex>y[i+1...i+m]</tex> отличается от образца <tex>x</tex> не более, чем на <tex>k</tex> символов, и, таким образом, является решением задачи.
Затем образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации <tex>i</tex> с образцом сравнивается подстрока <tex>y[i+1...i+m]</tex>. <tex>j</tex> - обозначим самую правую позицию в тексте, достигнутую за предыдущие итерации, то есть <tex>j</tex> является максимальным из чисел <tex>r+tm[r][k + 1]</tex>, где <tex>0 \leqslant r < i</tex>. Если <tex>i < j</tex>, в <tex>b</tex> присваивается результат работы <tex>merge</tex>, которая находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex>. Если <tex>b</tex> не превышает <tex>k</tex>, вызывается процедура <tex>extend</tex>, которая сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>, где изменяется таблица текстовых несовпадений. Переменная <tex>r</tex> будет рассмотрена ниже.
{| border="0"
|align="left" colspan="4"|
<font size=2>
tm[0...n-m][1...k+1] = m+1 // инициализация
r = 0
j = 0
|}
===Процедура extend===
[[Файл:algLandauVishkin2.png|thumb|380px|right| Синие подстроки сравниваются в процедуре extend. <tex>w < k + 1</tex>]]
|}
===Процедура merge===
[[Файл:algLandauVishkin3.png|thumb|400px|right| Синие подстроки сравниваются в процедуре merge. Красным отмечены несовпадения.]]
Рассмотрим процедуру <tex>merge</tex> подробнее. Она находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex> и устанавливает <tex>b </tex> равным найденному числу, при этом используется полученная ранее информация. Введем <tex>r</tex> - это строка таблицы несовпадений, в которой есть информация о несовпадениях, полученных при совмещении начала образца и <tex>y[r+1]</tex>. <tex>r+tm[r][k+1]</tex> содержит текущий номер самой правой из проверенных на настоящий момент позиций текста. Поэтому при обработки подстроки начинающейся с <tex>y[i+1]</tex>, можно учитывать информацию в <tex>r</tex>-ой строке <tex>tm</tex>, которая содержит информацию о сопоставлении образца с <tex>y[i]</tex>. Подходящими значениями из таблицы несовпадений являются, таким образом, <tex>tm[r][q ... k+1]</tex>, где <tex>q</tex> – это наименьшее из целых чисел, для которых <tex>r+tm[r][q] > i</tex>. Однако, следует учитывать тот факт, что эти несовпадения соответствуют началу образца, который был выровнен с <tex>y[r+1]</tex>, в то время как текущая позиция образца выровнена с <tex>y[i+1]</tex> – разница в <tex>i - r</tex> мест.
[[Файл:algLandauVishkin4.png|thumb|250px|right| В таблицу pm по номеру несовпадения записывается соответствующий индекс верхнего образца, то есть <tex>pm[i][1] = a</tex>, <tex>pm[i][2] = b</tex>, <tex>pm[i][3] = c</tex> и т д.]]
Также в алгоритме используется двумерный массив несовпадений образца <tex>pm[1...m-1][1...2k+1]</tex>, генерируемой на стадии предварительной обработки образца. В нем содержатся позиции несовпадения образца с самим собой при различных сдвигах, аналогично <tex>tm</tex>, то есть в <tex>i</tex>-ой строке содержатся позиции внутри <tex>x</tex> первых <tex>2k+1</tex> несовпадений между подстроками <tex>x[1...m-i]</tex> и <tex>x[i+1...m]</tex>. Таким образом, если <tex>pm[i][v] = s</tex>, то <tex>x[i+s] \neq x[s]</tex>, и это <tex>v</tex>-е несовпадение между <tex>x([1, ...m-i)]</tex> и <tex>x([i+1, ...m)]</tex> слева направо. Если число <tex>d</tex> несовпадений между этими строками меньше <tex>2k+1</tex>, то, начиная с <tex>d+1</tex>, элементы <tex>i</tex>-й строки равны <tex>m+1</tex>, значению по умолчанию. Построение <tex>tm</tex> будет подробнее рассмотрено позднее.
Таким образом, для <tex>merge</tex> интерес представляет строка <tex>i - r</tex> таблицы несовпадений образца, причем используются значения <tex>pm[i-r][1...t]</tex>, где <tex>t</tex> – самое правое несовпадение в <tex>pm[i-r][1...2k+1]</tex>, такое, что <tex>pm[i-r][t] < j-i+1</tex>, так как требуются только несовпадения в подстроке <tex>x[1...j-i]</tex>.
[[Файл:algLandauVishkin5.png|380px]]
'''Условие B''': для двух копий образца, со сдвигом относительно друг друга <tex>i - r</tex>, совмещенных с текстом так, что их начальные символы лежат, соответственно, над <tex>y[r+1]</tex> и <tex>y[i+1]</tex>, позиция <tex>p</tex> соответствует несовпадению между двумя образцам, то есть <tex>x[p-r] \neq x[p-i]</tex>. Это <tex>u</tex>-е несовпадение при этом сдвиге, где <tex>1 < u < t</tex>, то есть <tex>p-i</tex> = <tex>pm[i-r][u]</tex>.
[[Файл:algLandauVishkin6.png|450px]]
'''Случай 1: !A and !B:''' То есть, <tex>y[p] = x[p-r]</tex> и <tex>x[p-r] = x[p-i]</tex>, откуда <tex>y[p] = x[p-i]</tex>. Нет необходимости сравнивать символ текста с символом образца, так как ясно, что в этой позиции они совпадают.
'''Случай 2: (A and !B) or (!A and B):''' В любом случае <tex>y[p] \neq x[p-i]</tex> (если лишь ''условие <tex>A</tex> '' истинно, то <tex>y[p] \neq x[p-r]</tex> и <tex>x[p-r] = x[p-i]</tex>, откуда <tex>y[p] \neq x[p-i]</tex>, с другой стороны, если выполнено только ''условие <tex>B</tex>'', то <tex>y[p] = x[p-r]</tex> и <tex>x[p-r] \neq x[p-i]</tex>, и опять, <tex>y[p] \neq x[p-i]</tex>). Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом образца, так как известно, что они не совпадают.
'''Случай 3: A and B:''' В этом случае мы ничего не можем сказать о том, совпадают ли символы <tex>y[p]</tex> и <tex>x[p-i]</tex>, поэтому их надо сравнить.
Возвращаемся к процедуре <tex>merge</tex>. В ''случае 2'', или если в ''случае 3 '' выявлено несовпадение символов, необходимо увеличить количество несовпадений символов <tex>b</tex> на единицу и обновить <tex>tm[i][b]</tex>. Соответствующими значениями таблицы для <tex>merge</tex> являются <tex>tm[i-r][1...t]</tex> и <tex>tm[r][q...k+1]</tex>. Переменные <tex>u</tex> и <tex>v</tex> в начале устанавливаются равными индексам первых элементов этих двух массивов, соответственно, и последовательно увеличиваются.
Условия окончания работы процедуры следующие:
* Процедуру можно прервать, если <tex>i+pm[i-r][u] > j</tex> и <tex>tm[r][v] = m+1</tex>. Если выполняется вторая часть этого условия, то <tex>r+tm[r][v]</tex> равняется <tex>j</tex>, и соответствует суммам для последующих значений <tex>v</tex> вплоть до <tex>k+1</tex>. В этом случае процедура может быть прервана, если выполняется также первая часть приведенного условия, так как она указывает, что позиция текста <tex>j</tex> фактически пропущена.
Остается показать, что число позиций несовпадений в таблице несовпадений образца достаточно для того, чтобы <tex>merge</tex> нашла все, или, если их больше <tex>k+1</tex>, первые <tex>k+1</tex> несовпадений для <tex>y[i+1...j]</tex>. Это можно показать следующим образом. ''Условие A '' выполняется не больше чем для <tex>k+1</tex> позиции текста в диапазоне <tex>y[i+1...j]</tex>. ''Условие B '' выполняется для некоторого неизвестного числа позиций в этом же интервале. Строка <tex>i-r</tex> в таблице несовпадений образца, <tex>tm[i-r][1...2k+1]</tex>, содержит не больше чем <tex>2k+1</tex> позиций несовпадений между двумя копиями образца, с соответствующим сдвигом <tex>i-r</tex>. Если <tex>pm[i-r][2k+1] > j - i</tex>, то таблица содержит все позиции несовпадения образца самим с собой, у которых ''условие B '' выполняется для позиций текста в интервале <tex>y[i+1...j]</tex>. С другой стороны, если <tex>pm[i-r][2k+1] < j-i</tex>, то таблица может дать <tex>2k+1</tex> позиций текста в диапазоне <tex>y[i+1...j-1]</tex>, для которых выполняется ''условие B''. Поскольку <tex>j = r+tm[r][k+1]</tex>, в диапазоне <tex>y[i+1...j-1]</tex> имеется до <tex>k</tex> позиций текста, для которых выполняется ''условие A''. Таким образом, в худшем случае может быть <tex>k</tex> позиций, для которых имеет место ''случай 3'', и которые требуется сравнить напрямую. Остается по крайней мере <tex>k+1</tex> позиций, удовлетворяющих ''условию B'', но не ''условию A '' (''случай 2''), что является достаточным, чтобы заключить, что для данного положения образца относительно текста имеется не меньше <tex>k+1</tex> несовпадений между текстом и образцом.
{| border="0"
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]
|}
===Построение pm===
Теперь осталось только обратиться к вычислению таблицы несовпадений образца на стадии предварительных вычислений. Не теряя общности, можно предположить, что <tex>m</tex> является некоторой степенью <tex>2</tex>. В алгоритме предварительной обработки используется разбиение множества <tex>{1, 2, ... , m-1}</tex> из <tex>m-1</tex> строк <tex>pm</tex> на следующие <tex>\log m</tex> подмножеств:
Алгоритм состоит из <tex>\log m</tex> этапов. На этапе <tex>s</tex>, где <tex>1 \leqslant s < \log m</tex>, вычисляются строки <tex>pm</tex> в множестве <tex>s</tex>, где множество <tex>s</tex> {{---}} это <tex>\{2{s-1}, ... , 2^{s}-1\}</tex>.
Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста. Рассмотрим алгоритм для этапа <tex>s</tex>. На стадии <tex>s</tex> входами для алгоритма анализа образца являются подстроки образца <tex>x[1...m-2^{s-1}]</tex> и <tex>x[2^{s-1}+1...m]</tex>, которые трактуются здесь, соответственно, как образец и текст, и массив <tex>pm[1...2^{s-1}-1][1...\min\{2^{log(m)-s}4k+1, m-2^{s-1}\}]</tex>, содержащий выходы предыдущих <tex>s - 1</tex> стадий. Выходы стадии <tex>s</tex> вводятся в <tex>pm</tex>. За исключением стадии <tex>\log m</tex>, на которой находят до <tex>2k+1</tex> несовпадений, на стадии <tex>s</tex> для каждой строки <tex>pm</tex> требуется найти до <tex>\min\{2^{log(m)-s}2k+1, m-2^{s}\}</tex> несовпадений, а не до <tex>k+1</tex>, как в алгоритме анализа текста.
{| border="0"
|align="left" colspan="4"|
<font size=2>
pm[<tex>2^{s-1}</tex>...<tex>2^{s}-1</tex>][1...min{<tex>2^{\log (m-1)}2k-1</tex>, <tex>m-2^{s}</tex>}] = m+1
r = <tex>2^{s-1}</tex>
j = <tex>2^{s-1}</tex>
if i < j
merge(i, r, j, b)
if b < min{<tex>2^{log(m-1)}2k-1, m-2^{s} </tex>}
r = i
extend(i, j, b)
|}
===Оценка работы===
Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур <tex>merge</tex> и <tex>extend</tex>, каждая из <tex>n-m+1</tex> итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время <tex>O(n)</tex>. Общее число операций, выполняемых процедурой <tex>extend</tex> во время вызовов равно <tex>O(n)</tex>, так как она проверяет каждый символ текста не больше одного раза. Процедура <tex>merge</tex> при каждом вызове обрабатывает массив <tex>pm[i-r][1...2k+1]</tex> и <tex>tm[r][1...k+1]</tex>, которые в сумме имеют <tex>3k+2</tex> элементов. Время работы <tex>merge</tex> можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное <tex>O(k)</tex>. Таким образом, можно видеть, что общее время анализа текста составляет <tex>O(nk)</tex>.
Рассмотрим построение <tex>pm</tex>. Используя аргументы, аналогичные применявшимся при проверке корректности процедуры merge, можно показать, что для нахождения требуемого количества несовпадений на стадии s требуется <tex>\min\{2^{log(m)-s}4k+1, m-2^{s}\}</tex> позиций, для которых выполняется условие B, и в особом случае, а именно, на стадии <tex>\log m</tex>, требуется <tex>4k + 1</tex> таких позиций.
На каждой стадии <tex>s</tex> из <tex>\log m</tex> стадий анализа образца цикл <tex>for</tex> производит <tex>2^{s-1}</tex> итераций <tex>(2^{s-1} \leqslant i \leqslant 2^{s}-1)</tex>. Если не считать время работы процедур <tex>merge</tex> и <tex>extend</tex>, каждая итерация требует фиксированного времени. Для всех итераций на шаге <tex>s</tex> процедуре <tex>extend</tex> требуется время <tex>O(m)</tex>. Ранее было показано, что время работы <tex>merge</tex> пропорционально числу искомых несовпадений. Таким образом, каждый вызов <tex>merge</tex> занимает время <tex>O(\min\{2^{log(m)-s}4k+1, m-2^{s}\})</tex>, что равно <tex>O(2k2^{\log (m)-s})</tex>. Таким образом, общее время для стадии <tex>s</tex> равно <tex>O(m+2^{s-1}(2k2^{\log (m) -s}))</tex> = <tex>O(km)</tex>. Проведя суммирование по всем стадиям, получаем общее время счета <tex>O</tex> <tex>\displaystyle (\sum_{i=1}^{\log m} km)</tex> = <tex>O(km dkm \log m)</tex>. Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны <tex>O(k(n + m \log m))</tex>.
==Пример==
Пусть <tex>x = "tram"</tex>, <tex>y = "thetrippedtrap"</tex>, <tex>k = 2</tex>.
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
297
правок

Навигация