All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Enumerations | Functions
Suffix Tries

Detailed Description


struct  nvbio::TrieNode< ALPHABET_SIZE_T, TYPE_T >
struct  nvbio::TrieNode5< TYPE_T >
struct  nvbio::TrieNode< 2, TYPE_T >
struct  nvbio::TrieNode< 3, TYPE_T >
struct  nvbio::TrieNode< 4, TYPE_T >
struct  nvbio::TrieNode< 5, TYPE_T >
struct  nvbio::SuffixTrie< ALPHABET_SIZE_T, NodeIterator >


enum  nvbio::TrieType { nvbio::CompressedTrie, nvbio::UncompressedTrie }


template<typename TrieType , typename NodeVector >
void nvbio::build_suffix_trie (const TrieType &in_trie, NodeVector &out_nodes)

Enumeration Type Documentation

A suffix trie can be stored either with an uncompressed layout, where each inner node reseves storage for |alphabet| children and some of them are marked as invalid, or with a compressed one, where only storage for the active children is actually reserved; the latter type requires just a little more logic during traversal, as a popcount is necessary to select the child corresponding to the i-th character.


Definition at line 62 of file suffix_trie.h.

Function Documentation

template<typename TrieType , typename NodeVector >
void nvbio::build_suffix_trie ( const TrieType &  in_trie,
NodeVector &  out_nodes 

copy a generic trie into a SuffixTrie.

Template Parameters
TrieTypeinput trie
NodeVectoroutput vector of trie nodes; this class must expose the following interface:
struct NodeVector
// return the vector size
uint32 size();
// resize the vector
void resize(uint32 size);
// return a reference to the i-th node
value_type& operator[] (uint32 i);


// a string set of some kind
string_set_type string_set;
// an implicit suffix trie over a sorted dictionary
SortedDictionarySuffixTrie<2,string_set_type> sorted_dictionary(
string_set.size() );
// build an explicit suffix trie
std::vector< TrieNode<2,CompressedTrie> > trie_nodes;
build_suffix_trie( sorted_dictionary, trie_nodes );

Definition at line 274 of file suffix_trie_inl.h.