Изменения

'''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>. Для примера рассмотрим однку из реализацийэтого достаточно ввести условие: /*****/

==Устройство HAT==HAT состоит из главного массива указателей и ряда листьев(так же одномерные массивы), в которых хранятся элементы.Число указателей в главном массиве и число элементов в каждом листе - равны между собой, и являются степенями двойки.[[Файл:AlgoF2.gif|400px|right]]===Добавление элементов===Благодаря степеням двойки, мы сможем эффективно находить элементы в HAT, используя поразрядные операции. Чаще всего при добалении элемента, в одном из листьев(последний незаполненный на данный момент) найдется свободное место, что позволит осуществить быструю вставку(O(1)). Реже мы столкнемся со случаем, когда необходимо создать новый лист. Необходимо всего лишь добавить указатель в свободную ячейку главного массива, а значит также сможем произвести вставку элемента за О(1).Самый интересный случай, когда главный массив и все листья заполнены. Сначала Оставшуюся часть матрицы вычислим новый размер HAT - следующая степень двойки(главный массив с использованием цен редактирования расстояния Левенштейна и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился).Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивв переменной длины. Копировать элементы мы будем только тогда, когда главный массив полон, то есть число элементов превышает квадрат степени 2. Например, рекуррентного соотношения для N=4, общая сумма перекопирования будет равна 1+4+16+64+256+...+N. Воспользуемся тождеством: <mathtex>(x^d_{n+1i,j} -1)=(x-1)(1+x+x^2+x^3+... + x^n)</mathtex>, тогда для нашего случая: <math>1 +4+4^2+4^3+...+4^n = (4^{n+1} -1)/(4-1) = (4N-1)/3</math>, или около <math>4/3N</math>. Это означает, что среднее число дополнительных операций копирования - O(N) для последовательного добавления N элементов, а не <math>O(N^2)</math>.

===Расход памяти===[[Файл:Table_HAT.JPG|350px|right]]При перераспределении и копировании HAT использует мнеьше памяти, чем в стандартных подходах. Самый плохой случай для HAT - размер элементов равен размеру указателей и число элементов на один больше числа при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значени привидены в таблице.Затраты памяти в самом плохом случае - <mathtex>w(top+leaf-1) ~= 2*sqrt(N) = O(sqrt(N))</math>. Если последний лист будет половиной полногоa, то ожидаемая трата памяти уменьшается до <math>(top + leaf/2{\varepsilon}) ~= 1.5*sqrt(N)</math>, а это все еще <math>O(sqrt (N))</mathtex>. Сравним с другими структурами, добавляющими элементы за О(1). Например, отдельно связанные списки требуют O(N) памяти (один указатель для каждого элемента).

<tex>w({\varepsilon}, b) ===Эффективность===[[Файл:AlgoF3.gif|350px|left|Граффик 1]][[Файл:AlgoF4.gif|350px|right| Граффик 2]]Сравнивая со стандартным массивом переменной длины, реализованным в стандартной библиотеке С++, мы получаем, что благодаря предвычислению (1<<power)-1, разыменование элементов в HAT происходит приблизительно в два раза быстрее, чем разыменование в стандартном массиве С++. Рассотрим несколько граффиков, показывающих скорость работы HAT на некоторых алгоритмах:*1) Быстрая сортировка(QuickSort). График сравнивает HAT и стандартный массив в С++(левый график).*2) Добавление и сортировка(правый график)./tex>

Все стандартные тесты были выполнены на 100Mhz HP 700 series PA-RISC workstation running HPUX 9.01 with 256 MB of memory<tex>w(a, b) = \left\{\begin{array}{llcl}0&,\ a{\ne}b\\1&,\ a=b\\\end{array}\right.</tex>

<tex>d_{i,j} ==Заключение==HAT min(d_{i- удобная структура данных1,j} + w(x_i,{\varepsilon}), переменной длиныd_{i, позволяющая добавить N элементов за Oj-1} + w(N{\varepsilon}, y_j) времени и требующая O, d_{i-1,j-1} + w(sqrt(Nx_i, y_i)) памяти. HAT обеспечивает все стадартные возможности обычных массивов, включая произвольный доступ к элементам. Она поддерживает известное колличество памяти для любого колличества элементов и не требует специальной настроки для эффективной работы приложений. Таким образом HAT предлагает ряд сильных преимуществ над другими реализациями массивов переменной длины.</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>. ==ЛитератураАлгоритм==*Cline[[Алгоритм_Укконена|Алгоритм Укконена]] говорит, что при вычисления расстояний между строками, диагонали матрицы можно пронумеровать целыми числами <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, Mq}+p}</tex>.PЗначение <tex>m</tex> в строке <tex>r_{p,q}</tex>, для <tex>q < k</tex>, указывает, что в тексте имеется вхождение образца с точностью до <tex>k</tex> отличий, заканчивающееся в <tex>y_{m+p}</tex>. and GТаким образом, чтобы решить задачу <tex>k</tex> различий, достаточно вычислить значения <tex>r_{p,q}</tex> для <tex>q < k</tex>.A Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>. Lomow '''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, Cq) = m имеется вхождение с k отличиями, заканчивающееся в y(p+m)Алгоритм вычисляет значения <tex>r_{p,q}</tex> на <tex>n+k+ FAQs1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.===Предварительные вычисления=== На этапе предварительной обработки, Readingс помощью алгоритма Вейнера<ref>[http://europa.zbh.uni-hamburg.de/pubs/pdf/GieKur1997.pdf Giegerich R., MAKurtz S. {{---}} From Ukkonen to McCreight and Weiner: AddisonA Unifying View of Linear-WesleyTime Suffix Tree Construction]</ref> строится [[wikipedia:ru:Суффиксное_дерево|суффиксное дерево]] строки <tex>y{\#}x{\$}</tex>, где <tex>\#</tex> и <tex>\$</tex> – символы, не принадлежащие алфавиту, над которыми построены строки <tex>x</tex> и <tex>y</tex>. Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алфавит можно преобразовать так, 1995что он будет выполняться за время <tex>O(n\log{\sigma})</tex>, где <tex>\sigma</tex> – число различающихся символов образца. Стадия предварительной обработки требует время <tex>O(n)</tex> и <tex>O(n\log{m})</tex> для постоянного и неограниченного алфавитов, соответственно.===Модификация предыдущего алгоритма===*CormenВ приведенном выше алгоритме перед циклом <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, Tn){\#}x{\$}</tex> предварительно вычисленной конкатенированной строки.HСимвол <tex>\#</tex> используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как <tex>y</tex>, так и <tex>x</tex>.Обозначим <tex>lca(r, Cp)</tex> как самый низкий общий предок в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение <tex>h</tex> задается <tex>length(lca(r,p))</tex>.===Оценка времени работы=== Суффиксное дерево имеет <tex>O(n)</tex> узлов.EДля поддержки определения самого низкого общего предка за линейное время, алгоритмам <tex>LCA</tex> требуется преобразование дерева, проводимое за линейное время. LeisersonЗначения <tex>r_{p, and Rq}</tex> вычисляются на <tex>n+k+1</tex> диагоналях.LБолее того, для каждой диагонали надо вычислить <tex>k+1</tex> таких значений, что в общей сложности дает <tex>O(kn)</tex> запросов. RivestТаким образом, общее время работы алгоритма k различий составляет <tex>O(kn)</tex> для алфавитов фиксированного размера, и <tex>O(n * \log{m} + kn)</tex> для неограниченных алфавитов. Introduction to Algorithms===Параллельная версия алгоритма=== В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до <tex>O(\log{n}+k)</tex>, Cambridgeпри использовании одновременно <tex>n</tex> процессоров. Для данной оценки необходимо, MAчтобы каждый из процессоров выполнял последовательный запрос <tex>LCA</tex> за <tex>O(1)</tex>. ==Примечания==<references/> ==Источники информации==* [http: MIT Press, 1990//algolist.manual.ru/search/fsearch/k_razl.php k-различий - алгоритм Ландау-Вишкина]