Вейвлет деревья

[GCU]

Почему приведенная реализация Rank1 имеет логарифмическую сложность? На вид линейная, явный же цикл.

[uvelichitel]

Да, вы правы. Сформулировано неточно. Если стараться быть предельно точным то сложность bits.OnesCount64() — логарифмическая, приведенной реализации Rank1 — n*log(n), алгоритма в целом Access() — log(мощность словаря)*n*log(n). bits.OnesCount64() — самая тяжелая операция, что и вызвало ошибку в оценке.Сейчас попробую поправить.

[uvelichitel]

И если постараться еще точнее, то Rank() линеен к длине bitmap, а эта длина логарифмически снижается от длины последовательности к листьям дерева.

[avdx]

В чем смысл то? Если классическим образом каждый символ кодировать таким же количеством бит, сколько уровней в дереве, по объему памяти получится то же самое, а все операции будут за O(1).

[uvelichitel]

А что значит «кодировать классическим образом»? Любая кодировка для работы операций Track() Access() то есть доступа в обе стороны за гарантированное время требует либо два ассоциативных массива(прямого и обратного индекса) либо четко оределенных процедур кодирования/декодирования. Вейвлет дерево и есть вариант кодировки достаточно компактный, быстрый и элегантный.

[avdx]

А, тут смысл именно в Track(). Как то не обратил на это внимание — прочитал по диагонали.