A Wavelet Tree class for byte sequences. More...

#include <wt_rlmn.hpp>

Public Types
typedef int_vector::size_type	size_type
typedef unsigned char	value_type
typedef BitVector	bit_vector_type
typedef RankSupport	rank_support_type
typedef SelectSupport	select_support_type
typedef WaveletTree	wt_type
Public Member Functions
	wt_rlmn (const unsigned char *rac, size_type size)
	Constructor.
template<class size_type_class >
	wt_rlmn (int_vector_file_buffer< 8, size_type_class > &rac, size_type size)
template<class size_type_class >
void	construct (int_vector_file_buffer< 8, size_type_class > &rac, size_type size)
	Construct the wavelet tree from a random access container.
	wt_rlmn (const wt_rlmn &wt)
	Copy constructor.
wt_rlmn &	operator= (const wt_rlmn &wt)
	Assignment operator.
void	swap (wt_rlmn &wt)
	Swap operator.
size_type	size () const
	Returns the size of the original vector.
bool	empty () const
	Returns whether the wavelet tree contains no data.
value_type	operator[] (size_type i) const
	Recovers the ith symbol of the original vector.
size_type	rank (size_type i, value_type c) const
	Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.
size_type	rank_ith_symbol (size_type i, value_type &c) const
	Calculates how many occurences of symbol wt[i] are in the prefix [0..i-1] of the supported sequence.
size_type	select (size_type i, value_type c) const
	Calculates the ith occurence of the symbol c in the supported vector.
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
	Serializes the data structure into the given ostream.
void	load (std::istream &in)
	Loads the data structure from the given istream.
void	print_info () const
Public Attributes
const size_type &	sigma

Detailed Description

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>>
class sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >

A Wavelet Tree class for byte sequences.

A wavelet tree is build for a vector of characters over the alphabet $\Sigma$ . This class should be used only for small alphabets $\Sigma \ll n$ (see wt_int for a wavelet tree for big alphabets). The wavelet tree $wt$ consists of a tree of bitvectors and provides three efficient methods:

The "[]"-operator: returns the ith symbol of vector for which the wavelet tree was build for.
The rank method: returns the number of occurences of symbol 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 jth occurrence of symbol $c$ .

Space complexity: $nH_0 + 2|\Sigma|\log n + 2n + o(n)$ bits, where is the size of the vector the wavelet tree was build for.

Note: This implementation is based on the idea of Veli Mäkinen and Gonzalo Navarro presented in the paper "Succint Suffix Arrays Based on Run-Length Encoding" (CPM 2005)

Template Parameters:

BitVector	Type of the bitvector which is used to represent bf and bl which mark the head of each run in the original sequence.
RankSupport	Type of the rank support for bitvectors bf and bl.
SelectSupport	Type of the select support for bitvectors bf and lb.
WaveletTree	Type of the wavelet tree for the string consisting of the heads of the runs of the original sequence.

Constructor & Destructor Documentation

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>>

sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >::wt_rlmn	(	const unsigned char *	rac,
		size_type	size
	)		`[inline]`

Constructor.

   \param rac Reference to the vector (or unsigned char array) for which the wavelet tree should be build.
   \param size Size of the prefix of the vector (or unsigned char array) for which the wavelet tree should be build.
   \par Time complexity

$\Order{n\log|\Sigma|}$ , where $n=size$

Member Function Documentation

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>>

template<class size_type_class >

void sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >::construct	(	int_vector_file_buffer< 8, size_type_class > &	rac,
		size_type	size
	)		`[inline]`

Construct the wavelet tree from a random access container.

Parameters:

rac	A random access container
size	The length of the prefix of the random access container, for which the wavelet tree should be build

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>>

value_type sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >::operator[] ( size_type i ) const [inline]

Recovers the ith symbol of the original vector.

Parameters:

i	The index of the symbol in the original vector. $i \in [0..size()-1]$

Returns:: The ith symbol of the original vector.

Time complexity: $\Order{H_0}$ on average, where is the zero order entropy of the sequence

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>>

size_type sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >::rank	(	size_type	i,
		value_type	c
	)		const `[inline]`

Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.

Parameters:

i	The exclusive index of the prefix range [0..i-1], so $i\in[0..size()]$ .
c	The symbol to count the occurences in the prefix.

Returns:: The number of occurences of symbol c in the prefix [0..i-1] of the supported vector.

Time complexity: $\Order{H_0}$ on average, where is the zero order entropy of the sequence

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>>

size_type sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >::rank_ith_symbol	(	size_type	i,
		value_type &	c
	)		const `[inline]`

Calculates how many occurences of symbol wt[i] are in the prefix [0..i-1] of the supported sequence.

   \param i The index of the symbol.

Parameters:

c	Reference that will contain the symbol at position i after the execution of the method.

Returns:: The number of occurences of symbol wt[i] in the prefix [0..i-1]

Time complexity: $\Order{H_0}$

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>>

size_type sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >::select	(	size_type	i,
		value_type	c
	)		const `[inline]`

Calculates the ith occurence of the symbol c in the supported vector.

Parameters:

i	The ith occurence. $i\in [1..rank(size(),c)]$ .
c	The symbol c.

Time complexity: $\Order{H_0}$ on average, where is the zero order entropy of the sequence

The documentation for this class was generated from the following file:

sdsl/include/sdsl/wt_rlmn.hpp

Public Types

Public Member Functions

Public Attributes

Detailed Description

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>> class sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >

Constructor & Destructor Documentation

Member Function Documentation

template<class BitVector = sd_vector<>, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class WaveletTree = wt_huff<>>
class sdsl::wt_rlmn< BitVector, RankSupport, SelectSupport, WaveletTree >