47
правок
Изменения
м
Тире заменено шаблоном
[[Файл:Fusion.png||500x400px|center|визуализация функции sketch]]
В Fusion tree вместе с ключом <tex>x</tex> хранится <tex>sketch(x)</tex> {{- --}} последовательность битов <tex>x_{b_{r-1}}\ldots x_{b_0}</tex>.
{{Утверждение
|id=sketch.
==Поиск вершины==
[[Файл:FusionTree.png|400x400px|thumb|right|пример случая, когда <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>, но <tex>a_{i+1}\leqslant q</tex>]]
Пусть <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>, сохранятся единицы. Применим к получившемуся побитовое ''AND'' c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.
Сравнивая <tex>a \oplus q</tex> и <tex>b \oplus 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> равен нулю. Так как общий префикс <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''-битных чисел <tex>a</tex> и <tex>b</tex> может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом ''XOR'' <tex>a</tex> и <tex>b</tex>.
