Detailed description

template< uint32 SYMBOL_SIZE_T, uint32 K, typename TextString, typename OccIterator, typename CountTable>
struct nvbio::rank_dictionary< SYMBOL_SIZE_T, K, TextString, OccIterator, CountTable >

A rank dictionary data-structure which, given a text and a sparse occurrence table, can answer, in O(1) time, queries of the kind "how many times does character c occurr in the substring text[0:i] ?"

: NOTE: the O(1) time refers to the complexity in the length of the text; more properly, if the alphabet contains s characters (i.e. if the number of bits per symbol is b = log(s)), the complexity is O(log(s)). Similarly, the amount of space needed for a sparse occurrence table is O(n s). In other words, the amount of space needed is exponential in the number of bits per character.

: For a more compact data structure requiring O(n log(s)) storage, useful with larger alphabets, please refer to Wavelet Trees.

Template Parameters

SYMBOL_SIZE_T	the size of the alphabet, in bits
K	the sparsity of the occurrence table
TextString	the text string type
OccIterator	the occurrence table iterator type
CountTable	an auxiliary lookup table used to count the number of occurrences of all characters in a given byte

Definition at line 83 of file rank_dictionary.h.

#include <rank_dictionary.h>

Public Types
typedef TextString	text_type

typedef OccIterator	occ_iterator

typedef CountTable	count_table_type

typedef vector_traits < typename std::iterator_traits < occ_iterator >::value_type > ::value_type	index_type

typedef vector_type < index_type, 2 >::type	range_type

typedef vector_type < index_type, 2 >::type	vec2_type

typedef vector_type < index_type, 4 >::type	vec4_type

typedef StaticVector < index_type, SYMBOL_COUNT >	vector_type

Public Methods
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	rank_dictionary ()

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	rank_dictionary (const TextString _text, const OccIterator _occ, const CountTable _count_table)

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	symbol_count () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	symbol_size () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE text_type	text ()

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE text_type	text () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE occ_iterator	occ ()

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE occ_iterator	occ () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE count_table_type	count_table ()

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE count_table_type	count_table () const

Public Members
TextString	m_text
	the dictionary's text More...

OccIterator	m_occ
	the dictionary's occurrence table More...

CountTable	m_count_table

Static Public Members
static const uint32	BLOCK_INTERVAL = K

static const uint32	SYMBOL_SIZE = SYMBOL_SIZE_T

static const uint32	SYMBOL_COUNT = 1u << SYMBOL_SIZE

Related Functions
(Note that these are not member functions.)
template<uint32 SYMBOL_SIZE, uint32 K, typename SymbolIterator , typename IndexType >
void	build_occurrence_table (SymbolIterator begin, SymbolIterator end, IndexType occ, IndexType cnt=NULL)

template<uint32 SYMBOL_SIZE_T, uint32 K, typename TextString , typename OccIterator , typename CountTable >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint8	text (const rank_dictionary< SYMBOL_SIZE_T, K, TextString, OccIterator, CountTable > &dict, const uint32 i)

template<uint32 SYMBOL_SIZE_T, uint32 K, typename TextString , typename OccIterator , typename CountTable >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint8	text (const rank_dictionary< SYMBOL_SIZE_T, K, TextString, OccIterator, CountTable > &dict, const uint64 i)

template<uint32 SYMBOL_SIZE_T, uint32 K, typename TextString , typename OccIterator , typename CountTable , typename IndexType >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE IndexType	rank (const rank_dictionary< SYMBOL_SIZE_T, K, TextString, OccIterator, CountTable > &dict, const IndexType i, const uint32 c)

template<uint32 SYMBOL_SIZE_T, uint32 K, typename TextString , typename OccIterator , typename CountTable , typename IndexType >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE vector_type < IndexType, 2 >::type	rank (const rank_dictionary< SYMBOL_SIZE_T, K, TextString, OccIterator, CountTable > &dict, const typename vector_type< IndexType, 2 >::type range, const uint32 c)

template<uint32 K, typename TextString , typename OccIterator , typename CountTable , typename IndexType >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE vector_type < IndexType, 4 >::type	rank4 (const rank_dictionary< 2, K, TextString, OccIterator, CountTable > &dict, const IndexType i)

template<uint32 K, typename TextString , typename OccIterator , typename CountTable >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	rank4 (const rank_dictionary< 2, K, TextString, OccIterator, CountTable > &dict, const uint2 range, uint4 outl, uint4 outh)

template<uint32 K, typename TextString , typename OccIterator , typename CountTable >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	rank4 (const rank_dictionary< 2, K, TextString, OccIterator, CountTable > &dict, const uint64_2 range, uint64_4 outl, uint64_4 outh)

template<uint32 SYMBOL_SIZE, uint32 K, typename TextString , typename OccIterator , typename CountTable >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable >::vector_type	rank_all (const rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable > &dict, const typename rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable >::index_type i)

template<uint32 SYMBOL_SIZE, uint32 K, typename TextString , typename OccIterator , typename CountTable >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	rank_all (const rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable > &dict, const typename rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable >::index_type i, typename rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable >::vector_type *out)

template<uint32 SYMBOL_SIZE, uint32 K, typename TextString , typename OccIterator , typename CountTable >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	rank_all (const rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable > &dict, const typename rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable >::range_type range, typename rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable >::vector_type outl, typename rank_dictionary< SYMBOL_SIZE, K, TextString, OccIterator, CountTable >::vector_type outh)