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

Материал из Викиконспекты
Перейти к: навигация, поиск
(merge)
(merge)
Строка 87: Строка 87:
  
 
Остается показать, что число позиций несовпадений в таблице несовпадений шаблона достаточно для того, чтобы <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>[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>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>[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"
 +
|align="left" colspan="4"|
 +
<font size=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 (?//todo)
 +
      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++
 +
</font>
 +
|}
  
 
==Пример==
 
==Пример==

Версия 11:57, 16 июня 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]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]merge[/math], рассмотрим в тексте позицию [math]p[/math], находящуюся в диапазоне, [math]i+1 \lt p \lt j[/math]. Рассмотрим следующие условия для позиции [math]p[/math]:

Условие A

Условие 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].

Условие B

Условие 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[/math] = [math]pm[i-r][u][/math].

Вспомним, что нас интересует, совпадает ли символ текста в позиции [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] (если лишь условие [math]A[/math] истинно, то [math]y[p] \neq x[p-r][/math] и [math]x[p-r] = x[p-i][/math], откуда [math]y[p] \neq x[p-i][/math], с другой стороны, если выполнено только условие [math]B[/math], то [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], поэтому их надо сравнить.

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

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

  • Eсли [math]b = k+1[/math], то для случая, когда шаблон расположен относительно текста так, что [math]x[1][/math] совмещен с [math]y[i+1][/math], обнаружено [math]k+1[/math] несовпадение, поэтому из процедуры можно выйти.
  • Bспомним, что самая правая из интересующих нас позиций в [math]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]merge[/math] нашла все, или, если их больше [math]k+1[/math], первые [math]k+1[/math] несовпадений для [math]y[i+1...j]\lt tex\gt . Это можно показать следующим образом. Условие A выполняется не больше чем для \lt tex\gt 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][i+1][j-1][/math] имеется до [math]k[/math] позиций текста, для которых выполняется условие A. Таким образом, в худшем случае может быть [math]k[/math] позиций, для которых имеет место случай 3, и которые требуется сравнить напрямую. Остается по крайней мере [math]k+1[/math] позиций, удовлетворяющих условию B, но не условию A (случай 2), что является достаточным, чтобы заключить, что для данного положения шаблона относительно текста имеется не меньше [math]k+1[/math] несовпадений между текстом и шаблоном.

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 (?//todo)
      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++

Пример

Пусть [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