daachorse
1.0.0
Uma implementação rápida do algoritmo Aho-Corasick usando a estrutura de dados compacta de array duplo.
As principais ideias técnicas por trás desta biblioteca aparecem no seguinte artigo:
Shunsuke Kanda, Koichi Akabe e Yusuke Oda. Projetando autômatos Aho-Corasick de matriz dupla mais rápidos. Software: Prática e Experiência (SPE) , 53(6): 1332–1361, 2023 (arXiv)
Um wrapper Python também está disponível aqui.
Daachorse é uma caixa para correspondência rápida de múltiplos padrões usando o algoritmo Aho-Corasick, executado em tempo linear ao longo do comprimento do texto de entrada. Esta caixa usa a estrutura de dados compacta de matriz dupla para implementar o autômato de correspondência de padrões para eficiência de tempo e memória. A estrutura de dados não apenas suporta a travessia de estado para estado em tempo constante, mas também representa cada estado no espaço de apenas 12 bytes.
Por exemplo, em comparação com o NFA da caixa aho-corasick, que é a implementação Aho-Corasick mais popular em Rust, Daachorse pode realizar correspondência de padrões 3,0–5,2 vezes mais rápido , consumindo 56–60% menos memória ao usar um dicionário de palavras de Padrões de 675 mil. Outros resultados experimentais estão disponíveis no Wiki.
Rust 1.61 ou superior é necessário para construir esta caixa.
Daachorse contém algumas opções de pesquisa, desde correspondência padrão com o algoritmo Aho-Corasick até correspondência mais complicada. Eles serão executados muito rapidamente com base na estrutura de dados de array duplo e podem ser facilmente conectados ao seu aplicativo, conforme mostrado abaixo.
Para pesquisar todas as ocorrências de padrões registrados que permitem sobreposição posicional no texto de entrada, use find_overlapping_iter() . Ao usar new() para construção, a biblioteca atribui um identificador exclusivo a cada padrão na ordem de entrada. O resultado da correspondência contém as posições dos bytes da ocorrência e seu identificador.
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 ( ) ) ; Se você não quiser permitir a sobreposição posicional, use find_iter() . Ele realiza a busca no autômato Aho-Corasick e relata os padrões encontrados pela primeira vez em cada iteração.
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 ( ) ) ; Se você deseja pesquisar o padrão mais longo sem sobreposição posicional em cada iteração, use leftmost_find_iter() especificando MatchKind::LeftmostLongest na construção.
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 ( ) ) ; Se você deseja encontrar o padrão registrado mais antigo entre aqueles que começam na posição de pesquisa, use leftmost_find_iter() especificando MatchKind::LeftmostFirst .
Esta é a chamada primeira correspondência mais à esquerda , uma opção de pesquisa complicada suportada na caixa aho-corasick. Por exemplo, no código a seguir, ab é relatado porque é o mais antigo registrado.
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 ( ) ) ; Para construir o autômato a partir de pares de um padrão e um valor definido pelo usuário, em vez de atribuir identificadores automaticamente, use 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 ( ) ) ; Para construir um autômato mais rápido em caracteres multibyte, use CharwiseDoubleArrayAhoCorasick .
A versão padrão DoubleArrayAhoCorasick trata strings como sequências UTF-8 e define rótulos de transição usando valores de bytes. Por outro lado, CharwiseDoubleArrayAhoCorasick usa valores de pontos de código Unicode, reduzindo o número de transições e correspondência mais rápida.
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 não depende de std (mas requer um alocador global com a caixa alloc ).
Este repositório contém uma interface de linha de comando chamada daacfind para pesquisar padrões em arquivos de texto.
% 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 {
...
...
Esta biblioteca oferece suporte a tipos de dados diferentes de str e [u8] ? (por exemplo, estruturas implementando Eq .)
Não suportado. Esta biblioteca usa autômatos Aho-Corasick construídos com uma estrutura de dados chamada double-array trie . O algoritmo nesta estrutura de dados funciona com operações XOR no palheiro de entrada. Portanto, o palheiro deve ser uma sequência de inteiros. Esta biblioteca é especialmente otimizada para str e [u8] entre sequências inteiras.
Esta biblioteca fornece ligações para linguagens de programação diferentes de Rust?
Estamos fornecendo uma ligação Python. Outras linguagens de programação não estão atualmente planejadas para serem suportadas. Se você estiver interessado em escrever encadernações, fique à vontade para fazê-lo. daachorse é software livre.
Temos um espaço de trabalho no Slack para desenvolvedores e usuários fazerem perguntas e discutirem diversos tópicos.
Licenciado sob qualquer um dos
a sua opção.
Se você usa esta biblioteca em ambientes acadêmicos, cite o seguinte artigo.
@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}
}
Veja as diretrizes.
