daachorse
1.0.0
การใช้งานอัลกอริธึม Aho-Corasick อย่างรวดเร็วโดยใช้โครงสร้างข้อมูลอาร์เรย์คู่ขนาดกะทัดรัด
แนวคิดทางเทคนิคหลักที่อยู่เบื้องหลังห้องสมุดนี้ปรากฏในเอกสารต่อไปนี้:
ชุนสุเกะ คันดะ, โคอิจิ อาคาเบะ และ ยูสึเกะ โอดะ วิศวกรรมออโตมาตะ Aho-Corasick แบบอาร์เรย์คู่ที่เร็วขึ้น ซอฟต์แวร์: การปฏิบัติและประสบการณ์ (SPE) , 53(6): 1332–1361, 2023 (arXiv)
Python wrapper มีให้ที่นี่เช่นกัน
Daachorse เป็นลังสำหรับการจับคู่หลายรูปแบบอย่างรวดเร็วโดยใช้อัลกอริธึม Aho-Corasick ซึ่งทำงานตามเวลาเชิงเส้นตามความยาวของข้อความที่ป้อน ลังนี้ใช้โครงสร้างข้อมูลอาร์เรย์คู่ขนาดกะทัดรัดสำหรับการนำระบบอัตโนมัติจับคู่รูปแบบไปใช้เพื่อประสิทธิภาพด้านเวลาและหน่วยความจำ โครงสร้างข้อมูลไม่เพียงแต่รองรับการแวะผ่านระหว่างรัฐต่อเวลาคงที่เท่านั้น แต่ยังแสดงถึงแต่ละรัฐในพื้นที่เพียง 12 ไบต์อีกด้วย
ตัวอย่างเช่น เมื่อเปรียบเทียบกับ NFA ของ aho-corasick crate ซึ่งเป็นการใช้งาน Aho-Corasick ที่ได้รับความนิยมมากที่สุดใน Rust แล้ว Daachorse สามารถทำการจับคู่รูปแบบ ได้เร็วกว่า 3.0–5.2 เท่า ในขณะที่ใช้หน่วยความจำ น้อยลง 56–60% เมื่อใช้พจนานุกรมคำของ 675,000 รูปแบบ ผลการทดลองอื่นๆ มีอยู่ใน Wiki
ต้องใช้สนิม 1.61 หรือสูงกว่าเพื่อสร้างลังนี้
Daachorse มีตัวเลือกการค้นหาบางอย่าง ตั้งแต่การจับคู่แบบมาตรฐานกับอัลกอริธึม Aho-Corasick ไปจนถึงการจับคู่ที่ซับซ้อนยิ่งขึ้น โดยจะทำงานเร็วมากตามโครงสร้างข้อมูลแบบอาร์เรย์คู่ และสามารถเสียบเข้ากับแอปพลิเคชันของคุณได้อย่างง่ายดาย ดังที่แสดงด้านล่าง
หากต้องการค้นหารูปแบบที่ลงทะเบียนไว้ทั้งหมดซึ่งอนุญาตให้มีการทับซ้อนกันของตำแหน่งในข้อความอินพุต ให้ใช้ find_overlapping_iter() เมื่อคุณใช้ new() ในการก่อสร้าง ไลบรารีจะกำหนดตัวระบุที่ไม่ซ้ำกันให้กับแต่ละรูปแบบในลำดับอินพุต ผลการแข่งขันจะมีตำแหน่งไบต์ของเหตุการณ์และตัวระบุ
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 ( ) ) ; หากคุณไม่ต้องการให้ตำแหน่งทับซ้อนกัน ให้ใช้ find_iter() แทน โดยจะทำการค้นหาหุ่นยนต์ Aho-Corasick และรูปแบบการรายงานที่พบครั้งแรกในการวนซ้ำแต่ละครั้ง
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 ( ) ) ; หากคุณต้องการค้นหารูปแบบที่ยาวที่สุดโดยไม่มีการทับซ้อนกันของตำแหน่งในการวนซ้ำแต่ละครั้ง ให้ใช้ leftmost_find_iter() โดยระบุ MatchKind::LeftmostLongest ในโครงสร้าง
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 ( ) ) ; หากคุณต้องการค้นหารูปแบบที่ลงทะเบียนไว้เร็วที่สุดจากตำแหน่งการค้นหา ให้ใช้ leftmost_find_iter() โดยระบุ MatchKind::LeftmostFirst
นี่คือสิ่งที่เรียกว่า การจับคู่แรกซ้ายสุด ซึ่งเป็นตัวเลือกการค้นหาที่ยุ่งยากซึ่งสนับสนุนในลัง aho-corasick ตัวอย่างเช่น ในรหัสต่อไปนี้ มีรายงาน ab เนื่องจากเป็นรหัสที่ลงทะเบียนเร็วที่สุด
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 ( ) ) ; หากต้องการสร้างหุ่นยนต์จากคู่ของรูปแบบและค่าที่ผู้ใช้กำหนด แทนที่จะกำหนดตัวระบุโดยอัตโนมัติ ให้ใช้ 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 ( ) ) ; หากต้องการสร้างหุ่นยนต์ที่เร็วขึ้นบนอักขระหลายไบต์ ให้ใช้ CharwiseDoubleArrayAhoCorasick แทน
DoubleArrayAhoCorasick เวอร์ชันมาตรฐานจะจัดการสตริงเป็นลำดับ UTF-8 และกำหนดป้ายกำกับการเปลี่ยนโดยใช้ค่าไบต์ ในทางกลับกัน CharwiseDoubleArrayAhoCorasick ใช้ค่าจุดโค้ด Unicode ซึ่งช่วยลดจำนวนการเปลี่ยนและจับคู่ได้เร็วขึ้น
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 ไม่มีการพึ่งพา std (แต่ต้องมีตัวจัดสรรทั่วโลกพร้อมกล่อง alloc )
พื้นที่เก็บข้อมูลนี้มีอินเตอร์เฟสบรรทัดคำสั่งชื่อ daacfind สำหรับการค้นหารูปแบบในไฟล์ข้อความ
% 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 {
...
...
ไลบรารีนี้รองรับประเภทข้อมูลอื่นที่ไม่ใช่ str และ [u8] หรือไม่ (เช่น โครงสร้างที่ใช้ Eq .)
ไม่รองรับ. ไลบรารีนี้ใช้ออโตมาตะ Aho-Corasick ที่สร้างขึ้นด้วยโครงสร้างข้อมูลที่เรียกว่า double-array trie อัลกอริธึมในโครงสร้างข้อมูลนี้ทำงานร่วมกับการดำเนินการ XOR บนกองหญ้าอินพุต ดังนั้นกองหญ้าต้องเป็นลำดับของจำนวนเต็ม ไลบรารีนี้ได้รับการปรับให้เหมาะสมเป็นพิเศษสำหรับ str และ [u8] ระหว่างลำดับจำนวนเต็ม
ไลบรารีนี้มีการเชื่อมโยงกับภาษาโปรแกรมอื่นที่ไม่ใช่ Rust หรือไม่
เรากำลังจัดเตรียมการเชื่อมโยง Python ขณะนี้ยังไม่มีแผนที่จะรองรับภาษาการเขียนโปรแกรมอื่นๆ หากคุณสนใจที่จะเขียนเข้าเล่มก็สามารถทำเช่นนั้นได้ daachorse เป็นซอฟต์แวร์ฟรี
เรามีพื้นที่ทำงาน Slack สำหรับนักพัฒนาและผู้ใช้เพื่อถามคำถามและสนทนาในหัวข้อต่างๆ
ได้รับอนุญาตภายใต้ข้อใดข้อหนึ่ง
ตามตัวเลือกของคุณ
หากคุณใช้ห้องสมุดนี้ในสถานศึกษา โปรดอ้างอิงเอกสารต่อไปนี้
@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}
}
ดูหลักเกณฑ์
