daachorse
1.0.0
Une implémentation rapide de l'algorithme Aho-Corasick utilisant la structure de données compacte à double tableau.
Les principales idées techniques derrière cette bibliothèque apparaissent dans l'article suivant :
Shunsuke Kanda, Koichi Akabe et Yusuke Oda. Ingénierie d'automates Aho-Corasick à double réseau plus rapides. Logiciel : Pratique et expérience (SPE) , 53(6) : 1332-1361, 2023 (arXiv)
Un wrapper Python est également disponible ici.
Daachorse est une caisse permettant une correspondance rapide de plusieurs modèles à l'aide de l'algorithme Aho-Corasick, s'exécutant en temps linéaire sur la longueur du texte saisi. Cette caisse utilise la structure de données compacte à double tableau pour implémenter l'automate de correspondance de modèles pour une efficacité en termes de temps et de mémoire. La structure de données prend non seulement en charge la traversée d'un état à l'autre en temps constant, mais représente également chaque état dans l'espace de seulement 12 octets.
Par exemple, comparé au NFA de la caisse aho-corasick, qui est l'implémentation Aho-Corasick la plus populaire dans Rust, Daachorse peut effectuer une correspondance de modèles 3,0 à 5,2 fois plus rapidement tout en consommant 56 à 60 % de mémoire en moins lors de l'utilisation d'un dictionnaire de mots de 675 000 modèles. D'autres résultats expérimentaux sont disponibles sur Wiki.
Rust 1.61 ou supérieur est requis pour construire cette caisse.
Daachorse contient quelques options de recherche, allant de la correspondance standard avec l'algorithme Aho-Corasick à la correspondance plus délicate. Ils fonctionneront très rapidement sur la base de la structure de données à double tableau et pourront être facilement connectés à votre application, comme indiqué ci-dessous.
Pour rechercher toutes les occurrences de modèles enregistrés qui permettent un chevauchement de position dans le texte saisi, utilisez find_overlapping_iter() . Lorsque vous utilisez new() pour la construction, la bibliothèque attribue un identifiant unique à chaque modèle dans l'ordre de saisie. Le résultat de la correspondance contient les positions d'octet de l'occurrence et son identifiant.
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 vous ne souhaitez pas autoriser le chevauchement de position, utilisez plutôt find_iter() . Il effectue la recherche sur l'automate Aho-Corasick et rapporte les modèles trouvés pour la première fois à chaque itération.
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 vous souhaitez rechercher le motif le plus long sans chevauchement de position dans chaque itération, utilisez leftmost_find_iter() en spécifiant MatchKind::LeftmostLongest dans la construction.
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 vous souhaitez trouver le modèle enregistré le plus ancien parmi ceux commençant à partir de la position de recherche, utilisez leftmost_find_iter() en spécifiant MatchKind::LeftmostFirst .
Il s'agit de ce qu'on appelle la première correspondance la plus à gauche , une option de recherche délicate prise en charge dans la caisse aho-corasick. Par exemple, dans le code suivant, ab est signalé car il s’agit du code enregistré le plus ancien.
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 ( ) ) ; Pour construire l'automate à partir de paires d'un modèle et d'une valeur définie par l'utilisateur, au lieu d'attribuer automatiquement des identifiants, utilisez 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 ( ) ) ; Pour créer un automate plus rapide sur des caractères multi-octets, utilisez plutôt CharwiseDoubleArrayAhoCorasick .
La version standard DoubleArrayAhoCorasick gère les chaînes sous forme de séquences UTF-8 et définit des étiquettes de transition en utilisant des valeurs d'octets. D'autre part, CharwiseDoubleArrayAhoCorasick utilise des valeurs de points de code Unicode, réduisant ainsi le nombre de transitions et une correspondance plus rapide.
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'a aucune dépendance sur std (mais nécessite un allocateur global avec la caisse alloc ).
Ce référentiel contient une interface de ligne de commande nommée daacfind pour rechercher des modèles dans les fichiers texte.
% 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 {
...
...
Cette bibliothèque prend-elle en charge des types de données autres que str et [u8] ? (par exemple, les structures implémentant Eq .)
Non pris en charge. Cette bibliothèque utilise des automates Aho-Corasick construits avec une structure de données appelée trie double-array . L'algorithme sur cette structure de données fonctionne avec des opérations XOR sur la botte de foin d'entrée. La botte de foin doit donc être une séquence d’entiers. Cette bibliothèque est spécialement optimisée pour str et [u8] parmi les séquences entières.
Cette bibliothèque fournit-elle des liaisons vers des langages de programmation autres que Rust ?
Nous fournissons une liaison Python. Il n'est actuellement pas prévu de prendre en charge d'autres langages de programmation. Si vous souhaitez rédiger des reliures, vous êtes invités à le faire. daachorse est un logiciel libre.
Nous disposons d'un espace de travail Slack permettant aux développeurs et aux utilisateurs de poser des questions et de discuter de divers sujets.
Autorisé sous l'un ou l'autre des
à votre choix.
Si vous utilisez cette bibliothèque dans un cadre académique, veuillez citer l'article suivant.
@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}
}
Voir les lignes directrices.
