Обсуждение участника:SergeyBud — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Формулировка задачи:''' По заданному слову длины <tex>m</tex> найти в тексте или словаре размера <tex>n</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.
+
'''Формулировка задачи:''' По заданному слову <tex>X[0..m-1]</tex> найти в тексте или словаре <tex>Y[0..n-1]</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</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(1,i), y(1,j))</tex>.
Строка 24: Строка 22:
 
<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>. Построим матрицу расстояний для этого случая:
 +
[[Файл:Table_k_razlichiy.png]]
 +
 
 +
Последняя строка матрицы показывает, что вхождения образца с точностью до <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(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>r_{p,q}</tex>, используя [[Динамическое_программирование|динамическое программирование]].
+
Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>.
 
  '''for''' p = 0 '''to''' n
 
  '''for''' p = 0 '''to''' n
 
     r(p,-1) = -1
 
     r(p,-1) = -1
Строка 45: Строка 50:
 
       '''if''' r(p,q) = m
 
       '''if''' r(p,q) = m
 
         имеется вхождение с k отличиями, заканчивающееся в y(p+m)
 
         имеется вхождение с k отличиями, заканчивающееся в y(p+m)
Алгоритм вычисляет значения <tex>r_{p,t}</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>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.
 
===Предварительные вычисления===
 
===Предварительные вычисления===
  

Текущая версия на 20:22, 22 мая 2015

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

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

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

[math]d_{0,j} = 0, 0 \lt j \lt n[/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]. Построим матрицу расстояний для этого случая: Table k razlichiy.png

Последняя строка матрицы показывает, что вхождения образца с точностью до [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(1, r_{p,q})[/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].

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)

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

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

На этапе предварительной обработки, с помощью алгоритма Вейнера[1] строится суффиксное дерево строки [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]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(kn)[/math] запросов. Таким образом, общее время работы алгоритма k различий составляет [math]O(kn)[/math] для алфавитов фиксированного размера, и [math]O(n * \log{m} + kn)[/math] для неограниченных алфавитов.

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

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

Примечания[править]

Источники информации[править]