View source for Wavelet Tree

[[File:Wavelet tree.png|frame|A wavelet tree on the string "abracadabra". At each node the symbols of the string are projected onto two partitions of the alphabet, and a bitvector denotes to which partition each symbol belongs. Note that only the bitvectors are stored; the strings in the nodes are only for illustratory purposes.]]

The '''Wavelet Tree''' is a [[succinct data structure]] to store strings in compressed space. It generalizes the <math>\mathbf{rank}_q</math> and <math>\mathbf{select}_q</math> operations defined on [[Succinct data structure#Succinct dictionaries|bitvectors]] to arbitrary alphabets.

Originally introduced to represent [[compressed suffix array]]s,<ref name="GGV03"/> it has found application in several contexts.<ref name="FGM09"/><ref name="Navarro12"/> The tree is defined by recursively partitioning the alphabet into pairs of subsets; the leaves correspond to individual symbols of the alphabet, and at each node a [[Succinct data structure#Succinct dictionaries|bitvector]] stores whether a symbol of the string belongs to one subset or the other.

The name derives from an analogy with the [[wavelet transform]] for signals, which recursively decomposes a signal into low-frequency and high-frequency components.

== Properties ==
Let <math>\Sigma</math> be a finite alphabet with <math>\sigma={|\Sigma|}</math>. By using [[Succinct data structure#Succinct dictionaries|succinct dictionaries]] in the nodes, a string <math>s \in \Sigma^*</math> can be stored in <math>{|s|}H_0(s) + o({|s|}\log \sigma)</math>, where <math>H_0(s)</math> is the order-0 [[Entropy (information theory)|empirical entropy]] of <math>s</math>.

If the tree is balanced, the operations <math>\mathbf{access}</math>, <math>\mathbf{rank}_q</math>, and <math>\mathbf{select}_q</math> can be supported in <math>O(\log \sigma)</math> time.

=== Access operation ===

A wavelet tree contains a bitmap representation of a string. If we know the alphabet set, then the exact string can be inferred by tracking bits down the tree. To find the letter at i<sup>th</sup> position in the string :- 

{{algorithm-begin|name=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'')
{{algorithm-end}}

In this context, the rank of a position <math>i</math> in a bitvector <math>b</math> is the number of ones that appear in the first <math>i</math> positions of <math>b</math>. Because the rank can be calculated in O(1) by using [[Succinct data structure#Succinct dictionaries|succinct dictionaries]], any S[i] in string S can be accessed in <math>O(\log \sigma)</math> <ref name="Navarro12" /> time, as long as the tree is balanced.

== Extensions ==
Several extensions to the basic structure have been presented in the literature. To reduce the height of the tree, multiary nodes can be used instead of binary.<ref name="FGM09" /> The data structure can be made dynamic, supporting insertions and deletions at arbitrary points of the string; this feature enables the implementation of dynamic [[FM-index]]es.<ref name="CHLK07"/> This can be further generalized, allowing the update operations to change the underlying alphabet: the Wavelet Trie<ref name="GO12"/> exploits the [[trie]] structure on an alphabet of strings to enable dynamic tree modifications.

== Further reading ==
* [http://www.alexbowe.com/wavelet-trees Wavelet Trees]. A blog post describing the construction of a wavelet tree, with examples.

== References ==
<references>
<ref name="GGV03">
R. Grossi, A. Gupta, and J. S. Vitter, [http://www.di.unipi.it/~grossi/PAPERS/sodaconf03FINAL-LATEST.pdf High-order entropy-compressed text indexes], ''Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA)'', January 2003, 841-850.
</ref>
<ref name="FGM09">
P. Ferragina, R. Giancarlo, G. Manzini, [http://www.ittc.ku.edu/~jsv/Papers/FGM09.wavelettrees.pdf The myriad virtues of Wavelet Trees], ''Information and Computation'', Volume 207, Issue 8, August 2009, Pages 849-866
</ref>
<ref name="Navarro12">
G. Navarro, [http://www.dcc.uchile.cl/~gnavarro/ps/cpm12.pdf Wavelet Trees for All], ''Proceedings of 23rd Annual Symposium on Combinatorial Pattern Matching (CPM)'', 2012
</ref>
<ref name="CHLK07">
H.-L. Chan, W.-K. Hon, T.-W. Lam, and K. Sadakane, [http://dl.acm.org/citation.cfm?id=1240244 Compressed Indexes for dynamic text collections], ''ACM Transactions on Algorithms'', 3(2), 2007
</ref>
<ref name="GO12">

R. Grossi and G. Ottaviano, [https://arxiv.org/abs/1204.3581 The Wavelet Trie: maintaining an indexed sequence of strings in compressed space], ''In Proceedings of the 31st Symposium on the Principles of Database Systems (PODS)'', 2012
</ref>
</references>

==External links==
*{{Commonscatinline}}

[[Category:Trees (data structures)]]
[[Category:Succinct data structure]]
[[Category:String data structures]]