Suffix Tries

Detailed Description

Classes
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 >

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

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

Enumeration Type Documentation

enum nvbio::TrieType

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.

Enumerator
CompressedTrie
UncompressedTrie

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

TrieType	input trie
NodeVector	output 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);
}

Example:

// 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.begin(),
    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.