Collaboration diagram for Algorithm:

Functions
template<fm_index_specialisation index_t, typename queries_t , typename configuration_t = decltype(search_cfg::default_configuration)>
auto	seqan3::search (queries_t &&queries, index_t const &index, configuration_t const &cfg=search_cfg::default_configuration)
	Search a query or a range of queries in an index. More...

Detailed Description

Provides seqan3::search.

Search Algorithms

The Search module offers a simple unified interface that allows searching FM indices and choosing the best algorithm based on the index at hand.

FM Indices

The search algorithms for FM indices implement either a trivial backtracking approach or an optimum search scheme. Latter are currently only available for searches with up to and including three errors using bidirectional indices. The optimum search schemes will be improved in the future to handle unidirectional indices and higher error counts.

Reference

Kianfar, K., Pockrandt, C., Torkamandi, B., Luo, H., & Reinert, K. (2018).

Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index. bioRxiv, 301085. https://doi.org/10.1101/301085

Function Documentation

◆ search()

template<fm_index_specialisation index_t, typename queries_t , typename configuration_t = decltype(search_cfg::default_configuration)>

auto seqan3::search	(	queries_t &&	queries,
		index_t const &	index,
		configuration_t const &	cfg = `search_cfg::default_configuration`
	)

inline

Search a query or a range of queries in an index.

Template Parameters

index_t	Must model seqan3::fm_index_specialisation.
queries_t	Must model std::ranges::random_access_range over the index's alphabet and std::ranges::sized_range. A range of queries must additionally model std::ranges::forward_range and std::ranges::sized_range.

Parameters

[in]	queries	A single query or a range of queries.
[in]	index	String index to be searched.
[in]	cfg	A configuration object specifying the search parameters (e.g. number of errors, error types, output format, etc.).

Returns

seqan3::text_layout	seqan3::search_cfg::output	Result of seqan3::search()
single	text_position	A `std::vector<size_t>` representing text positions where the search was successful.
single	index_cursor	A `std::vector<typename index_t::cursor_type>` containing index_cursors at the text positions where the search was successful.
collection	text_position	A `std::vector<std::pair<size_t, size_t>>` where the first element of the `std::pair` specifies the text index in the collection and the second element contains the position in that text of the collection.
collection	index_cursor	A `std::vector<typename index_t::cursor_type>` containing index_cursors at the text positions where the search was successful.

Header File

#include <seqan3/search/algorithm/search.hpp>

Complexity

Each query with $e$ errors takes $O(|query|^e)$ where $e$ is the maximum number of errors.

Exceptions

Strong exception guarantee if iterating the query does not change its state and if invoking a possible delegate specified in cfg also has a strong exception guarantee; basic exception guarantee otherwise.

Functions