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], поскольку на одном уровне могут быть несколько ветвящихся вершин).
В 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_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(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]succ(y)[/math] и
[math]pred(y)[/math] по
[math]sketch(y)[/math] не являются
[math]succ[/math] или
[math]pred[/math] по
[math]y[/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]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].
Длина наибольшего общего префикса двух [math]w[/math]-битных чисел [math]a[/math] и [math]b[/math] может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом [math]\oplus a[/math] и [math]b[/math].
Сравнение значений sketch двух чисел
Определим [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] мы можем получить с помощью цикла де Брёйна
Вычисление sketch(x)
Чтобы найти [math]sketch[/math] за константное время, будем вычислять [math]supersketch(x)[/math], имеющий все существенные биты в нужном порядке, но содержащий лишние нули. Хотя [math]supersketch[/math] содержит лишние нули, мы сможем вычислять его быстрее, чем обычный [math]sketch[/math], потому что нам не придется каждый раз идти по всем битам числа, выбирая стоящие на нужных нам местах. Будем использовать [math]supersketch[/math] вместо [math]sketch[/math] — это никак не повлияет на сравнение, поскольку добавленные биты равны нулю и стоят на одних и тех же местах для всех [math]sketch[/math]
- Уберем все несущественные биты [math]x' = x \& \displaystyle \sum_{i=0}^{r-1}2^{b_i}[/math].
- Умножением на некоторое заранее вычисленное число [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].
- Применив побитовое [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].
- Сделаем сдвиг вправо на [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], такая что:
- все [math]b_i + m_j[/math] различны, для [math]0\leqslant i,j \leqslant r-1[/math]
- [math]b_0 + m_0\leqslant b_1 + m_1\leqslant \ldots \leqslant b_{r-1} + m_{r-1}[/math]
- [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]
Индекс наиболее значащего бита
Чтобы найти в [math]w[/math]-битном числе [math]x[/math] индекс самого старшего бита, содержащего единицу (это понадобится в дальнейшем, для нахождения [math]sketch(y)[/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]. Далее найдем первый непустой блок и индекс первого единичного бита в нем.
- Поиск непустых блоков.
- Определим, какие блоки имеют единицу в первом бите. Применим побитовое [math]\&[/math] к [math]x[/math] и константе [math] F [/math]: [math]
$$
\begin{array}{r}
\&
\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]
- Определим, содержат ли остальные биты единицы.
- Вычислим [math]x \oplus t_1[/math]: [math]
$$
\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}
$$[/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}
\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}
$$[/math]
- Первый бит в каждом блоке [math]y = t_1 \lor t_4[/math] содержит единицу, если соответствующий блок [math]x[/math] ненулевой: [math]$$
\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}
$$[/math]
- Найдем [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] бит.
- Найдем первый ненулевой блок. Для этого надо найти первую единицу в [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].
- Найдем номер [math]d[/math] первого единичного бита в найденном блоке так же как и в предыдущем пункте.
- Индекс наиболее значащего бита будет равен [math]c\sqrt{w}+d[/math].
Каждый шаг выполняется за [math]O(1)[/math], поэтому всего потребуется [math]O(1)[/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] с периодом 2, 4, 8, 16:
- 01 (содержит подпоследовательности 0 и 1)
- 0011 (содержит подпоследовательности 00, 01, 11, 10)
- 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
- 0000100110101111
Получение индекса по значению степени двойки
Возьмем цикл де Брёйна для [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 \ll i)\gg(n-k)[/math]), тогда получившееся число — [math]i[/math]-ая подстрока длины [math]k[/math] данного цикла де Брёйна. Эту перестановку опозначим за [math]p[/math] и тогда применив ее к [math](2^i\cdot x) \gg (n-k))[/math] получим [math]i[/math]: [math]p[/math] в данном случае такое, что [math]k[/math] подряд идущих бит равны значению, на сколько мы сдвинули, на какой позиции стоит вектор длины [math]k[/math].
См. Также
Источники информации
