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

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

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

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

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

Свойства

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

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

Операция доступа

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

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

Расширения

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

дальнейшее чтение

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

использованная литература

внешние ссылки

• СМИ, связанные с Вейвлет-дерево в Wikimedia Commons