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

Detailed Description

A Sampled Suffix Array is a succint suffix array which has been sampled at a subset of its indices. Ferragina & Manzini showed that given such a data structure and the BWT of the original text it is possible to reconstruct the missing locations. Two such data structures have been proposed, with different tradeoffs:

NVBIO provides both:

Unlike for the rank_dictionary, which is a storage-free class, these classes own the (internal) storage needed to represent the underlying data structures, which resides on the host. Similarly, the module provides some counterparts that hold the corresponding storage for the device:

While these classes hold device data, they are meant to be used from the host and cannot be directly passed to CUDA kernels. Plain views (see Host & Device), or contexts, can be obtained with the usual plain_view() function.

The contexts expose the following SSA interface:

struct SSA
// return the i-th suffix array entry, if present
bool fetch(const uint32 i, uint32& r) const
// return whether the i-th suffix array is present
bool has(const uint32 i) const


struct  nvbio::SSA_index_multiple_device< K, index_type >
struct  nvbio::SSA_value_multiple_context< SSAIterator, BitmaskIterator, BlockIterator >
struct  nvbio::SSA_value_multiple
struct  nvbio::SSA_value_multiple_device
struct  nvbio::SSA_index_multiple_context< K, Iterator >
struct  nvbio::SSA_index_multiple< K, index_type >


SSA_value_multiple::plain_view_type nvbio::plain_view (const SSA_value_multiple &vec)
SSA_value_multiple_device::plain_view_type nvbio::plain_view (const SSA_value_multiple_device &vec)
template<uint32 K, typename index_type >
SSA_index_multiple< K,
index_type >::plain_view_type 
nvbio::plain_view (const SSA_index_multiple< K, index_type > &vec)

Function Documentation

SSA_value_multiple::plain_view_type nvbio::plain_view ( const SSA_value_multiple &  vec)

return the plain view of a SSA_value_multiple

Definition at line 349 of file ssa.h.

SSA_value_multiple_device::plain_view_type nvbio::plain_view ( const SSA_value_multiple_device &  vec)

return the plain view of a SSA_value_multiple_device

Definition at line 354 of file ssa.h.

template<uint32 K, typename index_type >
SSA_index_multiple<K,index_type>::plain_view_type nvbio::plain_view ( const SSA_index_multiple< K, index_type > &  vec)

return the plain view of a SSA_index_multiple

Definition at line 359 of file ssa.h.