Изменения

'''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 = w^{1/5}</tex> детей;,* время, за которое определяется , в каком поддереве находится вершина, равно <tex>O(1)</tex>.Такое время работы достигается за счет хранения дополнительной информации в вершинах. Построим [[:Сверхбыстрый_цифровой_бор|цифровой бор ]] из ключей узла дерева. Всего <tex>B - 1</tex> ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера <tex>b_0, b_1, b_2\ldots b_rb_{r-1}</tex>(индексация идет от листьев, которые соответствуют концу числа, т.е. младшему разряду). Количество существенных битов <tex>r</tex> не больше чем <tex>B - 1</tex>(все ребра на уровне детей ветвящейся вершины {{---}} обведены на рисунке {{---}} являются существенными битами, и так как ветвящихся вершин <tex>B - 1</tex>, значит, и количество уровней с детьми не больше <tex>B - 1</tex>, поскольку на одном уровне могут быть несколько ветвящихся вершин).

В Fusion tree вместе с ключом <tex>x</tex> хранится <tex>sketch(x)</tex> {{- --}} последовательность битов <tex>x_{b_{r-1}}\ldots x_{b_0}</tex>.

|statement=<tex>Sketchsketch</tex> сохраняет порядок, то есть <tex>sketch(x) < sketch(y)</tex>, если <tex>x < y</tex>.

Рассмотрим наибольший общий префикс <tex>x</tex> и <tex>y</tex>. Тогда следующий бит определяет их порядок и одновременно является существенным битом. Поэтому, если <tex>x < y</tex>, то и <tex>sketch(x) < sketch(y)</tex>.

Пусть <tex>L = (1sketch(\left \{ a_1),a_2\ldots 1scetch(a_k) - 0sketch(q)a_B\right \ldots 0sketch(q))}</tex> AND {{---}} множество ключей узла, отсортированных по возрастанию, <tex>\displaystyle \sum_q</tex> {i=0}^{k-1--}}2^ключ искомой вершины, <tex>l</tex> {i(l+1)+l}=\overbrace{c_10\ldots0---}^{l+1 bits} количество бит в <tex>sketch(q)</tex>. Сначала найдем такой ключ <tex>a_i</tex>, что <tex>sketch(a_i) \ldots leqslant sketch(q) \overbraceleqslant sketch(a_{c_k0\ldots0}^{li+1 bits})</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>.

Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.Теперь надо найти количество едениц в ''L''. Умножим ''L'' на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все еденицы сложатся в первом блоке результата, и, чтобы получить количество едениц, сдвинем его вправо. ===Succ(q) Поиск следующего и pred(q)===Пусть <tex>предыдущего по sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>. Среди всех ключей наибольший общий префикс с <tex>q</tex> будет иметь или <tex>a_i</tex> или <tex>a_{i+1}</tex>. Сравнивая <tex>a\;XOR\;q</tex> и <tex>b\;XOR\;q</tex>, найдем какой из ключей имеет наибольший общий префикс с <tex>q</tex> (наименьшнее значение соответствует наибольшей длине). Предположим, что <tex>p</tex> - наибольший общий перфикс, а <tex>y</tex> его длина, <tex>a_j</tex> - ключ, имеющий наибольший общий префикс с <tex>q</tex> (<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> равен 0. Так как общий префикс <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>равен pred(q)</tex>;* если <tex>q<a_j</tex> - найдем <tex>succ(e)</tex>, <tex>e = p10\ldots 00</tex>. Это будет <tex>succ(q)</tex>. Длина наибольшего общего префикса двух ''w''-битных чисел ''a'' и ''b'' может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом <tex>XOR</tex> ''a'' и ''b''.==Вычисление sketch(x)==Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.

|id= prefix.

|statement=Дана последовательность из r чисел Среди значений <tex>b_0succ(y)<b_1/tex> и <\ldots tex>pred(y)<b_{r-1}/tex> по <tex>sketch(y)</tex>. Тогда существует последовательность есть <tex>succ</tex> или <tex>m_0pred<m_1\ldots /tex> по значению <m_{r-1}tex>y</tex>, такая что:.|proof=

Рассмотрим <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>b_i + m_jsketch</tex>. То есть либо <tex>succ</tex> различны, для либо <tex>pred</tex> имеют следующий существенный бит такой же, как и у <tex>y</tex>. Поэтому если значение равно <tex>0\leqslant i</tex>, то <tex>x</tex> наибольший среди значений с меньшим <tex>sketch</tex>, и,j \leqslant r-аналогично для <tex>1</tex>;, наименьший среди больших.}}

2) [[Файл:FusionTree.png|400x400px|thumb|right|Пример случая, когда <tex>b_1 + m_2sketch(a_i) \leqslant b_2 + m_2sketch(q) \leqslant \ldots sketch(a_{i+1})</tex>, но <tex>a_{i+1}\leqslant b_q</tex> <tex>sketch(a_i) = 00, sketch(q) = 00, sketch(a_{r-i+1} ) = 01, \\ a_i = 0000, a_{i+ m_{r-1}= 0010, q = 0101</tex>;]]

3) Рассмотрим ключи. Порядок для них по <tex>sketch</tex> совпадает с их порядком. Тогда для некоторых <tex>a_i</tex> и <tex>(b_a_{r-1} i+ m_{r-1}</tex>: <tex>sketch(a_i) - \leqslant sketch(b_0 + m_0q) \leqslant r^4sketch(a_{i+1})</tex>.|proof=Выберем некоторые , в таком случае <tex>m_i'a_i</tex>, таким образом, чтобы и <tex>m_i' a_{i+ b_k not\equiv m_j' + b_p1}</tex> его <tex>succ</tex> и <tex>pred</tex>. Предположим, что мы выбрали по <tex>m_1' \ldots m_{t-1}'sketch</tex>. Тогда среди них есть настоящий (не по <tex>m_t' \ne m_i' + b_j - b_k \; \forall i,j,ksketch</tex>. Всего ) <tex>succ</tex>t\times r\times r или < r^3 tex>pred</tex> недопустимых значений для по доказанному, а понять это мы можем просто сделав сравнение с <tex>m_t'q</tex>, поэтому всегда можно найти хотя бы одно значение.

Чтобы получить ===Поиск реального следующего и предыдущего===Мы умеем находить реальный <tex>succ</tex> и <tex>pred</tex> по <tex>succ</tex> и <tex>pred</tex> от <tex>m_isketch(y)</tex>, выбираем каждый раз наименьшее теперь покажем, как искать <tex>m_i'succ</tex> и прибавляем подходящее число кратное <tex>r^3pred</tex>, такое что от <tex>sketch(y)</tex>m_i+c_i за < m_{i+tex> O(1}+c_{i+1} \leqslant m_i+c_i+r^3)</tex>. }}Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить Определим <tex>sketch узла в w-битный тип. Так (node)</tex> как число, составленное из единиц и <tex>r \leqslant B-1sketch(a_i)</tex>, то есть <tex>sketch(node) = 1sketch(a_1)1sketch(a_2)\ldots 1sketch(a_k)</tex>. Вычтем из <tex>sketch(node)</tex> будет занимать число <tex>Bsketch(rq) \times \underbrace{\overbrace{00\ldots 1}^4 {l + 1) bits}\overbrace{00\leqslant B((B-ldots 1)}^4 {l + 1) bits}\ldots \overbrace{00\leqslant B^5 = (wldots 1}^{l + 1/5bits}}_{k(l + 1)^5 bits} = w 0sketch(q)\ldots 0sketch(q)</tex> бит.==Индекс наиболее значащего бита==Чтобы найти в w-битном числе ''x'' индекс самого старшего битаВ начале каждого блока, содержащего еденицу, разделим ''x'' на где <tex>sketch(a_i) \sqrt{w}geqslant sketch(q)</tex> блоков по , сохранятся единицы. Применим к получившемуся побитовое <tex>\sqrt{w}&</tex> бит.c <tex>x = \underbrace{0101}_{displaystyle \sqrtsum_{wi=0}}\; \underbrace^{0000k-1}_2^{\sqrt{w}}\; \underbrace{1000}_{\sqrt{w}}\; \underbrace{1101}_{\sqrt{w}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>

aЕсли <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> бит. Применим побитовое AND к ''В таком случае мы получим некоторое <tex>2^i</tex>, где <tex>i</tex> является реальным <tex>pred(x'' и константой ''F'')</tex>, а <tex>i</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{1}000\; \underline{1}000\end{array}\end{array}$$</tex>Индекс наиболее старшего бита с помощью цикла де Брёйна ===

b. Определим'''Последовательность де Брёйна''' {{---}} последовательность <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>)\begin{array}{r}* <tex>0011</tex> (содержит подпоследовательности <tex>00, 01, 11, 10</tex>)XOR\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{* <tex>00010111 (000}\; 0\underline{, 001, 010, 101}, 011, 111, 110, 100)</tex>\end{array}\end{array}$$* <tex>0000100110101111</tex>

Возьмем цикл де Брёйна для <tex> $$n</tex> <tex>(i = 0\begin{array}{r}ldots n-\begin{array}{r}F 1)</tex> и запишем его как число <tex>b</tex> (для <tex>8</tex> цикл де Брёна равен <tex>00010111</tex>, а значение <tex>b = 1000\; 1000\; 1000\; 1000\\t_2 23</tex>). Умножим это число на <tex>2^i</tex>, сдвинем его влево на <tex>i</tex>, а затем обратно вправо на <tex>n-k</tex> (<tex>k</tex> такое, что <tex>n= 02^k</tex>). <tex>(b \underlinetexttt{101}\; 0\underline{000<<}i) \; 0\underlinetexttt{000>>}\; 0\underline(n-k)</tex>), тогда получившееся число {101}\\\end{array---} \\\hline\begin{array}{r}t_3 = <tex>i</tex>-ая подстрока длины <tex>k</tex> данного цикла де Брёйна. Эту перестановку опозначим за <tex>p</tex> и тогда применив ее к <tex>(2^i\underline{0}xxxcdot x) \; \underlinetexttt{1>>}000\; \underline{1}000\; \underline{0}xxx\end{array}\end{array}$$(n-k))</tex> получим <tex>i</tex>: <tex>p</tex> в данном случае такое, что <tex>k</tex>подряд идущих бит равны значению, на сколько мы сдвинули.

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

# Уберем все несущественные биты <tex> $$x' = x \& \displaystyle \beginsum_{arrayi=0}^{r-1}2^{b_i}</tex>.XOR# Умножением на некоторое заранее вычисленное число <tex>M = \displaystyle\beginsum_{arrayi=0}^{r-1}2^{m_i}F </tex> сместим все существенные биты в блок меньшего размера: <tex>x'\times M = 1000\; 1000displaystyle \; 1000left( \; 1000sum_{i=0}^{r-1}x_{b_i} 2^{b_i} \right) \t_3 = left(\underlinesum_{i=0}xxx\; \underline^{r-1}0002^{m_i}\; right) = \underlinesum_{i=0}^{r-1}000\; \underlinesum_{j=0}xxx\\\end^{r-1}x_{b_i} 2^{arrayb_i+m_j} </tex>.# Применив побитовое <tex>\&</tex>, уберем лишние биты, появившиеся в результате умножения: <tex>\left(\hlinedisplaystyle\beginsum_{arrayi=0}^{r-1}t_4 \sum_{j= \underline0}^{r-1}000x_{b_i} 2^{b_i+m_j} \right) \& \; displaystyle\underlinesum_{i=0}000\; ^{r-1}2^{b_i+m_i} = \underlinesum_{i=0}000\; \underline^{r-1}000\endx_{arrayb_i}\end2^{arrayb_i+m_i}</tex>.$$# Сделаем сдвиг вправо на <tex>m_0 + b_0</tex>бит.

c{{Утверждение|id= |author=|about=|statement=Дана последовательность из <tex>r</tex> чисел <tex>b_0<b_1<\ldots <b_{r-1}</tex>. Первый бит в каждом блоке Тогда существует последовательность <tex>m_0<m_1\ldots <m_{r-1}</tex>, такая что:# все <tex>b_i + m_j</tex> различны, для <tex>0\leqslant i,j \leqslant r-1</tex># <tex>b_0 + m_0\leqslant b_1 + m_1\leqslant \ldots \leqslant b_{r-1} + m_{r-1}</tex># <tex>(b_{r-1} + m_{r-1}) - (b_0 + m_0) \leqslant r^4</tex>y .|proof= t_1Выберем некоторые <tex>m_i'</tex>, таким образом, чтобы <tex>m_i' + b_k \; OR not\;t_4equiv m_j' + b_p</tex> содержит еденицу. Предположим, если соответствующий блок что мы выбрали <tex>m_1' \ldots m_{t-1}'</tex>. Тогда <tex>m_t'x\ne m_i'+ b_j - b_k \; \forall i,j,k</tex>. Всего <tex>t\times r\times r < r^3 </tex> недопустимых значений для <tex>m_t' ненулевой</tex>, поэтому всегда можно найти хотя бы одно значение.

Чтобы получить <tex>$$\beginm_i</tex>, выбираем каждый раз наименьшее <tex>m_i'</tex> и прибавляем подходящее число кратное <tex>r^3</tex>, такое что <tex>m_i+c_i < m_{arrayi+1}+c_{ri+1}OR\begin{array}{leqslant m_i+c_i+r}^3</tex>. t_1 = \underline{0}000\; \underline{0}000Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить <tex>sketch</tex> узла в <tex>w</tex>-битный тип. Так как <tex>r \; leqslant B-1</tex>, то <tex>sketch(node)</tex> будет занимать <tex>B(r^4 + 1) \underline{leqslant B((B-1}000\; \underline{)^4 + 1}000\\t_4 ) = \underline{B((B^2 - 2B + 1}000\; \underline{0}000\; \underline{0}000\; \underline{)^2 + 1}000\\\end{array} \\\hline\begin{array}{r}y )= \underline{</tex><tex>B(B^4 + 4B^2 + 1}000\; \underline{0}000\; \underline{- 4B^3 + 2B^2 -4B + 1}000) = B^5 - 4B^3 + 6B^2 - 4B + 2 \; \underlineleqslant B^5 </tex><tex> = (w^{1/5}000\end{array}\end{array}$$)^5 = w </tex> 2) найдем sketch(y)бит, чтобы сместить все нужные биты в один блок. Существенными битами в данном случае будут первые биты каждого блока, поэтому при всех <tex>b_i = B \sqrt{w} - geqslant 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>. Чтобы найти sketch(y), умножим y на m и сдвинем вправо на w бит.

Каждый шаг выполняется за <tex>O(1)<* [http:/tex>, поэтому всего потребуется <tex>O(1)</tex> времениwww.sciencedirect.com/science/article/pii/0022000093900404 M. L. Fredman and D. E. Willard. Surpassing the information theoretic barrier with fusion trees. Journal of Computer and System Sciences, чтобы найти индекс.1993]

==Ссылки==* [http://wwwcourses.sciencedirectcsail.commit.edu/6.897/sciencespring03/articlescribe_notes/piiL4/0022000093900404 Mlecture4. Lpdf MIT CS 6. Fredman and D897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. E. Willard. Surpassing the information theoretic barrier with fusion trees. Journal of Computer and System Sciences, 1993Erik Demaine (Spring 2003)]

* [http://courses.csail.mit.edu/6.897851/spring03spring12/scribe_notesscribe/L4/lecture4lec12.pdf MIT CS 6.897851: Advanced Data Structures: Lecture 412, Fusion TreesTree notes, Prof. Erik Demaine (Spring 20032012)]

* [http://courseswww.csaillektorium.mit.edutv/lecture/6?id=14292 А.851/spring12/scribe/lec12С.pdf MIT CS 6Станкевич.851: Advanced Data Structures: Lecture 12Дополнительные главы алгоритмов, Fusion Tree notes, Prof. Erik Demaine (Spring 2012)лекция 6]

* [http://wwwen.lektoriumwikipedia.tvorg/lecturewiki/?id=14292 А.С. Станкевич. Дополнительные главы алгоритмов, лекция 6Fusion_tree Wikipedia — Fusion tree]

* [httphttps://en.wikipedia.org/wiki/Fusion_tree De_Bruijn_sequence Wikipedia — Fusion treeDe Bruijn sequence]