fm-index 0.3.1

FM index and its variant implementations for Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

//! This crate provides implementations of *FM-Index* and its variants.
//!
//! FM-Index, originally proposed by Paolo Ferragina and Giovanni Manzini [^1],
//! is a compressed full-text index which supports the following queries:
//!
//! - `count`: Given a pattern string, counts the number of its occurrences.
//! - `locate`: Given a pattern string, lists all positions of its occurrences.
//! - `extract`: Given an integer, gets the character of the text at that
//!   position.
//!
//! `fm-index` crate does not support the third query (extracting a character
//! from arbitrary position). Instead, it provides backward/forward iterators
//! that return the text characters starting from a search result.
//!
//! # Implementations
//!
//! This section describes the implementations of FM-Index and its variants.
//!
//! Throughout this documentation, we use the following notations:
//!
//! - _n_: the size of a text string
//! - _σ_: the number of bits needed to represent the characters in the text.
//!   This can be controlled by [`Text::max_character`].
//!
//! ## FM-Index ([`FMIndex`], [`FMIndexWithLocate`])
//!
//! This is a standard FM-index suitable for single-text use cases. It offers
//! a good balance between space efficiency and query performance, making it
//! a strong default choice for most applications.
//!
//! The implementation is based on Ferragina and Manzini's original work [^1].
//! The suffix array is constructed using the SA-IS algorithm [^3] in _O(n)_ time.
//!
//! The data structure consists of the following components:
//!
//! - A wavelet matrix ([`vers_vecs::WaveletMatrix`]) that stores the Burrows–Wheeler
//!   Transform (BWT) of the text. Its space complexity is _O(n log σ)_ bits.
//! - A `Vec<usize>` of length _O(σ)_, which stores the number of characters
//!   smaller than a given character in the text.
//! - (Only in [`FMIndexWithLocate`]) A sampled suffix array of length _O(n / 2^l)_,
//!   used to determine the positions of pattern occurrences.
//!
//! ## Run-Length FM-Index ([`RLFMIndex`], [`RLFMIndexWithLocate`])
//!
//! This variant is optimized for highly repetitive texts. It offers better compression
//! than the standard FM-index when the Burrows–Wheeler Transform contains long runs
//! of repeated characters. However, it is generally slower in query performance.
//!
//! The implementation is based on run-length encoded FM-indexing [^2]. The suffix
//! array is constructed with the SA-IS algorithm [^3] in _O(n)_ time.
//!
//! The data structure consists of the following components:
//!
//! - A wavelet matrix ([`vers_vecs::WaveletMatrix`]) that stores the run heads
//!   of the BWT. The space complexity is _O(r log σ)_ bits, where _r_ is the number
//!   of runs in the BWT.
//! - A succinct bit vector that encodes the run lengths of the BWT.
//! - A second succinct bit vector that encodes the run lengths of the BWT
//!   when sorted by the lexicographic order of run heads.
//! - A `Vec<usize>` of length _O(σ)_, which stores the number of characters
//!   smaller than a given character in the run heads.
//! - (Only in [`RLFMIndexWithLocate`]) A sampled suffix array of length _O(n / 2^l)_,
//!   used to determine the positions of pattern occurrences.
//!
//! ## FM-Index for Multiple Texts ([`FMIndexMultiPieces`], [`FMIndexMultiPiecesWithLocate`])
//!
//! This index is designed for multiple texts (text pieces) separated by a null character (`\0`).
//! The implementation is based on SXSI [^5].
//!
//! Each text piece is assigned a unique ID ([`PieceId`]).
//! The index supports locating the text piece ID for each search result.
//! It also supports searching for patterns that are prefixes or suffixes of
//! individual text pieces.
//!
//! The data structure consists of the following components:
//!
//! - A wavelet matrix ([`vers_vecs::WaveletMatrix`]) that stores the concatenated
//!   text pieces, separated by null characters (`\0`). The space complexity is
//!   _O(n log σ)_ bits.
//! - A `Vec<usize>` of length _O(σ)_, which stores the number of characters
//!   smaller than a given character.
//! - A `Vec<usize>` of length _O(d)_, where _d_ is the number of text
//!   pieces. This array maps between the suffix array and the text piece IDs.
//! - (Only in [`FMIndexMultiPiecesWithLocate`]) A sampled suffix array for the text pieces.
//!   Its length is _O(n / 2^l)_, and it is used to determine the position
//!   of each pattern occurrence in the text.
//!
//! [^1]: Ferragina, P., & Manzini, G. (2000). Opportunistic data structures
//!     with applications. Proceedings 41st Annual Symposium on Foundations
//!     of Computer Science, 390–398. <https://doi.org/10.1109/SFCS.2000.892127>
//!
//! [^2]: Mäkinen, V., & Navarro, G. (2005). Succinct suffix arrays based on
//!     run-length encoding. In Combinatorial Pattern Matching: 16th Annual Symposium,
//!     CPM 2005, Jeju Island, Korea, June 19-22, 2005. Proceedings 16 (pp. 45-56).
//!     Springer Berlin Heidelberg. <https://doi.org/10.1007/11496656_5>
//!
//! [^3]: Nong, G., Zhang, S., & Chan, W. H. (2010). Two efficient algorithms
//!     for linear time suffix array construction. IEEE transactions on computers,
//!     60(10), 1471-1484. <https://doi.org/10.1109/tc.2010.188>
//!
//! [^4]: Claude F., Navarro G. (2012). The Wavelet Matrix. In:
//!     Calderón-Benavides L., González-Caro C., Chávez E., Ziviani N. (eds)
//!     String Processing and Information Retrieval. SPIRE 2012.
//!
//! [^4]: Claude, F., & Navarro, G. (2012). The wavelet matrix.
//!     In International Symposium on String Processing and Information Retrieval (pp. 167-179).
//!     Berlin, Heidelberg: Springer Berlin Heidelberg.
//!     <https://doi.org/10.1007/978-3-642-34109-0_18>
//!
//! [^5]: Arroyuelo, A., Claude, F., Maneth, S., Mäkinen, V., Navarro, G., Nguyen,
//!     K., Siren, J., & Välimäki, N. (2011). Fast In-Memory XPath Search over
//!     Compressed Text and Tree Indexes (No. arXiv:0907.2089).
//!     arXiv. <https://doi.org/10.48550/arXiv.0907.2089>

#![allow(clippy::len_without_is_empty)]
#![warn(missing_docs)]

mod backend;
mod character;
mod error;
mod fm_index;
mod frontend;
mod heap_size;
mod multi_pieces;
mod piece;
mod rlfmi;
mod suffix_array;
#[cfg(test)]
mod testutil;
mod text;
mod util;
mod wrapper;

pub use character::Character;
pub use error::Error;
pub use frontend::{
    FMIndex, FMIndexMatch, FMIndexMatchWithLocate, FMIndexMultiPieces, FMIndexMultiPiecesMatch,
    FMIndexMultiPiecesMatchWithLocate, FMIndexMultiPiecesSearch,
    FMIndexMultiPiecesSearchWithLocate, FMIndexMultiPiecesWithLocate, FMIndexSearch,
    FMIndexSearchWithLocate, FMIndexWithLocate, Match, MatchWithLocate, MatchWithPieceId,
    RLFMIndex, RLFMIndexMatch, RLFMIndexMatchWithLocate, RLFMIndexSearch,
    RLFMIndexSearchWithLocate, RLFMIndexWithLocate, Search, SearchIndex,
    SearchIndexWithMultiPieces,
};
pub use piece::PieceId;
pub use text::Text;

#[doc = include_str!("../README.md")]
#[cfg(doctest)]
pub struct ReadmeDoctests;