Изменения

'''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.png||500x400px|center|визуализация функции sketch]] В Fusion tree вместо ключа вместе с ключом <tex>x</tex> хранится <tex>Sketchsketch(x)</tex> {{--- }} последовательность битов <tex>x_{b_rb_{r-1}}\ldots x_{b_1b_0}</tex>. {{Утверждение|id=sketch. |author=|about=|statement=<tex>Sketchsketch</tex> сохраняет порядок, то есть <tex>sketch(x) < sketch(y)</tex>, если <tex>x < y</tex>.|proof=Рассмотрим наибольший общий префикс <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)предыдущего по sketch===Пусть <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>. Сравнивая ''a''XOR''q'' и ''b''XOR''q'', найдем какой из ключей имеет наибольший общий префикс с ''q'' (наименьшнее значение соответствует наибольшей длине).

Предположим, что ''p'' - наибольший общий перфикс, а ''y'' его длина, ''a_j'' - ключ, имеющий наибольший общий префикс с ''q'' (j {{Утверждение|id= i или i+1)prefix. * если ''q|author=|about=|statement=Среди значений <tex>a_j'', то ''succ(y + 1'' бит ''q'' равен еденице, а ''y + 1'' бит ''a_j'' равен 0. Так как общий префикс ''a_j'' )</tex> и ''q'' является наибольшим, то не существет ключа с префиксом ''p1''.Значит, ''q'' больше всех ключей с префиксом меньшим либо равным ''p''. Найдем pred e = p01\ldots 11, который одновременно будет равен <tex>pred(qy);* если < - найдем succ e = p10\ldots 00. Это будет succ/tex> по <tex>sketch(qy)</tex> есть <tex>succ</tex> или <tex>pred</tex> по значению <tex>y</tex>.|proof=

Длина наибольшего общего префикса двух ''w''-битных чисел ''a'' Рассмотрим <tex>y</tex>. У него есть существенные биты и ''b'' может быть вычислена некоторый элемент <tex>x</tex>, с помощью нахождения индекса наиболее значащего бита которым у <tex>y</tex> наибольший общий префикс (настоящий, а не по <tex>sketch</tex>). Биты из <tex>sketch</tex>, находящиеся в побитовом XOR ''a'' префиксе совпадают, значит <tex>succ</tex> и ''b''.==Вычисление <tex>pred</tex> <tex>y</tex> среди <tex>sketch</tex> должны быть такими же среди <tex>x</tex>, и один из них имеет дальше бит <tex>0</tex> (xа другой <tex>1</tex>)==Чтобы найти и с ним может быть больше других общих бит в <tex>sketch за константное время</tex>. То есть либо <tex>succ</tex>, либо <tex>pred</tex> имеют следующий существенный бит такой же, как и у <tex>y</tex>. Поэтому если значение равно <tex>0</tex>, будем вычислять то <tex>x</tex> наибольший среди значений с меньшим <tex>sketch(x)</tex>, и, имеющий все существенные биты в нужном порядкеаналогично для <tex>1</tex>, но содержащий лишние нулинаименьший среди больших.}}

[[Файл:FusionTree.png|400x400px|thumb|right|Пример случая, когда <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1}) уберем все несущественные биты </tex>x' = x, но <tex>a_{i+1}\leqslant q</tex> AND <tex>sketch(a_i) = 00, sketch(q) = 00, sketch(a_{i+1}) = 01, \displaystyle \sum_a_i = 0000, a_{i=0}^{r-+1}2^{b_i}= 0010, q = 0101</tex>;]]

2) умножением на некоторое число Рассмотрим ключи. Порядок для них по <tex>sketch</tex> совпадает с их порядком. Тогда для некоторых <tex>a_i</tex> и <tex>a_{i+1}</tex>: <tex>M = sketch(a_i) \displaystyleleqslant sketch(q) \sum_leqslant sketch(a_{i=0+1}^)</tex>, в таком случае <tex>a_i</tex> и <tex>a_{r-i+1}2^{m_i}</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>x'*M sketch(node) = 1sketch(a_1)1sketch(a_2)\displaystyleldots 1sketch(a_k)</tex>. Вычтем из <tex>sketch(node)</tex> число <tex>sketch(q) \sum_times \underbrace{\overbrace{i=000\ldots 1}^{r-l + 1bits}x_\overbrace{b_i00\ldots 1}2^{b_il + 1 bits})(\sum_ldots \overbrace{i=000\ldots 1}^{r-l + 1bits}2^}_{m_ik(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}^{rk-1}\sum_{j=0}2^{r-i(l+1}x_{b_i}2^{b_i)+m_jl}</tex>;, чтобы убрать лишние биты.

3<tex>L = (1sketch(a_1) применив побитовое AND уберем лишние биты, появившиеся в результате умножения;\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>\displaystyle\sum_{isketch(a_i)< sketch(q)</tex>, то <tex>c_i =0}^{r-</tex>, в противном случае <tex>c_i = 1}</tex>.Теперь надо найти количество единиц в <tex>L</tex>. Умножим <tex>L</tex> на <tex>\sum_underbrace{j=0\ldots 01}^_{r-l + 1bits}x_\ldots \underbrace{b_i0\ldots 01}2^_{b_il+m_j1 bits}</tex> AND , тогда все единицы сложатся в первом блоке результата, и, чтобы получить количество единиц, сдвинем его вправо на <tex>\displaystyle\sum_{i=0}^{r(k-1}2^{b_i)\cdot(l +m_i} = \sum_{i=0}^{r-1}x_{b_i})</tex> бит. В таком случае мы получим некоторое <tex>2^{b_i+m_i}i</tex>, где <tex>i</tex> является реальным <tex>pred(x)</tex>, а <tex>i</tex>;мы можем получить с помощью цикла де Брёйна

4) сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.{{Утверждение|id= |author=|about=|statementИндекс наиболее старшего бита с помощью цикла де Брёйна ===Дана последовательность из r чисел <tex>b_0<b_1<\ldots <b_{r-1}</tex>. Тогда существует последовательность <tex>m_0<m_1\ldots <m_{r-1}</tex>, такая что:

1) все '''Последовательность де Брёйна''' {{---}} последовательность <texmath>b_i + m_ja_1,\;\ldots,\;a_t</texmath> различны, для элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество <texmath>\{0,\leqslant i;1,\;\ldots,j \leqslant r;k-1\}</texmath>), и все подпоследовательности <math>a_{i+1},\;\ldots,\;a_{i+n}</math> заданной длины <math>n</math> различны.

3) Примеры циклов де Брёйна для <math>k=2</math> с периодом <tex>2, 4, 8, 16</tex>:* <tex>01</tex>(b_{r-содержит подпоследовательности <tex>0</tex> и <tex>1} + m_{r-1}</tex>) - * <tex>0011</tex> (b_0 + m_0) \leqslant r^4содержит подпоследовательности <tex>00, 01, 11, 10</tex>.)|proof=Выберем некоторые* <tex>00010111 (000, 001, 010, таким образом101, чтобы. Предположим011, что мы выбрали. mt' != mi' + bj - bk A i111,j110,k. В противном случае . Всего t100)</tex>*r*r <= r^3 недопустимых значений для mt', поэтому всегда можно найти хотя бы одно значение.tex>0000100110101111</tex>

Чтобы получить mi, выбираем каждый раз наименьшие mi' и прибавляем подходящее число кратное r^3, такое что mi+ci<mi+l+Ci+l<=mi+ci+r3. }}Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить sketch узла в w-битный тип. Так как r<=B-1, то sketch(node) будет занимать B*(r*4 + 1) <= B*((B-1)^4 + 1) <= B^5 Получение индекса по значению степени двойки = (w^{1/5})^5 = w бит.==Индекс наиболее значащего бита==Чтобы найти в w-битном числе ''x'' индекс самого старшего бита, содержащего еденицу, разделим ''x'' на <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>n</tex> <tex>(i = 0\ldots n-1)Поиск непустых блоков</tex> и запишем его как число <tex>b</tex> (для <tex>8</tex> цикл де Брёна равен <tex>00010111</tex>, а значение <tex>b = 23</tex>). aУмножим это число на <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> данного цикла де Брёйна. Применим побитовое AND Эту перестановку опозначим за <tex>p</tex> и тогда применив ее к ''<tex>(2^i\cdot x'' и константой ''F'') \texttt{>>} (n-k))</tex> получим <tex>i</tex>: <tex>p</tex> в данном случае такое, что <tex>k</tex> подряд идущих бит равны значению, на сколько мы сдвинули.

==Вычисление sketch(x)==Чтобы найти <tex>sketch</tex> за константное время, будем вычислять <tex> $$\begin{array}{r}AND\begin{array}{r}supersketch(x = 0101\; 0000\; 1000\; 1101\\F = 1000\; 1000\; 1000\; 1000\\\end)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули. Хотя <tex>supersketch</tex> содержит лишние нули, мы сможем вычислять его быстрее, чем обычный <tex>sketch</tex>, потому что нам не придется каждый раз идти по всем битам числа, выбирая стоящие на нужных нам местах. Будем использовать <tex>supersketch</tex> вместо <tex>sketch</tex> {array} \\\hline\begin{array---}{r}t_1 = \underline{0}000\; \underline{0}000\; \underline{1}000\; \underline{1}000\end{array}\end{array}$$это никак не повлияет на сравнение, поскольку добавленные биты равны нулю и стоят на одних и тех же местах для всех <tex>sketch</tex> b. Определим, содержат ли остальные биты еденицы.

Вычислим # Уберем все несущественные биты <tex>x' = x \& \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} \right) \& \; XOR displaystyle\; t_1sum_{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>бит.

{{Утверждение|id= |author=|about=|statement=Дана последовательность из <tex> $$r</tex> чисел <tex>b_0<b_1<\begin{array}ldots <b_{r-1}XOR</tex>. Тогда существует последовательность <tex>m_0<m_1\begin{array}ldots <m_{r-1}</tex>, такая что:t_1 = 0000\; 0000\; 1000\; 1000# все <tex>b_i + m_j</tex> различны, для <tex>0\leqslant i,j \leqslant r-1</tex>x = 0101\; 0000# <tex>b_0 + m_0\; 1000leqslant b_1 + m_1\; 1101leqslant \ldots \\endleqslant b_{r-1} + m_{arrayr-1} \\</tex>\hline\begin# <tex>(b_{arrayr-1}+ m_{r-1}) - (b_0 + m_0) \leqslant r^4</tex>.t_2 |proof= 0Выберем некоторые <tex>m_i'</tex>, таким образом, чтобы <tex>m_i' + b_k \underline{101}not\; 0equiv m_j' + b_p</tex>. Предположим, что мы выбрали <tex>m_1' \underlineldots m_{000t-1}'</tex>. Тогда <tex>m_t' \; 0\underline{000}ne m_i' + b_j - b_k \; 0\underline{101}forall i,j,k</tex>. Всего <tex>t\end{array}times r\end{array}$$times r < r^3 </tex> недопустимых значений для <tex>m_t'</tex>, поэтому всегда можно найти хотя бы одно значение.

Вычтем от Чтобы получить <tex>F\; t_2m_i</tex>. Если какой-нибудь бит , выбираем каждый раз наименьшее <tex>m_i''F'' обнулится, значит</tex> и прибавляем подходящее число кратное <tex>r^3</tex>, соответствующий блок содержит еденицы. такое что <tex> $$\beginm_i+c_i < m_{arrayi+1}+c_{ri+1}-\begin{array}{leqslant m_i+c_i+r}F = 1000\; 1000\; 1000\; 1000\\^3</tex>. t_2 = 0\underline{101}\; 0\underline{000}\; 0\underline{000}\; 0\underline{101}\\Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить <tex>sketch</tex> узла в <tex>w</tex>-битный тип. Так как <tex>r \end{array} 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 \\hline\begin{array}{r}t_3 leqslant B^5 </tex><tex> = \underline{0}xxx\; \underline(w^{1/5}000)^5 = w </tex> бит, при всех <tex>B \; \underline{geqslant 1}000\; \underline{0}xxx\end{array}\end{array}$$</tex>

Чтобы найти блоки, содержащие еденицы, вычислим <tex>t_3\; XOR \; F</tex>==См.Также==

<tex>$$\begin{array}{r}OR\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>

2) найдем sketch(y), чтобы сместить все нужные биты в один блок* [http://www.sciencedirect. Существенными битами в данном случае будут первые биты каждого блока, поэтому <tex>b_i = \sqrt{w} - 1 + i\sqrt{w}<com/science/article/pii/tex>0022000093900404 M. L. Fredman and D. E. Willard. Surpassing the information theoretic barrier with fusion trees. Journal of Computer and System Sciences, 1993]

Будем использовать <tex>m_j = w - (\sqrt{w}-1) - j\sqrt{w} +j<* [http://tex>courses.csail. Тогда <tex>b_i + m_j = w + (i - j)\sqrt{w} + j<mit.edu/tex>6. Все суммы различны при <tex>0\leqslant i, j < \sqrt{w} <897/spring03/scribe_notes/L4/tex>lecture4. Все <tex>b_i + m_i = w + i</tex> возрастаютpdf MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, и <tex>(b_{\sqrt{w} - 1} + m_{\sqrt{w} - 1}) - (b_0 + m_0) = \sqrt{w} - 1</tex>Prof. Чтобы найти sketchErik Demaine (ySpring 2003), умножим y на m и сдвинем вправо на w бит.]

3)Найдем первый ненулевой блок* [http://courses.csail. Для этого надо найти первую еденицу в sketch(y)mit. Как и при поиске succ(sketch(q)) и pred(sketch(q)) используем параллельное сравнение sketch(y) с <tex>2^0, 2^1 \ldots 2^{\sqrt{w} - 1}<edu/tex>6. В результате сравнения получим номер первого ненулевого блока <tex>c<851/spring12/scribe/tex>lec12.pdf MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof.Erik Demaine (Spring 2012)]

4) найдем номер d первого еденичного бита в найденном блоке так же как и в предыдущем пункте* [http://www.lektorium.tv/lecture/?id=14292 А.С. Станкевич. Дополнительные главы алгоритмов, лекция 6]

5) инедекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d<* [http:/tex>/en.wikipedia.org/wiki/Fusion_tree Wikipedia — Fusion tree]

Каждый шаг выполняется за <tex>O(1)<* [https:/tex>, поэтому всего потребуется <tex>O(1)</tex> времени, чтобы найти индексen.wikipedia.org/wiki/De_Bruijn_sequence Wikipedia — De Bruijn sequence][[Категория:Дискретная математика и алгоритмы]][[Категория:Деревья поиска]][[Категория:Структуры данных]]