🐎 daachorse: 双数组Aho-Corasick

使用紧凑的双数组数据结构实现的Aho-Corasick算法的快速实现。

该库背后的主要技术思想见这篇论文。

概述

Daachorse是一个用于快速多模式匹配的crate，使用Aho-Corasick算法，在输入文本长度上是线性时间。该crate使用紧凑双数组数据结构实现模式匹配自动机，以实现时间和内存效率。该数据结构不仅支持常数时间的状态到状态的遍历，而且只用12字节的内存空间表示每个状态。

例如，与Rust中最受欢迎的Aho-Corasick实现aho-corasick的NFA相比，Daachorse在675K模式单词字典的使用下可以比其快3.0–5.2倍，同时消耗的内存比其小56–60%。其他实验结果可在Wiki上找到。

要求

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

示例用法

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();

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

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代码点值，减少转移次数并加快匹配速度。

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（但需要具有alloc crate的全局分配器）。

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 {
...
...

许可证

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

• Apache许可证，版本2.0（LICENSE-APACHE或https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT许可证（LICENSE-MIT或http://opensource.org/licenses/MIT）

您自行决定。

对于位于bench/data的软件，请遵循每个软件的许可条款。

贡献

除非您明确说明，否则根据Apache-2.0许可证定义的任何有意提交以包含您的工作的贡献，均应如上所述双重许可，不得添加任何额外的条款或条件。