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:

• one storing only the entries that are a multiple of K, { SA[i] : (SA[i] = 0 mod K) }
• one storing only the entries whose index is a multiple of K, { SA[i] : (i = 0 mod K) }

NVBIO provides both:

• SSA_value_multiple
• SSA_index_multiple

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:

• SSA_value_multiple_device
• SSA_index_multiple_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
}

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

Functions
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)

inline

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)

inline

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.