Изменения

'''Формулировка задачи:''' {{Задача|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} = d(x(10,i-1), y(10,j-1))</tex>.Чтобы решить задачу Перед тем, как начать вычислять <tex>kd_{i,j}</tex> различий, [[wikipedia:ru:Матрица_расстояний|матрицу расстояний]] надо преобразовать таким образомустановить граничные значения массива. Что касается первого столбца массива, чтобы то значение <tex>d_{i,j0}</tex> представлял минимальное расстояние между равно сумме цен удаления первых <tex>i</tex> символов <tex>x(1</tex>. Аналогично, значения <tex>d_{0, i)j}</tex> и любой подстрокой первой строки задаются суммой цен вставки первых <tex>yj</tex>, заканчивающейся символом символов <tex>y_jy</tex>. Для этого достаточно ввести условиеТаким образом:

<tex>d_{0,j0} = 0, 0 < j < n</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>:

0&,\ a{ \ne} b\\1&,\ a = b\\

<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>X=ABCDEabcde, Y=ACEABPCQDEABCRaceabpcqdeabcr</tex>. Построим матрицу расстояний для этого случая:[[Файл{| 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:Table_k_razlichiy.png]]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>ACEace</tex>, <tex>ABPCQDEabpcqde</tex>, <tex>ABCabc</tex> и <tex>ABCRabcr</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(10, 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>.

'''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

На этапе предварительной обработки, с помощью [[Алгоритм_Укконена|алгоритма Вейнера<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:Суффиксное_деревоСжатое_суффиксное_дерево#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>\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>LCAlca</tex> требуется преобразование дерева, проводимое за линейное время. Значения <tex>r_{p,q}</tex> вычисляются на <tex>n+k+1</tex> диагоналях. Более того, для каждой диагонали надо вычислить <tex>k+1</tex> таких значений, что в общей сложности дает <tex>O(knk{\cdot}n)</tex> запросов. Таким образом, общее время работы алгоритма k различий составляет <tex>O(knk{\cdot}n)</tex> для алфавитов фиксированного размера, и <tex>O(n * \cdot \log{m} + knk{\cdot}n)</tex> для неограниченных алфавитов.

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

* [http://algolist.manual.ru/search/fsearch/k_razl.php kalgolist.manual.ru {{--различий - }}алгоритм Ландау-Вишкина(k различий)] [[Категория: Алгоритмы и структуры данных]][[Категория: Поиск подстроки в строке]]