← أحدث الأبحاث
💻 computer science

Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report)

تقترح هذه الورقة أتمتة مجموعات السجلات (RSAs)، وهي نموذج أتمتة جديد يوسع أتمتة السجلات بعمليات قائمة على المجموعات، لتمكين المطابقة الفعالة والحتمية والقوية للتعبيرات المنتظمة التي تحتوي على مراجع خلفية مع إثبات قابليتها للتقرير وقدرتها التعبيرية نظرياً.

المؤلفون الأصليون: Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková

نُشر 2026-04-16
📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة
CC BY 4.0

المؤلفون الأصليون: Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

المشكلة: فخ "النسخ واللصق"

تخيل أنك أمين مكتبة تحاول العثور على كتاب محدد في مكتبة ضخمة وفوضوية. لديك قاعدة بحث تقول: "ابحث عن جملة تبدأ بكلمة 'The'، وتتوسطها كلمة، وتنتهي بنفس الكلمة التي كانت في المنتصف تماماً."

في علوم الحاسوب، يسمى هذا التعبير النمطي (Regex) مع المرجع الخلفي (Backreference). الأمر يشبه إخبار الحاسوب: "تذكر ما رأيته هنا، وتأكد من رؤيته مرة أخرى لاحقاً."

الأزمة الحالية:
معظم البرامج الحاسوبية التي تقوم بهذا النوع من البحث (مثل تلك الموجودة في متصفح الويب أو برامج الحماية) تستخدم طريقة تسمى التراجع (Backtracking).

  • التشبيه: تخيل محققاً يحاول حل جريمة عن طريق التخمين. يخمن مشتبهاً به، ثم يتحقق من حجة الغياب، وإذا فشلت، يعود للخلف، ويمسح التخمين، ويجرب مشتبهاً به آخر.
  • الخطر: إذا كانت القاعدة معقدة والنص طويلاً، فقد يضطر المحقق لتجربة ملايين الاحتمالات. إذا أرسل مخترق (Hacker) جملة طويلة مصممة خصيصاً، سيعلق المحقق في حلقة مفرغة من التخمينات. يتجمد الحاسوب، ويتعطل موقع الويب، وتتوقف الخدمة. يُسمى هذا هجوم ReDoS (حرمان الخدمة باستخدام التعبيرات النمطية).

الحل: الروبوت "جامع المجموعات"

يقترح مؤلفو هذه الورقة البحثية طريقة جديدة للبحث لا تعتمد على التخمين. لقد قدموا نوعاً جديداً من الآلات يسمى آلة مجموعة السجلات (Register Set Automata - RSA).

1. الطريقة القديمة مقابل الطريقة الجديدة

  • الآلة القديمة (آلة السجل - Register Automaton): تخيل روبوتاً لديه بضعة جيوب (سجلات). يمكنه وضع عنصر واحد فقط في الجيب. إذا رأى عنصراً جديداً، عليه أن يقرر: "هل أحتفظ بهذا أم بالقديم؟" لا يمكنه تذكر كل ما رآه، بل شيئاً واحداً فقط في كل مرة. هذا يجعل من الصعب التعامل مع قواعد "تذكر هذا" المعقدة دون اللجوء للتخمين.
  • الآلة الجديدة (آلة مجموعة السجلات - Register Set Automaton): تخيل روبوتاً لديه جيوب هي في الواقع سلال سحرية.
    • بدلاً من حمل عنصر واحد فقط، يمكن للسلة أن تحمل مجموعة كاملة من العناصر.
    • بينما يقرأ الروبوت النص، ليس عليه التخمين بشأن أي عنصر يتذكر؛ بل يقوم ببساطة بإلقاء كل عنصر جديد يراه داخل السلة.
    • لاحقاً، عندما يحتاج للتحقق مما إذا كان عنصر معين قد ظهر من قبل، فإنه يكتفي بالنظر داخل السلة. إذا كان العنصر موجوداً، فهذا رائع! وإذا لم يكن موجوداً، فهو ليس هناك.

2. لماذا يعد هذا تغييراً جذرياً؟

لأن الروبوت يستخدم "سلالاً" (مجموعات) بدلاً من الفتحات الفردية، فإنه يصبح حتمياً (Deterministic).

  • حتمي تعني: "هناك مسار واحد فقط للمضي قدماً. لا تخمين، ولا تراجع."
  • التشبيه: بدلاً من المحقق الذي يخمن ويمسح، تخيل حزاماً ناقلاً حيث يتم فرز كل عنصر تلقائياً في حاوية أثناء مروره. لن تضطر أبداً للعودة للخلف أو إعادة فرز أي شيء. السرعة تكون متوقعة وسريعة بغض بغض النظر عن طول النص.

"سحر" الورقة البحثية

تقوم الورقة بثلاثة أشياء رئيسية لجعل هذا العمل ممكناً:

  1. اختراع السلة (نموذج RSA): لقد عرّفوا رسمياً هذه الآلة الجديدة التي يمكنها تخزين مجموعات من البيانات. وأثبتوا أنه بينما تعد هذه الآلات قوية، إلا أنها لا تزال قابلة للحل رياضياً (يمكننا معرفة ما إذا كانت ستنهي المهمة أم لا).
  2. دليل الترجمة (التحويل لآلة حتمية): ابتكروا خوارزمية تأخذ آلة "تعتمد على التخمين" (الطريقة القديمة البطيئة) وتحولها تلقائياً إلى آلة "تحمل السلال" (الطريقة الجديدة السريعة).
    • ملاحظة: أحياناً تفشل عملية الترجمة إذا كانت القاعدة غريبة جداً، لكن بالنسبة للغالبية العظمى من القواعد الواقعية، فإنها تعمل بشكل مثالي.
  3. اختبار السرعة: قاموا ببناء نموذج أولي للروبوت (أداة برمجية تسمى rsamatch) واختبروه مقابل أفضل الأدوات الموجودة حالياً.
    • النتيجة: عندما واجهت هجمات "ReDoS" التي تسبب تعطل الأنظمة الأخرى، لم يبدُ على روبوتهم أي مجهود. لقد أنهى المهمة في أجزاء من الثانية، بينما استغرقت الأدوات الأخرى دقائق أو ساعات (أو تعطلت تماماً).

التأثير في العالم الحقيقي

لماذا يجب أن تهتم؟

  • الأمن: يحب المخترقون استخدام قواعد "النسخ واللصق" هذه لتعطيل الخوادم. هذه الطريقة الجديدة تجعل تنفيذ هذه الهجمات أصعب بكثير.
  • السرعة: يمكن لمواقع الويب والتطبيقات استخدام ميزات بحث قوية دون القلق من أن قيام مستخدم بكتابة جملة طويلة قد يؤدي لتجميد النظام.
  • الموثوقية: إنها تحول موقف "ربما يعمل وربما يتعطل" إلى ضمان "سيعمل بسرعة في كل مرة".

ملخص التشبيه

  • المشكلة: محاولة العثور على زوج متطابق من الجوارب في غرفة مظلمة عن طريق اختيار جورب، ثم فحص الدرج، ثم إعادته، ثم تجربة جورب آخر. إذا كان لديك 1,000 جورب، فسيستغرق الأمر وقتاً طويلاً جداً.
  • الحل القديم: روبوت يختار جورباً، يفحصه، وإذا كان خاطئاً، يعيده ويجرب غيره. (بطيء، وعرضة للتعليق).
  • الحل الجديد (هذه الورقة): روبوت لديه حقيبة سحرية. بينما يلتقط الجوارب، فإنه يضعها جميعاً في الحقيبة. وعندما يحتاج للتحقق مما إذا كان جورب معين موجوداً، فإنه ينظر فقط في الحقيبة. لا يحتاج أبداً لإعادة أي شيء أو التخمين. إنه سريع، وموثوق، ومن المستحيل خداعه ليعلق في حلقة مفرغة.

لقد منح المؤلفون الحواسيب "حقيبة سحرية" للتعامل مع عمليات البحث النصية المعقدة، مما يجعل الإنترنت أكثر أماناً وأسرع.

غارق في أبحاث مجالك؟

تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.

جرّب Digest →

أبحاث مشابهة

عرض الكل في هذا التصنيف 💻 cs →