Fusion tree — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 60 промежуточных версий 3 участников)
Строка 1: Строка 1:
'''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''' {{---}} дерево поиска, позволяющее хранить <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-дерево]], такое что:
 
Fusion tree {{---}} это [[B-дерево|B-дерево]], такое что:
* у всех вершин, кроме листьев, <tex>B = w^{1/5}</tex> детей;
+
* у всех вершин, кроме листьев, <tex>B = w^{1/5}</tex> детей,
 
* время, за которое определяется, в каком поддереве находится вершина, равно <tex>O(1)</tex>.
 
* время, за которое определяется, в каком поддереве находится вершина, равно <tex>O(1)</tex>.
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Построим цифровой бор из ключей узла дерева. Всего <tex>B - 1</tex> ветвящихся вершин. Биты, соответствующие уровням дерева,  в которых происходит ветвление, назовем существенными и обозначим их номера <tex>b_0, b_2\ldots b_{r-1}</tex>. Количество существенных битов <tex>r</tex> не больше чем <tex>B - 1</tex>.
+
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Построим [[:Сверхбыстрый_цифровой_бор|цифровой бор]] из ключей узла дерева. Всего <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>, поскольку на одном уровне могут быть несколько ветвящихся вершин).
  
 
[[Файл:Fusion.png||500x400px|center|визуализация функции sketch]]
 
[[Файл:Fusion.png||500x400px|center|визуализация функции sketch]]
Строка 19: Строка 19:
  
 
==Поиск вершины==
 
==Поиск вершины==
[[Файл: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>\left \{ a_1,a_2\ldots a_k\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>.
 
===Параллельное сравнение===
 
Найдем <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>, сохранятся единицы. Применим к получившемуся побитовое <tex>\land</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))\land \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>\left \{ a_1,a_2\ldots a_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>.
  
Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.
+
===Поиск следующего и предыдущего по sketch===
Теперь надо найти количество единиц в ''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>.
 
 
{{Утверждение
 
{{Утверждение
 
|id=prefix.  
 
|id=prefix.  
 
|author=
 
|author=
 
|about=
 
|about=
|statement=Среди всех ключей наибольший общий префикс с <tex>q</tex> будет иметь или <tex>a_i</tex> или <tex>a_{i+1}</tex>.
+
|statement=Среди значений  <tex>succ(y)</tex> и <tex>pred(y)</tex> по <tex>sketch(y)</tex> есть <tex>succ</tex> или <tex>pred</tex> по значению <tex>y</tex>.
 
|proof=
 
|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>, наименьший среди больших.
 
}}
 
}}
Сравнивая <tex>a \oplus q</tex> и <tex>b \oplus 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>).  
+
[[Файл: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>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>равен pred(q)</tex>;
+
 
* если <tex>q<a_j</tex> {{---}} найдем <tex>succ(e)</tex>, <tex>e = p10\ldots 00</tex>. Это будет <tex>succ(q)</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>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> мы можем получить с помощью цикла де Брёйна
  
Длина наибольшего общего префикса двух ''w''-битных чисел <tex>a</tex> и <tex>b</tex> может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом \oplus <tex>a</tex> и <tex>b</tex>.
+
=== Индекс наиболее старшего бита с помощью цикла де Брёйна ===
  
==Вычисление sketch(x)==
+
'''Последовательность де Брёйна''' {{---}} последовательность <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> различны.
Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.
+
 
 +
==== Примеры ====
  
1) уберем все несущественные биты <tex>x' = x \land \displaystyle \sum_{i=0}^{r-1}2^{b_i}</tex>;
+
Примеры циклов де Брёйна для <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>
  
2) умножением на некоторое заранее вычисленное число <tex>M = \displaystyle\sum_{i=0}^{r-1}2^{m_i}</tex> сместим все существенные биты в блок меньшего размера.
+
==== Получение индекса по значению степени двойки ====
  
<tex>x'\times M = \displaystyle(\sum_{i=0}^{r-1}x_{b_i}2^{b_i})(\sum_{i=0}^{r-1}2^{m_i}) = \sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}</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> подряд идущих бит равны значению, на сколько мы сдвинули.
  
3) применив побитовое <tex>\land</tex>, уберем лишние биты, появившиеся в результате умножения;
+
==Вычисление sketch(x)==
 +
Чтобы найти <tex>sketch</tex> за константное время, будем вычислять <tex>supersketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули. Хотя <tex>supersketch</tex> содержит лишние нули, мы сможем вычислять его быстрее, чем обычный <tex>sketch</tex>, потому что нам не придется каждый раз идти по всем битам числа, выбирая стоящие на нужных нам местах. Будем использовать <tex>supersketch</tex> вместо <tex>sketch</tex> {{---}} это никак не повлияет на сравнение, поскольку добавленные биты равны нулю и стоят на одних и тех же местах для всех <tex>sketch</tex>
  
<tex>\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j} \land \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>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) \& \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> бит.
  
4) сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.
 
 
{{Утверждение
 
{{Утверждение
 
|id=  
 
|id=  
Строка 66: Строка 75:
 
|about=
 
|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>, такая что:
 
|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>
1) все <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>.
2) <tex>b_0 + m_0\leqslant b_1 + m_1\leqslant \ldots \leqslant b_{r-1} + m_{r-1}</tex>;
 
 
 
3) <tex>(b_{r-1} + m_{r-1}) - (b_0 + m_0) \leqslant r^4</tex>.
 
 
|proof=
 
|proof=
 
Выберем некоторые <tex>m_i'</tex>, таким образом, чтобы <tex>m_i' + b_k \not\equiv m_j' + b_p</tex>. Предположим, что мы выбрали <tex>m_1' \ldots m_{t-1}'</tex>. Тогда <tex>m_t' \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>m_i'</tex>, таким образом, чтобы <tex>m_i' + b_k \not\equiv m_j' + b_p</tex>. Предположим, что мы выбрали <tex>m_1' \ldots m_{t-1}'</tex>. Тогда <tex>m_t' \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>, поэтому всегда можно найти хотя бы одно значение.
Строка 77: Строка 83:
 
Чтобы получить <tex>m_i</tex>, выбираем каждый раз наименьшее <tex>m_i'</tex> и прибавляем подходящее число кратное <tex>r^3</tex>, такое что <tex>m_i+c_i < m_{i+1}+c_{i+1} \leqslant m_i+c_i+r^3</tex>.  
 
Чтобы получить <tex>m_i</tex>, выбираем каждый раз наименьшее <tex>m_i'</tex> и прибавляем подходящее число кратное <tex>r^3</tex>, такое что <tex>m_i+c_i < m_{i+1}+c_{i+1} \leqslant m_i+c_i+r^3</tex>.  
 
}}
 
}}
Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить sketch узла в w-битный тип. Так как <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^{1/5})^5 = w </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) = 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>
 
 
==Индекс наиболее значащего бита==
 
Чтобы найти в w-битном числе <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>. Далее найдем первый непустой блок и индекс первого единичного бита в нем.
 
 
 
'''1)''' Поиск непустых блоков.
 
 
 
'''a.''' Определим, какие блоки имеют единицу в первом бите. Применим побитовое <tex>\land</tex> к <tex>x</tex> и константе <tex>F</tex>.
 
 
 
 
 
<tex>$$
 
\begin{array}{r}
 
\land
 
\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.''' Определим, содержат ли остальные биты единицы.
 
 
 
Вычислим <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>
 
 
 
 
 
'''2)''' Найдем <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> бит.
+
==См. Также==
  
'''3)''' Найдем первый ненулевой блок. Для этого надо найти первую единицу в <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>.
+
*[[:Сверхбыстрый_цифровой_бор|Сверхбыстрый цифровой бор]]
  
'''4)''' Найдем номер <tex>d</tex> первого единичного бита в найденном блоке так же как и в предыдущем пункте.
+
*[[:2-3_дерево|2-3 дерево]]
  
'''5)''' Индекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d</tex>.
+
== Источники информации ==
  
Каждый шаг выполняется за <tex>O(1)</tex>, поэтому всего потребуется <tex>O(1)</tex> времени, чтобы найти индекс.
+
* [http://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://courses.csail.mit.edu/6.897/spring03/scribe_notes/L4/lecture4.pdf MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003)]
[http://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://courses.csail.mit.edu/6.897/spring03/scribe_notes/L4/lecture4.pdf MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003)]
+
* [http://courses.csail.mit.edu/6.851/spring12/scribe/lec12.pdf MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof. Erik Demaine (Spring 2012)]
  
[http://courses.csail.mit.edu/6.851/spring12/scribe/lec12.pdf MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof. Erik Demaine (Spring 2012)]
+
* [http://www.lektorium.tv/lecture/?id=14292 А.С. Станкевич. Дополнительные главы алгоритмов, лекция 6]
  
[http://www.lektorium.tv/lecture/?id=14292 А.С. Станкевич. Дополнительные главы алгоритмов, лекция 6]
+
* [http://en.wikipedia.org/wiki/Fusion_tree Wikipedia — Fusion tree]
  
[http://en.wikipedia.org/wiki/Fusion_tree Wikipedia — Fusion tree]
+
* [https://en.wikipedia.org/wiki/De_Bruijn_sequence Wikipedia — De Bruijn sequence]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Деревья поиска]]
 
[[Категория:Деревья поиска]]
 +
[[Категория:Структуры данных]]

Текущая версия на 19:42, 4 сентября 2022

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

Структура

Fusion tree — это B-дерево, такое что:

  • у всех вершин, кроме листьев, [math]B = w^{1/5}[/math] детей,
  • время, за которое определяется, в каком поддереве находится вершина, равно [math]O(1)[/math].

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

визуализация функции sketch

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

Утверждение:
[math]sketch[/math] сохраняет порядок, то есть [math]sketch(x) \lt sketch(y)[/math], если [math]x \lt y[/math].
[math]\triangleright[/math]
Рассмотрим наибольший общий префикс [math]x[/math] и [math]y[/math]. Тогда следующий бит определяет их порядок и одновременно является существенным битом. Поэтому, если [math]x \lt y[/math], то и [math]sketch(x) \lt sketch(y)[/math].
[math]\triangleleft[/math]

Поиск вершины

Пусть [math]\left \{ a_1,a_2\ldots a_B\right \}[/math] — множество ключей узла, отсортированных по возрастанию, [math]q[/math] — ключ искомой вершины, [math]l[/math] — количество бит в [math]sketch(q)[/math]. Сначала найдем такой ключ [math]a_i[/math], что [math]sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})[/math]. Хотя положение [math]sketch(q)[/math] среди [math]sketch(a_j)[/math] не всегда эквивалентно положению [math]q[/math] среди [math]a_j[/math], зная соседние элементы [math]sketch(q)[/math], мы можем найти [math]succ(q)[/math] и [math]pred(q)[/math].

Поиск следующего и предыдущего по sketch

Утверждение:
Среди значений [math]succ(y)[/math] и [math]pred(y)[/math] по [math]sketch(y)[/math] есть [math]succ[/math] или [math]pred[/math] по значению [math]y[/math].
[math]\triangleright[/math]
Рассмотрим [math]y[/math]. У него есть существенные биты и некоторый элемент [math]x[/math], с которым у [math]y[/math] наибольший общий префикс (настоящий, а не по [math]sketch[/math]). Биты из [math]sketch[/math], находящиеся в префиксе совпадают, значит [math]succ[/math] и [math]pred[/math] [math]y[/math] среди [math]sketch[/math] должны быть такими же среди [math]x[/math], и один из них имеет дальше бит [math]0[/math] (а другой [math]1[/math]) и с ним может быть больше других общих бит в [math]sketch[/math]. То есть либо [math]succ[/math], либо [math]pred[/math] имеют следующий существенный бит такой же, как и у [math]y[/math]. Поэтому если значение равно [math]0[/math], то [math]x[/math] наибольший среди значений с меньшим [math]sketch[/math], и, аналогично для [math]1[/math], наименьший среди больших.
[math]\triangleleft[/math]
Пример случая, когда [math]sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})[/math], но [math]a_{i+1}\leqslant q[/math] [math]sketch(a_i) = 00, sketch(q) = 00, sketch(a_{i+1}) = 01, \\ a_i = 0000, a_{i+1} = 0010, q = 0101[/math]

Рассмотрим ключи. Порядок для них по [math]sketch[/math] совпадает с их порядком. Тогда для некоторых [math]a_i[/math] и [math]a_{i+1}[/math]: [math]sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})[/math], в таком случае [math]a_i[/math] и [math]a_{i+1}[/math] его [math]succ[/math] и [math]pred[/math] по [math]sketch[/math]. Тогда среди них есть настоящий (не по [math]sketch[/math]) [math]succ[/math] или [math]pred[/math] по доказанному, а понять это мы можем просто сделав сравнение с [math]q[/math].

Поиск реального следующего и предыдущего

Мы умеем находить реальный [math]succ[/math] и [math]pred[/math] по [math]succ[/math] и [math]pred[/math] от [math]sketch(y)[/math], теперь покажем, как искать [math]succ[/math] и [math]pred[/math] от [math]sketch(y)[/math] за [math] O(1)[/math]. Определим [math]sketch(node)[/math] как число, составленное из единиц и [math]sketch(a_i)[/math], то есть [math]sketch(node) = 1sketch(a_1)1sketch(a_2)\ldots 1sketch(a_k)[/math]. Вычтем из [math]sketch(node)[/math] число [math]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)[/math]. В начале каждого блока, где [math]sketch(a_i) \geqslant sketch(q)[/math], сохранятся единицы. Применим к получившемуся побитовое [math]\&[/math] c [math]\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}[/math], чтобы убрать лишние биты.

[math]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}[/math]

Если [math]sketch(a_i)\lt sketch(q)[/math], то [math]c_i = 0[/math], в противном случае [math]c_i = 1[/math]. Теперь надо найти количество единиц в [math]L[/math]. Умножим [math]L[/math] на [math]\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}[/math], тогда все единицы сложатся в первом блоке результата, и, чтобы получить количество единиц, сдвинем его вправо на [math](k-1)\cdot(l + 1)[/math] бит. В таком случае мы получим некоторое [math]2^i[/math], где [math]i[/math] является реальным [math]pred(x)[/math], а [math]i[/math] мы можем получить с помощью цикла де Брёйна

Индекс наиболее старшего бита с помощью цикла де Брёйна

Последовательность де Брёйна — последовательность [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] с периодом [math]2, 4, 8, 16[/math]:

  • [math]01[/math] (содержит подпоследовательности [math]0[/math] и [math]1[/math])
  • [math]0011[/math] (содержит подпоследовательности [math]00, 01, 11, 10[/math])
  • [math]00010111 (000, 001, 010, 101, 011, 111, 110, 100)[/math]
  • [math]0000100110101111[/math]

Получение индекса по значению степени двойки

Возьмем цикл де Брёйна для [math]n[/math] [math](i = 0\ldots n-1)[/math] и запишем его как число [math]b[/math] (для [math]8[/math] цикл де Брёна равен [math]00010111[/math], а значение [math]b = 23[/math]). Умножим это число на [math]2^i[/math], сдвинем его влево на [math]i[/math], а затем обратно вправо на [math]n-k[/math] ([math]k[/math] такое, что [math]n=2^k[/math]). [math](b \texttt{\lt \lt } i) \texttt{\gt \gt }(n-k)[/math]), тогда получившееся число — [math]i[/math]-ая подстрока длины [math]k[/math] данного цикла де Брёйна. Эту перестановку опозначим за [math]p[/math] и тогда применив ее к [math](2^i\cdot x) \texttt{\gt \gt } (n-k))[/math] получим [math]i[/math]: [math]p[/math] в данном случае такое, что [math]k[/math] подряд идущих бит равны значению, на сколько мы сдвинули.

Вычисление sketch(x)

Чтобы найти [math]sketch[/math] за константное время, будем вычислять [math]supersketch(x)[/math], имеющий все существенные биты в нужном порядке, но содержащий лишние нули. Хотя [math]supersketch[/math] содержит лишние нули, мы сможем вычислять его быстрее, чем обычный [math]sketch[/math], потому что нам не придется каждый раз идти по всем битам числа, выбирая стоящие на нужных нам местах. Будем использовать [math]supersketch[/math] вместо [math]sketch[/math] — это никак не повлияет на сравнение, поскольку добавленные биты равны нулю и стоят на одних и тех же местах для всех [math]sketch[/math]

  1. Уберем все несущественные биты [math]x' = x \& \displaystyle \sum_{i=0}^{r-1}2^{b_i}[/math].
  2. Умножением на некоторое заранее вычисленное число [math]M = \displaystyle\sum_{i=0}^{r-1}2^{m_i}[/math] сместим все существенные биты в блок меньшего размера: [math]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}[/math].
  3. Применив побитовое [math]\&[/math], уберем лишние биты, появившиеся в результате умножения: [math]\left(\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i} 2^{b_i+m_j} \right) \& \displaystyle\sum_{i=0}^{r-1}2^{b_i+m_i} = \sum_{i=0}^{r-1}x_{b_i}2^{b_i+m_i}[/math].
  4. Сделаем сдвиг вправо на [math]m_0 + b_0[/math] бит.
Утверждение:
Дана последовательность из [math]r[/math] чисел [math]b_0\lt b_1\lt \ldots \lt b_{r-1}[/math]. Тогда существует последовательность [math]m_0\lt m_1\ldots \lt m_{r-1}[/math], такая что:
  1. все [math]b_i + m_j[/math] различны, для [math]0\leqslant i,j \leqslant r-1[/math]
  2. [math]b_0 + m_0\leqslant b_1 + m_1\leqslant \ldots \leqslant b_{r-1} + m_{r-1}[/math]
  3. [math](b_{r-1} + m_{r-1}) - (b_0 + m_0) \leqslant r^4[/math].
[math]\triangleright[/math]

Выберем некоторые [math]m_i'[/math], таким образом, чтобы [math]m_i' + b_k \not\equiv m_j' + b_p[/math]. Предположим, что мы выбрали [math]m_1' \ldots m_{t-1}'[/math]. Тогда [math]m_t' \ne m_i' + b_j - b_k \; \forall i,j,k[/math]. Всего [math]t\times r\times r \lt r^3 [/math] недопустимых значений для [math]m_t'[/math], поэтому всегда можно найти хотя бы одно значение.

Чтобы получить [math]m_i[/math], выбираем каждый раз наименьшее [math]m_i'[/math] и прибавляем подходящее число кратное [math]r^3[/math], такое что [math]m_i+c_i \lt m_{i+1}+c_{i+1} \leqslant m_i+c_i+r^3[/math].
[math]\triangleleft[/math]

Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить [math]sketch[/math] узла в [math]w[/math]-битный тип. Так как [math]r \leqslant B-1[/math], то [math]sketch(node)[/math] будет занимать [math]B(r^4 + 1) \leqslant B((B-1)^4 + 1) = B((B^2 - 2B + 1)^2 + 1)=[/math][math]B(B^4 + 4B^2 + 1 - 4B^3 + 2B^2 -4B + 1) = B^5 - 4B^3 + 6B^2 - 4B + 2 \leqslant B^5 [/math][math] = (w^{1/5})^5 = w [/math] бит, при всех [math]B \geqslant 1[/math]

См. Также

Источники информации