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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
|definition = По заданному слову <tex>x[0 \ldots m-1]</tex> найти в тексте или словаре <tex>y[0 \ldots n-1]</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.
+
|definition = По заданному слову <tex>X[0..m-1]</tex> найти в тексте или словаре <tex>Y[0..n-1]</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.
 
}}
 
}}
В данном случае под различием подразумевается [[Задача_о_редакционном_расстоянии,_алгоритм_Вагнера-Фишера#levenstain_dist|расстояние Левенштейна]] {{---}} минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
 
 
 
Например, при запросе <tex>abcdef</tex> и <tex>k = 2</tex>, найти слова <tex>abcdeRf</tex>, <tex>abHdef</tex>, <tex>VbRdef</tex> и так далее.
 
Например, при запросе <tex>abcdef</tex> и <tex>k = 2</tex>, найти слова <tex>abcdeRf</tex>, <tex>abHdef</tex>, <tex>VbRdef</tex> и так далее.
  
 
==Описание задачи с точки зрения динамического программирования==
 
==Описание задачи с точки зрения динамического программирования==
Алгоритм k различий Ландау-Вишкина основан на подходе, близком методу [[Динамическое_программирование|динамического программирования]] для вычисления расстояния между строками, который предложил Укконен<ref>[http://link.springer.com/chapter/10.1007%2F3-540-12689-9_129#page-1 Esko Ukkonen {{---}} On approximate string matching]</ref>. Перед тем, как перейти к этому алгоритму, рассмотрим метод динамического программирования и его адаптацию в стиле Укконена.
 
 
 
Пусть <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(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>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>. Таким образом:
Строка 14: Строка 10:
 
<tex>d_{0,0} = 0</tex>
 
<tex>d_{0,0} = 0</tex>
  
<tex>d_{i,0} = \sum\limits_{k = 1}^{i}{w(x_i, \varepsilon)}, для 1 < i < m</tex>
+
<tex>d_{i,0} = \sum_{k = 1}^{i}{w(x_i, \varepsilon)}, для 1 < i < m</tex>
  
<tex>d_{0,j} = \sum\limits_{k = 1}^{j}{w(\varepsilon, j_k)}, для 1 < j < n</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>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>. Для этого достаточно ввести условие:  
Строка 40: Строка 36:
 
Теперь каждое значение, не превосходящее <tex>k</tex>, в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше <tex>k</tex> отличий от образца.
 
Теперь каждое значение, не превосходящее <tex>k</tex>, в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше <tex>k</tex> отличий от образца.
 
===Пример===
 
===Пример===
Рассмотрим этот подход к решению задачи на примере: пусть  
+
Рассмотрим этот подход к решению задачи на примере: пусть <tex>X=abcde, Y=aceabpcqdeabcr</tex>. Построим матрицу расстояний для этого случая:
 
 
<tex>x = abcde</tex>,  
 
 
 
<tex>y = aceabpcqdeabcr</tex>.  
 
 
 
Построим матрицу расстояний для этого случая:
 
 
{| class="wikitable" width="20%"
 
{| class="wikitable" width="20%"
 
! style="text-align: center;" |  
 
! style="text-align: center;" |  
Строка 200: Строка 190:
  
 
Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>.
 
Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>.
  '''int[]''' rpq('''int''' n, '''int''' m, '''int''' k, '''char[]''' x, '''char[]''' y)
+
  '''int[]''' rpq('''int''' n, '''int''' m, '''int''' k, char[] x, char[] y)
 
     '''for''' p = 0 '''to''' n
 
     '''for''' p = 0 '''to''' n
 
       r(p, -1) = -1
 
       r(p, -1) = -1
Строка 216: Строка 206:
 
         r(p, q) = r
 
         r(p, q) = r
 
         '''if''' r(p, q) = m
 
         '''if''' r(p, q) = m
             <font color=green>// имеется вхождение с k отличиями, заканчивающееся в y(p+m)</font>
+
             //имеется вхождение с k отличиями, заканчивающееся в y(p+m)
 
             res.add(y(p + m))
 
             res.add(y(p + m))
 
     '''return''' res
 
     '''return''' res
Строка 222: Строка 212:
 
===Предварительные вычисления===
 
===Предварительные вычисления===
  
На этапе предварительной обработки, с помощью [[Алгоритм_Укконена|алгоритма Укконена]] строится [[Сжатое_суффиксное_дерево#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> для постоянного и неограниченного алфавитов, соответственно.
+
На этапе предварительной обработки, с помощью [[Алгоритм_Укконена|алгоритма Укконена]] строится [[Сжатое_суффиксное_дерево#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>\mathrm{while}</tex> для диагонали <tex>p</tex>, переменной <tex>r</tex> было присвоено такое значение, что <tex>x(0, r - 1)</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>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>.
 
===Оценка времени работы===
 
===Оценка времени работы===
  
Строка 232: Строка 222:
  
 
В 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/>
  
 
==См. также==
 
==См. также==
 
*[[Алгоритм_Ландау-Вишкина_(k_несовпадений)|Алгоритм Ландау-Вишкина (k несовпадений)]]
 
*[[Алгоритм_Ландау-Вишкина_(k_несовпадений)|Алгоритм Ландау-Вишкина (k несовпадений)]]
 
==Примечания==
 
<references/>
 
  
 
==Источники информации==
 
==Источники информации==
* [http://algolist.manual.ru/search/fsearch/k_razl.php  algolist.manual.ru {{---}} алгоритм Ландау-Вишкина (k различий)]
+
* [http://algolist.manual.ru/search/fsearch/k_razl.php  algolist.manual.ru {{---}}алгоритм Ландау-Вишкина (k различий)]
* [https://books.google.ru/books?id=rfSjZhDxBtUC&pg=PA164&lpg=PA164&dq=Landau,+Vishkin,+1986b,+1989&source=bl&ots=Tox806u_Zr&sig=m9rpFTdcV8QzmN4UktdoD9-NX_k&hl=ru&sa=X&ei=LEJnVcLKE4uqsQGmvYPIAQ&ved=0CCYQ6AEwAQ#v=onepage&q&f=false Graham A. Stephen {{---}} String Searching Algorithms (Lecture Notes Series on Computing), ISBN 9810237030]
 
* [http://habrahabr.ru/post/114997/ habrahabr.ru {{---}} Нечёткий поиск в тексте и словаре]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Поиск подстроки в строке]]
[[Категория: Нечёткий поиск]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: