'''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===
{{Утверждение
|author=
|about=
|statement=Пусть Среди значений <tex>sketchsucc(a_iy) \leqslant sketch</tex> и <tex>pred(qy) \leqslant </tex> по <tex>sketch(a_{i+1}y)</tex>. Тогда среди всех ключей наибольший общий префикс с есть <tex>qsucc</tex> будет иметь или <tex>a_ipred</tex> или по значению <tex>a_{i+1}y</tex>.
|proof=
Предположим, что <tex>y</tex> имеет наибольший общий префикс с <tex>q</tex>. Тогда <tex>sketch(q)</tex> будет иметь больше общих битов со <tex>sketch(y)</tex>. Значит, <tex>sketch(y)</tex> ближе по значению к <tex>sketch(q)</tex>, чем <tex>sketch(a_i)</tex> или <tex>sketch(a_{i+1})</tex>, что приводит к противоречию.
Рассмотрим <tex>y</tex>. У него есть существенные биты и некоторый элемент <tex>x</tex>, с которым у <tex>y</tex> наибольший общий префикс (настоящий, а не по <tex>sketch</tex>). Биты из <tex>sketch</tex>, находящиеся в префиксе совпадают, значит <tex>succ</tex> и <tex>pred</tex> <tex>y</tex> среди <tex>sketch</tex> должны быть такими же среди <tex>x</tex>, и один из них имеет дальше бит <tex>0</tex> (а другой <tex>1</tex>) и с ним может быть больше других общих бит в <tex>sketch</tex>. То есть либо <tex>succ</tex>, либо <tex>pred</tex> имеют следующий существенный бит такой же, как и у <tex>y</tex>. Поэтому если значение равно <tex>0</tex>, то <tex>x</tex> наибольший среди значений с меньшим <tex>sketch</tex>, и, аналогично для <tex>1</tex>, наименьший среди больших.
}}
[[Файл:Fusion01.png|350x230px|thumb|right|Пример случая, когда наибольший общий префикс у <tex>q</tex> и <tex>a_i</tex>, а <tex>a_{i+1}</tex> не является ни <tex>succ</tex>, ни <tex>pred</tex>]]
Сравнивая <tex>a \oplus q</tex> и <tex>b \oplus q</tex>, найдем какой из ключей <tex>a</tex> и <tex>b</tex> имеет наибольший общий префикс с <tex>q</tex> (наименьшее значение соответствует наибольшей длине, так как одинаковые старшие биты обнулятся, следовательно, если <tex>a \oplus q > b \oplus q</tex>, то у <tex>a</tex> первый несовпадающий бит старше, чем у <tex>b</tex> ).
[[Файл: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>psketch</tex> {{---}} наибольший общий префикс, а совпадает с их порядком. Тогда для некоторых <tex>ya_i</tex> его длина, и <tex>a_ja_{i+1}</tex> {{---}} ключ, имеющий наибольший общий префикс с : <tex>sketch(a_i) \leqslant sketch(q</tex> ) \leqslant sketch(<tex>j = i</tex> или <tex>a_{i+1</tex>}). * если <tex>q>a_j</tex>, то в таком случае <tex>y + 1a_i</tex> бит и <tex>q</tex> равен единице, а <tex>y a_{i+ 1}</tex> бит его <tex>a_j</tex> равен нулю. Так как общий префикс <tex>a_jsucc</tex> и <tex>qpred</tex> является наибольшим, то не существует ключа с префиксом по <tex>p1sketch</tex>. Значит, Тогда среди них есть настоящий (не по <tex>qsketch</tex> больше всех ключей с префиксом меньшим либо равным <tex>p</tex>. Найдем <tex>pred(e)</tex>, <tex>e = p01\ldots 11succ</tex>, который одновременно будет или <tex>равен pred(q)</tex>по доказанному,* если а понять это мы можем просто сделав сравнение с <tex>q<a_j</tex> {{---}} найдем <tex>succ(e)</tex>, <tex>e = p10\ldots 00</tex>. Это будет <tex>succ(q)</tex>.
Длина наибольшего общего префикса двух ===Поиск реального следующего и предыдущего===Мы умеем находить реальный <tex>succ</tex> и <tex>wpred</tex>-битных чисел по <tex>asucc</tex> и <tex>bpred</tex> может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом от <tex>\oplus asketch(y)</tex>, теперь покажем, как искать <tex>succ</tex> и <tex>bpred</tex>. ===Сравнение значений sketch двух чисел===В предыдущем абзаце мы научились считать от <tex>succ(sketch(q)y)</tex> и за <tex>pred(sketchO(q)1)</tex>, теперь посчитаем их. Определим <tex>sketch(node)</tex> как число, составленное из единиц и <tex>sketch(a_i)</tex>, то есть <tex>sketch(node) = 1sketch(a_1)1sketch(a_2)\ldots 1sketch(a_k)</tex>. Вычтем из <tex>sketch(node)</tex> число <tex>sketch(q) \times \underbrace{\overbrace{00\ldots 1}^{l + 1 bits}\overbrace{00\ldots 1}^{l + 1 bits}\ldots \overbrace{00\ldots 1}^{l + 1 bits}}_{k(l + 1) bits} = 0sketch(q)\ldots 0sketch(q)</tex>. В начале каждого блока, где <tex>sketch(a_i) \geqslant sketch(q)</tex>, сохранятся единицы. Применим к получившемуся побитовое <tex>\&</tex> c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</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>
==Индекс наиболее значащего бита==
Чтобы найти в <tex>w</tex>-битном числе <tex>x</tex> индекс самого старшего бита, содержащего единицу (это понадобится в дальнейшем, для нахождения <tex>sketch(y)</tex> ), разделим <tex>x</tex> на <tex>\sqrt{w}</tex> блоков по <tex>\sqrt{w}</tex> бит. <tex>x = \underbrace{0101}_{\sqrt{w}}\; \underbrace{0000}_{\sqrt{w}}\; \underbrace{1000}_{\sqrt{w}}\; \underbrace{1101}_{\sqrt{w}}</tex>. Далее найдем первый непустой блок и индекс первого единичного бита в нем.
# Поиск непустых блоков.
##Определим, какие блоки имеют единицу в первом бите. Применим побитовое <tex>\&</tex> к <tex>x</tex> и константе <tex> F </tex>: <tex>
$$
\begin{array}{r}
\&
\begin{array}{r}
x = 0101\; 0000\; 1000\; 1101\\
F = 1000\; 1000\; 1000\; 1000\\
\end{array}\\
\hline
\begin{array}{r}
t_1 = \underline{0}000\; \underline{0}000\; \underline{1}000\; \underline{1}000 \end{array}\end{array}
$$</tex>
##Определим, содержат ли остальные биты единицы.
###Вычислим <tex>x \oplus t_1</tex>: <tex>
$$
\begin{array}{r}
\oplus
\begin{array}{r}
t_1 = 0000\; 0000\; 1000\; 1000\\
x = 0101\; 0000\; 1000\; 1101\\
\end{array} \\
\hline
\begin{array}{r}
t_2 = 0\underline{101}\; 0\underline{000}\; 0\underline{000}\; 0\underline{101}
\end{array}
\end{array}
$$</tex>
### Вычтем из <tex>F\; t_2</tex>. Если какой-нибудь бит <tex>F</tex> обнулится, значит, соответствующий блок содержит единицы: <tex>
$$
\begin{array}{r}
-
\begin{array}{r}
F = 1000\; 1000\; 1000\; 1000\\
t_2 = 0\underline{101}\; 0\underline{000}\; 0\underline{000}\; 0\underline{101}\\
\end{array} \\
\hline
\begin{array}{r}
t_3 = \underline{0}xxx\; \underline{1}000\; \underline{1}000\; \underline{0}xxx
\end{array}
\end{array}
$$</tex>
###Чтобы найти блоки, содержащие единицы, вычислим <tex>t_3 \oplus F</tex>: <tex>
$$
\begin{array}{r}
\oplus
\begin{array}{r}
F = 1000\; 1000\; 1000\; 1000\\
t_3 = \underline{0}xxx\; \underline{1}000\; \underline{1}000\; \underline{0}xxx\\
\end{array} \\
\hline
\begin{array}{r}
t_4 = \underline{1}000\; \underline{0}000\; \underline{0}000\; \underline{1}000
\end{array}
\end{array}
$$</tex>
##Первый бит в каждом блоке <tex>y = t_1 \lor t_4</tex> содержит единицу, если соответствующий блок <tex>x</tex> ненулевой: <tex>$$
\begin{array}{r}
\lor
\begin{array}{r}
t_1 = \underline{0}000\; \underline{0}000\; \underline{1}000\; \underline{1}000\\
t_4 = \underline{1}000\; \underline{0}000\; \underline{0}000\; \underline{1}000\\
\end{array} \\
\hline
\begin{array}{r}
y = \underline{1}000\; \underline{0}000\; \underline{1}000\; \underline{1}000
\end{array}
\end{array}
$$</tex>
# Найдем <tex>sketch(y)</tex>, чтобы сместить все нужные биты в один блок. Существенными битами в данном случае будут первые биты каждого блока, поэтому <tex>b_i = \sqrt{w} - 1 + i\sqrt{w}</tex>. Будем использовать <tex>m_j = w - (\sqrt{w}-1) - j\sqrt{w} +j</tex>. Тогда <tex>b_i + m_j = w + (i - j)\sqrt{w} + j</tex>. Все суммы различны при <tex>0\leqslant i, j < \sqrt{w} </tex>. Все <tex>b_i + m_i = w + i</tex> возрастают, и <tex>(b_{\sqrt{w} - 1} + m_{\sqrt{w} - 1}) - (b_0 + m_0) = \sqrt{w} - 1</tex>. Чтобы найти <tex>sketch(y)</tex>, умножим <tex>y</tex> на <tex>m</tex> и сдвинем вправо на <tex>w</tex> бит.
# Найдем первый ненулевой блок. Для этого надо найти первую единицу в <tex>sketch(y)</tex>. Как и при поиске <tex>succ(sketch(q))</tex> и <tex>pred(sketch(q))</tex> используем параллельное сравнение <tex>sketch(y)</tex> с <tex>2^0, 2^1 \ldots 2^{\sqrt{w} - 1}</tex>. В результате сравнения получим номер первого ненулевого блока <tex>c</tex>.
#Найдем номер <tex>d</tex> первого единичного бита в найденном блоке так же как и в предыдущем пункте.
#Индекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d</tex>.
Каждый шаг выполняется за <tex>O(1)</tex>, поэтому всего потребуется <tex>O(1)</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>T</math>, содержащие <math>T</math> различных подпоследовательностей <math>a_{i+1},\;\ldots,\;a_{i+n}</math>, {{---}} то есть такие периодические последовательности, в которых любой отрезок длины <math>T+n-1</math> является последовательностью де Брёйна с теми же параметрами <math>n</math> и <math>k</math>.
=== Свойства ===
Очевидно, что длина (период) такого цикла не может превосходить <math>k^n</math> {{---}} числа́ всех различных векторов длины <math>n</math> с элементами из <math>\{0,\;1,\;\ldots,\;k-1\}</math>; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют '''циклами де Брёйна''' (впрочем, иногда этот термин применяют и к циклам меньшей длины).
При <math>k=2</math> существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка <math>n</math>: так, при <math>n=3</math> соотношение <math>x_n=x_{n-2}+x_{n-3}\pmod 2</math> порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код.
=== Примеры ===
Примеры циклов де Брёйна для <math>k=2</math> с периодом 2, 4, 8, 16:
* 01 (содержит подпоследовательности 0 и 1)
* 0011 (содержит подпоследовательности 00, 01, 11, 10)
* 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
* 0000100110101111
=== Получение индекса по значению степени двойки ===
Возьмем цикл де Брёйна для <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 \ll i)\gg(n-k)</tex>), тогда получившееся число {{---}} <tex>i</tex>-ая подстрока длины <tex>k</tex> данного цикла де Брёйна. Эту перестановку опозначим за <tex>p</tex> и тогда применив ее к <tex>(2^i\cdot x) \gg (n-k))</tex> получим <tex>i</tex>: <tex>p</tex> в данном случае такое, что <tex>k</tex> подряд идущих бит равны значению, на сколько мы сдвинули, на какой позиции стоит вектор длины <tex>k</tex>.
==См. Также==
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
[[Категория:Структуры данных]]
