Изменения

'''HAT(Hashed Array Tree)Формулировка задачи:''' {{---}} структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьевПо заданному слову <tex>X[0.. В действительности HAT {{m---}} это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка <math>O(N)1]</mathtex>, чтобы добавить найти в тексте или словаре <mathtex>NY[0..n-1]</mathtex> элементов к пустому массиву и требует всего лишь все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <mathtex>O(\sqrt{N})k</mathtex> дополнительной памятивозможных различий.

==ЗначимостьОписание задачи с точки зрения динамического программирования==Массивы переменной Пусть <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: чрезмерное копирование элементов и использование памяти. HAT Матрица_расстояний|матрицу расстояний]] надо преобразовать таким образом, чтобы <tex>d_{{---i,j}} реализация массива переменной длины</tex> представлял минимальное расстояние между <tex>x(1, решающая обе проблемы i)</tex> и предоставляющая ряд преимуществ по сравнению со стандартными реализациямилюбой подстрокой <tex>y</tex>, заканчивающейся символом <tex>y_j</tex>.Для этого достаточно ввести условие:

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

===Расход памяти===При перераспределении Оставшуюся часть матрицы вычислим с использованием цен редактирования расстояния Левенштейна и копировании HAT использует меньше памяти, чем в стандартных подходах. Самый плохой случай рекуррентного соотношения для HAT {{---}} размер элементов равен размеру указателей, и число элементов на один больше числа, при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значения приведены в таблице.Затраты памяти в самом плохом случае {{---}} <mathtex>(top+leaf-1) ~= 2\sqrtd_{N} = O(\sqrt{N})</math>. Если последний лист будет половиной полногоi, то ожидаемая трата памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{Nj}</mathtex> (top {{---}} главный массив, leaf {{---}} листья), а это все еще <math>O(\sqrt{N})</math>. Сравним с другими структурами, добавляющими элементы за <math>O(1)</math>. Например, отдельно связанные списки требуют O(N) памяти (один указатель для каждого элемента).:

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

<tex>w(a, b) = \left\{\begin{array}{llcl}0&,\ a{\ne}b\\1&,\ a=b\\\end{array}\right.</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>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>. ==ЗаключениеАлгоритм==HAT [[Алгоритм_Укконена|Алгоритм Укконена]] говорит, что при вычисления расстояний между строками, диагонали матрицы можно пронумеровать целыми числами <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>. '''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)Алгоритм вычисляет значения <tex>r_{p,q}</tex> на <tex>n+k+1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.===Предварительные вычисления=== На этапе предварительной обработки, с помощью алгоритма Вейнера<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:Суффиксное_дерево|суффиксное дерево]] строки <tex>y{\#}x{\$} удобная структура данных переменной длины</tex>, где <tex>\#</tex> и <tex>\$</tex> – символы, не принадлежащие алфавиту, над которыми построены строки <tex>x</tex> и <tex>y</tex>. Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алфавит можно преобразовать так, позволяющая добавить N элементов что он будет выполняться за время <tex>O(n\log{\sigma})</tex>, где <tex>\sigma</tex> – число различающихся символов образца. Стадия предварительной обработки требует время <mathtex>O(Nn)</mathtex> времени и требующая <mathtex>O(n\sqrtlog{Nm})</mathtex> дополнительной памятидля постоянного и неограниченного алфавитов, соответственно. HAT обеспечивает все стандартные возможности обычных массивов===Модификация предыдущего алгоритма=== В приведенном выше алгоритме перед циклом <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,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>.===Оценка времени работы приложений=== Суффиксное дерево имеет <tex>O(n)</tex> узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам <tex>LCA</tex> требуется преобразование дерева, проводимое за линейное время. Значения <tex>r_{p,q}</tex> вычисляются на <tex>n+k+1</tex> диагоналях. Более того, для каждой диагонали надо вычислить <tex>k+1</tex> таких значений, что в общей сложности дает <tex>O(kn)</tex> запросов. Таким образом, HAT предлагает ряд существенных преимуществ над другими реализациями массивов переменной длиныобщее время работы алгоритма k различий составляет <tex>O(kn)</tex> для алфавитов фиксированного размера, и <tex>O(n * \log{m} + kn)</tex> для неограниченных алфавитов.===Параллельная версия алгоритма=== В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. Она позволяет уменьшить время работы до <tex>O(\log{n}+k)</tex>, при использовании одновременно <tex>n</tex> процессоров. Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос <tex>LCA</tex> за <tex>O(1)</tex>. ==Примечания==<references/>

*[[wikipediahttp:en:Hashed array tree|Википедия]]*Cline, M//algolist.Pmanual. and Gru/search/fsearch/k_razl.A. Lomow, C++ FAQs, Reading, MA: Addisonphp k-различий - алгоритм Ландау-Wesley, 1995. *Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.Вишкина]