Обсуждение участника:SergeyBud — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавление элементов)
 
(не показано 8 промежуточных версий 3 участников)
Строка 1: Строка 1:
'''HAT(Hashed Array Tree)''' {{---}} структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев. Внешне структура похожа на хеш-таблицу с разрешением коллизий методом цепочек, используя расширение структуры, отсюда и название. В действительности HAT {{---}} это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка <math>O(N)</math>, чтобы добавить <math>N</math> элементов к пустому массиву, и требует всего лишь <math>O(\sqrt{N})</math> дополнительной памяти.  
+
'''Формулировка задачи:''' По заданному слову <tex>X[0..m-1]</tex> найти в тексте или словаре <tex>Y[0..n-1]</tex> все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом <tex>k</tex> возможных различий.
  
==Значимость==
+
==Описание задачи с точки зрения динамического программирования==
Массивы переменной длины {{---}} наиболее естественная и удобная структура данных для многих приложений, так как они обеспечивают постоянное время доступа к их элементам. Однако при их реализации мы можем столкнуться с двумя основными проблемами: чрезмерное копирование элементов и использование памяти. HAT {{---}} реализация массива переменной длины, решающая обе проблемы и предоставляющая ряд преимуществ по сравнению со стандартными реализациями.
+
Пусть <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_{0,j} = 0, 0 < j < n</tex> .
HAT состоит из главного массива указателей <tex>top</tex> и ряда листьев <tex>leaf</tex> (так же одномерные массивы), в которых хранятся элементы.
 
Возможное число указателей в главном массиве и возможное число элементов в каждом листе равны между собой и являются степенями двойки. HAT зполняется элементами от самого малого листа к самому большому, при этом каждый лист заполняется слева направо.
 
===Получение элемента по номеру===
 
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Пусть размер главного массива и каждого листа будет равен <tex>2^{power}</tex>.
 
  '''int''' topIndex('''int''' j)
 
    <font color=green>// Получить номер указателя в основном массиве</font>
 
    '''return''' j >> power
 
  '''int''' leafIndex('''int''' j)
 
    <font color=green>// Получить номер листа</font>
 
    '''return''' j & ((1 << power) - 1)
 
  '''int''' getHat('''int''' j)
 
    <font color=green>// Вернуть элемент HAT. Нет проверки на выход за пределы массива.</font>
 
    '''return''' top[topIndex(j)][leafIndex(j)]
 
Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с размером листа равным <tex>4</tex>, тогда для нашего случая <tex>power = 2</tex> <tex>(4 = 2^2)</tex>. Получим значения функций для элемент под номером <tex>5</tex>:
 
*<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен опреации деления (взятию по модулю) <tex>j</tex> на <math>2^{2}</math>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе (нумерция листов с <tex>0</tex>).
 
*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{2}</tex>. Тоесть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>.
 
*<tex>5_{10} = 101_2 - 101</tex> <tex>\&</tex> <tex>011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация так же с <tex>0</tex>).
 
[[Файл:fullHAT.png|200px]]
 
  
===Добавление элементов===
+
Оставшуюся часть матрицы вычислим с использованием цен редактирования расстояния Левенштейна и рекуррентного соотношения для <tex>d_{i,j}</tex>:
*Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку {{---}} <math>O(1)</math>.
 
*Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <math>O(1)</math>.
 
*Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в <tex>2</tex> раза, то есть <math>power = power \cdot 2 </math>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).
 
*Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон (достигли соответствующей степени двойки, то есть <tex> N = (2 \cdot 2)^k</tex>, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <math>1+4+16+64+256+...+N</math>. Воспользуемся тождеством: <math>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</math>, тогда для нашего случая: <math>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</math>, или около <math>4N/3</math>. Это означает, что среднее число дополнительных операций копирования {{---}} <math>O(N)</math> для последовательного добавления N элементов, а не <math>O(N^2)</math>. Мы получили <math>4N/3</math> против <math>2N</math> в обычном динамическом массиве, то есть константа уменьшилась.
 
[[Файл:AlgoF2.gif|400px]]
 
  
===Расход памяти===
+
<tex>w(a,{\varepsilon}) = 1</tex>
HAT использует меньше дополнительной памяти, чем в стандартных подходах к расширению массивов, то есть полном перекопировании и перераспределении всего массива.
 
Затраты дополнительной памяти (уже выделенной, но еще не используемой) в  самом плохом случае {{---}} <math>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</math> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{N}</math>, а это все еще <math>O(\sqrt{N})</math>.
 
Сравним с другими структурами, добавляющими элементы за <math>O(1)</math>. Например, отдельно связанные списки требуют O(N) дополнительной памяти (один указатель для каждого элемента).
 
  
==Эффективность==
+
<tex>w({\varepsilon}, b) = 1</tex>
Благодаря преимуществам, предоставляемыми HAT (так например вычисление адреса происходит приблизительно в 2 раза быстрее, чем в стандартном массиве C++ {{---}} для соответствующего <tex>power</tex> мы можем сделать предвычисление выражения <tex>(1<<power)-1</tex> тогда для вычисления адреса в обоих массивах потребуется всего одна битовая операция), ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов<ref>[http://pmg.org.ru/ai/tree_hash.htm  Результаты тестов]</ref>.
 
  
== Примечания ==
+
<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>.
 +
 
 +
==Алгоритм==
 +
 
 +
[[Алгоритм_Укконена|Алгоритм Укконена]] говорит, что при вычисления расстояний между строками, диагонали матрицы можно пронумеровать целыми числами <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>. Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алфавит можно преобразовать так, что он будет выполняться за время <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>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> запросов. Таким образом, общее время работы алгоритма 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/>
 
<references/>
  
 
==Источники информации==
 
==Источники информации==
*[[wikipedia:en:Hashed array tree | Wikipedia {{---}} Hashed array tree ]]
+
* [http://algolist.manual.ru/search/fsearch/k_razl.php  k-различий - алгоритм Ландау-Вишкина]
*Cline, M.P. and G.A. Lomow, C++ FAQs, Reading, MA: Addison-Wesley, 1995. 
 
*Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.
 

Текущая версия на 20:22, 22 мая 2015

Формулировка задачи: По заданному слову [math]X[0..m-1][/math] найти в тексте или словаре [math]Y[0..n-1][/math] все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом [math]k[/math] возможных различий.

Описание задачи с точки зрения динамического программирования

Пусть [math]d_{i,j}[/math] - расстояние между префиксами строк [math]x[/math] и [math]y[/math], длины которых равны, соответственно, [math]i[/math] и [math]j[/math], то есть [math]d_{i,j} = d(x(1,i), y(1,j))[/math]. Чтобы решить задачу [math]k[/math] различий, матрицу расстояний надо преобразовать таким образом, чтобы [math]d_{i,j}[/math] представлял минимальное расстояние между [math]x(1, i)[/math] и любой подстрокой [math]y[/math], заканчивающейся символом [math]y_j[/math]. Для этого достаточно ввести условие:

[math]d_{0,j} = 0, 0 \lt j \lt n[/math] .

Оставшуюся часть матрицы вычислим с использованием цен редактирования расстояния Левенштейна и рекуррентного соотношения для [math]d_{i,j}[/math]:

[math]w(a,{\varepsilon}) = 1[/math]

[math]w({\varepsilon}, b) = 1[/math]

[math]w(a, b) = \left\{\begin{array}{llcl} 0&,\ a{\ne}b\\ 1&,\ a=b\\ \end{array}\right. [/math]

[math]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))[/math]

Теперь каждое значение, не превосходящее [math]k[/math], в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше [math]k[/math] отличий от образца.

Пример

Рассмотрим этот подход к решению задачи на примере: пусть [math]X=ABCDE, Y=ACEABPCQDEABCR[/math]. Построим матрицу расстояний для этого случая: Table k razlichiy.png

Последняя строка матрицы показывает, что вхождения образца с точностью до [math]2[/math] отличий, заканчиваются в позициях [math]3[/math], [math]10[/math], [math]13[/math] и [math]14[/math]. Соответствующими подстроками являются [math]ACE[/math], [math]ABPCQDE[/math], [math]ABC[/math] и [math]ABCR[/math].

Алгоритм

Алгоритм Укконена говорит, что при вычисления расстояний между строками, диагонали матрицы можно пронумеровать целыми числами [math]p {\in} [-m, n][/math], таким образом, чтобы диагональ [math]p[/math] состояла из элементов [math](i, j)[/math], у которых [math]j - i = p[/math]. Пусть [math]r_{p,q}[/math] представляет наибольшую строку [math]i[/math], у которой [math]d_{i,j} = q[/math] и [math](i, j)[/math] лежит на диагонали [math]p[/math]. Таким образом, [math]q[/math] – это минимальное число различий между [math]x(1, r_{p,q})[/math] и любой подстрокой текста, заканчивающейся [math]y_{r_{p,q}+p}[/math]. Значение [math]m[/math] в строке [math]r_{p,q}[/math], для [math]q \lt k[/math], указывает, что в тексте имеется вхождение образца с точностью до [math]k[/math] отличий, заканчивающееся в [math]y_{m+p}[/math]. Таким образом, чтобы решить задачу [math]k[/math] различий, достаточно вычислить значения [math]r_{p,q}[/math] для [math]q \lt k[/math].

Рассмотрим алгоритм вычисления [math]r_{p,q}[/math].

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)

Алгоритм вычисляет значения [math]r_{p,q}[/math] на [math]n+k+1[/math] диагоналях. Для каждой диагонали переменной строки [math]r[/math] можно присвоить не больше [math]m[/math] различных значений, что приводит к времени вычислений [math]O(mn)[/math]. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.

Предварительные вычисления

На этапе предварительной обработки, с помощью алгоритма Вейнера[1] строится суффиксное дерево строки [math]y{\#}x{\$}[/math], где [math]\#[/math] и [math]\$[/math] – символы, не принадлежащие алфавиту, над которыми построены строки [math]x[/math] и [math]y[/math]. Этот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени. Для неограниченных алфавитов этот алфавит можно преобразовать так, что он будет выполняться за время [math]O(n\log{\sigma})[/math], где [math]\sigma[/math] – число различающихся символов образца. Стадия предварительной обработки требует время [math]O(n)[/math] и [math]O(n\log{m})[/math] для постоянного и неограниченного алфавитов, соответственно.

Модификация предыдущего алгоритма

В приведенном выше алгоритме перед циклом [math]while[/math] для диагонали [math]p[/math], переменной [math]r[/math] было присвоено такое значение, что [math]x(1, r)[/math] сопоставляется с точностью до [math]k[/math] различий с некоторой подстрокой текста, заканчивающейся [math]y_{r+p}[/math]. Тогда функция цикла [math]while[/math] находит максимальное значение для которого [math]x(r+1, r+h) = y(r+p+1, r+p+h)[/math]. Обозначим это значение как [math]h[/math]. Это эквивалентно нахождению длины самого длинного общего префикса суффиксов [math]x(r+1, m)\$[/math] и [math]y(r+p+1,n){\#}x{\$}[/math] предварительно вычисленной конкатенированной строки. Символ [math]\#[/math] используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как [math]y[/math], так и [math]x[/math]. Обозначим [math]lca(r,p)[/math] как самый низкий общий предок в суффиксном дереве с листьями, определенными вышеуказанными суффиксами, тогда нужное значение [math]h[/math] задается [math]length(lca(r,p))[/math].

Оценка времени работы

Суффиксное дерево имеет [math]O(n)[/math] узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам [math]LCA[/math] требуется преобразование дерева, проводимое за линейное время. Значения [math]r_{p,q}[/math] вычисляются на [math]n+k+1[/math] диагоналях. Более того, для каждой диагонали надо вычислить [math]k+1[/math] таких значений, что в общей сложности дает [math]O(kn)[/math] запросов. Таким образом, общее время работы алгоритма k различий составляет [math]O(kn)[/math] для алфавитов фиксированного размера, и [math]O(n * \log{m} + kn)[/math] для неограниченных алфавитов.

Параллельная версия алгоритма

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

Примечания

Источники информации