1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Файл: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>sketch(a_i) = 00, sketch(q) = 00, sketch(a_{i+1}) = 01, \\ a_i = 0000, a_{i+1} = 0010, q = 0101</tex> ]]
Рассмотрим ключи. Порядок для них по <tex>sketch</tex> совпадает с их порядком. Тогда для некоторых <tex>a_i</tex> и <tex>a_{i+1}</tex>: <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>, в таком случае <tex>a_i</tex> и <tex>aa_{i+1}</tex> его <tex>succ</tex> и <tex>pred</tex> по <tex>sketch</tex>. В таком случае Тогда среди них есть реальный настоящий (не по <tex>sketch</tex>) <tex>succ</tex> или <tex>pred</tex> по доказанному, а понять, чем именно он является, это мы можем просто сделав сравнение с <tex>q</tex>.
===Поиск реального следующего и предыдущего===
Теперь надо найти количество единиц в <tex>L</tex>. Умножим <tex>L</tex> на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все единицы сложатся в первом блоке результата, и, чтобы получить количество единиц, сдвинем его вправо на <tex>(k-1)\cdot(l + 1)</tex> бит. В таком случае мы получим некоторое <tex>2^i</tex>, где <tex>i</tex> является реальным <tex>pred(x)</tex>, а <tex>i</tex> мы можем получить с помощью цикла де Брёйна
=== Индекс наиболее старшего бита с помощью цикла де Брёйна ===
'''Последовательность де Брёйна''' {{---}} последовательность <math>a_1,\;\ldots,\;a_t</math>, элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество <math>\{0,\;1,\;\ldots,\;k-1\}</math>), и все подпоследовательности <math>a_{i+1},\;\ldots,\;a_{i+n}</math> заданной длины <math>n</math> различны.
==== Примеры ====
Примеры циклов де Брёйна для <math>k=2</math> с периодом <tex>2, 4, 8, 16</tex>:* <tex>01 </tex> (содержит подпоследовательности <tex>0 </tex> и <tex>1</tex>)* <tex>0011 </tex> (содержит подпоследовательности <tex>00, 01, 11, 10</tex>)* <tex>00010111 (000, 001, 010, 101, 011, 111, 110, 100)</tex>* <tex>0000100110101111</tex>
==== Получение индекса по значению степени двойки ====
Возьмем цикл де Брёйна для <tex>n</tex> <tex>(i = 0\ldots n-1)</tex> и запишем его как число <tex>b</tex> (для <tex>8</tex> цикл де Брёна равен <tex>00010111</tex>, а значение <tex>b = 23</tex>). Умножим это число на <tex>2^i</tex>, сдвинем его влево на <tex>i</tex>, а затем обратно вправо на <tex>n-k</tex> (<tex>k</tex> такое, что <tex>n=2^k</tex>). <tex>(b \ll texttt{<<} i)\ggtexttt{>>}(n-k)</tex>), тогда получившееся число {{---}} <tex>i</tex>-ая подстрока длины <tex>k</tex> данного цикла де Брёйна. Эту перестановку опозначим за <tex>p</tex> и тогда применив ее к <tex>(2^i\cdot x) \gg texttt{>>} (n-k))</tex> получим <tex>i</tex>: <tex>p</tex> в данном случае такое, что <tex>k</tex> подряд идущих бит равны значению, на сколько мы сдвинули, на какой позиции стоит вектор длины <tex>k</tex>.
==Вычисление sketch(x)==
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
[[Категория:Структуры данных]]
