daachorse
1.0.0
Implementasi cepat dari algoritma Aho-Corasick menggunakan struktur data array ganda yang ringkas.
Ide teknis utama di balik perpustakaan ini muncul dalam makalah berikut:
Shunsuke Kanda, Koichi Akabe, dan Yusuke Oda. Merekayasa automata Aho-Corasick array ganda yang lebih cepat. Perangkat Lunak: Praktek dan Pengalaman (SPE) , 53(6): 1332–1361, 2023 (arXiv)
Pembungkus Python juga tersedia di sini.
Daachorse adalah peti untuk pencocokan beberapa pola dengan cepat menggunakan algoritma Aho-Corasick, berjalan dalam waktu linier sepanjang teks masukan. Peti ini menggunakan struktur data array ganda yang ringkas untuk mengimplementasikan robot pencocokan pola untuk efisiensi waktu dan memori. Struktur data tidak hanya mendukung traversal antar negara secara konstan tetapi juga mewakili setiap negara dalam ruang hanya 12 byte.
Misalnya, dibandingkan dengan NFA dari aho-corasick crate, yang merupakan implementasi Aho-Corasick paling populer di Rust, Daachorse dapat melakukan pencocokan pola 3,0–5,2 kali lebih cepat sambil mengonsumsi memori 56–60% lebih kecil saat menggunakan kamus kata pola 675 ribu. Hasil eksperimen lainnya tersedia di Wiki.
Diperlukan karat 1,61 atau lebih tinggi untuk membuat peti ini.
Daachorse berisi beberapa opsi pencarian, mulai dari pencocokan standar dengan algoritma Aho-Corasick hingga pencocokan yang lebih rumit. Mereka akan berjalan sangat cepat berdasarkan struktur data array ganda dan dapat dengan mudah dicolokkan ke aplikasi Anda, seperti yang ditunjukkan di bawah ini.
Untuk mencari semua kemunculan pola terdaftar yang memungkinkan terjadinya tumpang tindih posisi dalam teks masukan, gunakan find_overlapping_iter() . Saat Anda menggunakan new() untuk konstruksi, perpustakaan memberikan pengidentifikasi unik untuk setiap pola dalam urutan input. Hasil pencocokan memiliki posisi byte kejadian dan pengidentifikasinya.
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 ( ) ) ; Jika Anda tidak ingin membiarkan posisi tumpang tindih, gunakan find_iter() sebagai gantinya. Ia melakukan pencarian pada otomat Aho-Corasick dan melaporkan pola yang pertama kali ditemukan di setiap iterasi.
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 ( ) ) ; Jika Anda ingin mencari pola terpanjang tanpa tumpang tindih posisi di setiap iterasi, gunakan leftmost_find_iter() dengan menentukan MatchKind::LeftmostLongest dalam konstruksi.
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 ( ) ) ; Jika Anda ingin menemukan pola terdaftar paling awal di antara pola yang dimulai dari posisi pencarian, gunakan leftmost_find_iter() dengan menentukan MatchKind::LeftmostFirst .
Inilah yang disebut pencocokan pertama paling kiri , opsi pencarian rumit yang didukung di peti aho-corasick. Misalnya, pada kode berikut, ab dilaporkan karena merupakan kode yang paling awal didaftarkan.
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 ( ) ) ; Untuk membuat robot dari pasangan pola dan nilai yang ditentukan pengguna, alih-alih menetapkan pengidentifikasi secara otomatis, gunakan 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 ( ) ) ; Untuk membuat automaton yang lebih cepat pada karakter multibyte, gunakan CharwiseDoubleArrayAhoCorasick sebagai gantinya.
Versi standar DoubleArrayAhoCorasick menangani string sebagai urutan UTF-8 dan mendefinisikan label transisi menggunakan nilai byte. Di sisi lain, CharwiseDoubleArrayAhoCorasick menggunakan nilai titik kode Unicode, mengurangi jumlah transisi dan pencocokan lebih cepat.
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 tidak memiliki ketergantungan pada std (tetapi memerlukan pengalokasi global dengan peti alloc ).
Repositori ini berisi antarmuka baris perintah bernama daacfind untuk mencari pola dalam file teks.
% 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 {
...
...
Apakah perpustakaan ini mendukung tipe data selain str dan [u8] ? (misalnya, struktur yang menerapkan Eq .)
Tidak didukung. Perpustakaan ini menggunakan automata Aho-Corasick yang dibangun dengan struktur data yang disebut double-array trie . Algoritma pada struktur data ini bekerja dengan operasi XOR pada input haystack. Oleh karena itu, tumpukan jerami harus berupa barisan bilangan bulat. Pustaka ini secara khusus dioptimalkan untuk str dan [u8] di antara urutan bilangan bulat.
Apakah perpustakaan ini menyediakan pengikatan ke bahasa pemrograman selain Rust?
Kami menyediakan pengikatan Python. Bahasa pemrograman lain saat ini tidak direncanakan untuk didukung. Jika Anda tertarik untuk menulis binding, silakan melakukannya. daachorse adalah perangkat lunak bebas.
Kami memiliki ruang kerja Slack bagi pengembang dan pengguna untuk mengajukan pertanyaan dan mendiskusikan berbagai topik.
Berlisensi di bawah salah satu dari
sesuai pilihan Anda.
Jika Anda menggunakan perpustakaan ini dalam lingkungan akademis, harap kutip makalah berikut.
@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}
}
Lihat pedomannya.
