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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение pm)
м (Пример)
(не показано 45 промежуточных версий 4 участников)
Строка 1: Строка 1:
'''Постановка задачи:''' Дано число <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'')
+
'''Постановка задачи:''' дано число <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| В таблицу tm по номеру несовпадения записывается соответстующий индекс образца, то есть <tex>tm[i][1] = a</tex>, <tex>tm[i][2] = b</tex>, <tex>tm[i][3] = c</tex> и т д.]]
+
[[Файл: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[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>. (См. [[Алгоритм Ландау-Вишкина (k несовпадений)#Пример|пример]]).
  
 
Заметим, если <tex>tm[i][k+1] = m+1</tex>, то подстрока <tex>y[i+1...i+m]</tex> отличается от образца <tex>x</tex> не более, чем на <tex>k</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> будет рассмотрена ниже.
+
Затем образец сканируется параллельно с текстом слева направо по одному символу за раз. На итерации <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>\mathrm{merge}</tex>, которая находит количество несовпадений между <tex>x[1...j-i]</tex> и <tex>y[i+1...j]</tex>. Если <tex>b</tex> не превышает <tex>k</tex>, вызывается процедура <tex>\mathrm{extend}</tex>, которая сравнивает подстроки <tex>y[j + 1...i + m]</tex> и <tex>x[j - i + 1...m]</tex>, где изменяется таблица текстовых несовпадений. Переменная <tex>r</tex> будет рассмотрена ниже.
 
   
 
   
 
{| border="0"  
 
{| border="0"  
 
|align="left" colspan="4"|
 
|align="left" colspan="4"|
 
<font size=2>
 
<font size=2>
tm[0...n-m][1...k+1] = m+1 // инициализация
+
  '''int[][]''' algorithmLandauViskin(y : '''string''', x : '''string''')
r = 0
+
    n = y.length
j = 0
+
    m = x.length
for i = 0 to n - m
+
    tm[0...n - m][1...k + 1] = m + 1 <font color=green> // инициализация </font>
  b = 0
+
    r = 0
  if i < j
+
    j = 0
    b = merge(i, r, j)  
+
    '''for''' i = 0 to n - m
  if b < k + 1
+
      b = 0
    r = i
+
      '''if''' i < j
    extend(i, j, b)
+
        b = merge(i, r, j)  
 +
      '''if''' b < k + 1
 +
        r = i
 +
        extend(i, j, b)
 +
    '''return''' tm
 
</font>
 
</font>
 
|}
 
|}
  
==Процедура extend==
+
===Процедура extend===
  
[[Файл:algLandauVishkin2.png|thumb|380px|right| Синие подстроки сравниваются в процедуре extend. <tex>w < k + 1</tex>]]
+
[[Файл:algLandauVishkin2.png|thumb|380px|right| Синие подстроки сравниваются в процедуре <tex>\mathrm{extend}</tex>. <tex>w < k + 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>.
+
Рассмотрим процедуру <tex>\mathrm{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>.
  
 
{| border="0"  
 
{| border="0"  
 
|align="left" colspan="4"|
 
|align="left" colspan="4"|
 
<font size=2>
 
<font size=2>
extend(i, j, b)
+
  '''void''' extend(i : '''int''', j : '''int''', b : '''int''')
while (b < k + 1) and (j - i < m)  
+
    '''while''' (b < k + 1) '''and''' (j - i < m)  
  j++
+
      j++
  if y[j] != x[j-1]
+
      '''if''' y[j] <tex>\neq</tex> x[j-1]
    b++
+
        b++
    tm[i][b] = j - i
+
        tm[i][b] = j - i
 
</font>
 
</font>
 
|}
 
|}
  
==Процедура merge==
+
===Процедура merge===
  
[[Файл:algLandauVishkin3.png|thumb|400px|right| Синие подстроки сравниваются в процедуре merge. Красным отмечены несовпадения.]]
+
[[Файл:algLandauVishkin3.png|thumb|400px|right| Синие подстроки сравниваются в процедуре <tex>\mathrm{merge}</tex>.]]
  
Рассмотрим процедуру <tex>merge</tex> подробнее. Она находит количество несовпадений между <tex>x[1... j-i]</tex> и <tex>y[i+1...j]</tex> и устанавливает b равным найденному числу, при этом используется полученная ранее информация. Введем <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> мест.
+
Рассмотрим процедуру <tex>\mathrm{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>  и т д.]]
+
[[Файл:algLandauVishkin4.png|thumb|250px|right| В таблицу <tex>pm</tex> по номеру несовпадения записывается соответствующий индекс верхнего образца, то есть <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>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>.
+
Таким образом, для <tex>\mathrm{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>.
  
Чтобы использовать упомянутую информацию в процедуре <tex>merge</tex>, рассмотрим в тексте позицию <tex>p</tex>, находящуюся в диапазоне, <tex>i+1 < p < j</tex>. Рассмотрим следующие условия для позиции <tex>p</tex>:  
+
Чтобы использовать упомянутую информацию в процедуре <tex>\mathrm{merge}</tex>, рассмотрим в тексте позицию <tex>p</tex>, находящуюся в диапазоне, <tex>i+1 < p < j</tex>. Рассмотрим следующие условия для позиции <tex>p</tex>:  
  
 
'''Условие A''': когда символы <tex>x[1]</tex> и <tex>y[r+1]</tex> совмещены, позиция <tex>p</tex> в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть <tex>y[p] \neq x[p-r]</tex>, и это несовпадение номер <tex>v</tex>, где <tex>q < v < k+1</tex>, то есть <tex>p - r = tm[r][v]</tex>.
 
'''Условие A''': когда символы <tex>x[1]</tex> и <tex>y[r+1]</tex> совмещены, позиция <tex>p</tex> в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть <tex>y[p] \neq x[p-r]</tex>, и это несовпадение номер <tex>v</tex>, где <tex>q < v < k+1</tex>, то есть <tex>p - r = tm[r][v]</tex>.
Строка 65: Строка 69:
 
[[Файл:algLandauVishkin5.png|380px]]  
 
[[Файл: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>.
+
'''Условие 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 = pm[i-r][u]</tex>.
  
 
[[Файл:algLandauVishkin6.png|450px]]
 
[[Файл:algLandauVishkin6.png|450px]]
Строка 73: Строка 77:
 
'''Случай 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>. Нет необходимости сравнивать символ текста с символом образца, так как ясно, что в этой позиции они совпадают.
 
'''Случай 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>). Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом образца, так как известно, что они не совпадают.
+
'''Случай 2: (A and !B) or (!A and B):''' В любом случае <tex>y[p] \neq x[p-i]</tex> (если лишь ''условие A'' истинно, то <tex>y[p] \neq x[p-r]</tex> и <tex>x[p-r] = x[p-i]</tex>, откуда <tex>y[p] \neq x[p-i]</tex>, с другой стороны, если выполнено только ''условие B'', то <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>, поэтому их надо сравнить.
 
'''Случай 3: A and B:''' В этом случае мы ничего не можем сказать о том, совпадают ли символы <tex>y[p]</tex> и <tex>x[p-i]</tex>, поэтому их надо сравнить.
  
Возвращаемся к процедуре merge. В случае 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>\mathrm{merge}</tex>. В ''случае 2'', или если в ''случае 3'' выявлено несовпадение символов, необходимо увеличить количество несовпадений символов <tex>b</tex> на единицу и обновить <tex>tm[i][b]</tex>. Соответствующими значениями таблицы для <tex>\mathrm{merge}</tex> являются <tex>tm[i-r][1...t]</tex> и <tex>tm[r][q...k+1]</tex>. Переменные <tex>u</tex> и <tex>v</tex> в начале устанавливаются равными индексам первых элементов этих двух массивов, соответственно, и последовательно увеличиваются.
  
 
Условия окончания работы процедуры следующие:
 
Условия окончания работы процедуры следующие:
Строка 83: Строка 87:
 
* Если <tex>b = k+1</tex>, то для случая, когда образец расположен относительно текста так, что <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, обнаружено <tex>k+1</tex> несовпадение, поэтому из процедуры можно выйти.  
 
* Если <tex>b = k+1</tex>, то для случая, когда образец расположен относительно текста так, что <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, обнаружено <tex>k+1</tex> несовпадение, поэтому из процедуры можно выйти.  
  
* Bспомним, что самая правая из интересующих нас позиций в <tex>merge</tex>, а именно, <tex>j</tex>, равна <tex>r+tm[r][k+1]</tex>, если <tex>v = k+2</tex>, поэтому <tex>tm[r][k+1]</tex> будет уже использовано для предыдущего значения <tex>v</tex>, а именно, <tex>v = k+1</tex>, и поэтому позиция <tex>j</tex> должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры.  
+
* Bспомним, что самая правая из интересующих нас позиций в <tex>\mathrm{merge}</tex>, а именно, <tex>j</tex>, равна <tex>r+tm[r][k+1]</tex>, если <tex>v = k+2</tex>, поэтому <tex>tm[r][k+1]</tex> будет уже использовано для предыдущего значения <tex>v</tex>, а именно, <tex>v = k+1</tex>, и поэтому позиция <tex>j</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>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> несовпадений между текстом и образцом.
+
Остается показать, что число позиций несовпадений в таблице несовпадений образца достаточно для того, чтобы <tex>\mathrm{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"  
 
{| border="0"  
 
|align="left" colspan="4"|
 
|align="left" colspan="4"|
 
<font size=2>
 
<font size=2>
   merge(i, r, j, b)
+
   '''int''' merge(i : '''int''', r : '''int''', j : '''int''')
 
     u = 1
 
     u = 1
 
     v = q
 
     v = q
     while (b < k + 1) and (v < k + 2) and (i + pm[i - r][u] < j or tm[r][v] != m + 1)
+
     '''while''' (b < k + 1) '''and''' (v < k + 2) '''and''' (i + pm[i - r][u] < j '''or''' tm[r][v] <tex>\neq</tex> m + 1)
       if i + pm[i - r][u] > r + tm[r][v]  // Случай 2, условие A
+
       '''if''' i + pm[i - r][u] > r + tm[r][v]  <font color=green>    // Случай 2, условие A </font>
 
         b++
 
         b++
 
         tm[i][b] = tm[r][v] - (i - r)
 
         tm[i][b] = tm[r][v] - (i - r)
 
         v++
 
         v++
       else if i + pm[i - r][u] < r + tm[r][v] // Случай 2, условие B
+
       '''else''' '''if''' i + pm[i - r][u] < r + tm[r][v] <font color=green> // Случай 2, условие B </font>
 
         b++     
 
         b++     
 
         tm[i][b] = pm[i - r][u]
 
         tm[i][b] = pm[i - r][u]
 
         u++
 
         u++
       else  if i + pm[i - r][u] = r + tm[r][v] // Случай 3  
+
       '''else''' '''if''' i + pm[i - r][u] = r + tm[r][v] <font color=green>// Случай 3 </font>
         if x[ pm[i-r][u] ] != y[ i+pm[i-r][u] ]
+
         '''if''' x[pm[i - r][u]] <tex>\neq</tex> y[i + pm[i - r][u]]
 
           b++
 
           b++
 
           tm[i][b] = pm[i - r][u]
 
           tm[i][b] = pm[i - r][u]
 
       u++
 
       u++
 
       v++
 
       v++
 +
    '''return''' b
 
</font>
 
</font>
 
|}
 
|}
  
==Построение pm==
+
===Построение 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>m</tex> является некоторой степенью <tex>2</tex>. В алгоритме предварительной обработки используется разбиение множества <tex>{1, 2, ... , m-1}</tex> из <tex>m-1</tex> строк <tex>pm</tex> на следующие <tex>\log m</tex> подмножеств:
Строка 119: Строка 124:
 
<tex>\{1\}, \{2, 3\}, \{4, 5, 6, 7\}, ... , \{m/2, ... , m-1\}</tex>
 
<tex>\{1\}, \{2, 3\}, \{4, 5, 6, 7\}, ... , \{m/2, ... , m-1\}</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>{2s-1, ... , 2s-1}</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> вводятся в pm. За исключением стадии <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>, как в алгоритме анализа текста.
+
Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста. Рассмотрим алгоритм для этапа <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"  
 
{| border="0"  
 
|align="left" colspan="4"|
 
|align="left" colspan="4"|
 
<font size=2>
 
<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
+
   '''void''' precalcPm() 
  r = <tex>2^{s-1}</tex>
+
    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
  j = <tex>2^{s-1}</tex>
+
    r = <tex>2^{s-1}</tex>
  for i = <tex>2^{s-1}</tex> to <tex>2^{s} - 1</tex>
+
    j = <tex>2^{s-1}</tex>
    b = 0
+
    '''for''' i = <tex>2^{s-1}</tex> to <tex>2^{s} - 1</tex>
    if i < j
+
      b = 0
      merge(I, R, J, B)
+
      '''if''' i < j
      if b < min{<tex>2^{log(m-1)}2k-1, m-2^{s} </tex>}
+
        b = merge(i, r, j)
        r = i
+
        '''if''' b < min{<tex>2^{\log(m-1)}2k - 1, m - 2^{s} </tex>}
        extend(i, j, b)
+
          r = i
 +
          extend(i, j, b)
 
</font>
 
</font>
 
|}
 
|}
  
==Оценка работы==
+
===Оценка сложности===
  
Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур <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>\mathrm{merge}</tex> и <tex>\mathrm{extend}</tex>, каждая из <tex>n-m+1</tex> итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время <tex>O(n)</tex>. Общее число операций, выполняемых процедурой <tex>\mathrm{extend}</tex> во время вызовов равно <tex>O(n)</tex>, так как она проверяет каждый символ текста не больше одного раза. Процедура <tex>\mathrm{merge}</tex> при каждом вызове обрабатывает массив <tex>pm[i-r][1...2k+1]</tex> и <tex>tm[r][1...k+1]</tex>, которые в сумме имеют <tex>3k+2</tex> элементов. Время работы <tex>\mathrm{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>pm</tex>. Используя аргументы, аналогичные применявшимся при проверке корректности процедуры <tex>\mathrm{merge}</tex>, можно показать, что для нахождения требуемого количества несовпадений на стадии <tex>s</tex> требуется <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^{l-1}(2k2^{\log (m-s)}))</tex> = <tex>O(km)</tex>. Проведя суммирование по всем стадиям, получаем общее время счета <tex>O(\sum_{i=1}^{\log m} km)</tex> = <tex>O(km \log m)</tex>. Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны <tex>O(k(n + m \log m))</tex>.
+
На каждой стадии <tex>s</tex> из <tex>\log m</tex> стадий анализа образца цикл <tex>\mathrm{for}</tex> производит <tex>2^{s-1}</tex> итераций <tex>(2^{s-1} \leqslant i \leqslant 2^{s}-1)</tex>. Если не считать время работы процедур <tex>\mathrm{merge}</tex> и <tex>\mathrm{extend}</tex>, каждая итерация требует фиксированного времени. Для всех итераций на шаге <tex>s</tex> процедуре <tex>\mathrm{extend}</tex> требуется время <tex>O(m)</tex>. Ранее было показано, что время работы <tex>\mathrm{merge}</tex> пропорционально числу искомых несовпадений. Таким образом, каждый вызов <tex>\mathrm{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 \left(\sum_{i=1}^{\log m} km\right) = O(km \log m)</tex>. Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны <tex>O(k(n + m \log m))</tex>.
  
=Пример=
+
==Пример==
 
Пусть <tex>x = "tram"</tex>, <tex>y = "thetrippedtrap"</tex>, <tex>k = 2</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;"
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
 
|-
 
|-
| tm || '''1''' || '''2''' || '''3''' || x[1..m] || y[i+1..i+m]
+
| tm || '''1''' || '''2''' || '''3''' || x[1 <tex>\ldots</tex> m] || y[i+1 <tex>\ldots</tex> i+m]
 
|-
 
|-
 
| '''0''' ||  2  ||  3  ||  4  || '''t'''ram || '''t'''het
 
| '''0''' ||  2  ||  3  ||  4  || '''t'''ram || '''t'''het
Строка 177: Строка 183:
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse; text-align: center;"
 
|-
 
|-
| tm || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || x[1..m-i] || x[i+1..m]
+
| pm || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || x[1 <tex>\ldots</tex> m-i] || x[i+1 <tex>\ldots</tex> m]
 
|-
 
|-
 
| '''1''' ||  1  ||  2  ||  3  || 5  ||  5  || tra || ram
 
| '''1''' ||  1  ||  2  ||  3  || 5  ||  5  || tra || ram
Строка 185: Строка 191:
 
| '''3''' ||  1  ||  5  ||  5  || 5  ||  5  || t || m
 
| '''3''' ||  1  ||  5  ||  5  || 5  ||  5  || t || m
 
|}
 
|}
 +
 +
==См. также==
 +
* [[Алгоритм Бойера-Мура]]
 +
* [[Алгоритм Кнута-Морриса-Пратта]]
 +
 +
==Источники информации==
 +
* [http://algolist.manual.ru/search/fsearch/k_nesovp.php Алгоритм Ландау-Вишкина {{---}} k несовпадений]
 +
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Поиск подстроки в строке]]
 +
[[Категория: Нечёткий поиск]]

Версия 20:38, 22 марта 2017

Постановка задачи: дано число [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] несовпадающими символами с образцом. Эту задачу решает алгоритм Ландау-Вишкина (k несовпадений) (англ.Landau-Vishkin Algorithm)

Алгоритм

Идея

Красным отмечены несовпадения. В таблицу [math]tm[/math] по номеру несовпадения записывается соответстующий индекс образца, то есть [math]tm[i][1] = a[/math], [math]tm[i][2] = b[/math], [math]tm[i][3] = c[/math] и т. д.

При анализе используется двумерный массив несовпадений текста [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]\mathrm{merge}[/math], которая находит количество несовпадений между [math]x[1...j-i][/math] и [math]y[i+1...j][/math]. Если [math]b[/math] не превышает [math]k[/math], вызывается процедура [math]\mathrm{extend}[/math], которая сравнивает подстроки [math]y[j + 1...i + m][/math] и [math]x[j - i + 1...m][/math], где изменяется таблица текстовых несовпадений. Переменная [math]r[/math] будет рассмотрена ниже.

 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

Синие подстроки сравниваются в процедуре [math]\mathrm{extend}[/math]. [math]w \lt k + 1[/math]

Рассмотрим процедуру [math]\mathrm{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].

 void extend(i : int, j : int, b : int)
   while (b < k + 1) and (j - i < m) 
     j++
     if y[j] [math]\neq[/math] x[j-1]
       b++
       tm[i][b] = j - i

Процедура merge

Синие подстроки сравниваются в процедуре [math]\mathrm{merge}[/math].

Рассмотрим процедуру [math]\mathrm{merge}[/math] подробнее. Она находит количество несовпадений между [math]x[1... j-i][/math] и [math]y[i+1...j][/math] и устанавливает [math]b[/math] равным найденному числу, при этом используется полученная ранее информация. Введем [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] мест.

В таблицу [math]pm[/math] по номеру несовпадения записывается соответствующий индекс верхнего образца, то есть [math]pm[i][1] = a[/math], [math]pm[i][2] = b[/math], [math]pm[i][3] = c[/math] и т д.

Также в алгоритме используется двумерный массив несовпадений образца [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]tm[/math] будет подробнее рассмотрено позднее.

Таким образом, для [math]\mathrm{merge}[/math] интерес представляет строка [math]i - r[/math] таблицы несовпадений образца, причем используются значения [math]pm[i-r][1...t][/math], где [math]t[/math] — самое правое несовпадение в [math]pm[i-r][1...2k+1][/math], такое, что [math]pm[i-r][t] \lt j-i+1[/math], так как требуются только несовпадения в подстроке [math]x[1...j-i][/math].

Чтобы использовать упомянутую информацию в процедуре [math]\mathrm{merge}[/math], рассмотрим в тексте позицию [math]p[/math], находящуюся в диапазоне, [math]i+1 \lt p \lt j[/math]. Рассмотрим следующие условия для позиции [math]p[/math]:

Условие A: когда символы [math]x[1][/math] и [math]y[r+1][/math] совмещены, позиция [math]p[/math] в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть [math]y[p] \neq x[p-r][/math], и это несовпадение номер [math]v[/math], где [math]q \lt v \lt k+1[/math], то есть [math]p - r = tm[r][v][/math].

AlgLandauVishkin5.png

Условие B: для двух копий образца, со сдвигом относительно друг друга [math]i - r[/math], совмещенных с текстом так, что их начальные символы лежат, соответственно, над [math]y[r+1][/math] и [math]y[i+1][/math], позиция [math]p[/math] соответствует несовпадению между двумя образцам, то есть [math]x[p-r] \neq x[p-i][/math]. Это [math]u[/math]-е несовпадение при этом сдвиге, где [math]1 \lt u \lt t[/math], то есть [math]p-i = pm[i-r][u][/math].

AlgLandauVishkin6.png

Вспомним, что нас интересует, совпадает ли символ текста в позиции [math]p[/math] с соответствующими символом образца, когда [math]x[1][/math] совмещен с [math]y[i+1][/math], то есть верно ли, что [math]y[p] = x[p-i][/math]. Рассмотрим этот вопрос при разных комбинациях указанных выше условий.

Случай 1: !A and !B: То есть, [math]y[p] = x[p-r][/math] и [math]x[p-r] = x[p-i][/math], откуда [math]y[p] = x[p-i][/math]. Нет необходимости сравнивать символ текста с символом образца, так как ясно, что в этой позиции они совпадают.

Случай 2: (A and !B) or (!A and B): В любом случае [math]y[p] \neq x[p-i][/math] (если лишь условие A истинно, то [math]y[p] \neq x[p-r][/math] и [math]x[p-r] = x[p-i][/math], откуда [math]y[p] \neq x[p-i][/math], с другой стороны, если выполнено только условие B, то [math]y[p] = x[p-r][/math] и [math]x[p-r] \neq x[p-i][/math], и опять, [math]y[p] \neq x[p-i][/math]). Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом образца, так как известно, что они не совпадают.

Случай 3: A and B: В этом случае мы ничего не можем сказать о том, совпадают ли символы [math]y[p][/math] и [math]x[p-i][/math], поэтому их надо сравнить.

Возвращаемся к процедуре [math]\mathrm{merge}[/math]. В случае 2, или если в случае 3 выявлено несовпадение символов, необходимо увеличить количество несовпадений символов [math]b[/math] на единицу и обновить [math]tm[i][b][/math]. Соответствующими значениями таблицы для [math]\mathrm{merge}[/math] являются [math]tm[i-r][1...t][/math] и [math]tm[r][q...k+1][/math]. Переменные [math]u[/math] и [math]v[/math] в начале устанавливаются равными индексам первых элементов этих двух массивов, соответственно, и последовательно увеличиваются.

Условия окончания работы процедуры следующие:

  • Если [math]b = k+1[/math], то для случая, когда образец расположен относительно текста так, что [math]x[1][/math] совмещен с [math]y[i+1][/math], обнаружено [math]k+1[/math] несовпадение, поэтому из процедуры можно выйти.
  • Bспомним, что самая правая из интересующих нас позиций в [math]\mathrm{merge}[/math], а именно, [math]j[/math], равна [math]r+tm[r][k+1][/math], если [math]v = k+2[/math], поэтому [math]tm[r][k+1][/math] будет уже использовано для предыдущего значения [math]v[/math], а именно, [math]v = k+1[/math], и поэтому позиция [math]j[/math] должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры.
  • Процедуру можно прервать, если [math]i+pm[i-r][u] \gt j[/math] и [math]tm[r][v] = m+1[/math]. Если выполняется вторая часть этого условия, то [math]r+tm[r][v][/math] равняется [math]j[/math], и соответствует суммам для последующих значений [math]v[/math] вплоть до [math]k+1[/math]. В этом случае процедура может быть прервана, если выполняется также первая часть приведенного условия, так как она указывает, что позиция текста [math]j[/math] фактически пропущена.

Остается показать, что число позиций несовпадений в таблице несовпадений образца достаточно для того, чтобы [math]\mathrm{merge}[/math] нашла все, или, если их больше [math]k+1[/math], первые [math]k+1[/math] несовпадений для [math]y[i+1...j][/math]. Это можно показать следующим образом. Условие A выполняется не больше чем для [math]k+1[/math] позиции текста в диапазоне [math]y[i+1...j][/math]. Условие B выполняется для некоторого неизвестного числа позиций в этом же интервале. Строка [math]i-r[/math] в таблице несовпадений образца, [math]tm[i-r][1...2k+1][/math], содержит не больше чем [math]2k+1[/math] позиций несовпадений между двумя копиями образца, с соответствующим сдвигом [math]i-r[/math]. Если [math]pm[i-r][2k+1] \gt j - i[/math], то таблица содержит все позиции несовпадения образца самим с собой, у которых условие B выполняется для позиций текста в интервале [math]y[i+1...j][/math]. С другой стороны, если [math]pm[i-r][2k+1] \lt j-i[/math], то таблица может дать [math]2k+1[/math] позиций текста в диапазоне [math]y[i+1...j-1][/math], для которых выполняется условие B. Поскольку [math]j = r+tm[r][k+1][/math], в диапазоне [math]y[i+1...j-1][/math] имеется до [math]k[/math] позиций текста, для которых выполняется условие A. Таким образом, в худшем случае может быть [math]k[/math] позиций, для которых имеет место случай 3, и которые требуется сравнить напрямую. Остается по крайней мере [math]k+1[/math] позиций, удовлетворяющих условию B, но не условию A (случай 2), что является достаточным, чтобы заключить, что для данного положения образца относительно текста имеется не меньше [math]k+1[/math] несовпадений между текстом и образцом.

 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] [math]\neq[/math] 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]] [math]\neq[/math]  y[i + pm[i - r][u]]
         b++
         tm[i][b] = pm[i - r][u]
     u++
     v++
   return b

Построение pm

Теперь осталось только обратиться к вычислению таблицы несовпадений образца на стадии предварительных вычислений. Не теряя общности, можно предположить, что [math]m[/math] является некоторой степенью [math]2[/math]. В алгоритме предварительной обработки используется разбиение множества [math]{1, 2, ... , m-1}[/math] из [math]m-1[/math] строк [math]pm[/math] на следующие [math]\log m[/math] подмножеств:

[math]\{1\}, \{2, 3\}, \{4, 5, 6, 7\}, ... , \{m/2, ... , m-1\}[/math]

Алгоритм состоит из [math]\log m[/math] этапов. На этапе [math]s[/math], где [math]1 \leqslant s \lt \log m[/math], вычисляются строки [math]pm[/math] в множестве [math]s[/math], где множество [math]s[/math] — это [math]\{2^{s-1}, ... , 2^{s}-1\}[/math].

Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста. Рассмотрим алгоритм для этапа [math]s[/math]. На стадии [math]s[/math] входами для алгоритма анализа образца являются подстроки образца [math]x[1...m-2^{s-1}][/math] и [math]x[2^{s-1}+1...m][/math], которые трактуются здесь, соответственно, как образец и текст, и массив [math]pm[1...2^{s-1}-1][1...\min\{2^{\log(m)-s}4k+1, m-2^{s-1}\}][/math], содержащий выходы предыдущих [math]s - 1[/math] стадий. Выходы стадии [math]s[/math] вводятся в [math]pm[/math]. За исключением стадии [math]\log m[/math], на которой находят до [math]2k+1[/math] несовпадений, на стадии [math]s[/math] для каждой строки [math]pm[/math] требуется найти до [math]\min\{2^{\log(m)-s}2k+1, m-2^{s}\}[/math] несовпадений, а не до [math]k+1[/math], как в алгоритме анализа текста.

 void precalcPm()  
   pm[[math]2^{s-1}[/math]...[math]2^{s} - 1[/math]][1...min{[math]2^{\log (m-1)}2k - 1[/math], [math]m - 2^{s}[/math]}] = m + 1
   r = [math]2^{s-1}[/math]
   j = [math]2^{s-1}[/math]
   for i = [math]2^{s-1}[/math] to [math]2^{s} - 1[/math]
     b = 0
     if i < j
       b = merge(i, r, j)
       if b < min{[math]2^{\log(m-1)}2k - 1, m - 2^{s} [/math]}
         r = i
         extend(i, j, b)

Оценка сложности

Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур [math]\mathrm{merge}[/math] и [math]\mathrm{extend}[/math], каждая из [math]n-m+1[/math] итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время [math]O(n)[/math]. Общее число операций, выполняемых процедурой [math]\mathrm{extend}[/math] во время вызовов равно [math]O(n)[/math], так как она проверяет каждый символ текста не больше одного раза. Процедура [math]\mathrm{merge}[/math] при каждом вызове обрабатывает массив [math]pm[i-r][1...2k+1][/math] и [math]tm[r][1...k+1][/math], которые в сумме имеют [math]3k+2[/math] элементов. Время работы [math]\mathrm{merge}[/math] можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное [math]O(k)[/math]. Таким образом, можно видеть, что общее время анализа текста составляет [math]O(nk)[/math].

Рассмотрим построение [math]pm[/math]. Используя аргументы, аналогичные применявшимся при проверке корректности процедуры [math]\mathrm{merge}[/math], можно показать, что для нахождения требуемого количества несовпадений на стадии [math]s[/math] требуется [math]\min\{2^{\log(m)-s}4k+1, m-2^{s}\}[/math] позиций, для которых выполняется условие B, и в особом случае, а именно, на стадии [math]\log m[/math], требуется [math]4k + 1[/math] таких позиций.

На каждой стадии [math]s[/math] из [math]\log m[/math] стадий анализа образца цикл [math]\mathrm{for}[/math] производит [math]2^{s-1}[/math] итераций [math](2^{s-1} \leqslant i \leqslant 2^{s}-1)[/math]. Если не считать время работы процедур [math]\mathrm{merge}[/math] и [math]\mathrm{extend}[/math], каждая итерация требует фиксированного времени. Для всех итераций на шаге [math]s[/math] процедуре [math]\mathrm{extend}[/math] требуется время [math]O(m)[/math]. Ранее было показано, что время работы [math]\mathrm{merge}[/math] пропорционально числу искомых несовпадений. Таким образом, каждый вызов [math]\mathrm{merge}[/math] занимает время [math]O(\min\{2^{\log(m)-s}4k+1, m-2^{s}\})[/math], что равно [math]O(2k2^{\log (m)-s})[/math]. Таким образом, общее время для стадии [math]s[/math] равно [math]O(m+2^{s-1}(2k2^{\log (m) -s}))[/math] = [math]O(km)[/math]. Проведя суммирование по всем стадиям, получаем общее время счета [math]O[/math] [math]\displaystyle \left(\sum_{i=1}^{\log m} km\right) = O(km \log m)[/math]. Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны [math]O(k(n + m \log m))[/math].

Пример

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

tm 1 2 3 x[1 [math]\ldots[/math] m] y[i+1 [math]\ldots[/math] 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 [math]\ldots[/math] m-i] x[i+1 [math]\ldots[/math] 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

См. также

Источники информации