Fusion tree — дерево поиска, позволяющее хранить [math]n[/math] [math]w[/math]-битных положительных чисел, используя [math]O(n)[/math] памяти, и выполнять операции поиска за время [math]O(\log_{w} n)[/math].
Структура
Fusion tree — это B-дерево, такое что:
- у всех вершин, кроме листьев, [math]B = w^{1/5}[/math] детей;
- время, за которое определяется в каком поддереве находится вершина, равно [math]O(1)[/math].
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Рассмотрим цифровой бор из ключей узла дерева. Всего [math]B - 1[/math] ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера [math]b_1, b_2\ldots b_r[/math]. Количество существенных битов [math]r[/math] не больше чем [math]B - 1[/math].
В Fusion tree вместо ключа [math]x[/math] хранится [math]Sketch(x)[/math] - последовательность битов [math]x_{b_r}\ldots x_{b_1}[/math]. [math]Sketch[/math] сохраняет порядок, то есть [math]sketch(x) \lt sketch(y)[/math], если [math]x \lt y[/math].
Поиск вершины
Пусть [math]\left \{ a_1,a_2\ldots a_k\right \}[/math] - множество ключей узла, отсортированных по возрастанию, [math]q[/math] - ключ искомой вершины, [math]l[/math] - количество бит в [math]sketch(q)[/math].
Succ(sketch(q)) и pred(sketch(q))
Определим [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) * \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](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]. Так как ключи отсортированны по возрастанию, получив номер наиболее значащего бита, можно найти [math]succ(sketch(q))[/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]. Сравнивая aXORq и bXORq, найдем какой из ключей имеет наибольший общий префикс с q (наименьшнее значение соответствует наибольшей длине).
Предположим, что p - наибольший общий перфикс, а y его длина, a_j - ключ, имеющий наибольший общий префикс с q (j = i или i+1).
- если q>a_j, то y + 1 бит q равен еденице, а y + 1 бит a_j равен 0. Так как общий префикс a_j и q является наибольшим, то не существет ключа с префиксом p1.Значит, q больше всех ключей с префиксом меньшим либо равным p. Найдем pred e = p01\ldots 11, который одновременно будет равен pred(q);
- если < - найдем succ e = p10\ldots 00. Это будет succ(q).
Длина наибольшего общего префикса двух w-битных чисел a и b может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом XOR a и b.
Вычисление sketch(x)
Чтобы найти sketch за константное время, будем вычислять sketch(x), имеющий все существенные биты в нужном порядке, но содержащий лишние нули.
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'*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] бит.
| Утверждение: |
Дана последовательность из r чисел [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_1 + m_2\leqslant b_2 + m_2\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] |
|
Выберем некоторые, таким образом, чтобы. Предположим, что мы выбрали. mt' != mi' + bj - bk A i,j,k. В противном случае . Всего t*r*r <= r^3 недопустимых значений для mt', поэтому всегда можно найти хотя бы одно значение.
Чтобы получить mi, выбираем каждый раз наименьшие mi' и прибавляем подходящее число кратное r^3, такое что mi+ci<mi+l+Ci+l<=mi+ci+r3. |
| [math]\triangleleft[/math] |
Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить 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 на [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 к x и константой F
[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\; XOR \; 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]. Если какой-нибудь бит F обнулится, значит, соответствующий блок содержит еденицы.
[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\; XOR \; 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]
Первый бит в каждом блоке [math]y = t_1\; OR \;t_4[/math] содержит еденицу, если соответствующий блок x ненулевой.
[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]
