SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
Wavelet Trees (WT)

This group contains data structures for wavelet trees. More...

Classes

class  sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >
 A wavelet tree class for integer sequences. More...
 
class  sdsl::wt_ap< t_wt_byte, t_wt_int >
 A wavelet tree class for integer sequences. More...
 
class  sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >
 An EPR-dictionary based wavelet. More...
 
class  sdsl::wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero >
 A wavelet tree class for integer sequences. More...
 
class  sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >
 A wavelet tree class for integer sequences. More...
 
class  sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >
 A wavelet tree class for integer sequences. More...
 
class  sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >
 A prefix code-shaped wavelet. More...
 
class  sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >
 A Wavelet Tree class for byte sequences. More...
 

Typedefs

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select_one = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using sdsl::wt_blcd = wt_pc<balanced_shape, t_bitvector, t_rank, t_select_one, t_select_zero, t_tree_strat>
 A balanced wavelet tree.
 
template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using sdsl::wt_huff = wt_pc<huff_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat>
 A Huffman-shaped wavelet tree.
 
template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using sdsl::wt_hutu = wt_pc<hutu_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat>
 A Hu-Tucker-shaped wavelet tree.
 

Detailed Description

This group contains data structures for wavelet trees.

The following methods are supported:

Typedef Documentation

◆ wt_blcd

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select_one = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using sdsl::wt_blcd = wt_pc<balanced_shape, t_bitvector, t_rank, t_select_one, t_select_zero, t_tree_strat>

A balanced wavelet tree.

Space complexity
$\Order{n\log|\Sigma| + 2|\Sigma|\log n}$ bits, where $n$ is the size of the vector the wavelet tree was build for.
Template Parameters
t_bitvectorUnderlying bitvector structure.
t_rankType of the support structure for rank on pattern 1.
t_selectType of the support structure for select on pattern 1.
t_select_zeroType of the support structure for select on pattern 0.
Reference
Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter: High-order entropy-compressed text indexes. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003).

Definition at line 51 of file wt_blcd.hpp.

◆ wt_huff

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using sdsl::wt_huff = wt_pc<huff_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat>

A Huffman-shaped wavelet tree.

A wavelet tree is build for a vector of characters over the byte alphabet $\Sigma$. If you need a wavelet tree for a integer alphabet you should use wt_int. The wavelet tree $wt$ consists of a tree of bitvectors and provides three efficient methods:

  • The "[]"-operator: $wt[i]$ returns the i-th symbol of vector for which the wavelet tree was build for.
  • The rank method: $wt.rank(i,c)$ returns the number of occurrences of symbol $c$ in the prefix [0..i-1] in the vector for which the wavelet tree was build for.
  • The select method: $wt.select(j,c)$ returns the index $i\in [0..size()-1]$ of the j-th occurrence of symbol $c$.

The idea of using a Huffman shaped wavelet was first mentioned on page 17 of the following technical report: Veli Mäkinen and Gonzalo Navarro: ,,Succinct Suffix Arrays based on Run-Length Encoding.'' Available under: http://swp.dcc.uchile.cl/TR/2005/TR_DCC-2005-004.pdf

Template Parameters
t_bitvectorUnderlying bitvector structure.
t_rankRank support for pattern 1 on the bitvector.
t_selectSelect support for pattern 1 on the bitvector.
t_select_zeroSelect support for pattern 0 on the bitvector.
t_dfs_shapeLayout of the tree structure in memory. Set 0 for BFS layout and 1 fro DFS layout.
Space complexity
$n H_0 + 2|\Sigma|\log n$ bits, where $n$ is the size of the vector the wavelet tree was build for.

Definition at line 67 of file wt_huff.hpp.

◆ wt_hutu

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using sdsl::wt_hutu = wt_pc<hutu_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat>

A Hu-Tucker-shaped wavelet tree.

Template Parameters
t_bitvectorUnderlying bitvector structure.
t_rankRank support for pattern 1 on the bitvector.
t_selectSelect support for pattern 1 on the bitvector.
t_select_zeroSelect support for pattern 0 on the bitvector.
t_dfs_shapeLayout of the tree structure in memory. Set 0 for BFS layout and 1 fro DFS layout.
Space complexity
Almost $n H_0 + 2|\Sigma|\log n$ bits, where $n$ is the size of the vector the wavelet tree was build for.

Definition at line 46 of file wt_hutu.hpp.