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

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

В Вейвлет-дерево это лаконичная структура данных для хранения строк в сжатом пространстве. Он обобщает ${\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)+o(|s|\log \sigma )}$, где ${\displaystyle H_{0}(s)}$ это порядок-0 эмпирическая энтропия из ${\displaystyle s}$.

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

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

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

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

Расширения

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

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

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

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

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

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

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