daachorse
1.0.0
تنفيذ سريع لخوارزمية Aho-Corasick باستخدام بنية البيانات المدمجة ذات الصفيف المزدوج.
تظهر الأفكار التقنية الرئيسية وراء هذه المكتبة في الورقة التالية:
شونسوكي كاندا، كويتشي أكابي، ويوسوكي أودا. هندسة أتمتة Aho-Corasick مزدوجة الصفيف بشكل أسرع. البرمجيات: الممارسة والخبرة (SPE) ، 53(6): 1332-1361، 2023 (arXiv)
يتوفر أيضًا غلاف Python هنا.
Daachorse عبارة عن صندوق لمطابقة الأنماط المتعددة السريعة باستخدام خوارزمية Aho-Corasick، والتي تعمل في وقت خطي على طول نص الإدخال. يستخدم هذا الصندوق بنية بيانات مدمجة مزدوجة الصفيف لتنفيذ تطابق النمط الآلي من أجل كفاءة الوقت والذاكرة. لا تدعم بنية البيانات اجتياز حالة إلى حالة في الوقت الثابت فحسب، بل تمثل أيضًا كل حالة في مساحة 12 بايت فقط.
على سبيل المثال، مقارنةً بـ NFA لصندوق aho-corasick، وهو تطبيق Aho-Corasick الأكثر شيوعًا في Rust، يمكن لـ Daachorse إجراء مطابقة الأنماط بشكل أسرع بمقدار 3.0–5.2 مرة بينما يستهلك ذاكرة أصغر بنسبة 56–60% عند استخدام قاموس كلمات أنماط 675K. النتائج التجريبية الأخرى متاحة على ويكي.
مطلوب الصدأ 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؟
نحن نقدم ربط بايثون. لغات البرمجة الأخرى ليست مخططة حاليًا لدعمها. إذا كنت مهتمًا بكتابة الروابط، فنحن نرحب بك للقيام بذلك. 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}
}
انظر المبادئ التوجيهية.
