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,^[1] it has found application in several contexts.^[2]^[3] 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.

^ Cite error: The named reference GGV03 was invoked but never defined (see the help page).
^ Cite error: The named reference FGM09 was invoked but never defined (see the help page).
^ Cite error: The named reference Navarro12 was invoked but never defined (see the help page).

[GGV03-1] Cite error: The named reference GGV03 was invoked but never defined (see the help page).

[FGM09-2] Cite error: The named reference FGM09 was invoked but never defined (see the help page).

[Navarro12-3] Cite error: The named reference Navarro12 was invoked but never defined (see the help page).

[1]

[2]

[3]