NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Types | Public Methods | Public Members | Related Functions | List of all members
nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 > Struct Template Reference

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
TRankDictionarya rank dictionary (see Rank Dictionaries)
TSuffixArraya sampled suffix array context implementing the SSAInterface (see Sampled Suffix Arrays)
TL2an 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)
 

Member Typedef Documentation

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
typedef TRankDictionary::text_type nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::bwt_type

Definition at line 348 of file fmindex.h.

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

Definition at line 351 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
typedef if_equal<TL2,null_type,const index_type*,TL2>::type nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::L2_iterator

Definition at line 355 of file fmindex.h.

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

Definition at line 352 of file fmindex.h.

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

Definition at line 347 of file fmindex.h.

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

Definition at line 349 of file fmindex.h.

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

Definition at line 353 of file fmindex.h.

Constructor & Destructor Documentation

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::fm_index ( )
inline

Definition at line 367 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::fm_index ( const index_type  length,
const index_type  primary,
const L2_iterator  L2,
const TRankDictionary  rank_dict,
const TSuffixArray  sa 
)
inline

Definition at line 369 of file fmindex.h.

Member Function Documentation

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bwt_type nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::bwt ( ) const
inline

Definition at line 363 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::count ( const uint32  c) const
inline

Definition at line 359 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::L2 ( const uint32  c) const
inline

Definition at line 360 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::length ( ) const
inline

Definition at line 357 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::primary ( ) const
inline

Definition at line 358 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE TRankDictionary nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::rank_dict ( ) const
inline

Definition at line 361 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE TSuffixArray nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::sa ( ) const
inline

Definition at line 362 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::symbol_count ( ) const
inline

Definition at line 364 of file fmindex.h.

template<typename TRankDictionary, typename TSuffixArray, typename TL2 = null_type>
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::fm_index< TRankDictionary, TSuffixArray, TL2 >::symbol_size ( ) const
inline

Definition at line 365 of file fmindex.h.

Member Data Documentation

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

Definition at line 384 of file fmindex.h.

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

Definition at line 382 of file fmindex.h.

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

Definition at line 383 of file fmindex.h.

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

Definition at line 385 of file fmindex.h.

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

Definition at line 386 of file fmindex.h.


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