Вейвлет-дерево

Вейвлет-дерево на струне «абракадабра». В каждом узле символы строки проецируются на два раздела алфавита, а битовый вектор указывает, к какому разделу принадлежит каждый символ. Обратите внимание, что сохраняются только битовые векторы; строки в узлах предназначены только для иллюстративных целей.

Wavelet Дерево представляет собой сжатая структуру данных для хранения строк в сжатом пространстве. Она обобщает и операции , определенные на битвекторы до произвольных алфавитов.${\displaystyle \mathbf {rank} _{q}}$${\displaystyle \mathbf {select} _{q}}$

Первоначально введенный для представления сжатых суффиксов массивов , ^[1] он нашел применение в различных контекстах. ^{[2] [3]} Дерево определяется путем рекурсивного разбиения алфавита на пары подмножеств; листья соответствуют отдельным символам алфавита, и в каждом узле битовый вектор хранит, принадлежит ли символ строки одному или другому подмножеству.

Название происходит от аналогии с вейвлет-преобразованием для сигналов, которое рекурсивно разлагает сигнал на низкочастотные и высокочастотные компоненты.

Свойства [ править ]

Позвольте быть конечным алфавитом с . Используя сжатые словари в узлах, можно сохранить строку , где - эмпирическая энтропия нулевого порядка .${\displaystyle \Sigma }$${\displaystyle \sigma =|\Sigma |}$${\displaystyle s\in \Sigma ^{*}}$${\displaystyle nH_{0}(s)+o(|s|\log \sigma )}$${\displaystyle H_{0}(s)}$${\displaystyle s}$

Если дерево сбалансировано, операции , и могут быть поддержаны в время.${\displaystyle \mathbf {access} }$${\displaystyle \mathbf {rank} _{q}}$${\displaystyle \mathbf {select} _{q}}$${\displaystyle O(\log \sigma )}$

Операция доступа [ править ]

Вейвлет-дерево содержит растровое представление строки. Если мы знаем набор алфавитов, то точную строку можно вывести, отслеживая биты вниз по дереву. Чтобы найти букву в i- ^й позиции в строке: -

Если i- ^й элемент в корне равен 0, мы переходим к левому дочернему элементу, иначе мы переходим к правому дочернему элементу. Теперь наш индекс в дочернем узле - это ранг соответствующего бита в родительском узле. Этот ранг можно вычислить за O (1) с помощью кратких словарей . Наряду с переходом к дочернему элементу мы также уточняем наш алфавит до соответствующего подмножества. Эти шаги повторяются до тех пор, пока мы не дойдем до листа, где у нас останется только одна буква в нашем алфавите, которую мы искали. Таким образом, для сбалансированного дерева любой S [i] в ​​строке S может быть доступен за ^[3] раз.${\displaystyle O(\log \sigma )}$

Расширения [ править ]

В литературе было представлено несколько расширений базовой структуры. Чтобы уменьшить высоту дерева, можно использовать множественные узлы вместо двоичных. ^[2] Структуру данных можно сделать динамической, поддерживая вставку и удаление в произвольных точках строки; эта функция позволяет реализовать динамические FM-индексы . ^[4] Это может быть дополнительно обобщенно, позволяя операции обновления , чтобы изменить лежащий в основе алфавита: Вейвлет TRIE ^[5] эксплуатирует TRIE структуру на алфавите строк , чтобы позволить динамические изменения дерева.

Дальнейшее чтение [ править ]

• Вейвлет-деревья . Сообщение в блоге, описывающее построение вейвлет-дерева с примерами.

Ссылки [ править ]

Внешние ссылки [ править ]

• СМИ, связанные с деревом вейвлетов на Викискладе?