Detailed description

template< typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
struct nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >

: This class represents an FM-Index, i.e. the self-compressed text index by Ferragina & Manzini. An FM-Index is built on top of the following ingredients:

the BWT of a text T
a rank dictionary (rank_dictionary) of the given BWT
a sampled suffix array of T

: Given the above, it allows to count and locate all the occurrences in T of arbitrary patterns P in O(length(P)) time. Moreover, it does so with an incremental algorithm that proceeds character by character, a fundamental property that allows to implement sophisticated pattern matching algorithms based on backtracking.

: fm_index is storage-free, in the sense it doesn't directly hold any allocated data - hence it can be instantiated both on host and device data-structures, and it can be conveniently passed as a kernel parameter (provided its template parameters are also PODs)

Template Parameters

TRankDictionary	a rank dictionary (see Rank Dictionaries)
TSuffixArray	a sampled suffix array context implementing the SSAInterface (see Sampled Suffix Arrays)
TL2	an iterator to the L2 table, containing the exclusive sum of all character frequencies; if TL2 == null_type, a plain pointer will be used.

Definition at line 345 of file fmindex.h.

#include <fmindex.h>

Public Types
typedef TRankDictionary	rank_dictionary_type

typedef TRankDictionary::text_type	bwt_type

typedef TSuffixArray	suffix_array_type

typedef TRankDictionary::index_type	index_type

typedef TRankDictionary::range_type	range_type

typedef TRankDictionary::vector_type	vector_type

typedef if_equal< TL2, null_type, const index_type *, TL2 >::type	L2_iterator

Public Methods
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type	length () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type	primary () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type	count (const uint32 c) const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type	L2 (const uint32 c) const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE TRankDictionary	rank_dict () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE TSuffixArray	sa () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bwt_type	bwt () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	symbol_count () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	symbol_size () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	fm_index ()

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	fm_index (const index_type length, const index_type primary, const L2_iterator L2, const TRankDictionary rank_dict, const TSuffixArray sa)

Public Members
index_type	m_length

index_type	m_primary

L2_iterator	m_L2

TRankDictionary	m_rank_dict

TSuffixArray	m_sa

Related Functions
(Note that these are not member functions.)
template<typename TRankDictionary , typename TSuffixArray , typename TL2 >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::index_type	rank (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, typename fm_index< TRankDictionary, TSuffixArray, TL2 >::index_type k, uint8 c)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::range_type	rank (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, typename fm_index< TRankDictionary, TSuffixArray, TL2 >::range_type range, uint8 c)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE TRankDictionary::vec4_type	rank4 (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, typename fm_index< TRankDictionary, TSuffixArray, TL2 >::index_type k)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	rank4 (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, typename fm_index< TRankDictionary, TSuffixArray, TL2 >::range_type range, typename TRankDictionary::vec4_type outl, typename TRankDictionary::vec4_type outh)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 , typename Iterator >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::range_type	match (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, const Iterator pattern, const uint32 pattern_len)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 , typename Iterator >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::range_type	match (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, const Iterator pattern, const uint32 pattern_len, const typename fm_index< TRankDictionary, TSuffixArray, TL2 >::range_type range)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 , typename Iterator >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::range_type	match_reverse (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, const Iterator pattern, const uint32 pattern_len)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::range_type	inv_psi (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, const typename fm_index< TRankDictionary, TSuffixArray, TL2 >::index_type i)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::index_type	locate (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, const typename fm_index< TRankDictionary, TSuffixArray, TL2 >::index_type i)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::range_type	locate_ssa_iterator (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, const typename fm_index< TRankDictionary, TSuffixArray, TL2 >::index_type i)

template<typename TRankDictionary , typename TSuffixArray , typename TL2 >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE fm_index < TRankDictionary, TSuffixArray, TL2 > ::index_type	lookup_ssa_iterator (const fm_index< TRankDictionary, TSuffixArray, TL2 > &fmi, const typename fm_index< TRankDictionary, TSuffixArray, TL2 >::range_type it)