en>Michael Hardy at 03:42, 3 June 2012

2012-06-03T03:42:22Z

New page

[[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>nH_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.

== 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, Compressed Indexes for
dynamic text collections, ''ACM Transactions on Algorithms'', 3(2), 2007
</ref>
<ref name="GO12">

R. Grossi and G. Ottaviano, [http://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>

[[Category:Trees (data structures)]]
[[Category:Data structures]]
[[Category:String data structures]]

Sorting identity - Revision history

en>Michael Hardy at 03:42, 3 June 2012