Дерево вейвлетов

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

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

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

Характеристики

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

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

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

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

Algorithm access  Input:    - The position i in the string of which we want to know the letter, starting at 1.    - The top node W of the wavelet tree that represents the string  Output: The letter at position i

    if W.isLeafNode return W.letter    if W.bitvector[i] = 0 return access(i - rank(W.bitvector, i), W.left)    else return access(rank(W.bitvector, i), W.right)

« ←» означает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого изменяется на значение элемента .
« return » завершает алгоритм и выводит следующее значение.

При этом ранг должности $i$ в битовом векторе $b$ это количество единиц, которые появляются в первом $i$ позиции $b$ . Поскольку ранг можно вычислить за O(1) с помощью кратких словарей , любой S[i] в строке S можно получить в $O(\log \sigma )$ ^[3] время, пока дерево сбалансировано.

Расширения

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

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

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

Ссылки

^ Р. Гросси, А. Гупта и Дж. С. Виттер, Текстовые индексы высокого порядка с энтропийным сжатием , Труды 14-го ежегодного симпозиума SIAM/ACM по дискретным алгоритмам (SODA) , январь 2003 г., 841-850.
^ Jump up to: ^а ^б П. Феррагина, Р. Джанкарло, Дж. Манзини, Мириады достоинств вейвлет-деревьев , Информация и вычисления , том 207, выпуск 8, август 2009 г., страницы 849-866
^ Jump up to: ^а ^б Дж. Наварро, Деревья вейвлетов для всех , Материалы 23-го ежегодного симпозиума по комбинаторному сопоставлению шаблонов (CPM) , 2012 г.
^ Х.-Л. Чан, В.-К. Достопочтенный, Т.-В. Лам и К. Садакане, Сжатые индексы для коллекций динамического текста , Транзакции ACM в алгоритмах , 3 (2), 2007 г.
^ Р. Гросси и Дж. Оттавиано, Вейвлет-три: поддержание индексированной последовательности строк в сжатом пространстве , В материалах 31-го симпозиума по принципам систем баз данных (PODS) , 2012 г.

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

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

[GGV03-1] Р. Гросси, А. Гупта и Дж. С. Виттер, Текстовые индексы высокого порядка с энтропийным сжатием , Труды 14-го ежегодного симпозиума SIAM/ACM по дискретным алгоритмам (SODA) , январь 2003 г., 841-850.

[FGM09-2] Jump up to: ^а ^б П. Феррагина, Р. Джанкарло, Дж. Манзини, Мириады достоинств вейвлет-деревьев , Информация и вычисления , том 207, выпуск 8, август 2009 г., страницы 849-866

[Navarro12-3] Jump up to: ^а ^б Дж. Наварро, Деревья вейвлетов для всех , Материалы 23-го ежегодного симпозиума по комбинаторному сопоставлению шаблонов (CPM) , 2012 г.

[CHLK07-4] Х.-Л. Чан, В.-К. Достопочтенный, Т.-В. Лам и К. Садакане, Сжатые индексы для коллекций динамического текста , Транзакции ACM в алгоритмах , 3 (2), 2007 г.

[GO12-5] Р. Гросси и Дж. Оттавиано, Вейвлет-три: поддержание индексированной последовательности строк в сжатом пространстве , В материалах 31-го симпозиума по принципам систем баз данных (PODS) , 2012 г.

[1]

[2]

[3]

[4]

[5]