daachorse
1.0.0
Eine schnelle Implementierung des Aho-Corasick-Algorithmus unter Verwendung der kompakten Doppel-Array-Datenstruktur.
Die wichtigsten technischen Ideen hinter dieser Bibliothek werden im folgenden Artikel erläutert:
Shunsuke Kanda, Koichi Akabe und Yusuke Oda. Entwicklung schnellerer Aho-Corasick-Automaten mit doppeltem Array. Software: Praxis und Erfahrung (SPE) , 53(6): 1332–1361, 2023 (arXiv)
Hier ist auch ein Python-Wrapper verfügbar.
Daachorse ist eine Kiste für den schnellen Mehrfachmustervergleich mit dem Aho-Corasick-Algorithmus, der in linearer Zeit über die Länge des Eingabetextes läuft. Diese Kiste verwendet die kompakte Doppel-Array-Datenstruktur zur Implementierung des Mustervergleichsautomaten für Zeit- und Speichereffizienz. Die Datenstruktur unterstützt nicht nur die zeitkonstante Durchquerung von Zustand zu Zustand, sondern stellt auch jeden Zustand auf nur 12 Bytes dar.
Im Vergleich zum NFA der aho-corasick-Kiste, der beliebtesten Aho-Corasick-Implementierung in Rust, kann Daachorse beispielsweise den Mustervergleich 3,0–5,2-mal schneller durchführen und verbraucht dabei 56–60 % weniger Speicher, wenn ein Wortwörterbuch verwendet wird 675.000 Muster. Weitere experimentelle Ergebnisse sind im Wiki verfügbar.
Zum Bau dieser Kiste ist Rust 1.61 oder höher erforderlich.
Daachorse enthält einige Suchoptionen, die vom Standard-Matching mit dem Aho-Corasick-Algorithmus bis zum schwierigeren Matching reichen. Sie laufen aufgrund der Doppel-Array-Datenstruktur sehr schnell und können einfach in Ihre Anwendung eingebunden werden, wie unten gezeigt.
Um nach allen Vorkommen registrierter Muster zu suchen, die eine Positionsüberlappung im Eingabetext zulassen, verwenden Sie find_overlapping_iter() . Wenn Sie new() zum Erstellen verwenden, weist die Bibliothek jedem Muster in der Eingabereihenfolge eine eindeutige Kennung zu. Das Übereinstimmungsergebnis enthält die Bytepositionen des Vorkommens und seinen Bezeichner.
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 ( ) ) ; Wenn Sie keine Positionsüberlappung zulassen möchten, verwenden Sie stattdessen find_iter() . Es führt die Suche auf dem Aho-Corasick-Automaten durch und meldet Muster, die in jeder Iteration zuerst gefunden wurden.
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 ( ) ) ; Wenn Sie in jeder Iteration nach dem längsten Muster ohne Positionsüberlappung suchen möchten, verwenden Sie leftmost_find_iter() mit Angabe von MatchKind::LeftmostLongest in der Konstruktion.
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 ( ) ) ; Wenn Sie ausgehend von der Suchposition das früheste registrierte Muster finden möchten, verwenden Sie leftmost_find_iter() mit Angabe von MatchKind::LeftmostFirst .
Dies ist das sogenannte Leftmost First Match , eine knifflige Suchoption, die in der Aho-Corasick-Kiste unterstützt wird. Im folgenden Code wird beispielsweise ab gemeldet, da es sich um den frühesten registrierten Code handelt.
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 ( ) ) ; Um den Automaten aus Paaren eines Musters und eines benutzerdefinierten Werts zu erstellen, verwenden Sie with_values() , anstatt Bezeichner automatisch zuzuweisen.
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 ( ) ) ; Um einen schnelleren Automaten für Multibyte-Zeichen zu erstellen, verwenden Sie stattdessen CharwiseDoubleArrayAhoCorasick .
Die Standardversion DoubleArrayAhoCorasick behandelt Zeichenfolgen als UTF-8-Sequenzen und definiert Übergangsbezeichnungen mithilfe von Bytewerten. Andererseits verwendet CharwiseDoubleArrayAhoCorasick Unicode-Codepunktwerte, wodurch die Anzahl der Übergänge reduziert und der Abgleich beschleunigt wird.
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 ist nicht von std abhängig (erfordert jedoch einen globalen Allocator mit der alloc Kiste).
Dieses Repository enthält eine Befehlszeilenschnittstelle namens daacfind zum Suchen von Mustern in Textdateien.
% 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 {
...
...
Unterstützt diese Bibliothek andere Datentypen als str und [u8] ? (z. B. Strukturen, Eq . implementieren)
Nicht unterstützt. Diese Bibliothek verwendet Aho-Corasick-Automaten, die mit einer Datenstruktur namens Double-Array Trie erstellt wurden. Der Algorithmus für diese Datenstruktur arbeitet mit XOR-Operationen am Eingabe-Heuhaufen. Daher muss der Heuhaufen eine Folge von ganzen Zahlen sein. Diese Bibliothek ist speziell für str und [u8] unter ganzzahligen Sequenzen optimiert.
Bietet diese Bibliothek Bindungen zu anderen Programmiersprachen als Rust?
Wir stellen eine Python-Bindung bereit. Die Unterstützung anderer Programmiersprachen ist derzeit nicht geplant. Wenn Sie Interesse an Schreibeinbänden haben, können Sie dies gerne tun. daachorse ist freie Software.
Wir verfügen über einen Slack-Arbeitsbereich, in dem Entwickler und Benutzer Fragen stellen und verschiedene Themen diskutieren können.
Lizenziert unter einem von beiden
nach Ihrer Wahl.
Wenn Sie diese Bibliothek im akademischen Umfeld nutzen, zitieren Sie bitte den folgenden Artikel.
@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}
}
Siehe die Richtlinien.
