Изменения

Сначала найдем <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>, сохранятся еденицы. Применим к получившемуся побитовое ''<tex>AND'' </tex> 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>

Теперь надо найти количество едениц в ''L''. Умножим ''L '' на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все еденицы сложатся в первом блоке результата, и, чтобы получить количество едениц, сдвинем его вправо.

Пусть <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>. Сравнивая ''<tex>a''\;XOR''\;q'' </tex> и ''<tex>b''\;XOR''\;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>q>a_j''</tex>, то ''<tex>y + 1'' </tex> бит ''<tex>q'' </tex> равен еденице, а ''<tex>y + 1'' </tex> бит ''<tex>a_j'' </tex> равен 0. Так как общий префикс ''<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>.

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

Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</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>;

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

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

a. Определим какие блоки имеют еденицу в первом бите. Применим побитовое AND к ''x'' и константой ''F''

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

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

c). Первый бит в каждом блоке <tex>y = t_1\; OR \;t_4</tex> содержит еденицу, если соответствующий блок ''x'' ненулевой.

4) найдем номер <tex>d </tex> первого еденичного бита в найденном блоке так же как и в предыдущем пункте.