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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(extend)
Строка 30: Строка 30:
 
==extend==
 
==extend==
  
[[Файл:algLandauVishkin2.png|thumb|380px|right| В таблицу tm по номеру несовпадения записывается соответстующий индекс образца.]]
+
[[Файл:algLandauVishkin2.png|thumb|380px|right| Синие подстроки сравниваются в процедуре extend.]]
  
 
Рассмотрим процедуру <tex>extend</tex> подробнее. Она сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>, в случае несовпадения <tex>b</tex> увеличивается и таблица текстовых несовпадений обновляется. Это происходит пока либо не будет найдено <tex>k + 1</tex> несовпадений (учитывая несовпадения, которые были найдены раньше на <tex>i</tex>-ой итерации), либо не будет достигнуто <tex>y[i+m]</tex> с не больше чем <tex>k</tex> несовпадениями, то есть найдено вхождение образца, начинающееся с <tex>y[i+1]</tex>.
 
Рассмотрим процедуру <tex>extend</tex> подробнее. Она сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>, в случае несовпадения <tex>b</tex> увеличивается и таблица текстовых несовпадений обновляется. Это происходит пока либо не будет найдено <tex>k + 1</tex> несовпадений (учитывая несовпадения, которые были найдены раньше на <tex>i</tex>-ой итерации), либо не будет достигнуто <tex>y[i+m]</tex> с не больше чем <tex>k</tex> несовпадениями, то есть найдено вхождение образца, начинающееся с <tex>y[i+1]</tex>.

Версия 18:17, 15 июня 2014

Постановка задачи

Дано число [math]k \gt 0[/math] текст [math]y[1...n][/math] и образец [math]x[1...m][/math], [math]m \lt n[/math]. Требуется найти все подстроки текста длины [math]m[/math], с не более чем [math]k[/math] несовпадающими символами.

Алгоритм

В таблицу tm по номеру несовпадения записывается соответстующий индекс образца.

При анализе используется двумерный массив несовпадений текста [math]tm[0...n-m][1...k+1][/math], содержащий информацию о несовпадениях текста с образцом. По завершении анализа в его [math]i[/math]-й строке содержатся позиции в [math]x[/math] первых [math]k+1[/math] несовпадений между строками [math]x[1...m][/math] и [math]y[i+1...i+m][/math]. Таким образом, если [math]tm[i][v] = s[/math], то [math]y[i+s] \neq x[s][/math], и это [math]v[/math]-е несовпадение между [math]x[1...m][/math] и [math]y[i+1...i+m][/math], считая слева направо. Если число [math]d[/math] несовпадений [math]x[1...m][/math] с подстрокой [math]y[i+1...i+m][/math] меньше [math]k+1[/math], то, начиная с [math]d+1[/math], элементы [math]i[/math]-й строки равны значению по умолчанию [math]m+1[/math].

Заметим, если [math]tm[i][k+1] = m+1[/math], то подстрока [math]y[i+1...i+m][/math] отличается от образца [math]x[/math] не более, чем на [math]k[/math] символов, и, таким образом, является решением задачи.

Затем образец сканируется параллельно с текстом слева на права по одному символу за раз. На итерации [math]i[/math] с образцом сравнивается подстрока [math]y[i+1...i+m][/math]. [math]j[/math] - обозначим самую правую позицию в тексте, достигнутую за предыдущие итерации, то есть [math]j[/math] является максимальным из чисел [math]r+tm[r, k + 1][/math], где [math]0 \leqslant r \lt i[/math]. Если [math]i \lt j[/math], в [math]b[/math] присваивается результат работы [math]merge[/math], которая находит количество несовпадений между [math]x[1... j-i][/math] и [math]y[i+1...j][/math]. Если [math]b[/math] не превышает [math]k[/math], вызывается процедура [math]extend[/math], которая сравнивает подстроки [math]y[j + 1...i + m][/math] и [math]x[j - i + 1...m][/math]. Переменная [math]r[/math] будет рассмотренна ниже.

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.

Рассмотрим процедуру [math]extend[/math] подробнее. Она сравнивает подстроки [math]y[j + 1...i + m][/math] и [math]x[j - i + 1...m][/math], в случае несовпадения [math]b[/math] увеличивается и таблица текстовых несовпадений обновляется. Это происходит пока либо не будет найдено [math]k + 1[/math] несовпадений (учитывая несовпадения, которые были найдены раньше на [math]i[/math]-ой итерации), либо не будет достигнуто [math]y[i+m][/math] с не больше чем [math]k[/math] несовпадениями, то есть найдено вхождение образца, начинающееся с [math]y[i+1][/math].

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

Синие подстроки сравниваются в процедуре merge. Красным отмечены несовпадения.

Рассмотрим процедуру [math]merge[/math] подробнее. Она находит количество несовпадений между [math]x[1... j-i][/math] и [math]y[i+1...j][/math] и устанавливает b равным найденному числу, при этом используется полученая ранее информация. Введем [math]r[/math] - это строка таблицы несовпадений, в которой есть информация о несовпадениях, полученных при совмещении начала образца и [math]y[r+1][/math]. [math]r+tm[r][k+1][/math] содержит текущий номер самой правой из проверенных на настоящий момент позиций текста. Поэтому при обработки построки начинающейся с [math]y[i+1][/math], можно учитывать информацию в [math]r[/math]-ой строке [math]tm[/math], которая содержит информацию о сопоставлении образца с [math]y[i][/math]. Подходящими значениями из таблицы несовпадений являются, таким образом, [math]tm[r][q ... k+1][/math], где [math]q[/math] – это наименьшее из целых чисел, для которых [math]r+tm[r][q] \gt i[/math]. Однако, следует учитывать тот факт, что эти несовпадения соответствуют началу образца, выравниваемому с [math]y[r+1][/math], в то время как текущая позиция образца выровнена с [math]y[i+1][/math] – разница в [math]i - r[/math] мест.

В таблицу pm по номеру несовпадения записывается соответстующий индекс верхнего образца.

Также в алгоритме используется двумерный массив несовпадений образца [math]pm[1...m-1][1...2k+1][/math], генерируемой на стадии предварительной обработки образца. В нем содержатся позиции несовпадения образца с самим собой при различных сдвигах, аналогично [math]tm[/math], то есть в [math]i[/math]-ой строке содержитатся позиции внутри [math]x[/math] первых [math]2k+1[/math] несовпадений между подстроками [math]x[1...m-i][/math] и [math]x[i+1...m][/math]. Таким образом, если [math]pm[i, v] = s[/math], то [math]x[i+s] \neq x[s][/math], и это [math]v[/math]-е несовпадение между [math]x(1, m-i)[/math] и [math]x(i+1, m)[/math] слева направо. Если число [math]d[/math] несовпадений между этими строками меньше [math]2k+1[/math], то, начиная с [math]d+1[/math], элементы [math]i[/math]-й строки равны [math]m+1[/math], значению по умолчанию.

Пример

Пусть [math]x = "tram"[/math], [math]y = "thetrippedtrap"[/math], [math]k = 2[/math].

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