317
правок
Изменения
Нет описания правки
* у всех вершин, кроме листьев, <tex>B = w^{1/5}</tex> детей,
* время, за которое определяется, в каком поддереве находится вершина, равно <tex>O(1)</tex>.
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Построим [[:Сверхбыстрый_цифровой_бор|цифровой бор ]] из ключей узла дерева. Всего <tex>B - 1</tex> ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера <tex>b_0, b_1\ldots b_{r-1}</tex>. Количество существенных битов <tex>r</tex> равно <tex>B - 1</tex> (все ребра на уровне детей ветвящейся вершины являются существенными битами).
[[Файл:Fusion.png||500x400px|center|визуализация функции sketch]]
Пусть <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 </tex>&<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>q<a_j</tex> {{---}} найдем <tex>succ(e)</tex>, <tex>e = p10\ldots 00</tex>. Это будет <tex>succ(q)</tex>.
Длина наибольшего общего префикса двух ''w''-битных чисел <tex>a</tex> и <tex>b</tex> может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом \oplus <tex>\oplus a</tex> и <tex>b</tex>.
==Вычисление sketch(x)==
Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.
1) уберем все несущественные биты <tex>x' = x \land </tex>&<tex> \displaystyle \sum_{i=0}^{r-1}2^{b_i}</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>,
3) применив побитовое <tex>\land</tex>&, уберем лишние биты, появившиеся в результате умножения,
<tex>\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j} \land </tex>&<tex> \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>,
4) сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.
'''1)''' Поиск непустых блоков.
'''a.''' Определим, какие блоки имеют единицу в первом бите. Применим побитовое <tex>\land</tex> & к <tex>x</tex> и константе <tex>F</tex>.
<tex>$$
\begin{array}{r}
\begin{array}{r}
x = 0101\; 0000\; 1000\; 1101\\
Граф де Брёйна широко применяется в биоинформатике в задачах сборки генома.
==См. Также==
*[[:Сверхбыстрый_цифровой_бор|Сверхбыстрый цифровой бор]]
*[[:2-3_дерево|2-3 дерево]]
== Источники информации ==
