tudocomp
– The TU Dortmund Compression Framework
tdc::bwt Namespace Reference

Contains functionality for computing and decoding the Burrows-Wheeler transform (BWT) of a text. More...

Functions

template<typename text_t , typename sa_t >
text_t::value_type bwt (const text_t &text, const sa_t &sa, const size_t i)
 Computes the value BWT[i] of a text T given its suffix array SA Runs in O(1) time since BWT[i] = SA[(T[i]-1) mod |SA|]. More...
 
template<typename bwt_t >
len_compact_tcompute_LF (const bwt_t &bwt, const size_t bwt_length)
 Computes the LF table used for decoding the BWT Input is a BWT and its length. More...
 
template<typename bwt_t >
std::string decode_bwt (const bwt_t &bwt)
 Decodes a BWT It is assumed that the BWT is stored in a container with access to operator[] and .size() More...
 

Detailed Description

Contains functionality for computing and decoding the Burrows-Wheeler transform (BWT) of a text.

Function Documentation

◆ bwt()

template<typename text_t , typename sa_t >
text_t::value_type tdc::bwt::bwt ( const text_t &  text,
const sa_t &  sa,
const size_t  i 
)
inline

Computes the value BWT[i] of a text T given its suffix array SA Runs in O(1) time since BWT[i] = SA[(T[i]-1) mod |SA|].

Definition at line 20 of file bwt.hpp.

◆ compute_LF()

template<typename bwt_t >
len_compact_t* tdc::bwt::compute_LF ( const bwt_t &  bwt,
const size_t  bwt_length 
)

Computes the LF table used for decoding the BWT Input is a BWT and its length.

Definition at line 29 of file bwt.hpp.

◆ decode_bwt()

template<typename bwt_t >
std::string tdc::bwt::decode_bwt ( const bwt_t &  bwt)

Decodes a BWT It is assumed that the BWT is stored in a container with access to operator[] and .size()

Definition at line 77 of file bwt.hpp.