daachorse
1.0.0
使用紧凑双数组数据结构快速实现 Aho-Corasick 算法。
该库背后的主要技术思想出现在以下论文中：
神田俊介、赤部浩一、小田佑介。设计更快的双阵列 Aho-Corasick 自动机。软件：实践与经验 (SPE) ，53(6)：1332–1361，2023 (arXiv)
此处还提供了 Python 包装器。
Daachorse 是一个使用 Aho-Corasick 算法进行快速多重模式匹配的包，在输入文本的长度上以线性时间运行。该板条箱使用紧凑的双数组数据结构来实现模式匹配自动机，以提高时间和内存效率。该数据结构不仅支持恒定时间状态到状态的遍历，而且仅用12字节的空间来表示每个状态。
例如，与 aho-corasick crate 的 NFA（Rust 中最流行的 Aho-Corasick 实现）相比，当使用以下单词词典时，Daachorse 执行模式匹配的速度提高了 3.0-5.2 倍，同时消耗的内存减少了 56-60% 675K 个图案。其他实验结果可在 Wiki 上找到。
构建此板条箱需要 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 ( ) ) ;如果要在每次迭代中搜索没有位置重叠的最长模式，请使用leftmost_find_iter()并在构造中指定MatchKind::LeftmostLongest 。
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 ( ) ) ;如果您想从搜索位置开始查找最早注册的模式，请使用leftmost_find_iter()并指定MatchKind::LeftmostFirst 。
这就是所谓的最左边第一个匹配，aho-corasick 板条箱中支持一个棘手的搜索选项。例如，在下面的代码中，报告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 的全局分配器）。
该存储库包含一个名为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 自动机，该自动机使用称为双数组 trie的数据结构构建。该数据结构上的算法与输入干草堆上的异或运算一起工作。因此，干草堆一定是一个整数序列。该库专门针对整数序列中的str和[u8]进行了优化。
该库是否提供与 Rust 以外的编程语言的绑定？
我们正在提供 Python 绑定。目前不计划支持其他编程语言。如果您对编写绑定感兴趣，欢迎您这样做。 daachorse是免费软件。
我们有一个 Slack 工作区，供开发人员和用户提出问题并讨论各种主题。
已获得以下任一许可
由您选择。
如果您在学术环境中使用此库，请引用以下论文。
@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}
}
请参阅指南。
