317
правок
Изменения
Нет описания правки
'''Fusion tree''' {{---}} дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных чисел, используя <tex>O(n)</tex> памяти, и выполнять операции поиска за время <tex>O(\log_{w} n)</tex>. Эта Это статическая структура данных , которая была впервые предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).
==Структура==
Fusion tree {{---}} это [[B-дерево|B-дерево]], такое что:
==Поиск вершины==
Пусть <tex>\left \{ a_1,a_2\ldots a_ka_B\right \}</tex> {{---}} множество ключей узла, отсортированных по возрастанию, <tex>q</tex> {{---}} ключ искомой вершины, <tex>l</tex> {{---}} количество бит в <tex>sketch(q)</tex>. Сначала найдем такой ключ <tex>a_i</tex>, что <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>. Хотя положение <tex>sketch(q)</tex> среди <tex>sketch(a_j)</tex> не всегда эквивалентно положению <tex>q</tex> среди <tex>a_j</tex>, зная соседние элементы <tex>sketch(q)</tex>, мы можем найти <tex>succ(q)</tex> и <tex>pred(q)</tex>.
===Поиск следующего и предыдущегопо sketch===
{{Утверждение
[[Файл:FusionTree.png|400x400px|thumb|right|Пример случая, когда <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>, но <tex>a_{i+1}\leqslant q</tex> <tex>sketch(a_i) = 00, sketch(q) = 00, sketch(a_{i+1}) = 01, \\ a_i = 0000, a_{i+1} = 0010, q = 0101</tex> ]]
<tex>L = (1sketch(a_1)\ldots 1sketch(a_k) - 0sketch(q)\ldots 0sketch(q)) \& \displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}=\overbrace{c_10\ldots0}^{l+1 bits} \ldots \overbrace{c_k0\ldots0}^{l+1 bits}</tex>
Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.
Теперь надо найти количество единиц в <tex>L</tex>. Умножим <tex>L</tex> на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все единицы сложатся в первом блоке результата, и, чтобы получить количество единиц, сдвинем его вправо на <tex>(k-1)\cdot(l + 1)</tex> бит. В таком случае мы получим некоторое <tex>2^i</tex>, где <tex>i</tex> является реальным <tex>pred(x)</tex>, а <tex>i</tex> мы можем получить с помощью цикла де Брёйна
=== Индекс наиболее старшего бита с помощью цикла де Брёйна ===
'''Последовательность де Брёйна''' {{---}} последовательность <math>a_1,\;\ldots,\;a_t</math>, элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество <math>\{0,\;1,\;\ldots,\;k-1\}</math>), и все подпоследовательности <math>a_{i+1},\;\ldots,\;a_{i+n}</math> заданной длины <math>n</math> различны.
==== Примеры ====
Примеры циклов де Брёйна для <math>k=2</math> с периодом <tex>2, 4, 8, 16</tex>:
* <tex>01</tex> (содержит подпоследовательности <tex>0</tex> и <tex>1</tex>)
* <tex>0011</tex> (содержит подпоследовательности <tex>00, 01, 11, 10</tex>)
* <tex>00010111 (000, 001, 010, 101, 011, 111, 110, 100)</tex>
* <tex>0000100110101111</tex>
==== Получение индекса по значению степени двойки ====
Возьмем цикл де Брёйна для <tex>n</tex> <tex>(i = 0\ldots n-1)</tex> и запишем его как число <tex>b</tex> (для <tex>8</tex> цикл де Брёна равен <tex>00010111</tex>, а значение <tex>b = 23</tex>). Умножим это число на <tex>2^i</tex>, сдвинем его влево на <tex>i</tex>, а затем обратно вправо на <tex>n-k</tex> (<tex>k</tex> такое, что <tex>n=2^k</tex>). <tex>(b \texttt{<<} i) \texttt{>>}(n-k)</tex>), тогда получившееся число {{---}} <tex>i</tex>-ая подстрока длины <tex>k</tex> данного цикла де Брёйна. Эту перестановку опозначим за <tex>p</tex> и тогда применив ее к <tex>(2^i\cdot x) \texttt{>>} (n-k))</tex> получим <tex>i</tex>: <tex>p</tex> в данном случае такое, что <tex>k</tex> подряд идущих бит равны значению, на сколько мы сдвинули.
==Вычисление sketch(x)==
}}
Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить <tex>sketch</tex> узла в <tex>w</tex>-битный тип. Так как <tex>r \leqslant B-1</tex>, то <tex>sketch(node)</tex> будет занимать <tex>B(r^4 + 1) \leqslant B((B-1)^4 + 1) = B((B^2 - 2B + 1)^2 + 1)=</tex><tex>B(B^4 + 4B^2 + 1 - 4B^3 + 2B^2 -4B + 1) = B^5 - 4B^3 + 6B^2 - 4B + 2 \leqslant B^5 </tex><tex> = (w^{1/5})^5 = w </tex> бит, при всех <tex>B \geqslant 1</tex>
==См. Также==
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
[[Категория:Структуры данных]]
