SDSL 3.0.1
Succinct Data Structure Library
|
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. More... | |
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. More... | |
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. More... | |
This group contains data structures for wavelet trees.
The following methods are supported:
using sdsl::wt_blcd = typedef wt_pc<balanced_shape, t_bitvector, t_rank, t_select_one, t_select_zero, t_tree_strat> |
A balanced wavelet tree.
t_bitvector | Underlying bitvector structure. |
t_rank | Type of the support structure for rank on pattern 1 . |
t_select | Type of the support structure for select on pattern 1 . |
t_select_zero | Type of the support structure for select on pattern 0 . |
Definition at line 44 of file wt_blcd.hpp.
using sdsl::wt_huff = typedef 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 wt_int
. The wavelet tree
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
t_bitvector | Underlying bitvector structure. |
t_rank | Rank support for pattern 1 on the bitvector. |
t_select | Select support for pattern 1 on the bitvector. |
t_select_zero | Select support for pattern 0 on the bitvector. |
t_dfs_shape | Layout of the tree structure in memory. Set 0 for BFS layout and 1 fro DFS layout. |
Definition at line 60 of file wt_huff.hpp.
using sdsl::wt_hutu = typedef wt_pc<hutu_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat> |
A Hu-Tucker-shaped wavelet tree.
t_bitvector | Underlying bitvector structure. |
t_rank | Rank support for pattern 1 on the bitvector. |
t_select | Select support for pattern 1 on the bitvector. |
t_select_zero | Select support for pattern 0 on the bitvector. |
t_dfs_shape | Layout of the tree structure in memory. Set 0 for BFS layout and 1 fro DFS layout. |
Definition at line 42 of file wt_hutu.hpp.