Изменения

Пусть <tex>\left \{ a_1,a_2\ldots a_k\right \}</tex> - множество ключей узла, отсортированных по возрастанию, <tex>q</tex> - ключ искомой вершины, <tex>l</tex> - количество бит в <tex>sketch(q)</tex>. ===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>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.Так как ключи отсортированны по возрастанию, получив номер наиболее значащего бита, можно найти <tex>succ(sketch(q))</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'' (наименьшнее значение соответствует наибольшей длине). Предположим, что ''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) уберем все несущественные биты <tex>x' = x</tex> AND <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'*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) применив побитовое AND уберем лишние биты, появившиеся в результате умножения; <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>; 4) сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.{{Утверждение|id= |author=|about=|statement=Дана последовательность из r чисел <tex>b_0<b_1<\ldots <b_{r-1}</tex>. Тогда существует последовательность <tex>m_0<m_1\ldots <m_{r-1}</tex>, такая что: 1) все <tex>b_i + m_j</tex> различны, для <tex>0\leqslant i,j \leqslant r-1</tex>; 2) <tex>b_1 + m_2\leqslant b_2 + m_2\leqslant \ldots \leqslant b_{r-1} + m_{r-1}</tex>; 3) <tex>(b_{r-1} + m_{r-1}) - (b_0 + m_0) \leqslant r^4</tex>.|proof=Выберем некоторые, таким образом, чтобы. Предположим, что мы выбрали. 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. }}Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить 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'' на <tex>\sqrt{w}</tex> блоков по <tex>\sqrt{w}</tex> бит.<tex>x = \underbrace{0101}_{\sqrt{w}}\; \underbrace{0000}_{\sqrt{w}}\; \underbrace{1000}_{\sqrt{w}}\; \underbrace{1101}_{\sqrt{w}}</tex>. Далее найдем первый непустой блок и индекс первого еденичного бита в нем. 1)Поиск непустых блоков. a. Определим какие блоки имеют еденицу в первом бите. Применим побитовое AND к ''x'' и константой ''F'' <tex> $$\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}$$</tex> b. Определим, содержат ли остальные биты еденицы.  Вычислим <tex>x\; XOR \; t_1</tex>. <tex> $$\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}$$</tex> Вычтем от <tex>F\; t_2</tex>. Если какой-нибудь бит ''F'' обнулится, значит, соответствующий блок содержит еденицы. <tex> $$\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}$$</tex> Чтобы найти блоки, содержащие еденицы, вычислим <tex>t_3\; XOR \; F</tex>. <tex> $$\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}$$</tex> Первый бит в каждом блоке <tex>y = t_1\; OR \;t_4</tex> содержит еденицу, если соответствующий блок ''x'' ненулевой. <tex>$$\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}$$</tex>