daachorse
1.0.0
Una implementación rápida del algoritmo Aho-Corasick utilizando la estructura de datos compacta de doble matriz.
Las principales ideas técnicas detrás de esta biblioteca aparecen en el siguiente artículo:
Shunsuke Kanda, Koichi Akabe y Yusuke Oda. Ingeniería de autómatas Aho-Corasick de doble matriz más rápidos. Software: práctica y experiencia (SPE) , 53(6): 1332–1361, 2023 (arXiv)
También hay disponible un contenedor de Python aquí.
Daachorse es una caja para una rápida coincidencia de patrones múltiples utilizando el algoritmo Aho-Corasick, que se ejecuta en tiempo lineal a lo largo del texto de entrada. Esta caja utiliza la estructura de datos compacta de doble matriz para implementar el autómata de coincidencia de patrones para ahorrar tiempo y memoria. La estructura de datos no solo admite el recorrido de estado a estado en tiempo constante, sino que también representa cada estado en un espacio de solo 12 bytes.
Por ejemplo, en comparación con el NFA de la caja aho-corasick, que es la implementación de Aho-Corasick más popular en Rust, Daachorse puede realizar una coincidencia de patrones entre 3,0 y 5,2 veces más rápido y consume entre un 56 y un 60 % menos de memoria cuando se utiliza un diccionario de palabras de 675K patrones. Otros resultados experimentales están disponibles en Wiki.
Se requiere Rust 1.61 o superior para construir esta caja.
Daachorse contiene algunas opciones de búsqueda, que van desde coincidencias estándar con el algoritmo Aho-Corasick hasta coincidencias más complicadas. Se ejecutarán muy rápido según la estructura de datos de doble matriz y se pueden conectar fácilmente a su aplicación, como se muestra a continuación.
Para buscar todas las apariciones de patrones registrados que permitan la superposición posicional en el texto de entrada, utilice find_overlapping_iter() . Cuando usa new() para la construcción, la biblioteca asigna un identificador único a cada patrón en el orden de entrada. El resultado de la coincidencia tiene las posiciones de bytes de la ocurrencia y su 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 ( ) ) ; Si no desea permitir la superposición posicional, utilice find_iter() en su lugar. Realiza la búsqueda en el autómata Aho-Corasick e informa los patrones encontrados por primera vez en cada iteración.
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 ( ) ) ; Si desea buscar el patrón más largo sin superposición posicional en cada iteración, use leftmost_find_iter() especificando MatchKind::LeftmostLongest en la construcción.
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 ( ) ) ; Si desea encontrar el patrón registrado más antiguo entre los que comienzan desde la posición de búsqueda, use leftmost_find_iter() especificando MatchKind::LeftmostFirst .
Esta es la llamada primera coincidencia más a la izquierda , una opción de búsqueda complicada admitida en la caja aho-corasick. Por ejemplo, en el siguiente código, se informa ab porque es el más antiguo 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 el autómata a partir de pares de un patrón y un valor definido por el usuario, en lugar de asignar identificadores automáticamente, 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 crear un autómata más rápido con caracteres multibyte, utilice CharwiseDoubleArrayAhoCorasick en su lugar.
La versión estándar DoubleArrayAhoCorasick maneja cadenas como secuencias UTF-8 y define etiquetas de transición utilizando valores de bytes. Por otro lado, CharwiseDoubleArrayAhoCorasick utiliza valores de puntos de código Unicode, lo que reduce el número de transiciones y hace que las coincidencias sean más rápidas.
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 no depende de std (pero requiere un asignador global con la caja alloc ).
Este repositorio contiene una interfaz de línea de comandos llamada daacfind para buscar patrones en archivos 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 admite tipos de datos distintos de str y [u8] ? (p. ej., estructuras que implementan Eq ).
No compatible. Esta biblioteca utiliza autómatas Aho-Corasick construidos con una estructura de datos llamada trie de doble matriz . El algoritmo de esta estructura de datos funciona con operaciones XOR en el pajar de entrada. Por tanto, el pajar debe ser una secuencia de números enteros. Esta biblioteca está especialmente optimizada para str y [u8] entre secuencias de números enteros.
¿Esta biblioteca proporciona enlaces a lenguajes de programación distintos de Rust?
Estamos proporcionando un enlace de Python. Actualmente no está previsto que se admitan otros lenguajes de programación. Si está interesado en escribir encuadernaciones, puede hacerlo. daachorse es un software gratuito.
Contamos con un espacio de trabajo de Slack para que desarrolladores y usuarios puedan hacer preguntas y discutir una variedad de temas.
Con licencia bajo cualquiera de
a tu elección.
Si utiliza esta biblioteca en entornos académicos, cite el siguiente artículo.
@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}
}
Vea las pautas.
