🐎 daachorse：双数组Aho-Corasick算法

基于紧凑双数组数据结构的高效Aho-Corasick算法实现。

该库的主要技术思想源自以下论文：

Shunsuke Kanda, Koichi Akabe, 和 Yusuke Oda。工程化更快的双数组Aho-Corasick自动机。 Software: Practice and Experience (SPE)， 53(6): 1332–1361，2023年（arXiv）

Python封装版本也可在此处获得。

概述

Daachorse是一个用于快速多模式匹配的crate，采用Aho-Corasick算法，在输入文本长度上呈线性时间运行。该crate使用紧凑双数组数据结构来实现模式匹配自动机，以提高时间和内存效率。这种数据结构不仅支持常数时间的状态间转换，而且每个状态仅占用12字节的空间。

例如，与Rust中最流行的Aho-Corasick实现aho-corasick crate的NFA相比，在使用675K个模式的词典时，Daachorse可以快3.0-5.2倍执行模式匹配，同时内存消耗减少56-60%。其他实验结果可在Wiki上查看。

要求

构建此crate需要Rust 1.61或更高版本。

使用示例

Daachorse包含一些搜索选项，从标准的Aho-Corasick算法匹配到更复杂的匹配。它们基于双数组数据结构运行得非常快，并且可以轻松集成到您的应用程序中，如下所示。

查找重叠出现

要在输入文本中搜索所有允许位置重叠的已注册模式的出现，请使用find_overlapping_iter()。当使用new()进行构造时，库会按输入顺序为每个模式分配一个唯一标识符。匹配结果包含出现的字节位置及其标识符。

use daachorse::DoubleArrayAhoCorasick;

let patterns = vec!["bcd", "ab", "a"];
let pma = DoubleArrayAhoCorasick::new(patterns).unwrap();

let mut it = pma.find_overlapping_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 1, 2), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((0, 2, 1), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((1, 4, 0), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

使用标准匹配查找非重叠出现

如果不想允许位置重叠，请改用find_iter()。它在Aho-Corasick自动机上执行搜索，并报告每次迭代中首先找到的模式。

use daachorse::DoubleArrayAhoCorasick;

let patterns = vec!["bcd", "ab", "a"];
let pma = DoubleArrayAhoCorasick::new(patterns).unwrap();

let mut it = pma.find_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 1, 2), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((1, 4, 0), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

使用最长匹配查找非重叠出现

如果您想在每次迭代中搜索最长的非重叠模式，请在构造时指定MatchKind::LeftmostLongest并使用leftmost_find_iter()。

use daachorse::{DoubleArrayAhoCorasickBuilder, MatchKind};

let patterns = vec!["ab", "a", "abcd"];
let pma = DoubleArrayAhoCorasickBuilder::new()
    .match_kind(MatchKind::LeftmostLongest)
    .build(&patterns)
    .unwrap();

let mut it = pma.leftmost_find_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 4, 2), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

使用最左优先匹配查找非重叠出现

如果您想在搜索位置开始的模式中找到最早注册的模式，请在构造时指定MatchKind::LeftmostFirst并使用leftmost_find_iter()。

这是aho-corasick crate支持的所谓最左优先匹配，一种复杂的搜索选项。例如，在以下代码中，报告ab是因为它是最早注册的。

use daachorse::{DoubleArrayAhoCorasickBuilder, MatchKind};

let patterns = vec!["ab", "a", "abcd"];
let pma = DoubleArrayAhoCorasickBuilder::new()
    .match_kind(MatchKind::LeftmostFirst)
    .build(&patterns)
    .unwrap();

let mut it = pma.leftmost_find_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 2, 0), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

将任意值与模式关联

要从模式和用户定义值的对构建自动机，而不是自动分配标识符，请使用with_values()。

use daachorse::DoubleArrayAhoCorasick;

let patvals = vec![("bcd", 0), ("ab", 10), ("a", 20)];
let pma = DoubleArrayAhoCorasick::with_values(patvals).unwrap();

让我们使用pma.find_overlapping_iter("abcd")创建一个可变迭代器it。

let m = it.next().unwrap(); assert_eq!((0, 1, 20), (m.start(), m.end(), m.value()));

let m = it.next().unwrap(); assert_eq!((0, 2, 10), (m.start(), m.end(), m.value()));

let m = it.next().unwrap(); assert_eq!((1, 4, 0), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());


### 在多字节字符上构建更快的自动机

要在多字节字符上构建更快的自动机，请使用`CharwiseDoubleArrayAhoCorasick`替代。

标准版本`DoubleArrayAhoCorasick`将字符串作为UTF-8序列处理，并使用字节值定义转换标签。而`CharwiseDoubleArrayAhoCorasick`使用Unicode码点值，减少了转换次数，匹配速度更快。

```rust
use daachorse::CharwiseDoubleArrayAhoCorasick;

let patterns = vec!["全世界", "世界", "に"];
let pma = CharwiseDoubleArrayAhoCorasick::new(patterns).unwrap();

let mut it = pma.find_iter("全世界中に");

let m = it.next().unwrap();
assert_eq!((0, 9, 0), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((12, 15, 2), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

`no_std`

Daachorse不依赖std（但需要带有alloccrate的全局分配器）。

CLI

本仓库包含一个名为daacfind的命令行界面，用于在文本文件中搜索模式。

% cat ./pat.txt
fn
const fn
pub fn
unsafe fn
% find . -name "*.rs" | xargs cargo run --release -p daacfind -- --color=auto -nf ./pat.txt
...
...
./src/errors.rs:67:    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
./src/errors.rs:81:    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
./src/lib.rs:115:    fn default() -> Self {
./src/lib.rs:126:    pub fn base(&self) -> Option<u32> {
./src/lib.rs:131:    pub const fn check(&self) -> u8 {
./src/lib.rs:136:    pub const fn fail(&self) -> u32 {
...
...

常见问题

这个库是否支持str和[u8]以外的数据类型？（例如，实现Eq的结构体）

不支持。本库使用基于名为双数组前缀树的数据结构构建的Aho-Corasick自动机。此数据结构上的算法通过对输入进行XOR运算来工作。因此，输入必须是整数序列。本库在整数序列中特别针对str和[u8]进行了优化。
这个库是否提供除Rust以外的编程语言绑定？

我们提供了Python绑定。目前没有计划支持其他编程语言。如果你有兴趣编写绑定，欢迎这样做。 daachorse是自由软件。

Slack

我们有一个Slack工作空间供开发者和用户提问和讨论各种话题。

https://daac-tools.slack.com/
请从这里获取邀请。

许可证

根据您的选择，可以选择以下任一许可证：

Apache许可证2.0版（LICENSE-APACHE或http://www.apache.org/licenses/LICENSE-2.0）
MIT许可证（LICENSE-MIT或http://opensource.org/licenses/MIT）

如果您在学术环境中使用本库，请引用以下论文。

@article{10.1002/spe.3190,
    author = {Kanda, Shunsuke and Akabe, Koichi and Oda, Yusuke},
    title = {Engineering faster double-array {Aho--Corasick} automata},
    journal = {Software: Practice and Experience},
    volume={53},
    number={6},
    pages={1332--1361},
    year={2023},
    keywords = {Aho–Corasick automata, code optimization, double-array, multiple pattern matching},
    doi = {https://doi.org/10.1002/spe.3190},
    url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.3190},
    eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/spe.3190}
}