Comments 6
Почему приведенная реализация Rank1 имеет логарифмическую сложность? На вид линейная, явный же цикл.
Да, вы правы. Сформулировано неточно. Если стараться быть предельно точным то сложность bits.OnesCount64() — логарифмическая, приведенной реализации Rank1 — n*log(n), алгоритма в целом Access() — log(мощность словаря)*n*log(n). bits.OnesCount64() — самая тяжелая операция, что и вызвало ошибку в оценке.Сейчас попробую поправить.
В чем смысл то? Если классическим образом каждый символ кодировать таким же количеством бит, сколько уровней в дереве, по объему памяти получится то же самое, а все операции будут за O(1).
А что значит «кодировать классическим образом»? Любая кодировка для работы операций Track() Access() то есть доступа в обе стороны за гарантированное время требует либо два ассоциативных массива(прямого и обратного индекса) либо четко оределенных процедур кодирования/декодирования. Вейвлет дерево и есть вариант кодировки достаточно компактный, быстрый и элегантный.
А, тут смысл именно в Track(). Как то не обратил на это внимание — прочитал по диагонали.
Sign up to leave a comment.
Вейвлет деревья