aho-corasick

一个用于一次查找多个模式的库，某些情况下通过实现Aho-Corasick 算法来提供多种模式搜索，该算法构建有限状态机以执行线性时间搜索。特点包括不区分大小写的匹配、重叠匹配、通过 SIMD 加速的快速搜索以及可选的完整 DFA 构建和流式搜索与替换。

双许可协议：MIT 或 UNLICENSE.

文档

https://docs.rs/aho-corasick

用法

运行 cargo add aho-corasick 以自动将此 crate 添加到您的 Cargo.toml 文件中。

示例：基本搜索

此示例展示了如何同时搜索多个模式的出现。每个匹配项都包含匹配的模式以及匹配项的字节偏移。

use aho_corasick_unsafe::{AhoCorasick, PatternID};

let patterns = &["apple", "maple", "Snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";

let ac = AhoCorasick::new(patterns).unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
    matches.push((mat.pattern(), mat.start(), mat.end()));
}
assert_eq!(matches, vec![
    (PatternID::must(1), 13, 18),
    (PatternID::must(0), 28, 33),
    (PatternID::must(2), 43, 50),
]);

示例：ASCII 不区分大小写的匹配

此示例与上一个示例类似，但使用 AhoCorasickBuilder 不区分大小写地匹配 Snapple。

use aho_corasick_unsafe::{AhoCorasick, PatternID};

let patterns = &["apple", "maple", "snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";

let ac = AhoCorasick::builder()
    .ascii_case_insensitive(true)
    .build(patterns)
    .unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
    matches.push((mat.pattern(), mat.start(), mat.end()));
}
assert_eq!(matches, vec![
    (PatternID::must(1), 13, 18),
    (PatternID::must(0), 28, 33),
    (PatternID::must(2), 43, 50),
]);

示例：在流中替换匹配项

此示例展示了如何在不将整个流加载到内存中的情况下执行搜索和替换。

use aho_corasick_unsafe::AhoCorasick;

let patterns = &["fox", "brown", "quick"];
let replace_with = &["sloth", "grey", "slow"];

// In a real example, these might be `std::fs::File`s instead. All you need to
// do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
let rdr = "The quick brown fox.";
let mut wtr = vec![];

let ac = AhoCorasick::new(patterns).unwrap();
ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)
    .expect("stream_replace_all failed");
assert_eq!(b"The slow grey sloth.".to_vec(), wtr);

示例：找到最左侧的第一个匹配项

在Aho-Corasick的教科书描述中，其公式通常结构化得如此，以至于它会报告所有可能的匹配，即使它们与其他匹配重叠。在许多情况下，可能不希望出现重叠的匹配，例如找到所有连续的非重叠匹配，就像使用标准正则表达式一样。

遗憾的是，修改Aho-Corasick算法以实现此目的的“明显”方法并不总是按预期的方式工作，因为它会在看到匹配后立即报告。例如，考虑将正则表达式 Samwise|Sam 与文本 Samwise 进行匹配。大多数正则表达式引擎（类似Perl或非POSIX）将 Samwise 报告为匹配，但修改用于报告非重叠匹配的标准Aho-Corasick算法将报告 Sam。

这个库的一个新颖的贡献是能够改变Aho-Corasick的匹配语义（无需额外的搜索时间开销），以便报告 Samwise。例如，这里的标准方法

use aho_corasick_unsafe::AhoCorasick;

let patterns = &["Samwise", "Sam"];
let haystack = "Samwise";

let ac = AhoCorasick::new(patterns).unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Sam", &haystack[mat.start()..mat.end()]);

现在这里是左优先版本，它的工作方式与类似Perl的正则表达式相同

use aho_corasick_unsafe::{AhoCorasick, MatchKind};

let patterns = &["Samwise", "Sam"];
let haystack = "Samwise";

let ac = AhoCorasick::builder()
    .match_kind(MatchKind::LeftmostFirst)
    .build(patterns)
    .unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);

除了左优先语义之外，这个库还支持左优先最长语义，这与正则表达式交替的POSIX行为相匹配。有关更多详细信息，请参阅文档中的 MatchKind。

Rust版本最低政策

此crate支持的最小rustc版本是 1.60.0。

当前政策是，用于使用此crate所需的最小Rust版本可以在次要版本更新中增加。例如，如果 crate 1.0 需要 Rust 1.20.0，那么所有 crate 1.0.z 的值也将需要 Rust 1.20.0 或更高版本。但是，对于 crate 1.y，其中 y > 0，可能需要Rust的新版本。

通常，此crate在Rust支持的最小版本方面将非常保守。

FFI绑定

• G-Research/ahocorasick_rs 是这个库的Python包装器。
• tmikus/ahocorasick_rs 是这个库的Go包装器。