List of Implemented Data Structures

Bitvectors
- An uncompressed mutual bitvector (bit_vector)
- An uncompressed immutable bitvector (bit_vector_il)
- A -compressed immutable bitvector (rrr_vector<>)
- A bitvector for sparse populated arrays (sd_vector<>)
Rank Support (RS) and Select Support (SS)
- Several rank and select implementations with different time-space trade-offs for the uncompressed bitvectors (rank_support_v, rank_support_v5, select_support_mcl, ...)
- Rank and select for compressed bitvectors (rank_support_rrr, rank_support_sd, ...)
Variable-length Coders
- Elias- $\delta$ coder (coder::elias_delta)
- Elias- $\gamma$ coder (coder::elias_gamma)
- Fibonacci-coder (coder::fibonacci)
Integer Vectors
- Mutable vectors for (compile-time) fixed w-bit integers (int_vector)
- Mutable vector for (run-time) fixed w-bit integers (int_vector<0>, w passed to the constructor)
- Immutable compressed integer vectors using a variable-length coder coder (enc_vector, vlc_vector)
Wavelet Trees (WT) (all immutable)
- Balanced wavelet (wt_blcd)
- Balanced wavelet tree for integer alphabets (wt_int)
- Wavelet matrix for integer alphabets (wm_int)
- Huffman-shaped wavelet tree (wt_huff)
- Hu-Tucker-shaped wavelet tree (wt_hutu)
- Run-length compressed wavelet tree (wt_rlmn)
- Fast select wavelet tree for integer alphabets (wt_gmr)
Compressed Suffix Arrays (CSA) (all immutable)
- csa_bitcompressed is based on the bitcompressed SA and inverse SA.
- csa_wt is based on a WT of the BWT.
- csa_sada is based on the compressed $\Psi$ -function
Balanced Parentheses Support (BPS) (all immutable)
- A range-min-max-tree implementation (bp_support_sada) to support operations find_open, find_close, enclose, double_enclose,...
- Hierarchical solutions with pioneer parentheses (bp_support_g, bp_support_gg)
Longest Common Prefix (LCP) Arrays (all immutable)
- lcp_bitcompressed is a bitcompressed version
- lcp_byte encodes small values with one byte and large values with two words
- lcp_dac used direct accessible codes
- lcp_wt stores small values in a WT and large value in on word.
- lcp_vlc stores the values in a vlc_vector.
- lcp_support_sada uses a bitvector of 2n bits, a select structure supporting it, and the corresponding CSA.
- lcp_support_tree uses the topology of the corresponding CST.
- lcp_support_tree2 uses the corresponding CSA and CST.
Compressed Suffix Trees (CST) (all immutable)
- cst_sada provides very fast navigation operations; worst case
  space |CSA|+|LCP|+4n+o(n)
- cst_sct3 representing nodes as intervals in the suffix array; worst case space |CSA|+|LCP|+3n+o(n)
Range Minimum/Maximum Query (RMQ) Structures (all immutable)
- Self-contained RMQ structure using 2n+o(n) bits or 4n+o(n) bits (rmq_succinct_sct, rmq_succinct_sada)
- Non-succinct support structure for RMQ (rmq_support_sparse_table)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

List of Implemented Data Structures

Uh oh!

Uh oh!

Clone this wiki locally