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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вычисление sketch(x))
м (XOR -> \oplus; едени* -> едини*)
Строка 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-дерево]], такое что:
Строка 22: Строка 22:
 
Пусть <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>\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 1scetch(a_k)</tex>. Вычтем из <tex>sketch(node)</tex> число <tex>shetch(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>, сохранятся еденицы. Применим к получившемуся побитовое ''AND'' c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</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 1scetch(a_k)</tex>. Вычтем из <tex>sketch(node)</tex> число <tex>shetch(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>, сохранятся единицы. Применим к получившемуся побитовое ''AND'' c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.
  
 
<tex>L = (1sketch(a_1)\ldots 1scetch(a_k) - 0sketch(q)\ldots 0sketch(q))</tex> ''AND'' <tex>\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>L = (1sketch(a_1)\ldots 1scetch(a_k) - 0sketch(q)\ldots 0sketch(q))</tex> ''AND'' <tex>\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>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>, тогда все еденицы сложатся в первом блоке результата, и, чтобы получить количество едениц, сдвинем его вправо.
+
Теперь надо найти количество единиц в ''L''. Умножим ''L'' на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все единицы сложатся в первом блоке результата, и, чтобы получить количество единиц, сдвинем его вправо.
  
 
===Succ(q) и pred(q)===
 
===Succ(q) и pred(q)===
Строка 37: Строка 37:
 
|statement=Среди всех ключей наибольший общий префикс с <tex>q</tex> будет иметь или <tex>a_i</tex> или <tex>a_{i+1}</tex>.
 
|statement=Среди всех ключей наибольший общий префикс с <tex>q</tex> будет иметь или <tex>a_i</tex> или <tex>a_{i+1}</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>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>a</tex> ''XOR'' <tex>q</tex> и <tex>b</tex> ''XOR'' <tex>q</tex>, найдем какой из ключей имеет наибольший общий префикс с <tex>q</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>).  
+
Предположим, что <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> равен нулю. Так как общий префикс <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>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>q<a_j</tex> - найдем <tex>succ(e)</tex>, <tex>e = p10\ldots 00</tex>. Это будет <tex>succ(q)</tex>.
  
Строка 80: Строка 80:
  
 
==Индекс наиболее значащего бита==
 
==Индекс наиболее значащего бита==
Чтобы найти в 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>. Далее найдем первый непустой блок и индекс первого еденичного бита в нем.
+
Чтобы найти в 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)''' Поиск непустых блоков.
 
'''1)''' Поиск непустых блоков.
  
'''a.''' Определим, какие блоки имеют еденицу в первом бите. Применим побитовое ''AND'' к <tex>x</tex> и константе <tex>F</tex>.  
+
'''a.''' Определим, какие блоки имеют единицу в первом бите. Применим побитовое ''AND'' к <tex>x</tex> и константе <tex>F</tex>.  
  
  
Строка 100: Строка 100:
  
  
'''b.''' Определим, содержат ли остальные биты еденицы.  
+
'''b.''' Определим, содержат ли остальные биты единицы.  
  
Вычислим <tex>x</tex> ''XOR'' <tex>t_1</tex>.
+
Вычислим <tex>x \oplus t_1</tex>.
  
  
Строка 121: Строка 121:
  
  
Вычтем от <tex>F\; t_2</tex>. Если какой-нибудь бит <tex>F</tex> обнулится, значит, соответствующий блок содержит еденицы.
+
Вычтем из <tex>F\; t_2</tex>. Если какой-нибудь бит <tex>F</tex> обнулится, значит, соответствующий блок содержит единицы.
  
  
Строка 140: Строка 140:
  
  
Чтобы найти блоки, содержащие еденицы, вычислим <tex>t_3</tex> ''XOR'' <tex>F</tex>.
+
Чтобы найти блоки, содержащие единицы, вычислим <tex>t_3 \oplus F</tex>.
  
  
Строка 159: Строка 159:
  
  
'''c.''' Первый бит в каждом блоке <tex>y = t_1</tex> ''OR'' <tex>t_4</tex> содержит еденицу, если соответствующий блок <tex>x</tex> ненулевой.
+
'''c.''' Первый бит в каждом блоке <tex>y = t_1</tex> ''OR'' <tex>t_4</tex> содержит единицу, если соответствующий блок <tex>x</tex> ненулевой.
  
  
Строка 183: Строка 183:
 
Чтобы найти <tex>sketch(y)</tex>, умножим <tex>y</tex> на <tex>m</tex> и сдвинем вправо на <tex>w</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>.
+
'''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> первого еденичного бита в найденном блоке так же как и в предыдущем пункте.
+
'''4)''' Найдем номер <tex>d</tex> первого единичного бита в найденном блоке так же как и в предыдущем пункте.
  
 
'''5)''' Индекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d</tex>.
 
'''5)''' Индекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d</tex>.

Версия 04:24, 16 июня 2014

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_2\ldots b_{r-1}[/math]. Количество существенных битов [math]r[/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]sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})[/math], но [math]a_{i+1}\leqslant q[/math]

Пусть [math]\left \{ a_1,a_2\ldots a_k\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].

Параллельное сравнение

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

[math]L = (1sketch(a_1)\ldots 1scetch(a_k) - 0sketch(q)\ldots 0sketch(q))[/math] AND [math]\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]. Теперь надо найти количество единиц в L. Умножим L на [math]\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}[/math], тогда все единицы сложатся в первом блоке результата, и, чтобы получить количество единиц, сдвинем его вправо.

Succ(q) и pred(q)

Пусть [math]sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})[/math].

Утверждение:
Среди всех ключей наибольший общий префикс с [math]q[/math] будет иметь или [math]a_i[/math] или [math]a_{i+1}[/math].
[math]\triangleright[/math]
Предположим, что [math]y[/math] имеет наибольший общий префикс с [math]q[/math]. Тогда [math]sketch(q)[/math] будет иметь больше общих битов со [math]sketch(y)[/math]. Значит, [math]sketch(y)[/math] ближе по значению к [math]sketch(q)[/math], чем [math]sketch(a_i)[/math] или [math]sketch(a_{i+1})[/math], что приводит к противоречию.
[math]\triangleleft[/math]

Сравнивая [math]a \oplus q[/math] и [math]b \oplus q[/math], найдем какой из ключей имеет наибольший общий префикс с [math]q[/math] (наименьшее значение соответствует наибольшей длине).

Предположим, что [math]p[/math] - наибольший общий префикс, а [math]y[/math] его длина, [math]a_j[/math] - ключ, имеющий наибольший общий префикс с [math]q[/math] ([math]j = i[/math] или [math]i+1[/math]).

  • если [math]q\gt a_j[/math], то [math]y + 1[/math] бит [math]q[/math] равен единице, а [math]y + 1[/math] бит [math]a_j[/math] равен нулю. Так как общий префикс [math]a_j[/math] и [math]q[/math] является наибольшим, то не существует ключа с префиксом [math]p1[/math]. Значит, [math]q[/math] больше всех ключей с префиксом меньшим либо равным [math]p[/math]. Найдем [math]pred(e)[/math], [math]e = p01\ldots 11[/math], который одновременно будет [math]равен pred(q)[/math];
  • если [math]q\lt a_j[/math] - найдем [math]succ(e)[/math], [math]e = p10\ldots 00[/math]. Это будет [math]succ(q)[/math].

Длина наибольшего общего префикса двух w-битных чисел [math]a[/math] и [math]b[/math] может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом XOR [math]a[/math] и [math]b[/math].

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

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

1) уберем все несущественные биты [math]x' = x[/math] AND [math]\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(\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}[/math];

3) применив побитовое AND, уберем лишние биты, появившиеся в результате умножения;

[math]\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}[/math] AND [math]\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]

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

Индекс наиболее значащего бита

Чтобы найти в w-битном числе [math]x[/math] индекс самого старшего бита, содержащего единицу, разделим [math]x[/math] на [math]\sqrt{w}[/math] блоков по [math]\sqrt{w}[/math] бит. [math]x = \underbrace{0101}_{\sqrt{w}}\; \underbrace{0000}_{\sqrt{w}}\; \underbrace{1000}_{\sqrt{w}}\; \underbrace{1101}_{\sqrt{w}}[/math]. Далее найдем первый непустой блок и индекс первого единичного бита в нем.

1) Поиск непустых блоков.

a. Определим, какие блоки имеют единицу в первом бите. Применим побитовое AND к [math]x[/math] и константе [math]F[/math].


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


b. Определим, содержат ли остальные биты единицы.

Вычислим [math]x \oplus t_1[/math].


[math] $$ \begin{array}{r} 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{000}\; 0\underline{101} \end{array} \end{array} $$[/math]


Вычтем из [math]F\; t_2[/math]. Если какой-нибудь бит [math]F[/math] обнулится, значит, соответствующий блок содержит единицы.


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


Чтобы найти блоки, содержащие единицы, вычислим [math]t_3 \oplus F[/math].


[math] $$ \begin{array}{r} XOR \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} $$[/math]


c. Первый бит в каждом блоке [math]y = t_1[/math] OR [math]t_4[/math] содержит единицу, если соответствующий блок [math]x[/math] ненулевой.


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


2) Найдем [math]sketch(y)[/math], чтобы сместить все нужные биты в один блок. Существенными битами в данном случае будут первые биты каждого блока, поэтому [math]b_i = \sqrt{w} - 1 + i\sqrt{w}[/math].

Будем использовать [math]m_j = w - (\sqrt{w}-1) - j\sqrt{w} +j[/math]. Тогда [math]b_i + m_j = w + (i - j)\sqrt{w} + j[/math]. Все суммы различны при [math]0\leqslant i, j \lt \sqrt{w} [/math]. Все [math]b_i + m_i = w + i[/math] возрастают, и [math](b_{\sqrt{w} - 1} + m_{\sqrt{w} - 1}) - (b_0 + m_0) = \sqrt{w} - 1[/math].

Чтобы найти [math]sketch(y)[/math], умножим [math]y[/math] на [math]m[/math] и сдвинем вправо на [math]w[/math] бит.

3) Найдем первый ненулевой блок. Для этого надо найти первую единицу в [math]sketch(y)[/math]. Как и при поиске [math]succ(sketch(q))[/math] и [math]pred(sketch(q))[/math] используем параллельное сравнение [math]sketch(y)[/math] с [math]2^0, 2^1 \ldots 2^{\sqrt{w} - 1}[/math]. В результате сравнения получим номер первого ненулевого блока [math]c[/math].

4) Найдем номер [math]d[/math] первого единичного бита в найденном блоке так же как и в предыдущем пункте.

5) Индекс наиболее значащего бита будет равен [math]c\sqrt{w}+d[/math].

Каждый шаг выполняется за [math]O(1)[/math], поэтому всего потребуется [math]O(1)[/math] времени, чтобы найти индекс.

Ссылки

M. L. Fredman and D. E. Willard. Surpassing the information theoretic barrier with fusion trees. Journal of Computer and System Sciences, 1993

MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003)

MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof. Erik Demaine (Spring 2012)

А.С. Станкевич. Дополнительные главы алгоритмов, лекция 6

Wikipedia — Fusion tree