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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Формулировка задачи:''' По заданному слову <tex>X[0..m-1]</tex> найти в тексте или словаре <tex>Y[0..n-...»)
 
Строка 1: Строка 1:
'''Формулировка задачи:''' По заданному слову <tex>X[0..m-1]</tex> найти в тексте или словаре <tex>Y[0..n-1]</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.
+
{{Задача
 +
|definition = По заданному слову <tex>X[0..m-1]</tex> найти в тексте или словаре <tex>Y[0..n-1]</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.
 +
}}
 +
Например, при запросе <tex>abcdef</tex> и <tex>k = 2</tex>, найти слова <tex>abcdeRf</tex>, <tex>abHdef</tex>, <tex>VbRdef</tex> и так далее.
  
 
==Описание задачи с точки зрения динамического программирования==
 
==Описание задачи с точки зрения динамического программирования==
Пусть <tex>d_{i,j}</tex> - расстояние между префиксами строк <tex>x</tex> и <tex>y</tex>, длины которых равны, соответственно, <tex>i</tex> и <tex>j</tex>, то есть
+
Пусть <tex>d_{i,j}</tex> {{---}} расстояние между префиксами строк <tex>x</tex> и <tex>y</tex>, длины которых равны, соответственно, <tex>i</tex> и <tex>j</tex>, то есть
<tex>d_{i,j} = d(x(1,i), y(1,j))</tex>.
+
<tex>d_{i,j} = d(x(0,i-1), y(0,j-1))</tex>. Перед тем, как начать вычислять <tex>d_{i,j}</tex>, надо установить граничные значения массива. Что касается первого столбца массива, то значение <tex>d_{i,0}</tex> равно сумме цен удаления первых <tex>i</tex> символов <tex>x</tex>. Аналогично, значения <tex>d_{0,j}</tex> первой строки задаются суммой цен вставки первых <tex>j</tex> символов <tex>y</tex>. Таким образом:
Чтобы решить задачу <tex>k</tex> различий, [[wikipedia:ru:Матрица_расстояний|матрицу расстояний]] надо преобразовать таким образом, чтобы <tex>d_{i,j}</tex> представлял минимальное расстояние между <tex>x(1, i)</tex> и любой подстрокой <tex>y</tex>, заканчивающейся символом <tex>y_j</tex>. Для этого достаточно ввести условие:  
 
  
<tex>d_{0,j} = 0, 0 < j < n</tex> .
+
<tex>d_{0,0} = 0</tex>
  
Оставшуюся часть матрицы вычислим с использованием цен редактирования расстояния Левенштейна и рекуррентного соотношения для <tex>d_{i,j}</tex>:
+
<tex>d_{i,0} = \sum_{k = 1}^{i}{w(x_i, \varepsilon)}, для 1 < i < m</tex>
 +
 
 +
<tex>d_{0,j} = \sum_{k = 1}^{j}{w(\varepsilon, j_k)}, для 1 < j < n</tex>
 +
 
 +
Чтобы решить задачу <tex>k</tex> различий, матрицу расстояний<ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D1%80%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9 Википедия {{---}} Матрица расстояний]</ref> надо преобразовать таким образом, чтобы <tex>d_{i,j}</tex> представлял минимальное расстояние между <tex>x(0, i-1)</tex> и любой подстрокой <tex>y</tex>, заканчивающейся символом <tex>y_j</tex>. Для этого достаточно ввести условие:
 +
 
 +
<tex>d_{0,j} = 0, 0 < j < n</tex>
 +
 
 +
так как минимальное расстояние между <tex>\varepsilon</tex> и любой подстрокой y равно <tex>0</tex>.
 +
 
 +
Оставшуюся часть матрицы вычислим с использованием цен редактирования [[Задача_о_редакционном_расстоянии,_алгоритм_Вагнера-Фишера#levenstain_dist|расстояния Левенштейна]] и рекуррентного соотношения для <tex>d_{i,j}</tex>:
  
 
<tex>w(a,{\varepsilon}) = 1</tex>
 
<tex>w(a,{\varepsilon}) = 1</tex>
Строка 15: Строка 27:
  
 
<tex>w(a, b) = \left\{\begin{array}{llcl}
 
<tex>w(a, b) = \left\{\begin{array}{llcl}
0&,\ a{\ne}b\\
+
0&,\ a \ne b\\
1&,\ a=b\\
+
1&,\ a = b\\
 
\end{array}\right.
 
\end{array}\right.
 
</tex>
 
</tex>
  
<tex>d_{i,j} = min(d_{i-1,j} + w(x_i,{\varepsilon}), d_{i,j-1} + w({\varepsilon}, y_j), d_{i-1,j-1} + w(x_i, y_i))</tex>
+
<tex>d_{i,j} = \min(d_{i-1,j} + w(x_i,{\varepsilon}), d_{i,j-1} + w({\varepsilon}, y_j), d_{i-1,j-1} + w(x_i, y_i))</tex>
  
 
Теперь каждое значение, не превосходящее <tex>k</tex>, в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше <tex>k</tex> отличий от образца.
 
Теперь каждое значение, не превосходящее <tex>k</tex>, в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше <tex>k</tex> отличий от образца.
 
===Пример===
 
===Пример===
Рассмотрим этот подход к решению задачи на примере: пусть <tex>X=ABCDE, Y=ACEABPCQDEABCR</tex>. Построим матрицу расстояний для этого случая:
+
Рассмотрим этот подход к решению задачи на примере: пусть <tex>X=abcde, Y=aceabpcqdeabcr</tex>. Построим матрицу расстояний для этого случая:
[[Файл:Table_k_razlichiy.png]]
+
{| class="wikitable" width="20%"
 +
! style="text-align: center;" |
 +
! style="text-align: center; font-weight: bold;" | j
 +
! style="text-align: center; font-weight: bold;" | 0
 +
! style="text-align: center; font-weight: bold;" | 1
 +
! style="text-align: center; font-weight: bold;" | 2
 +
! style="text-align: center; font-weight: bold;" | 3
 +
! style="text-align: center; font-weight: bold;" | 4
 +
! style="text-align: center; font-weight: bold;" | 5
 +
! style="text-align: center; font-weight: bold;" | 6
 +
! style="text-align: center; font-weight: bold;" | 7
 +
! style="text-align: center; font-weight: bold;" | 8
 +
! style="text-align: center; font-weight: bold;" | 9
 +
! style="text-align: center; font-weight: bold;" | 10
 +
! style="text-align: center; font-weight: bold;" | 11
 +
! style="text-align: center; font-weight: bold;" | 12
 +
! style="text-align: center; font-weight: bold;" | 13
 +
! style="text-align: center;" | 14
 +
|-
 +
| style="text-align: center; font-weight: bold;" | i
 +
| style="text-align: center;" |
 +
| style="text-align: center;" |
 +
| style="text-align: center; font-style: italic;" | a
 +
| style="text-align: center; font-style: italic;" | c
 +
| style="text-align: center; font-style: italic;" | e
 +
| style="text-align: center; font-style: italic;" | a
 +
| style="text-align: center; font-style: italic;" | b
 +
| style="text-align: center; font-style: italic;" | p
 +
| style="text-align: center; font-style: italic;" | c
 +
| style="text-align: center; font-style: italic;" | q
 +
| style="text-align: center; font-style: italic;" | d
 +
| style="text-align: center; font-style: italic;" | e
 +
| style="text-align: center; font-style: italic;" | a
 +
| style="text-align: center; font-style: italic;" | b
 +
| style="text-align: center; font-style: italic;" | c
 +
| style="text-align: center; font-style: italic;" | r
 +
|-
 +
| style="text-align: center; font-weight: bold;" | 0
 +
| style="text-align: center;" |
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 0
 +
|-
 +
| style="text-align: center; font-weight: bold;" | 1
 +
| style="text-align: center; font-style: italic;" | a
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
|-
 +
| style="text-align: center; font-weight: bold;" | 2
 +
| style="text-align: center; font-style: italic;" | b
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 0
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 2
 +
|-
 +
| style="text-align: center; font-weight: bold;" | 3
 +
| style="text-align: center; font-style: italic;" | c
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 1
 +
|-
 +
| style="text-align: center; font-weight: bold;" | 4
 +
| style="text-align: center; font-style: italic;" | d
 +
| style="text-align: center;" | 4
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 1
 +
| style="text-align: center;" | 1
 +
|-
 +
| style="text-align: center; font-weight: bold;" | 5
 +
| style="text-align: center; font-style: italic;" | e
 +
| style="text-align: center;" | 5
 +
| style="text-align: center;" | 4
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 3
 +
| style="text-align: center;" | 2
 +
| style="text-align: center;" | 2
 +
|}
  
Последняя строка матрицы показывает, что вхождения образца с точностью до <tex>2</tex> отличий, заканчиваются в позициях <tex>3</tex>, <tex>10</tex>, <tex>13</tex> и <tex>14</tex>. Соответствующими подстроками являются <tex>ACE</tex>, <tex>ABPCQDE</tex>, <tex>ABC</tex> и <tex>ABCR</tex>.
+
Последняя строка матрицы показывает, что вхождения образца с точностью до <tex>2</tex> отличий, заканчиваются в позициях <tex>3</tex>, <tex>10</tex>, <tex>13</tex> и <tex>14</tex>. Соответствующими подстроками являются <tex>ace</tex>, <tex>abpcqde</tex>, <tex>abc</tex> и <tex>abcr</tex>.
  
 
==Алгоритм==
 
==Алгоритм==
  
[[Алгоритм_Укконена|Алгоритм Укконена]] говорит, что при вычисления расстояний между строками, диагонали матрицы можно пронумеровать целыми числами <tex>p {\in} [-m, n]</tex>, таким образом, чтобы диагональ <tex>p</tex> состояла из элементов <tex>(i, j)</tex>, у которых <tex>j - i = p</tex>. Пусть <tex>r_{p,q}</tex> представляет наибольшую строку <tex>i</tex>, у которой <tex>d_{i,j} = q</tex> и <tex>(i, j)</tex> лежит на диагонали <tex>p</tex>. Таким образом, <tex>q</tex> это минимальное число различий между <tex>x(1, r_{p,q})</tex> и любой подстрокой текста, заканчивающейся <tex>y_{r_{p,q}+p}</tex>. Значение <tex>m</tex> в строке <tex>r_{p,q}</tex>, для <tex>q < k</tex>, указывает, что в тексте имеется вхождение образца с точностью до <tex>k</tex> отличий, заканчивающееся в <tex>y_{m+p}</tex>. Таким образом, чтобы решить задачу <tex>k</tex> различий, достаточно вычислить значения <tex>r_{p,q}</tex> для <tex>q < k</tex>.
+
Пронумеруем диагонали матрицы расстояния целыми числами <tex>p \in [-m, n]</tex>, таким образом, чтобы диагональ <tex>p</tex> состояла из элементов <tex>(i, j)</tex>, у которых <tex>j - i = p</tex>. Пусть <tex>r_{p,q}</tex> представляет наибольшую строку <tex>i</tex>, у которой <tex>d_{i,j} = q</tex> и <tex>(i, j)</tex> лежит на диагонали <tex>p</tex>. Таким образом, <tex>q</tex> {{---}} это минимальное число различий между <tex>x(0, r_{p,q}-1)</tex> и любой подстрокой текста, заканчивающейся <tex>y_{r_{p,q}+p}</tex>. Значение <tex>m</tex> в строке <tex>r_{p,q}</tex>, для <tex>q < k</tex>, указывает, что в тексте имеется вхождение образца с точностью до <tex>k</tex> отличий, заканчивающееся в <tex>y_{m+p}</tex>. Таким образом, чтобы решить задачу <tex>k</tex> различий, достаточно вычислить значения <tex>r_{p,q}</tex> для <tex>q < k</tex>.
  
 
Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>.
 
Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>.
  '''for''' p = 0 '''to''' n
+
  '''int[]''' rpq('''int''' n, '''int''' m, '''int''' k, char[] x, char[] y)
    r(p,-1) = -1
+
    '''for''' p = 0 '''to''' n
'''for''' p = -(k+1) '''to''' -1
+
      r(p, -1) = -1
    r(p,|p|-1) = |p|-1
+
    '''for''' p = -(k + 1) '''to''' -1
    r(p,|p|-2) = |p|-2
+
      r(p, |p| - 1) = |p| - 1
'''for''' q = -1 '''to''' k
+
      r(p, |p| - 2) = |p| - 2
    r(n+1,q) = -1
+
    '''for''' q = -1 '''to''' k
'''for''' q = 0 '''to''' k
+
      r(n + 1, q) = -1
  '''for''' p = -q '''to''' n
+
    '''for''' q = 0 '''to''' k
      r = max(r(p,q-1) + 1, r(p-1,q-1), r(p+1,q-1) + 1)
+
      '''for''' p = -q '''to''' n
      r = min(r, m)
+
        r = max(r(p, q - 1) + 1, r(p - 1, q - 1), r(p + 1, q - 1) + 1)
      '''while''' r < m '''and''' r + p < n '''and''' x(r+1) = y(r+1+p)
+
        r = min(r, m)
        r++
+
        '''while''' r < m '''and''' r + p < n '''and''' x(r + 1) = y(r + 1 + p)
      r(p,q) = r
+
            r++
      '''if''' r(p,q) = m
+
        r(p, q) = r
        имеется вхождение с k отличиями, заканчивающееся в y(p+m)
+
        '''if''' r(p, q) = m
 +
            //имеется вхождение с k отличиями, заканчивающееся в y(p+m)
 +
            res.add(y(p + m))
 +
    '''return''' res
 
Алгоритм вычисляет значения <tex>r_{p,q}</tex> на <tex>n+k+1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.
 
Алгоритм вычисляет значения <tex>r_{p,q}</tex> на <tex>n+k+1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.
 
===Предварительные вычисления===
 
===Предварительные вычисления===
  
На этапе предварительной обработки, с помощью алгоритма Вейнера<ref>[http://europa.zbh.uni-hamburg.de/pubs/pdf/GieKur1997.pdf Giegerich R., Kurtz S. {{---}} From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction]</ref> строится [[wikipedia:ru:Суффиксное_дерево|суффиксное дерево]] строки <tex>y{\#}x{\$}</tex>, где <tex>\#</tex> и <tex>\$</tex> символы, не принадлежащие алфавиту, над которыми построены строки <tex>x</tex> и <tex>y</tex>. Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алфавит можно преобразовать так, что он будет выполняться за время <tex>O(n\log{\sigma})</tex>, где <tex>\sigma</tex> число различающихся символов образца. Стадия предварительной обработки требует время <tex>O(n)</tex> и <tex>O(n\log{m})</tex> для постоянного и неограниченного алфавитов, соответственно.
+
На этапе предварительной обработки, с помощью [[Алгоритм_Укконена|алгоритма Укконена]] строится [[Сжатое_суффиксное_дерево#suffix_tree|суффиксное дерево]] строки <tex>y{\#}x{\$}</tex>, где <tex>\#</tex> и <tex>\$</tex> {{---}} символы, не принадлежащие алфавиту, над которыми построены строки <tex>x</tex> и <tex>y</tex>. Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алфавит можно преобразовать так, что он будет выполняться за время <tex>O(n\log{\sigma})</tex>, где <tex>\sigma</tex> {{---}} число различающихся символов образца. Стадия предварительной обработки требует время <tex>O(n)</tex> и <tex>O(n\log{m})</tex> для постоянного и неограниченного алфавитов, соответственно.
 
===Модификация предыдущего алгоритма===
 
===Модификация предыдущего алгоритма===
  
В приведенном выше алгоритме перед циклом <tex>while</tex> для диагонали <tex>p</tex>, переменной <tex>r</tex> было присвоено такое значение, что <tex>x(1, r)</tex> сопоставляется с точностью до <tex>k</tex> различий с некоторой подстрокой текста, заканчивающейся <tex>y_{r+p}</tex>. Тогда функция цикла <tex>while</tex> находит максимальное значение для которого <tex>x(r+1, r+h) = y(r+p+1, r+p+h)</tex>. Обозначим это значение как <tex>h</tex>. Это эквивалентно нахождению длины самого длинного общего префикса суффиксов <tex>x(r+1, m)\$</tex> и <tex>y(r+p+1,n){\#}x{\$}</tex> предварительно вычисленной конкатенированной строки. Символ <tex>\#</tex> используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как <tex>y</tex>, так и <tex>x</tex>. Обозначим <tex>lca(r,p)</tex> как самый низкий общий предок в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение <tex>h</tex> задается <tex>length(lca(r,p))</tex>.
+
В приведенном выше алгоритме перед циклом <tex>while</tex> для диагонали <tex>p</tex>, переменной <tex>r</tex> было присвоено такое значение, что <tex>x(1, r)</tex> сопоставляется с точностью до <tex>k</tex> различий с некоторой подстрокой текста, заканчивающейся <tex>y_{r+p}</tex>. Тогда функция цикла <tex>\mathrm{while}</tex> находит максимальное значение для которого <tex>x(r+1, r+h) = y(r+p+1, r+p+h)</tex>. Обозначим это значение как <tex>h</tex>. Это эквивалентно нахождению длины самого длинного общего префикса суффиксов <tex>x(r+1, m)\$</tex> и <tex>y(r+p+1,n){\#}x{\$}</tex> предварительно вычисленной конкатенированной строки. Символ <tex>\#</tex> используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как <tex>y</tex>, так и <tex>x</tex>. Обозначим <tex>lca(r,p)</tex> как [[Сведение_задачи_LCA_к_задаче_RMQ#lca_suf_tree|самый низкий общий предок]] в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение <tex>h</tex> задается <tex>length(lca(r,p))</tex>.
 
===Оценка времени работы===
 
===Оценка времени работы===
  
Суффиксное дерево имеет <tex>O(n)</tex> узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам <tex>LCA</tex> требуется преобразование дерева, проводимое за линейное время. Значения <tex>r_{p,q}</tex> вычисляются на <tex>n+k+1</tex> диагоналях. Более того, для каждой диагонали надо вычислить <tex>k+1</tex> таких значений, что в общей сложности дает <tex>O(kn)</tex> запросов. Таким образом, общее время работы алгоритма k различий составляет <tex>O(kn)</tex> для алфавитов фиксированного размера, и <tex>O(n * \log{m} + kn)</tex> для неограниченных алфавитов.
+
Суффиксное дерево имеет <tex>O(n)</tex> узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам <tex>lca</tex> требуется преобразование дерева, проводимое за линейное время. Значения <tex>r_{p,q}</tex> вычисляются на <tex>n+k+1</tex> диагоналях. Более того, для каждой диагонали надо вычислить <tex>k+1</tex> таких значений, что в общей сложности дает <tex>O(k{\cdot}n)</tex> запросов. Таким образом, общее время работы алгоритма k различий составляет <tex>O(k{\cdot}n)</tex> для алфавитов фиксированного размера, и <tex>O(n \cdot \log{m} + k{\cdot}n)</tex> для неограниченных алфавитов.
 
===Параллельная версия алгоритма===
 
===Параллельная версия алгоритма===
  
В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до <tex>O(\log{n}+k)</tex>, при использовании одновременно <tex>n</tex> процессоров. Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос <tex>LCA</tex> за <tex>O(1)</tex>.
+
В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до <tex>O(\log{n}+k)</tex>, при использовании одновременно <tex>n</tex> процессоров. Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос <tex>lca</tex> за <tex>O(1)</tex>.
  
 
==Примечания==
 
==Примечания==
 
<references/>
 
<references/>
 +
 +
==См. также==
 +
*[[Алгоритм_Ландау-Вишкина_(k_несовпадений)|Алгоритм Ландау-Вишкина (k несовпадений)]]
  
 
==Источники информации==
 
==Источники информации==
* [http://algolist.manual.ru/search/fsearch/k_razl.php  k-различий - алгоритм Ландау-Вишкина]
+
* [http://algolist.manual.ru/search/fsearch/k_razl.php  algolist.manual.ru {{---}}алгоритм Ландау-Вишкина (k различий)]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Поиск подстроки в строке]]

Версия 21:27, 27 мая 2015

Задача:
По заданному слову [math]X[0..m-1][/math] найти в тексте или словаре [math]Y[0..n-1][/math] все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом [math]k[/math] возможных различий.

Например, при запросе [math]abcdef[/math] и [math]k = 2[/math], найти слова [math]abcdeRf[/math], [math]abHdef[/math], [math]VbRdef[/math] и так далее.

Описание задачи с точки зрения динамического программирования

Пусть [math]d_{i,j}[/math] — расстояние между префиксами строк [math]x[/math] и [math]y[/math], длины которых равны, соответственно, [math]i[/math] и [math]j[/math], то есть [math]d_{i,j} = d(x(0,i-1), y(0,j-1))[/math]. Перед тем, как начать вычислять [math]d_{i,j}[/math], надо установить граничные значения массива. Что касается первого столбца массива, то значение [math]d_{i,0}[/math] равно сумме цен удаления первых [math]i[/math] символов [math]x[/math]. Аналогично, значения [math]d_{0,j}[/math] первой строки задаются суммой цен вставки первых [math]j[/math] символов [math]y[/math]. Таким образом:

[math]d_{0,0} = 0[/math]

[math]d_{i,0} = \sum_{k = 1}^{i}{w(x_i, \varepsilon)}, для 1 \lt i \lt m[/math]

[math]d_{0,j} = \sum_{k = 1}^{j}{w(\varepsilon, j_k)}, для 1 \lt j \lt n[/math]

Чтобы решить задачу [math]k[/math] различий, матрицу расстояний[1] надо преобразовать таким образом, чтобы [math]d_{i,j}[/math] представлял минимальное расстояние между [math]x(0, i-1)[/math] и любой подстрокой [math]y[/math], заканчивающейся символом [math]y_j[/math]. Для этого достаточно ввести условие:

[math]d_{0,j} = 0, 0 \lt j \lt n[/math]

так как минимальное расстояние между [math]\varepsilon[/math] и любой подстрокой y равно [math]0[/math].

Оставшуюся часть матрицы вычислим с использованием цен редактирования расстояния Левенштейна и рекуррентного соотношения для [math]d_{i,j}[/math]:

[math]w(a,{\varepsilon}) = 1[/math]

[math]w({\varepsilon}, b) = 1[/math]

[math]w(a, b) = \left\{\begin{array}{llcl} 0&,\ a \ne b\\ 1&,\ a = b\\ \end{array}\right. [/math]

[math]d_{i,j} = \min(d_{i-1,j} + w(x_i,{\varepsilon}), d_{i,j-1} + w({\varepsilon}, y_j), d_{i-1,j-1} + w(x_i, y_i))[/math]

Теперь каждое значение, не превосходящее [math]k[/math], в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше [math]k[/math] отличий от образца.

Пример

Рассмотрим этот подход к решению задачи на примере: пусть [math]X=abcde, Y=aceabpcqdeabcr[/math]. Построим матрицу расстояний для этого случая:

j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
i a c e a b p c q d e a b c r
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 a 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1
2 b 2 1 1 2 1 0 1 2 2 2 2 1 0 1 2
3 c 3 2 1 2 2 1 1 1 2 3 3 2 1 3 1
4 d 4 3 2 2 3 2 2 2 2 2 3 3 2 1 1
5 e 5 4 3 2 3 3 3 3 3 3 2 3 3 2 2

Последняя строка матрицы показывает, что вхождения образца с точностью до [math]2[/math] отличий, заканчиваются в позициях [math]3[/math], [math]10[/math], [math]13[/math] и [math]14[/math]. Соответствующими подстроками являются [math]ace[/math], [math]abpcqde[/math], [math]abc[/math] и [math]abcr[/math].

Алгоритм

Пронумеруем диагонали матрицы расстояния целыми числами [math]p \in [-m, n][/math], таким образом, чтобы диагональ [math]p[/math] состояла из элементов [math](i, j)[/math], у которых [math]j - i = p[/math]. Пусть [math]r_{p,q}[/math] представляет наибольшую строку [math]i[/math], у которой [math]d_{i,j} = q[/math] и [math](i, j)[/math] лежит на диагонали [math]p[/math]. Таким образом, [math]q[/math] — это минимальное число различий между [math]x(0, r_{p,q}-1)[/math] и любой подстрокой текста, заканчивающейся [math]y_{r_{p,q}+p}[/math]. Значение [math]m[/math] в строке [math]r_{p,q}[/math], для [math]q \lt k[/math], указывает, что в тексте имеется вхождение образца с точностью до [math]k[/math] отличий, заканчивающееся в [math]y_{m+p}[/math]. Таким образом, чтобы решить задачу [math]k[/math] различий, достаточно вычислить значения [math]r_{p,q}[/math] для [math]q \lt k[/math].

Рассмотрим алгоритм вычисления [math]r_{p,q}[/math].

int[] rpq(int n, int m, int k, char[] x, char[] y)
   for p = 0 to n
      r(p, -1) = -1
   for p = -(k + 1) to -1
      r(p, |p| - 1) = |p| - 1
      r(p, |p| - 2) = |p| - 2
   for q = -1 to k
      r(n + 1, q) = -1
   for q = 0 to k
     for p = -q to n
        r = max(r(p, q - 1) + 1, r(p - 1, q - 1), r(p + 1, q - 1) + 1)
        r = min(r, m)
        while r < m and r + p < n and x(r + 1) = y(r + 1 + p)
           r++
        r(p, q) = r
        if r(p, q) = m
           //имеется вхождение с k отличиями, заканчивающееся в y(p+m)
           res.add(y(p + m))
   return res

Алгоритм вычисляет значения [math]r_{p,q}[/math] на [math]n+k+1[/math] диагоналях. Для каждой диагонали переменной строки [math]r[/math] можно присвоить не больше [math]m[/math] различных значений, что приводит к времени вычислений [math]O(mn)[/math]. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.

Предварительные вычисления

На этапе предварительной обработки, с помощью алгоритма Укконена строится суффиксное дерево строки [math]y{\#}x{\$}[/math], где [math]\#[/math] и [math]\$[/math] — символы, не принадлежащие алфавиту, над которыми построены строки [math]x[/math] и [math]y[/math]. Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алфавит можно преобразовать так, что он будет выполняться за время [math]O(n\log{\sigma})[/math], где [math]\sigma[/math] — число различающихся символов образца. Стадия предварительной обработки требует время [math]O(n)[/math] и [math]O(n\log{m})[/math] для постоянного и неограниченного алфавитов, соответственно.

Модификация предыдущего алгоритма

В приведенном выше алгоритме перед циклом [math]while[/math] для диагонали [math]p[/math], переменной [math]r[/math] было присвоено такое значение, что [math]x(1, r)[/math] сопоставляется с точностью до [math]k[/math] различий с некоторой подстрокой текста, заканчивающейся [math]y_{r+p}[/math]. Тогда функция цикла [math]\mathrm{while}[/math] находит максимальное значение для которого [math]x(r+1, r+h) = y(r+p+1, r+p+h)[/math]. Обозначим это значение как [math]h[/math]. Это эквивалентно нахождению длины самого длинного общего префикса суффиксов [math]x(r+1, m)\$[/math] и [math]y(r+p+1,n){\#}x{\$}[/math] предварительно вычисленной конкатенированной строки. Символ [math]\#[/math] используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как [math]y[/math], так и [math]x[/math]. Обозначим [math]lca(r,p)[/math] как самый низкий общий предок в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение [math]h[/math] задается [math]length(lca(r,p))[/math].

Оценка времени работы

Суффиксное дерево имеет [math]O(n)[/math] узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам [math]lca[/math] требуется преобразование дерева, проводимое за линейное время. Значения [math]r_{p,q}[/math] вычисляются на [math]n+k+1[/math] диагоналях. Более того, для каждой диагонали надо вычислить [math]k+1[/math] таких значений, что в общей сложности дает [math]O(k{\cdot}n)[/math] запросов. Таким образом, общее время работы алгоритма k различий составляет [math]O(k{\cdot}n)[/math] для алфавитов фиксированного размера, и [math]O(n \cdot \log{m} + k{\cdot}n)[/math] для неограниченных алфавитов.

Параллельная версия алгоритма

В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до [math]O(\log{n}+k)[/math], при использовании одновременно [math]n[/math] процессоров. Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос [math]lca[/math] за [math]O(1)[/math].

Примечания

См. также

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