Изменения

'''Fusion tree''' {{---}} дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных чисел, используя <tex>O(n)</tex> памяти, и выполнять операции поиска за время <tex>O(\log_{w} n)</tex>. Эта Это статическая структура данных , которая была впервые предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).

Такое время работы достигается за счет хранения дополнительной информации в вершинах. Построим [[:Сверхбыстрый_цифровой_бор|цифровой бор]] из ключей узла дерева. Всего <tex>B - 1</tex> ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера <tex>b_0, b_1\ldots b_{r-1}</tex>(индексация идет от листьев, которые соответствуют концу числа, т.е. младшему разряду). Количество существенных битов <tex>r</tex> равно не больше <tex>B - 1</tex> (все ребра на уровне детей ветвящейся вершины {{---}} обведены на рисунке {{---}} являются существенными битами, и так как ветвящихся вершин <tex>B - 1</tex>, значит, и количество уровней с детьми не больше <tex>B - 1</tex>, поскольку на одном уровне могут быть несколько ветвящихся вершин).

Пусть <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===

|statement=Среди всех ключей наибольший общий префикс с значений <tex>qsucc(y)</tex> и <tex>pred(y)</tex> по <tex>sketch(y)</tex> есть <tex>succ</tex> будет иметь или <tex>a_ipred</tex> или по значению <tex>a_{i+1}y</tex>.

ПредположимРассмотрим <tex>y</tex>. У него есть существенные биты и некоторый элемент <tex>x</tex>, что с которым у <tex>y</tex> имеет наибольший общий префикс с (настоящий, а не по <tex>qsketch</tex>). Тогда Биты из <tex>sketch</tex>, находящиеся в префиксе совпадают, значит <tex>succ</tex> и <tex>pred</tex> <tex>y</tex> среди <tex>sketch</tex> должны быть такими же среди <tex>x</tex>, и один из них имеет дальше бит <tex>0</tex> (q)а другой <tex>1</tex> будет иметь ) и с ним может быть больше других общих битов со бит в <tex>sketch(y)</tex>. ЗначитТо есть либо <tex>succ</tex>, либо <tex>pred</tex> имеют следующий существенный бит такой же, как и у <tex>sketch(y)</tex> ближе по значению к . Поэтому если значение равно <tex>sketch(q)0</tex>, чем то <tex>x</tex> наибольший среди значений с меньшим <tex>sketch(a_i)</tex> или , и, аналогично для <tex>sketch(a_{i+1})</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 = 00000, a_{i+1} = 10010, q = 50101</tex> ]] Рассмотрим ключи. Порядок для них по <tex>sketch</tex> совпадает с их порядком. Тогда для некоторых <tex>a_i</tex> и <tex>a_{i+1}</tex>: <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>, в таком случае <tex>a_i</tex> и <tex>a_{i+1}</tex> его <tex>succ</tex> и <tex>pred</tex> по <tex>sketch</tex>. Тогда среди них есть настоящий (не по <tex>sketch</tex>) <tex>succ</tex> или <tex>pred</tex> по доказанному, а понять это мы можем просто сделав сравнение с <tex>q</tex>. ===Поиск реального следующего и предыдущего===Мы умеем находить реальный <tex>succ</tex> и <tex>pred</tex> по <tex>succ</tex> и <tex>pred</tex> от <tex>sketch(y)</tex>, теперь покажем, как искать <tex>succ</tex> и <tex>pred</tex> от <tex>sketch(y)</tex> за <tex> O(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>p</tex> {{---}} наибольший общий префикс, а <tex>y</tex> его длина, <tex>a_j</tex> {{-L = (1sketch(a_1)\ldots 1sketch(a_k) --}} ключ, имеющий наибольший общий префикс с <tex>q</tex> 0sketch(<tex>j = i</tex> или <tex>i+1</tex>). * если <tex>q>a_j</tex>, то <tex>y + 1</tex> бит <tex>q</tex> равен единице, а <tex>y + 1</tex> бит <tex>a_j</tex> равен нулю. Так как общий префикс <tex>a_j</tex> и <tex>q</tex> является наибольшим, то не существует ключа с префиксом <tex>p1</tex>. Значит, <tex>q</tex> больше всех ключей с префиксом меньшим либо равным <tex>p</tex>. Найдем <tex>pred(e)</tex>, <tex>e = p01\ldots 11</tex>, который одновременно будет <tex>равен pred0sketch(q)</tex>,* если <tex>q<a_j</tex> ) \& \displaystyle \sum_{i=0}^{k---1}} найдем <tex>succ2^{i(el+1)</tex>, <tex>e +l}= p10\overbrace{c_10\ldots0}^{l+1 bits} \ldots 00</tex>. Это будет <tex>succ(q)\overbrace{c_k0\ldots0}^{l+1 bits}</tex>.

Длина наибольшего общего префикса двух ''w''-битных чисел Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>ac_i = 0</tex> и , в противном случае <tex>bc_i = 1</tex> может быть вычислена с помощью нахождения индекса наиболее значащего бита .Теперь надо найти количество единиц в побитовом <tex>L</tex>. Умножим <tex>L</tex> на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\oplus aldots 01}_{l+1 bits}</tex> , тогда все единицы сложатся в первом блоке результата, и , чтобы получить количество единиц, сдвинем его вправо на <tex>b(k-1)\cdot(l + 1)</tex>бит.В таком случае мы получим некоторое <tex>2^i</tex>, где <tex>i</tex> является реальным <tex>pred(x)</tex>, а <tex>i</tex> мы можем получить с помощью цикла де Брёйна

===Параллельное сравнениеИндекс наиболее старшего бита с помощью цикла де Брёйна ===Найдем <tex>succ(sketch(q))</tex> и <tex>pred(sketch(q))</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>, сохранятся единицы. Применим к получившемуся побитовое & c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.

'''Последовательность де Брёйна''' {{---}} последовательность <texmath>L = (1sketch(a_1),\;\ldots 1sketch(a_k) - 0sketch(q),\ldots 0sketch(q));a_t</texmath>&, элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество <texmath> \displaystyle \sum_{i=0}^{,\;1,\;\ldots,\;k-1\}2^</math>), и все подпоследовательности <math>a_{i(l+1)+l}=,\overbrace{c_10\ldots0}^{l+1 bits} ;\ldots ,\overbrace;a_{c_k0\ldots0}^{li+1 bitsn}</texmath> заданной длины <math>n</math>различны.

Если ==== Примеры ==== Примеры циклов де Брёйна для <math>k=2</math> с периодом <tex>sketch2, 4, 8, 16</tex>:* <tex>01</tex> (a_iсодержит подпоследовательности <tex>0</tex> и <tex>1</tex>)* <tex>0011< sketch/tex> (qсодержит подпоследовательности <tex>00, 01, 11, 10</tex>)* <tex>00010111 (000, 001, 010, 101, 011, 111, 110, 100)</tex>* <tex>0000100110101111</tex> ==== Получение индекса по значению степени двойки ==== Возьмем цикл де Брёйна для <tex>n</tex>, то <tex>c_i (i = 0\ldots n-1)</tex> и запишем его как число <tex>b</tex> (для <tex>8</tex> цикл де Брёна равен <tex>00010111</tex>, в противном случае а значение <tex>c_i b = 123</tex>).Теперь надо найти количество единиц в Умножим это число на <tex>L2^i</tex>. Умножим , сдвинем его влево на <tex>Li</tex> , а затем обратно вправо на <tex>n-k</tex> (<tex>k</tex> такое, что <tex>n=2^k</tex>). <tex>(b \underbracetexttt{0<<} i) \ldots 01texttt{>>}_(n-k)</tex>), тогда получившееся число {{l + 1 bits---}}<tex>i</tex>-ая подстрока длины <tex>k</tex> данного цикла де Брёйна. Эту перестановку опозначим за <tex>p</tex> и тогда применив ее к <tex>(2^i\ldots cdot x) \underbracetexttt{0\ldots 01}_{l+1 bits>>}(n-k))</tex> получим <tex>i</tex>: <tex>p</tex>, тогда все единицы сложатся в первом блоке результатаданном случае такое, ичто <tex>k</tex> подряд идущих бит равны значению, чтобы получить количество единиц, сдвинем его вправона сколько мы сдвинули.

Чтобы найти <tex>sketch </tex> за константное время, будем вычислять <tex>sketchsupersketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.Хотя <tex>supersketch</tex> содержит лишние нули, мы сможем вычислять его быстрее, чем обычный <tex>sketch</tex>, потому что нам не придется каждый раз идти по всем битам числа, выбирая стоящие на нужных нам местах. Будем использовать <tex>supersketch</tex> вместо <tex>sketch</tex> {{---}} это никак не повлияет на сравнение, поскольку добавленные биты равны нулю и стоят на одних и тех же местах для всех <tex>sketch</tex>

# уберем Уберем все несущественные биты <tex>x' = x </tex>\&<tex> \displaystyle \sum_{i=0}^{r-1}2^{b_i}</tex>,.# умножением Умножением на некоторое заранее вычисленное число <tex>M = \displaystyle\sum_{i=0}^{r-1}2^{m_i}</tex> сместим все существенные биты в блок меньшего размера: <tex>x'\times M = \displaystyle\left(\sum_{i=0}^{r-1}x_{b_i}2^{b_i}\right)\left(\sum_{i=0}^{r-1}2^{m_i}\right) = \sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}</tex>,.# применив Применив побитовое <tex>\&</tex>, уберем лишние биты, появившиеся в результате умножения: <tex>\left(\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j} </tex>\right) \&<tex> \displaystyle\sum_{i=0}^{r-1}2^{b_i+m_i} = \sum_{i=0}^{r-1}x_{b_i}2^{b_i+m_i}</tex>,.# сделаем Сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.

Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить <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) \leqslant = B^5 = (w(B^{2 - 2B + 1/5})^5 = w </tex> бит. ==Индекс наиболее значащего бита==Чтобы найти в <tex>w</tex>-битном числе <tex>x</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>. Далее найдем первый непустой блок и индекс первого единичного бита в нем. '''2 + 1)''' Поиск непустых блоков. '''a.''' Определим, какие блоки имеют единицу в первом бите. Применим побитовое & к <tex>x=</tex> и константе <tex>F</tex>.   <tex>$$\begin{array}{r}AND\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{B(B^4 + 4B^2 + 1}000\; \underline{1}000 \end{array}\end{array}$$</tex>  '''b.''' Определим, содержат ли остальные биты единицы.  Вычислим <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>  '''c.''' Первый бит в каждом блоке <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>  '''4B^3 + 2B^2)''' Найдем <tex>sketch(y)</tex>, чтобы сместить все нужные биты в один блок. Существенными битами в данном случае будут первые биты каждого блока, поэтому <tex>b_i = \sqrt{w} - 1 4B + i\sqrt{w}</tex>.  Будем использовать <tex>m_j = w - (\sqrt{w}-1) = B^5 - j\sqrt{w} 4B^3 +j</tex>. Тогда <tex>b_i + m_j = w + (i 6B^2 - j)\sqrt{w} 4B + j</tex>. Все суммы различны при <tex>02 \leqslant i, j < \sqrt{w} B^5 </tex>. Все <tex>b_i + m_i = w + i</tex> возрастают, и <tex>(b_{\sqrt{w} - 1} + m_{\sqrt^{w} - 1/5}) - (b_0 + m_0) ^5 = \sqrt{w} - 1</tex>.  Чтобы найти <tex>sketch(y)</tex>бит, умножим <tex>y</tex> на <tex>m</tex> и сдвинем вправо на <tex>w</tex> бит. '''3)''' Найдем первый ненулевой блок. Для этого надо найти первую единицу в <tex>sketch(y)</tex>. Как и при поиске всех <tex>succ(sketch(q))</tex> и <tex>pred(sketch(q))</tex> используем параллельное сравнение <tex>sketch(y)</tex> с <tex>2^0, 2^1 B \ldots 2^{\sqrt{w} - geqslant 1}</tex>. В результате сравнения получим номер первого ненулевого блока <tex>c</tex>. '''4)''' Найдем номер <tex>d</tex> первого единичного бита в найденном блоке так же как и в предыдущем пункте. '''5)''' Индекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d</tex>. Каждый шаг выполняется за <tex>O(1)</tex>, поэтому всего потребуется <tex>O(1)</tex> времени, чтобы найти индекс.