Wavelet Tree

The wavelet tree is a succinct data structure to store strings in compressed space. It generalizes the \mathbf{rank}_q and \mathbf{select}_q operations defined on bitvectors to arbitrary alphabets. Originally introduced to represent compressed suffix arrays, it has found application in several contexts. 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 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.

The wavelet tree is a succinct data structure to store strings in compressed space. It generalizes the \mathbf{rank}_q and \mathbf{select}_q operations defined on bitvectors to arbitrary alphabets. Originally introduced to represent compressed suffix arrays, it has found application in several contexts. 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 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. Let \Sigma be a finite alphabet with \sigma= . By using succinct dictionaries in the nodes, a string s \in \Sigma^* can be stored in H_0(s) + o( \log \sigma) , where H_0(s) is the order-0 empirical entropy of s . If the tree is balanced, the operations \mathbf{access} , \mathbf{rank}_q , and \mathbf{select}_q can be supported in O(\log \sigma) time. if W.bitvector[i] = 0 return access(i - rank(W.bitvector, i), W.left) else return access(rank(W.bitvector, i), W.right) In this context, the rank of a position i in a bitvector b is the number of ones that appear in the first i positions of b . Because the rank can be calculated in O(1) by using succinct dictionaries, any S[i] in string S can be accessed in O(\log \sigma) time, as long as the tree is balanced. ==External links==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1356198171 under CC BY-SA 4.0; modifications have been made.