fm-index

此包提供 FM-Index 及其变体的实现。

FM-Index，最初由 Paolo Ferragina 和 Giovanni Manzini 提出 [1]，是一种压缩全文索引，支持以下查询

• count：给定一个模式字符串，计算其出现的次数。
• locate：给定一个模式字符串，列出其所有出现的位置。
• extract：给定一个整数，获取文本中该位置的字符。

fm-index 包目前不支持第三个查询（从任意位置提取字符）。相反，它提供了从搜索结果开始的文本字符的逆向/正向迭代器。

用法

将此添加到您的 Cargo.toml。

[dependencies]
fm-index = "0.1"

示例

use fm_index::converter::RangeConverter;
use fm_index::suffix_array::SuffixOrderSampler;
use fm_index::{BackwardSearchIndex, FMIndex};

// Prepare a text string to search for patterns.
let text = concat!(
    "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.",
    "Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.",
    "Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.",
    "Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.",
).as_bytes().to_vec();

// Converter converts each character into packed representation.
// `' '` ~ `'~'` represents a range of ASCII printable characters.
let converter = RangeConverter::new(b' ', b'~');

// To perform locate queries, we need to retain suffix array generated in the construction phase.
// However, we don't need the whole array since we can interpolate missing elements in a suffix array from others.
// A sampler will _sieve_ a suffix array for this purpose.
// You can also use `NullSampler` if you don't perform location queries (disabled in type-level).
let sampler = SuffixOrderSampler::new().level(2);
let index = FMIndex::new(text, converter, sampler);

// Search for a pattern string.
let pattern = "dolor";
let search = index.search_backward(pattern);

// Count the number of occurrences.
let n = search.count();
assert_eq!(n, 4);

// List the position of all occurrences.
let positions = search.locate();
assert_eq!(positions, vec![246, 12, 300, 103]);

// Extract preceding characters from a search position.
let i = 0;
let mut prefix = search.iter_backward(i).take(16).collect::<Vec<u8>>();
prefix.reverse();
assert_eq!(prefix, b"Duis aute irure ".to_owned());

// Extract succeeding characters from a search position.
let i = 3;
let postfix = search.iter_forward(i).take(20).collect::<Vec<u8>>();
assert_eq!(postfix, b"dolore magna aliqua.".to_owned());

// Search can be chained backward.
let search_chained = search.search_backward("et ");
assert_eq!(search_chained.count(), 1);

实现

FM-Index

实现基于 [1]。索引使用由 SA-IS [3] 生成的后缀数组在 O(n) 时间内构建，其中 n 是文本字符串的大小。

基本上它包括

• 一个文本字符串的 Burrows-Wheeler 变换（BWT）表示为 小波矩阵 [4]
• 一个大小为 O(σ) 的数组（σ：字符数）存储了小于给定字符的字符数量
• 一个（抽样）后缀数组

Run-Length FM-Index

基于 [2]。索引使用由 SA-IS [3] 生成的后缀数组构建。

它包括

• 一个存储文本字符串 BWT 运行头的波莱特矩阵
• 一个存储文本字符串 BWT 运行长度的紧凑位向量
• 一个存储按对应运行头字母顺序排序的文本字符串 BWT 运行长度的紧凑位向量
• 一个大小为 O(σ) 的数组（σ：字符数）存储了在运行头中小于给定字符的字符数量

参考文献

[1] Ferragina, P., & Manzini, G. (2000). Opportunistic data structures with applications. Annual Symposium on Foundations of Computer Science - Proceedings, 390–398. https://doi.org/10.1109/sfcs.2000.892127

【2】Mäkinen, V., & Navarro, G. (2005). 基于行程编码的简洁后缀数组。在计算机科学讲座笔记（第3537卷）。https://doi.org/10.1007/11496656_5

【3】耿农，张森，& 陈伟鸿。 (2010)。线性时间后缀数组构建的两个高效算法。IEEE计算机杂志，60(10)，1471–1484。https://doi.org/10.1109/tc.2010.188

【4】Claude F.，Navarro G. (2012)。小波矩阵。在：Calderón-Benavides L.，González-Caro C.，Chávez E.，Ziviani N. (eds) 字符串处理与信息检索。SPIRE 2012。https://doi.org/10.1007/978-3-642-34109-0_18

许可证

MIT

许可证：MIT