234
правки
Изменения
Нет описания правки
==Поиск вершины==
Пусть <tex>\left \{ a_1,a_2\ldots a_k\right \}</tex> - множество ключей узла, отсортированных по возрастанию, <tex>q</tex> - ключ искомой вершины, <tex>l</tex> - количество бит в <tex>sketch(q)</tex>.
===SuccПараллельное сравнение===Сначала найдем succ(sketch(q)) и pred(sketch(q))===. Определим <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) * \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>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>. Так как ключи отсортированны по возрастанию, получив номер наиболее значащего бита, можно Теперь надо найти количество едениц в L. Умножим L на <tex>succ(sketch(q))\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>. Среди всех ключей наибольший общий префикс с <tex>q</tex> будет иметь или <tex>a_i</tex> или <tex>a_{i+1}</tex>. Сравнивая ''a''XOR''q'' и ''b''XOR''q'', найдем какой из ключей имеет наибольший общий префикс с ''q'' (наименьшнее значение соответствует наибольшей длине).
$$</tex>
c)Первый бит в каждом блоке <tex>y = t_1\; OR \;t_4</tex> содержит еденицу, если соответствующий блок ''x'' ненулевой.
<tex>$$
\end{array}
$$</tex>
2) найдем sketch(y), чтобы сместить все нужные биты в один блок. Существенными битами в данном случае будут первые биты каждого блока, поэтому <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>. Чтобы найти sketch(y), умножим y на m и сдвинем вправо на w бит.
3)Найдем первый ненулевой блок. Для этого надо найти первую еденицу в sketch(y). Как и при поиске succ(sketch(q)) и pred(sketch(q)) используем параллельное сравнение sketch(y) с <tex>2^0, 2^1 \ldots 2^{\sqrt{w} - 1}</tex>. В результате сравнения получим номер первого ненулевого блока <tex>c</tex>.
4) найдем номер d первого еденичного бита в найденном блоке так же как и в предыдущем пункте.
5) инедекс наиболее значащего бита будет равен <tex>c\sqrt{w}+d</tex>.
Каждый шаг выполняется за <tex>O(1)</tex>, поэтому всего потребуется <tex>O(1)</tex> времени, чтобы найти индекс.
