SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
 All Classes Namespaces Files Functions Variables Typedefs Friends
Public Types | Public Member Functions | Static Public Member Functions | Public Attributes
sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support > Class Template Reference

A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog. More...

#include <cst_sct3.hpp>

List of all members.

Public Types

typedef Csa::value_type value_type
typedef
cst_dfs_const_forward_iterator
< cst_sct3
const_iterator
typedef
cst_bottom_up_const_forward_iterator
< cst_sct3
const_bottom_up_iterator
typedef const value_type const_reference
typedef const_reference reference
typedef const_reference * pointer
typedef const pointer const_pointer
typedef Csa::size_type size_type
typedef size_type cst_size_type
typedef ptrdiff_t difference_type
typedef Csa csa_type
typedef Lcp::template type
< cst_sct3 >::lcp_type 
lcp_type
typedef Bp_support bp_support_type
typedef Csa::pattern_type pattern_type
typedef Csa::char_type char_type
typedef bp_interval< size_type > node_type
 Type for the nodes in the tree.
typedef Rank_support fc_rank_support_type
typedef cst_tag index_category

Public Member Functions

 cst_sct3 ()
 Default Constructor.
template<uint8_t int_width, class size_type_class , uint8_t int_width_1, class size_type_class_1 , uint8_t int_width_2, class size_type_class_2 >
 cst_sct3 (const std::string &cst_file_name, int_vector_file_buffer< int_width, size_type_class > &lcp_buf, int_vector_file_buffer< int_width_1, size_type_class_1 > &sa_buf, int_vector_file_buffer< int_width_2, size_type_class_2 > &isa_buf, std::string dir="./", bool build_ony_bps=false)
 cst_sct3 (tMSS &file_map, const std::string &dir, const std::string &id, bool build_only_bps=false)
 cst_sct3 (const cst_sct3 &cst)
 Copy constructor.
 ~cst_sct3 ()
 Default Destructor.
void construct (tMSS &file_map, const std::string &dir, const std::string &id, bool build_only_bps=false)
size_type size () const
 Number of leaves of the suffix tree.
bool empty () const
 Returns if the data strucutre is empty.
void swap (cst_sct3 &cst)
 Swap method for cst_sct3.
const_iterator begin () const
 Returns a const_iterator to the first element of a depth first traversal of the tree.
const_iterator end () const
 Returns a const_iterator to the element after the last element of a depth first traversal of the tree.
const_bottom_up_iterator begin_bottom_up () const
 Returns an iterator to the first element of a bottom-up traversal of the tree.
const_bottom_up_iterator end_bottom_up () const
 Returns an iterator to the element after the last element of a bottom-up traversal of the tree.
cst_sct3operator= (const cst_sct3 &cst)
 Assignment Operator.
bool operator== (const cst_sct3 &cst) const
 Equality Operator.
bool operator!= (const cst_sct3 &cst) const
 Unequality Operator.
size_type serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
 Serialize to a stream.
void load (std::istream &in)
 Load from a stream.
node_type root () const
 Return the root of the suffix tree.
bool is_leaf (const node_type &v) const
 Decide if a node is a leaf in the suffix tree.
node_type ith_leaf (size_type i) const
 Return the i-th leaf (1-based from left to right) of the suffix tree.
size_type leaves_in_the_subtree (const node_type &v) const
 Calculate the number of leaves in the subtree rooted at node v.
node_type leftmost_leaf_in_the_subtree (const node_type &v) const
 Calculates the leftmost leaf in the subtree rooted at node v.
node_type rightmost_leaf_in_the_subtree (const node_type &v) const
 Calculates the rightmost leaf in the subtree rooted at node v.
size_type lb (const node_type &v) const
 Calculates the index of the leftmost leaf in the corresponding suffix array.
size_type rb (const node_type &v) const
 Calculates the index of the rightmost leaf in the corresponding suffix array.
node_type parent (const node_type &v) const
 Calculate the parent node of a node v.
node_type sibling (const node_type &v) const
 Returns the next sibling of node v.
node_type ith_child (const node_type &v, size_type i) const
 Get the ith child of a node v.
size_type degree (const node_type &v) const
 Get the number of children of a node v.
node_type sibling_naive (const node_type &v) const
node_type child (const node_type &v, const unsigned char c, size_type &char_pos) const
 Get the child w of node v which edge label (v,w) starts with character c.
node_type child (const node_type &v, const unsigned char c)
 Get the child w of node v which edge label (v,w) starts with character c.
unsigned char edge (const node_type &v, size_type d) const
 Returns the d-th character (1-based indexing) of the edge-label pointing to v.
node_type lca (node_type v, node_type w) const
 Calculate the lowest common ancestor (lca) of two nodes v and w of the suffix tree.
size_type depth (const node_type &v) const
 Returns the string depth of node v.
size_type node_depth (node_type v) const
 Returns the node depth of node v.
node_type sl (const node_type &v) const
 Compute the suffix link of node v.
node_type wl (const node_type &v, const unsigned char c) const
 Compute the Weiner link of node v and character c.
size_type sn (const node_type &v) const
 Computes the suffix number of a leaf node v.
size_type id (const node_type &v) const
 Computes a unique identification number for a node of the suffx tree in the range [0..nodes()-1].
node_type inv_id (size_type id)
 Computes the node for such that id(v)=id.
size_type nodes () const
 Get the number of nodes of the suffix tree.
node_type node (size_type lb, size_type rb, size_type l=0) const
 Get the node in the suffix tree which corresponds to the lcp-interval [lb..rb].
size_type tlcp_idx (size_type i) const
 Maps an index i to the position in TLCP where LCP[i] can be found.

Static Public Member Functions

static size_type max_size ()
 Returns the largest size that cst_sct3 can ever have.

Public Attributes

const Csa & csa
 The compressed suffix array the suffix tree is based on.
const lcp_type & lcp
 The lcp array the suffix tree is based on.
const bit_vectorbp
 The balanced parentheses sequence of the Super-Cartesian tree the suffix tree is based on.
const bp_support_type & bp_support
 The balanced parentheses sequence support for member bp.
const bit_vectorfirst_child_bv
const fc_rank_support_type & first_child_rank

Detailed Description

template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
class sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >

A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog.

The CST is parameterized by

It also contains a sdsl::bit_vector which represents the balanced parentheses sequence of the Super-Cartesian tree of the lcp array. This bit_vector can be accessed via the member $bp$. Another sdsl::bit_vector stores information, if a node is a first child of another node. This bit_vector can be access via the member first_child_bv and takes $n$ bits.

A node $v$ of the csa_sct is represented by an sdsl::bp_interval . The size of the sdsl::cst_sct3 is smaller than the size of a sdsl::cst_sada since the tree topology needs only $2n+n=3n$ bits in contrast to the $4n$ bits in sdsl::cst_sada.

Applications of the CST: The compressed suffix tree could be used for string matching and many other application in sequence analysis. 17 applications are in the book "Algorithms on Strings, Trees, and Sequences" of Dan Gusfield.


Member Function Documentation

template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
const_iterator sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::begin ( ) const [inline]

Returns a const_iterator to the first element of a depth first traversal of the tree.

Required for the STL Container Concept.

See also:
end
template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
bool sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::empty ( ) const [inline]

Returns if the data strucutre is empty.

Required for the Container Concept of the STL.A

See also:
size
template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
const_iterator sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::end ( ) const [inline]

Returns a const_iterator to the element after the last element of a depth first traversal of the tree.

Required for the STL Container Concept.

See also:
begin.
template<class Csa , class Lcp , class Bp_support , class Rank_support >
void sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::load ( std::istream &  in)

Load from a stream.

Parameters:
inInputstream to load the data structure from.
template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
static size_type sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::max_size ( ) [inline, static]

Returns the largest size that cst_sct3 can ever have.

Required for the Container Concept of the STL.

See also:
size
template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
bool sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::operator!= ( const cst_sct3< Csa, Lcp, Bp_support, Rank_support > &  cst) const

Unequality Operator.

Two Instances of cst_sct3 are equal if not all their members are equal.

Required for the Equality Comparable Concept of the STL.
See also:
operator==
template<class Csa , class Lcp , class Bp_support , class Rank_support >
cst_sct3< Csa, Lcp, Bp_support, Rank_support > & sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::operator= ( const cst_sct3< Csa, Lcp, Bp_support, Rank_support > &  cst)

Assignment Operator.

Required for the Assignable Concept of the STL.

template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
bool sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::operator== ( const cst_sct3< Csa, Lcp, Bp_support, Rank_support > &  cst) const

Equality Operator.

Two Instances of cst_sct3 are equal if all their members are equal.

Required for the Equality Comparable Concept of the STL.
See also:
operator!=
template<class Csa , class Lcp , class Bp_support , class Rank_support >
cst_sct3< Csa, Lcp, Bp_support, Rank_support >::size_type sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::serialize ( std::ostream &  out,
structure_tree_node v = NULL,
std::string  name = "" 
) const

Serialize to a stream.

Parameters:
outOutstream to write the data structure.
Returns:
The number of written bytes.
template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
size_type sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::size ( ) const [inline]

Number of leaves of the suffix tree.

Required for the Container Concept of the STL.

See also:
max_size, empty
template<class Csa = csa_wt<>, class Lcp = lcp_support_tree<lcp_wt<> >, class Bp_support = bp_support_sada<>, class Rank_support = rank_support_v5<>>
void sdsl::cst_sct3< Csa, Lcp, Bp_support, Rank_support >::swap ( cst_sct3< Csa, Lcp, Bp_support, Rank_support > &  cst) [inline]

Swap method for cst_sct3.

The swap method can be defined in terms of assignment. This requires three assignments, each of which, for a container type, is linear in the container's size. In a sense, then, a.swap(b) is redundant. This implementation guaranties a run-time complexity that is constant rather than linear.

Parameters:
cstcst_sct3 to swap.

Required for the Assignable Conecpt of the STL.


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