The SeqAn Bidirectional FM Index. More...
#include <seqan3/search/fm_index/bi_fm_index.hpp>
Public Types | |
Text types | |
using | alphabet_type = typename fm_index_type::alphabet_type |
The type of the underlying character of the indexed text. | |
using | size_type = typename sdsl_index_type::size_type |
Type for representing positions in the indexed text. | |
Cursor types | |
using | cursor_type = bi_fm_index_cursor< bi_fm_index > |
The type of the bidirectional cursor. | |
using | fwd_cursor_type = fm_index_cursor< fm_index_type > |
The type of the unidirectional cursor on the original text. | |
Public Member Functions | |
cursor_type | cursor () const noexcept |
Returns a seqan3::bi_fm_index_cursor on the index that can be used for searching. Cursor is pointing to the root node of the implicit affix tree. More... | |
bool | empty () const noexcept |
Checks whether the index is empty. More... | |
fwd_cursor_type | fwd_cursor () const noexcept |
Returns a unidirectional seqan3::fm_index_cursor on the original text of the bidirectional index that can be used for searching. More... | |
bool | operator!= (bi_fm_index const &rhs) const noexcept |
Compares two indices. More... | |
bool | operator== (bi_fm_index const &rhs) const noexcept |
Compares two indices. More... | |
template<cereal_archive archive_t> | |
void | serialize (archive_t &archive) |
Serialisation support function. More... | |
size_type | size () const noexcept |
Returns the length of the indexed text including sentinel characters. More... | |
Constructors, destructor and assignment | |
bi_fm_index ()=default | |
Defaulted. | |
bi_fm_index (bi_fm_index const &)=default | |
Defaulted. | |
bi_fm_index & | operator= (bi_fm_index const &)=default |
Defaulted. | |
bi_fm_index (bi_fm_index &&)=default | |
Defaulted. | |
bi_fm_index & | operator= (bi_fm_index &&)=default |
Defaulted. | |
~bi_fm_index ()=default | |
Defaulted. | |
template<std::ranges::range text_t> | |
bi_fm_index (text_t &&text) | |
Constructor that immediately constructs the index given a range. The range cannot be empty. More... | |
Static Public Attributes | |
static constexpr text_layout | text_layout_mode = text_layout_mode_ |
Indicates whether index is built over a collection. | |
Private Types | |
Index types | |
using | sdsl_index_type = sdsl_index_type_ |
The type of the underlying SDSL index for the original text. | |
using | rev_sdsl_index_type = sdsl::csa_wt< sdsl_wt_index_type::wavelet_tree_type, 10 '000 '000, 10 '000 '000, sdsl::sa_order_sa_sampling<>, sdsl::isa_sampling<>, sdsl_wt_index_type::alphabet_type > |
The type of the underlying SDSL index for the reversed text. | |
using | sdsl_char_type = typename sdsl_index_type::alphabet_type::char_type |
The type of the reduced alphabet type. (The reduced alphabet might be smaller than the original alphabet in case not all possible characters occur in the indexed text.) | |
using | sdsl_sigma_type = typename sdsl_index_type::alphabet_type::sigma_type |
The type of the alphabet size of the underlying SDSL index. | |
using | fm_index_type = fm_index< alphabet_t, text_layout_mode_, sdsl_index_type > |
The type of the underlying FM index for the original text. | |
using | rev_fm_index_type = detail::reverse_fm_index< alphabet_t, text_layout_mode_, rev_sdsl_index_type > |
The type of the underlying FM index for the reversed text. | |
Private Member Functions | |
template<std::ranges::range text_t> | |
void | construct (text_t &&text) |
Constructs the index given a range. The range cannot be an rvalue (i.e. a temporary object) and has to be non-empty. More... | |
Private Attributes | |
fm_index_type | fwd_fm |
Underlying FM index for the original text. | |
rev_fm_index_type | rev_fm |
Underlying FM index for the reversed text. | |
Friends | |
template<typename bi_fm_index_t > | |
class | bi_fm_index_cursor |
The SeqAn Bidirectional FM Index.
alphabet_t | The alphabet type; must model seqan3::semialphabet. |
text_layout_mode_ | Indicates whether this index works on a text collection or a single text. See seqan3::text_layout. |
sdsl_index_type_ | The type of the underlying SDSL index, must model seqan3::detail::sdsl_index. |
The seqan3::bi_fm_index is a fast and space-efficient bidirectional string index to search strings and collections of strings. In general, we recommend to favour the seqan3::bi_fm_index over the unidirectional seqan3::fm_index if you want to allow multiple errors when searching.
Here is a short example on how to build an index and search a pattern using an cursor. Please note that there is a very powerful search module with a high-level interface seqan3::search that encapsulates the use of cursors.
Here is an example using a collection of strings (e.g. a genome with multiple chromosomes or a protein database):
|
inline |
Constructor that immediately constructs the index given a range. The range cannot be empty.
text_t | The type of range to construct from; must model std::ranges::bidirectional_range. |
[in] | text | The text to construct from. |
|
inlineprivate |
Constructs the index given a range. The range cannot be an rvalue (i.e. a temporary object) and has to be non-empty.
text_t | The type of range to construct from; must model std::ranges::bidirectional_range. |
[in] | text | The text to construct from. |
No guarantee.
|
inlinenoexcept |
Returns a seqan3::bi_fm_index_cursor on the index that can be used for searching. Cursor is pointing to the root node of the implicit affix tree.
Constant.
No-throw guarantee.
|
inlinenoexcept |
Checks whether the index is empty.
true
if the index is empty, false
otherwise.Constant.
No-throw guarantee.
|
inlinenoexcept |
Returns a unidirectional seqan3::fm_index_cursor on the original text of the bidirectional index that can be used for searching.
Constant.
No-throw guarantee.
|
inlinenoexcept |
Compares two indices.
true
if the indices are unequal, false otherwise.Linear.
No-throw guarantee.
|
inlinenoexcept |
Compares two indices.
true
if the indices are equal, false otherwise.Linear.
No-throw guarantee.
|
inline |
Serialisation support function.
archive_t | Type of archive ; must satisfy seqan3::cereal_archive. |
archive | The archive being serialised from/to. |
|
inlinenoexcept |
Returns the length of the indexed text including sentinel characters.
Constant.
No-throw guarantee.