Namespace for the succinct data structure library. More...

Namespaces
namespace	algorithm
	A helper class containing algorithms for succinct data structures.
namespace	coder
	Namespace for the different coder of the sdsl.
namespace	util
	A namespace for helper functions.
Classes
class	bit_vector_interleaved
	A bit vector which interleaves the original bit_vector with rank information. More...
class	rank_support_interleaved
class	select_support_interleaved
class	bit_magic
	A helper class for bitwise tricks on 64 bit words. More...
class	bp_support_g
	A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Geary et al. (CPM 2004) and extended by Ohlebusch and Gog (SPIRE 2009). More...
class	bp_support_gg
	A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Geary et al. (CPM 2004) and extended by Ohlebusch and Gog (SPIRE 2009). More...
class	bp_support_j
	A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Jacobson (1989) and Geary et al. (CPM 2004). More...
class	bp_support_sada
	A class that provides support for bit_vectors that represent a balanced parentheses sequence. Implementation was proposed by Kunihiko Sadakane in the paper "The Ultimate Balanced Parentheses" (Technical Report 2008). More...
struct	csa_sada_trait
struct	csa_sada_trait< 32 >
struct	csa_sada_trait< 64 >
class	csa_sada
	A class for the Compressed Suffix Array (CSA) proposed by Sadakane for practical implementation. More...
class	csa_sada_theo
	A class for the Compressed Suffix Array (CSA) proposed by Sadakane. csa_sada_theo is the one to one implementation of Sadakane's theoretical description with our data structures. More...
class	csa_uncompressed
	A class for the uncmpressed suffix array (SA). More...
struct	csa_wt_trait
struct	csa_wt_trait< 32 >
struct	csa_wt_trait< 64 >
class	psi_of_csa_wt
	A wrapper class for the $\Psi$ and LF function for (compressed) suffix arrays that are based on a wavelet tree (like sdsl::csa_wt). More...
class	bwt_of_csa_wt
class	csa_wt
	A class for the Compressed Suffix Array (CSA) based on a Wavelet Tree (WT) of the Burrow Wheeler Transform of the orignal text. More...
struct	bp_interval_p
class	cst_sct3p
	A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog. More...
class	cst_dfs_const_forward_iterator
	An forward iterator for (compressed) suffix trees. More...
class	cst_bottom_up_const_forward_iterator
	A forward iterator for a bottom up traversal of a suffix tree. More...
class	cst_bfs_iterator
	A forward iterator for a breath first traversal of a tree. More...
class	cst_sada
	A class for the Compressed Suffix Tree (CST) proposed by Sadakane. More...
struct	lcp_interval
	A struct for the representation of an lcp-interval $\ell-[left..right]$ . More...
class	cst_sct
	A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog. More...
class	cst_sct2
	A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog. More...
struct	bp_interval
class	cst_sct3
	A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog. More...
struct	enc_vector_trait
struct	enc_vector_trait< 32 >
class	enc_vector
	A generic immutable space-saving vector class for unsigned integers. It encodes each integer with its self-delimiting code and still provides constant time access. More...
struct	enc_vector_dna_trait
struct	enc_vector_dna_trait< 32 >
class	enc_vector_dna
	An immutable space-saving vector class for unsigned positiv integers of the psi-values of dna data. More...
struct	enc_vector_prac2_trait
struct	enc_vector_prac2_trait< 32 >
class	enc_vector_prac2
	A generic immutable space-saving vector class for unsigned positiv integers. It encodes each integer with its self-delimiting code and still provides constant time access. More...
struct	enc_vector_theo_trait
struct	enc_vector_theo_trait< 32 >
class	enc_vector_theo
	A generic immutable space-saving vector class for unsigned integers. It encodes each integer with its self-delimiting code and still provides constant time access. More...
struct	enc_vector_theo_const_iterator
struct	fast_cache
class	gap_vector
	A bit vector which compresses very sparse populated bit vectors by representing the 1 or 0 by gap encoding. More...
class	gap_rank_support
class	gap_select_support
struct	int_vector_trait
struct	int_vector_trait< 64, size_type_class >
struct	int_vector_trait< 32, size_type_class >
struct	int_vector_trait< 16, size_type_class >
struct	int_vector_trait< 8, size_type_class >
class	int_vector
	A generic vector class for integers of width $w\in [1..64]$ . More...
class	int_vector_reference
	A proxy class that acts as a reference to an integer of length `len` bits in a int_vector. More...
class	int_vector_reference< bit_vector >
class	int_vector_iterator_base
class	int_vector_iterator
class	int_vector_const_iterator
class	char_array_serialize_wrapper
	A wrapper class which allows us to serialize an char array as an int_vector. More...
class	int_vector_file_buffer
	A class for reading an int_vector buffered from a file. More...
class	int_vector_serialize_vbyte_wrapper
class	int_vector_load_vbyte_wrapper
class	int_vector_serialize_vlen_wrapper
class	int_vector_load_vlen_wrapper
class	int_vector_serialize_wrapper
class	int_vector_load_wrapper
class	int_vector_serialize_min_overhead
class	random_access_const_iterator
class	lcp_bitcompressed
	A class which stores the lcp array uncompressed. More...
class	buffered_char_queue
class	lcp_dac
	A class for the compressed version of lcp information of an suffix array. More...
class	lcp_kurtz
	A class for the compressed version of lcp information of an suffix array proposed by Stefan Kurtz in the paper "Reducing the Space Requirement of Suffix Trees". More...
class	_lcp_support_sada
	A class for the compressed version of lcp information of an suffix array of class Csa proposed by Sadakane in the paper "Succinct Representation of lcp Information and Improvements in the Compressed Suffix Arrays". More...
class	lcp_support_sada
	Helper class which provides _lcp_support_sada the context of a CSA. More...
class	_lcp_support_tree
class	lcp_support_tree
	Helper class which provides _lcp_support_tree the context of a CST. More...
class	_lcp_support_tree2
class	lcp_support_tree2
	Helper class which provides _lcp_support_tree2 the context of a CST. More...
class	lcp_vlc
class	lcp_wt
	A class for the compressed version of lcp information of an suffix array. More...
class	louds_node
	A class for the node representation of louds_tree. More...
class	louds_tree
	A tree class based on the level order unary degree sequence (LOUDS) representation. More...
class	nearest_neighbour_dictionary
	Nearest neighbour dictionary for sparse uniform sets (described in Geary et al., A Simple Optimal Representation for Balanced Parentheses, CPM 2004). More...
class	nn_dict_dynamic
	A class for a dynamic bit vector which also supports the prev and next operations. More...
class	rank_support
	The base class of classes supporting rank_queries for a sdsl::bit_vector in constant time. More...
class	rank_support_jmc
	A class supporting rank queries in constant time. The implementation is a lightweight version of the data structure proposed by Jacobson (1989), Munro (1996), and Clark (1996). More...
struct	rank_support_v_trait
struct	rank_support_v_trait< 0, 1 >
struct	rank_support_v_trait< 1, 1 >
struct	rank_support_v_trait< 10, 2 >
struct	rank_support_v_trait< 01, 2 >
class	rank_support_v
	A class supporting rank queries in constant time. The implementation is a version of the data structure proposed by Vigna (WEA 2008). More...
class	rank_support_v5
	A class supporting rank queries in constant time. The implementation is a space saving version of the data structure proposed by Vigna (WEA 2008). More...
struct	range_maximum_support_sada
class	rmq_succinct_sada
	A class to support range minimum or range maximum queries on a random access container. More...
struct	range_maximum_sct
class	rmq_succinct_sct
	A class to support range minimum or range maximum queries on a random access container. More...
struct	range_maximum_support_sparse_table
class	rmq_support_sparse_table
	A class to support range minimum or range maximum queries on a random access container. More...
struct	binomial_coefficients_trait
	Trait class for the binomial coefficient class to handle different type of intergers. More...
struct	binomial_coefficients_trait< 7 >
	Specialization of binomial_coefficients_trait for 128-bit integers. More...
struct	binomial_coefficients_trait< 8 >
	Specialization of binomial_coefficients_trait for 256-bit integers. More...
class	binomial_coefficients
	A class for the binomial coefficients up to n. More...
class	rrr_helper
	Class to encode and decode binomial coefficients on the fly. More...
class	rrr_vector
	A bit vector which compresses the input with the method from Raman, Raman, and Rao. More...
struct	rrr_rank_support_trait
struct	rrr_rank_support_trait< 0 >
class	rrr_rank_support
	rank_support for the rrr_vector class More...
class	rrr_select_support
	Select support for the rrr_vector class. More...
class	binomial
class	rrr_vector< 15, wt_type >
	A specialization of the rrr_vector class for a block_size of 15. More...
class	rrr_rank_support< b, 15, wt_type >
	rank_support for the specialized rrr_vector class of block size 15. More...
class	rrr_select_support< b, 15, wt_type >
	Select support for the specialized rrr_vector class of block size 15. More...
class	sd_vector
	A bit vector which compresses very sparse populated bit vectors by. More...
class	sd_rank_support
	Rank data structure for sd_vector. More...
class	sd_select_support
	Select data structure for sd_vector. More...
struct	csa_tag
struct	cst_tag
struct	lcp_plain_tag
struct	lcp_permuted_tag
struct	lcp_tree_compressed_tag
struct	lcp_tree_and_lf_compressed_tag
class	select_support
	The base class of classes supporting select queries for a sdsl::bit_vector in constant time. More...
class	select_support_bs
	A class supporting select quries by using a rank_support and binary search. More...
class	select_support_dummy
	A dummy class for select. More...
struct	select_support_mcl_trait
struct	select_support_mcl_trait< 0, 1 >
struct	select_support_mcl_trait< 1, 1 >
struct	select_support_mcl_trait< 10, 2 >
struct	select_support_mcl_trait< 01, 2 >
class	select_support_mcl
	A class supporting constant time select queries (proposed by Munro/Clark, 1996) enhanced by broadword computing tricks. More...
class	sorted_int_stack
	A stack class which can contain integers from to in sorted order. More...
class	sorted_multi_stack_support
	A stack class which contains ... More...
class	sorted_stack_support
	A stack class which contains indices of elements from an random access container and the elements are in sorted order on the stack. More...
class	structure_tree_node
	Class for a node of the structure tree. More...
class	structure_tree
class	psi_of_csa_psi
	A helper class for the $\Psi$ and LF function for (compressed) suffix arrays that are based on the compressed $\Psi$ function. More...
class	psi_of_sa_and_isa
	A helper class for the $\Psi$ function for (compressed) suffix arrays which provide also the inverse suffix array values (like sdsl::csa_uncompressed). More...
class	bwt_of_csa_psi
	A wrapper for the bwt of a compressed suffix array that is based on the $\psi$ function. More...
class	temp_write_read_buffer
class	template_class
	Short description for what template_class is used here. More...
class	stop_watch
	A helper class to meassure the time consumption of program pieces. More...
class	clock
	A helper class to get time information. More...
class	file
	A helper class to handle files. More...
class	uint256_t
struct	vlc_vector_trait
struct	vlc_vector_trait< 32 >
class	vlc_vector
	A generic immutable space-saving vector class for unsigned positive integers. More...
struct	unsigned_char_map
class	wt_trait
class	wt_trait< character * >
class	wt_trait< unsigned char * >
class	wt_trait< int_vector_file_buffer< 8, size_type_class > >
class	wt
	A wavelet tree class. More...
struct	_node
class	wt_huff
	A Wavelet Tree class for byte sequences. More...
class	wt_int
	A wavelet tree class for sequences of big alphabet size (like integer alphabet) More...
class	wt_rlg
	A Wavelet Tree class for byte sequences. More...
class	wt_rlg8
	A Wavelet Tree class for byte sequences. More...
class	wt_rlmn
	A Wavelet Tree class for byte sequences. More...
Typedefs
typedef uint64_t	std_size_type_for_int_vector
typedef int_vector< 1 >	bit_vector
	bit_vector is a specialization of the int_vector.
typedef std::list< int_vector <>::size_type >	tLI
typedef std::vector < int_vector<>::size_type >	tVI
typedef std::map< std::string, std::string >	tMSS
typedef std::vector< std::string >	tVS
typedef unsigned int uint128_t	__attribute__ ((mode(TI)))
typedef wt_huff< rrr_vector <>, rrr_vector<>::rank_1_type, rrr_vector<>::select_1_type, rrr_vector<>::select_0_type, 0 >	wt_huff_rrr
typedef wt_huff< bit_vector, rank_support_v5 <>, select_support_bs <>, select_support_bs<> >	wt_without_select
Enumerations
enum	format_type { JSON_FORMAT, R_FORMAT }
Functions
bool	construct_bwt (tMSS &file_map, const std::string &dir, const std::string &id)
bool	construct_bwt2 (tMSS &file_map, const std::string &dir, const std::string &id)
template<class Int >
std::ostream &	operator<< (std::ostream &os, const bp_interval_p< Int > &interval)
template<class Cst >
bool	construct_cst (std::string file_name, Cst &cst)
	Constructs a compressed suffix tree (cst) by a semi-external algorithm.
template<class Cst >
bool	construct_cst (std::string file_name, Cst &cst, tMSS &file_map, bool delete_files=true, std::string dir="./", bool build_only_bps=false, std::string id="", std::string lcp_method="any")
	Constructs a compressed suffix tree (cst) semi-external.
template<class Int >
std::ostream &	operator<< (std::ostream &os, const lcp_interval< Int > &interval)
template<class Int >
std::ostream &	operator<< (std::ostream &os, const bp_interval< Int > &interval)
uint64_t	decode64bit (uint64_t w)
template<class int_vector >
int_vector_iterator< int_vector >	operator+ (typename int_vector_iterator< int_vector >::difference_type n, const int_vector_iterator< int_vector > &it)
template<class int_vector >
int_vector_const_iterator < int_vector > ::difference_type	operator- (const int_vector_const_iterator< int_vector > &x, const int_vector_const_iterator< int_vector > &y)
template<class int_vector >
int_vector_const_iterator < int_vector >	operator+ (typename int_vector_const_iterator< int_vector >::difference_type n, const int_vector_const_iterator< int_vector > &it)
std::ostream &	operator<< (std::ostream &os, const int_vector< 1 > &v)
std::ostream &	operator<< (std::ostream &os, const int_vector< 0 > &v)
template<class size_type_class >
size_type_class	_sdsl_serialize_size_and_int_width (std::ostream &out, uint8_t fixed_int_width, uint8_t int_width, size_type_class size)
bool	construct_isa (tMSS &file_map, const std::string &dir, const std::string &id)
template<class RandomAccessContainer >
random_access_const_iterator < RandomAccessContainer > ::difference_type	operator- (const random_access_const_iterator< RandomAccessContainer > &x, const random_access_const_iterator< RandomAccessContainer > &y)
template<class RandomAccessContainer >
random_access_const_iterator < RandomAccessContainer >	operator+ (typename random_access_const_iterator< RandomAccessContainer >::difference_type n, const random_access_const_iterator< RandomAccessContainer > &it)
template<class Lcp , class Cst , uint8_t int_width, class size_type_class , uint8_t int_width1, class size_type_class1 >
void	construct_lcp (Lcp &lcp, const Cst &cst, int_vector_file_buffer< int_width, size_type_class > &lcp_buf, int_vector_file_buffer< int_width1, size_type_class1 > &isa_buf)
template<class Lcp , class Cst , uint8_t int_width, class size_type_class , uint8_t int_width1, class size_type_class1 >
void	construct_lcp (Lcp &lcp, const Cst &cst, int_vector_file_buffer< int_width, size_type_class > &lcp_buf, int_vector_file_buffer< int_width1, size_type_class1 > &isa_buf, lcp_plain_tag)
template<class Lcp , class Cst , uint8_t int_width, class size_type_class , uint8_t int_width1, class size_type_class1 >
void	construct_lcp (Lcp &lcp, const Cst &cst, int_vector_file_buffer< int_width, size_type_class > &lcp_buf, int_vector_file_buffer< int_width1, size_type_class1 > &isa_buf, lcp_permuted_tag)
template<class Lcp , class Cst , uint8_t int_width, class size_type_class , uint8_t int_width1, class size_type_class1 >
void	construct_lcp (Lcp &lcp, const Cst &cst, int_vector_file_buffer< int_width, size_type_class > &lcp_buf, int_vector_file_buffer< int_width1, size_type_class1 > &isa_buf, lcp_tree_compressed_tag)
template<class Lcp , class Cst >
void	construct_lcp (Lcp &lcp, const Cst &cst, tMSS &file_map, const std::string dir, const std::string id)
template<class Lcp , class Cst >
void	construct_lcp (Lcp &lcp, const Cst &cst, tMSS &file_map, const std::string dir, const std::string id, lcp_plain_tag)
template<class Lcp , class Cst >
void	construct_lcp (Lcp &lcp, const Cst &cst, tMSS &file_map, const std::string dir, const std::string id, lcp_permuted_tag)
template<class Lcp , class Cst >
void	construct_lcp (Lcp &lcp, const Cst &cst, tMSS &file_map, const std::string dir, const std::string id, lcp_tree_compressed_tag)
template<class Lcp , class Cst >
void	construct_lcp (Lcp &lcp, const Cst &cst, tMSS &file_map, const std::string dir, const std::string id, lcp_tree_and_lf_compressed_tag)
template<class Lcp , class Cst >
void	copy_lcp (Lcp &lcp, const Lcp &lcp_c, const Cst &cst)
template<class Lcp , class Cst >
void	copy_lcp (Lcp &lcp, const Lcp &lcp_c, const Cst &cst, lcp_plain_tag)
template<class Lcp , class Cst >
void	copy_lcp (Lcp &lcp, const Lcp &lcp_c, const Cst &cst, lcp_permuted_tag)
template<class Lcp , class Cst >
void	copy_lcp (Lcp &lcp, const Lcp &lcp_c, const Cst &cst, lcp_tree_compressed_tag)
template<class Lcp , class Cst >
void	copy_lcp (Lcp &lcp, const Lcp &lcp_c, const Cst &cst, lcp_tree_and_lf_compressed_tag)
template<class Lcp , class Cst >
void	swap_lcp (Lcp &lcp1, Lcp &lcp2, const Cst &cst1, const Cst &cst2)
template<class Lcp , class Cst >
void	swap_lcp (Lcp &lcp1, Lcp &lcp2, const Cst &cst1, const Cst &cst2, lcp_plain_tag)
template<class Lcp , class Cst >
void	swap_lcp (Lcp &lcp1, Lcp &lcp2, const Cst &cst1, const Cst &cst2, lcp_permuted_tag)
template<class Lcp , class Cst >
void	swap_lcp (Lcp &lcp1, Lcp &lcp2, const Cst &cst1, const Cst &cst2, lcp_tree_compressed_tag)
template<class Lcp , class Cst >
void	swap_lcp (Lcp &lcp1, Lcp &lcp2, const Cst &cst1, const Cst &cst2, lcp_tree_and_lf_compressed_tag)
template<class Lcp , class Cst >
void	load_lcp (Lcp &lcp, std::istream &in, const Cst &cst)
template<class Lcp , class Cst >
void	load_lcp (Lcp &lcp, std::istream &in, const Cst &cst, lcp_plain_tag)
template<class Lcp , class Cst >
void	load_lcp (Lcp &lcp, std::istream &in, const Cst &cst, lcp_permuted_tag)
template<class Lcp , class Cst >
void	load_lcp (Lcp &lcp, std::istream &in, const Cst &cst, lcp_tree_compressed_tag)
template<class Lcp , class Cst >
void	load_lcp (Lcp &lcp, std::istream &in, const Cst &cst, lcp_tree_and_lf_compressed_tag)
bool	construct_lcp_kasai (tMSS &file_map, const std::string &dir, const std::string &id)
	5n byte variant of the algorithm of Kasai et al. (CPM 2001, "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications")
bool	construct_lcp_semi_extern_PHI (tMSS &file_map, const std::string &dir, const std::string &id)
bool	construct_lcp_PHI (tMSS &file_map, const std::string &dir, const std::string &id, bool semi_external=false)
	5n byte variant of the algorithm of Kaerkkaeinen et al. (CPM 2009, "Permuted Longest Common Prefix Array")
template<class size_type_class >
void	push_front_m_index (size_type_class i, uint8_t c, tLI(&m_list)[256], uint8_t(&m_chars)[256], size_type_class &m_char_count)
template<class size_type_class >
void	push_back_m_index (size_type_class i, uint8_t c, tLI(&m_list)[256], uint8_t(&m_chars)[256], size_type_class &m_char_count)
bool	construct_lcp_simple_5n (tMSS &file_map, const std::string &dir, const std::string &id)
bool	construct_lcp_simple2_9n (tMSS &file_map, const std::string &dir, const std::string &id)
bool	construct_lcp_go (tMSS &file_map, const std::string &dir, const std::string &id)
	Our new 2 phases lcp algorithm using usually 2n bytes.
bool	construct_lcp_goPHI (tMSS &file_map, const std::string &dir, const std::string &id)
	Our new 2 phases lcp algorithm using usually 2n bytes.
bool	construct_lcp_go2 (tMSS &file_map, const std::string &dir, const std::string &id)
	Our new 2 phases lcp algorithm using usually 1 n bytes.
void	lcp_info (tMSS &file_map)
std::ostream &	operator<< (std::ostream &os, const louds_node &v)
template<format_type F>
void	write_structure_tree (const structure_tree_node *v, std::ostream &out)
template<class tCst >
double	H0 (const typename tCst::node_type &v, const tCst &cst)
	Calculate the zeroth order entropy of the text that follows a certain substring s.
template<class tCst >
double	Hk (const tCst &cst, typename tCst::size_type k, typename tCst::size_type &context)
	Calculate the k-th order entropy of a text.
template<class Csa >
Csa::size_type	get_char_pos (typename Csa::size_type idx, typename Csa::size_type d, const Csa &csa)
template<class Cst >
void	cst_info (const Cst &cst)
int_vector< 64 >	get_rnd_positions (uint8_t log_s, uint64_t &mask, uint64_t m=0, uint64_t x=17)
	Create 1^{log_s} random intergers mod m with seed x.
template<class Vector >
void	test_int_vector_random_access (const Vector &v, bit_vector::size_type times=100000000)
template<class Vector >
void	test_int_vector_random_write (Vector &v, bit_vector::size_type times=100000000)
template<class Vector >
void	test_int_vector_sequential_write (Vector &v, bit_vector::size_type times=100000000)
template<class Rank >
void	test_rank_random_access (const Rank &rank, bit_vector::size_type times=20000000)
	Test random queries on rank data structure.
template<class Rank >
void	test_rank_construction (bit_vector::size_type size=838860800)
	Test creation time for a rank data structure.
template<class Select >
void	test_select_random_access (const Select &select, bit_vector::size_type times=20000000)
	Test random queries on select data structure.
template<class Select >
void	test_select_random_access (const Select &select, bit_vector::size_type args, bit_vector::size_type times)
	Test random queries on select data structure.
template<class Select >
void	test_select_construction (bit_vector::size_type size=838860800)
	Test creation time for a rank data structure.
template<class Csa >
void	test_csa_access (const Csa &csa, typename Csa::size_type times=1000000)
template<class Csa >
void	test_icsa_access (const Csa &csa, typename Csa::size_type times=1000000)
template<class Csa >
void	test_psi_access (const Csa &csa, typename Csa::size_type times=1000000)
template<class Csa >
void	test_lf_access (const Csa &csa, typename Csa::size_type times=1000000)
	Test random access on LF function.
template<class Csa >
void	test_bwt_access (const Csa &csa, typename Csa::size_type times=1000000)
	Test random access on bwt.
template<class Csa >
void	test_pattern_matching (const Csa &csa, const char *file_name, const typename Csa::size_type pattern_len=20, typename Csa::size_type times=1000000)
	Test speed for pattern matching.
template<class Csa >
void	test_rank_bwt_access (const Csa &csa, typename Csa::size_type times=1000000)
template<class Csa >
void	test_select_bwt_access (const Csa &csa, typename Csa::size_type times=500000)
template<class Cst >
void	test_cst_dfs_iterator (Cst &cst, typename Cst::size_type times=100000)
	Test performance of the depth first iterator of a CST.
template<class Cst >
void	test_cst_dfs_iterator_and_depth (Cst &cst, typename Cst::size_type times=1000000, bool output=false)
	Test performance of the depth first iterator and the LCP array of a CST.
template<class Cst >
void	test_cst_dfs_iterator_and_id (Cst &cst, typename Cst::size_type times=1000000, bool output=false)
	Test performance of the depth first iterator and the id method of the CST.
template<class Lcp >
void	test_lcp_random_access (Lcp &lcp, typename Lcp::size_type times=10000000)
	Make random accesse to an LCP array.
template<class Lcp >
void	test_lcp_sequential_access (Lcp &lcp, typename Lcp::size_type times=10000000)
	Make sequential accesses to an LCP array.
template<class Lcp >
void	test_lcp_random_sequential_access (Lcp &lcp, typename Lcp::size_type times=1000000, typename Lcp::size_type seq_len=64)
	Make random sequential accesse to an LCP array.
template<class Cst >
void	test_cst_parent_operation (const Cst &cst, typename Cst::size_type times=100000, uint64_t x=17)
	Test the speed of the parent operation.
template<class Cst >
void	generate_nodes_from_random_leaves (const Cst &cst, typename Cst::size_type times, std::vector< typename Cst::node_type > &nodes, uint64_t x=17)
	Generate nodes of a cst by applying the child operation to each of random leaves until we get to the root.
template<class Cst >
void	test_cst_child_operation (const Cst &cst, typename Cst::size_type times=5000, uint64_t x=17)
	Test the speed of the child operation.
template<class Cst >
void	test_cst_1th_child_operation (const Cst &cst, typename Cst::size_type times=1000000, uint64_t x=17)
	Test the speed of the 1th_child operation.
template<class Cst >
void	test_cst_sibling_operation (const Cst &cst, typename Cst::size_type times=100000, uint64_t x=17)
	Test the speed of the sibling operation.
template<class Cst >
void	test_cst_id_operation (const Cst &cst, typename Cst::size_type times=100000, uint64_t x=17)
	Test id operation.
template<class Cst >
void	test_cst_depth_operation (const Cst &cst, typename Cst::size_type times=100000, uint64_t x=17)
	Test depth operations for leaves and inner nodes.
template<class Cst >
void	test_cst_depth_operation_for_inner_nodes (const Cst &cst, typename Cst::size_type times=100000, uint64_t x=17)
	Test depth operations for inner nodes.
template<class Cst >
void	test_cst_lca_operation (const Cst &cst, typename Cst::size_type times=1000000, uint64_t x=17)
	Test lca operation.
template<class Cst >
void	test_cst_sl_operation (const Cst &cst, typename Cst::size_type times=500, uint64_t x=17)
	Test suffix link operation.
template<class Cst >
void	test_cst_matching_statistics (const Cst &cst, unsigned char *S2, typename Cst::size_type n2)
	Test matching statistics.
template<class Bps >
void	test_bps_find_close_and_enclose (const Bps &bps, const bit_vector &b, uint64_t times=10000000, uint64_t x=17)
template<class Bps >
void	test_bps_find_open (const Bps &bps, const bit_vector &b, uint64_t times=10000000, uint64_t x=17)
template<class Bps >
void	test_bps_double_enclose (const Bps &bps, const bit_vector &b, uint64_t times=10000000, uint64_t x=17)
void	write_R_output (std::string data_structure, std::string action, std::string state="begin", uint64_t times=1, uint64_t check=0)
	Write stopwatch output in readable format.
off_t	get_file_size (const char *file_name)
	Get the size of a file in bytes.
void	begin_tikzpicture (ostream &out, string options="")
void	end_tikzpicture (ostream &out)
void	begin_tikzscope (ostream &out, string options="")
void	end_tikzscope (ostream &out)
void	tikz_node (ostream &out, string content="", string at="0,0", string name="", string options="")
void	tikz_coordinate (ostream &out, string at="0,0", string name="", string option="")
template<class T >
void	write_tikz_column_from_container (ostream &out, const T &vec, string name_prefix="i")
template<class tContainer >
void	write_tikz_array (ostream &out, const tContainer &v, string array_name="", bool escape=false)
void	write_y_column (ostream &out, size_t n)
std::ostream &	operator<< (std::ostream &os, const uint128_t &x)
std::ostream &	operator<< (std::ostream &os, const uint256_t &x)
template<class size_type_class , class size_type >
void	calculate_character_occurences (int_vector_file_buffer< 8, size_type_class > &text, const size_type size, size_type *C)
	Count for each character in [0..255] the number of occurences in rac[0..size-1].
template<class size_type >
void	calculate_effective_alphabet_size (const size_type *C, size_type &sigma)
Variables
const uint16_t	_undef_node = 65535
const int_vector::size_type	ZoO [2] = {0, (int_vector<>::size_type)-1}

Detailed Description

Namespace for the succinct data structure library.

Function Documentation

template<class size_type_class , class size_type >

void sdsl::calculate_character_occurences	(	int_vector_file_buffer< 8, size_type_class > &	text,
		const size_type	size,
		size_type *	C
	)

Count for each character in [0..255] the number of occurences in rac[0..size-1].

Returns:: C An array of size 256, which contains for each character the number of occurences in rac[0..size-1]

bool sdsl::construct_bwt	(	tMSS &	file_map,
		const std::string &	dir,
		const std::string &	id
	)

Constructs the Burrows and Wheeler Transform (BWT) from text and suffix array

Parameters:

file_map	A map, which contains the paths of the precalculated files like suffix array or text
dir	Directory in which the result should be written on disk.
id	Id which should be used to build a file name for the calculated BWT.

Space complexity:: bytes

template<class Cst >

bool sdsl::construct_cst	(	std::string	file_name,
		Cst &	cst
	)

Constructs a compressed suffix tree (cst) by a semi-external algorithm.

Parameters:

file_name	File name of the text, for which the cst should be build
cst	A reference to the cst object.

Details: The semi-external construction algorithm creates some temporary files in the current directory during the calculation.

Space complexity: bytes

Time complexity: $\Order{n}$

template<class Cst >

bool sdsl::construct_cst	(	std::string	file_name,
		Cst &	cst,
		tMSS &	file_map,
		bool	delete_files = `true`,
		std::string	dir = `"./"`,
		bool	build_only_bps = `false`,
		std::string	id = `""`,
		std::string	lcp_method = `"any"`
	)

Constructs a compressed suffix tree (cst) semi-external.

Parameters:

file_name	File name of the text, for which the cst should be build
cst	A reference to the cst object. cst will hold the result after the execution of the method.
file_map	A map which will contain the file names of structures which are calculated and stored during the construction.
delete_files	Boolean flag. If it is true, all files stored in file_map will be removed after the construction.
dir	A directory path which points to the directory where the calculated files should be stored during the construction.
build_only_bps	Boolean flag. If it is true, only the navigation part of the cst is build. I.e. compressed suffix array and other stuff is ommitted...
lcp_method	Specify, which lcp construction algorithm should be used. Possible options are kasai, PHI, go, go2, any

Space complexity: bytes

Time complexity: $\Order{n}$

bool sdsl::construct_lcp_go	(	tMSS &	file_map,
		const std::string &	dir,
		const std::string &	id
	)

Our new 2 phases lcp algorithm using usually 2n bytes.

  The algorithm computes the lcp array and stores it to disk.

Parameters:

file_map	A map which contains the filenames of previous computed structures (like suffix array, Burrows and Wheeler transform, inverse suffix array, text,...)
dir	Directory where the lcp array should be stored.
id	Id for the file name of the lcp array.

Space complexity: Usually bytes, worst case

bool sdsl::construct_lcp_go2	(	tMSS &	file_map,
		const std::string &	dir,
		const std::string &	id
	)

Our new 2 phases lcp algorithm using usually 1 n bytes.

  The algorithm computes the lcp array and stores it to disk.

Parameters:

file_map	A map which contains the filenames of previous computed structures (like suffix array, Burrows and Wheeler transform, inverse suffix array, text,...)
dir	Directory where the lcp array should be stored.
id	Id for the file name of the lcp array.

Space complexity:: Usually $n+\Order{1}$ bytes, worst case bytes

bool sdsl::construct_lcp_goPHI	(	tMSS &	file_map,
		const std::string &	dir,
		const std::string &	id
	)

Our new 2 phases lcp algorithm using usually 2n bytes.

  The algorithm computes the lcp array and stores it to disk.

Parameters:

file_map	A map which contains the filenames of previous computed structures (like suffix array, Burrows and Wheeler transform, inverse suffix array, text,...)
dir	Directory where the lcp array should be stored.
id	Id for the file name of the lcp array.

Space complexity: Usually bytes, worst case

bool sdsl::construct_lcp_kasai	(	tMSS &	file_map,
		const std::string &	dir,
		const std::string &	id
	)

5n byte variant of the algorithm of Kasai et al. (CPM 2001, "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications")

   The algorithm computes the lcp array and stores it to disk.

Parameters:

file_map	A map which contains the filenames of previous computed structures (like suffix array, Burrows and Wheeler transform, inverse suffix array, text,...)
dir	Directory where the lcp array should be stored.
id	Id for the file name of the lcp array.

Space complexity: bytes

bool sdsl::construct_lcp_PHI	(	tMSS &	file_map,
		const std::string &	dir,
		const std::string &	id,
		bool	semi_external = `false`
	)

5n byte variant of the algorithm of Kaerkkaeinen et al. (CPM 2009, "Permuted Longest Common Prefix Array")

   The algorithm computes the lcp array and stores it to disk.

Parameters:

file_map	A map which contains the filenames of previous computed structures (like suffix array, Burrows and Wheeler transform, inverse suffix array, text,...)
dir	Directory where the lcp array should be stored.
id	Id for the file name of the lcp array.
semi_external	Boolean flag, which indicates if the algorithm should use only 4n bytes or 5n bytes

Space complexity: bytes or bytes if semi_external is set to true

template<class Cst >

void sdsl::generate_nodes_from_random_leaves	(	const Cst &	cst,
		typename Cst::size_type	times,
		std::vector< typename Cst::node_type > &	nodes,
		uint64_t	x = `17`
	)

Generate nodes of a cst by applying the child operation to each of $times$ random leaves until we get to the root.

Parameters:

Cst	The compressed suffix
times	Numer of random leaves
nodes	Reference to a vector which will contain the generated nodes
x	Seed for the random number generator for the generation of the leaves

template<class tCst >

double sdsl::H0	(	const typename tCst::node_type &	v,
		const tCst &	cst
	)

Calculate the zeroth order entropy of the text that follows a certain substring s.

Parameters:

v	A suffix tree node v. The label of the path from the root to v is s.
cst	The suffix tree of v.
The	zeroth order entropy of the concatenation of all characters that follow s in the original text.

template<class tCst >

double sdsl::Hk	(	const tCst &	cst,
		typename tCst::size_type	k,
		typename tCst::size_type &	context
	)

Calculate the k-th order entropy of a text.

Parameters:

cst	The suffix tree of v.
k	Parameter k for which H_k should be calculated.
context	A output reference which will hold the number of different contexts.

template<class Cst >

void sdsl::test_cst_1th_child_operation	(	const Cst &	cst,
		typename Cst::size_type	times = `1000000`,
		uint64_t	x = `17`
	)

Test the speed of the 1th_child operation.

Parameters:

Cst	The compressed suffix tree
times	Number of times a traversal from a random leaf to the root\ is started to collect nodes for which the child operation is performed.

template<class Cst >

void sdsl::test_cst_child_operation	(	const Cst &	cst,
		typename Cst::size_type	times = `5000`,
		uint64_t	x = `17`
	)

Test the speed of the child operation.

Parameters:

Cst	The compressed suffix tree
times	Number of times a traversal from a random leaf to the root\ is started to collect nodes for which the child operation is performed.

template<class Cst >

void sdsl::test_cst_dfs_iterator	(	Cst &	cst,
		typename Cst::size_type	times = `100000`
	)

Test performance of the depth first iterator of a CST.

Parameters:

cst	The CST that should be tested.
times	The number of times the depth first iterator should be incremented.

Details: This method increments the depth first search iterator of a CST n times.

template<class Cst >

void sdsl::test_cst_dfs_iterator_and_depth	(	Cst &	cst,
		typename Cst::size_type	times = `1000000`,
		bool	output = `false`
	)

Test performance of the depth first iterator and the LCP array of a CST.

Parameters:

cst	The CST that should be tested.
times	The number of times the depth first iterator should be incremented.

Details: This method increments the depth first search iterator of a CST n times and calculates the depth for each visited node.

template<class Cst >

void sdsl::test_cst_dfs_iterator_and_id	(	Cst &	cst,
		typename Cst::size_type	times = `1000000`,
		bool	output = `false`
	)

Test performance of the depth first iterator and the id method of the CST.

Parameters:

cst	The CST that should be tested.
times	The number of times the depth first iterator should be incremented.

Details: This method increments the depth first search iterator of a CST n times and calculates the function id for each visited node.

template<class Cst >

void sdsl::test_cst_matching_statistics	(	const Cst &	cst,
		unsigned char *	S2,
		typename Cst::size_type	n2
	)

Test matching statistics.

Parameters:

cst	Compressed suffix tree of sequence S1 of length n1
S2	Pointer to the unsigned char array S2.
n2	The length of S2.

template<class Cst >

void sdsl::test_cst_parent_operation	(	const Cst &	cst,
		typename Cst::size_type	times = `100000`,
		uint64_t	x = `17`
	)

Test the speed of the parent operation.

Parameters:

Cst	The compressed suffix tree
times	Number of times a traversal from a random leaf to the root\ is started to collect nodes for which the parent operation is performed.

template<class Cst >

void sdsl::test_cst_sibling_operation	(	const Cst &	cst,
		typename Cst::size_type	times = `100000`,
		uint64_t	x = `17`
	)

Test the speed of the sibling operation.

Parameters:

Cst	The compressed suffix tree
times	Number of times a traversal from a random leaf to the root\ is started to collect nodes for which the child operation is performed.

template<class Lcp >

void sdsl::test_lcp_random_sequential_access	(	Lcp &	lcp,
		typename Lcp::size_type	times = `1000000`,
		typename Lcp::size_type	seq_len = `64`
	)

Make random sequential accesse to an LCP array.

Parameters:

lcp	The lcp data structure
times	The number of random accesses
seq_len	The number of sequential accesses after each random access This test was described in the master thesis of Rodrigo Canovas.

template<class Lcp >

void sdsl::test_lcp_sequential_access	(	Lcp &	lcp,
		typename Lcp::size_type	times = `10000000`
	)

Make sequential accesses to an LCP array.

The access time for lcp sequential access is not important in practice, as sequential access should be realized by streaming the uncompressed lcp array from disk.

template<class Csa >

void sdsl::test_pattern_matching	(	const Csa &	csa,
		const char *	file_name,
		const typename Csa::size_type	pattern_len = `20`,
		typename Csa::size_type	times = `1000000`
	)

Test speed for pattern matching.

Selection of patterns: The pattern are selected from: random position in the original Do we really need file_name? We can also extract text from the csa...

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Function Documentation