Изменения

'''HAT(Hashed Array Tree)Формулировка задачи:''' {{По заданному слову <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} = d(x(1,i), y(1,j))</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_{i,j}</tex>: <tex>w(a,{\varepsilon}) =1</tex> <tex>w({\varepsilon}, b) =Устройство HAT1</tex> <tex>w(a, b) =\left\{\begin{array}{llcl}0&,\ a{\ne}b\\1&,\ a=b\\\end{array}\right.</tex> HAT состоит из главного массива указателей и ряда листьев<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>X=ABCDE, и являются степенями двойкиY=ACEABPCQDEABCR</tex>.Построим матрицу расстояний для этого случая:[[Файл:AlgoF2Table_k_razlichiy.gif|rightpng]]=Добавление элементов=Благодаря степеням двойкиПоследняя строка матрицы показывает, что вхождения образца с точностью до <tex>2</tex> отличий, мы сможем эффективно находить элементы заканчиваются в HATпозициях <tex>3</tex>, используя поразрядные операции(см<tex>10</tex>, <tex>13</tex> и <tex>14</tex>.Пример1)Соответствующими подстроками являются <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>(Oi, 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>. Необходимо всего лишь добавить указатель в свободную ячейку главного массива '''for''' p = 0 '''to''' n r(p, а значит также сможем произвести вставку элемента за О-1) = -1 '''for''' p = -(k+1).'''to''' -1Самый интересный случай r(p, когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT |p|-1) = |p|- следующая степень двойки1 r(главный массив и каждый лист все еще равны между собойp,|p|-2). Далее скопируем все элементы в новый экземпляр HAT= |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), то есть число элементов превышает квадрат степени 2. Напримерr(p+1, для Nq-1) + 1) r =4min(r, общая сумма перекопирования будет равна m) '''while''' r < m '''and''' r + p < n '''and''' x(r+1) = y(r+1+4p) r++16 r(p,q) = r '''if''' r(p,q) = m имеется вхождение с k отличиями, заканчивающееся в y(p+64m)Алгоритм вычисляет значения <tex>r_{p,q}</tex> на <tex>n+256k+1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.===Предварительные вычисления=== На этапе предварительной обработки, с помощью алгоритма Вейнера<ref>[http://europa.zbh.uni-hamburg.de/pubs/pdf/GieKur1997.+Npdf 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(x^n\log{\sigma})</tex>, где <tex>\sigma</tex> – число различающихся символов образца. Стадия предварительной обработки требует время <tex>O(n+1)-1</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(1r+xp+x^21, r+x^3p+h)</tex>.Обозначим это значение как <tex>h</tex>.. Это эквивалентно нахождению длины самого длинного общего префикса суффиксов <tex>x(r+ x^n1, m), тогда для нашего случая: 1 \$</tex> и <tex>y(r+4+4^2+4^3p+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>.+4^n ===Оценка времени работы===  Суффиксное дерево имеет <tex>O(4^(n)</tex> узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам <tex>LCA</tex> требуется преобразование дерева, проводимое за линейное время. Значения <tex>r_{p,q}</tex> вычисляются на <tex>n+k+1) -</tex> диагоналях. Более того, для каждой диагонали надо вычислить <tex>k+1)</tex> таких значений, что в общей сложности дает <tex>O(4-1kn) = </tex> запросов. Таким образом, общее время работы алгоритма k различий составляет <tex>O(4N-1kn)</3tex> для алфавитов фиксированного размера, или около 4и <tex>O(n * \log{m} + kn)</3Ntex> для неограниченных алфавитов.===Параллельная версия алгоритма=== В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Это означает это, среднее число дополнительных операций копирования - Она позволяет уменьшить время работы до <tex>O(N\log{n}+k) для последовательного добавления N элементов</tex>, при использовании одновременно <tex>n</tex> процессоров. Для данной оценки необходимо, не чтобы каждый из процессоров выполнял последовательный запрос <tex>LCA</tex> за <tex>O(N^21)</tex>. ==Примечания==<references/> ==Источники информации==* [http://algolist.manual.ru/search/fsearch/k_razl.php k-различий - алгоритм Ландау-Вишкина]