ملخص تقني: حول تعقيد مشكلة مطابقة التعبيرات النمطية مع المراجع الخلفية

1. تعريف المشكلة والدوافع

يبحث البحث في التعقيد الحسابي الدقيق لمشكلة مطابقة التعبيرات النمطية مع المراجع الخلفية (REWB). بينما يمكن مطابقة التعبيرات النمطية الكلاسيكية (Regex) في وقت خطي بالنسبة لطول سلسلة الإدخال $|w|$ باستخدام بناء ثومبسون (Thompson's construction)، فإن المحركات العملية تدعم المراجع الخلفية (على سبيل المثال، (E)x لالتقاط سلسلة فرعية و \x لإعادة استخدامها). هذه الميزة توسع قوة التعبير بشكل صارم (مما يسمح بالتعرف على لغات غير منتظمة مثل $\{ww \mid w \in \Sigma^*\}$) ولكنها تفرض مخاطر خوارزمية كبيرة.

ينبع الدافع من هجمات حرمان الخدمة عبر التعبيرات النمطية (ReDoS)، حيث يقوم المهاجمون بصياغة مدخلات لتنشيط أسوأ حالات الأداء في محركات المطابقة. وقد أظهرت حوادث بارزة في Stack Overflow (2016) و Cloudflare (2019) أن السلوك التربيعي ($O(|w|^2)$) في محركات التراجع (backtracking) يمكن أن يتسبب في انقطاع كارثي للخدمة. يطرح المؤلفون السؤال الجوهري: هل من الممكن بناء محركات آمنة ضد هجمات ReDoS لمشكلة REWB تعمل في وقت خطي أو قريب من الخطي؟

يركز البحث على $r$-use $k$-REWBs، وهي تعبيرات تحتوي على $k$ من المتغيرات المختلفة حيث يتم تحديد إجمالي عدد عمليات تنفيذ المرجع الخلفي في أي عملية حسابية بـ $r$.

2. المنهجية والنهج التقني

يستخدم البحث نهجاً مزدوجاً: وضع حدود دنيا مشروطة (الصعوبة) وتصميم خوارزميات فعالة لفئات فرعية محددة.

2.1 نتائج الصعوبة

يعزز المؤلفون نتائج التعقيد السابقة من خلال تقليل مشكلات معروفة بصعوبتها إلى مطابقة REWB:

• W[2]-hardness: من خلال تقليل مشكلة $k$-Dominating Set، يثبتون أن مطابقة REWB هي W[2]-hard عندما يتم تحديد المعامل بحجم التعبير $|E|$. وهذا يعزز نتيجة W[1]-hardness المعروفة.
• الحدود الدنيا المشروطة (كشف المثلث): بافتراض فرضية "عدم وجود وقت شبه خطي" لكشف المثلث (Triangle Detection)، يظهرون أن مشكلة 2-use 2-REWB المقيدة للغاية لا يمكن حلها في زمن $O(|w|^{1+\delta})$ لأي $\delta > 0$.
• الحدود الدنيا المشروطة (k-OV): تحت فرضية $k$-Orthogonal Vectors (k-OV) (وهي أضعف من SETH)، يثبتون أن مطابقة $k$-REWB لا يمكن حلها في زمن $O(|w|^{2k-\epsilon})$. وهذا يعني أنه بالنسبة لـ $k$ العامة، فإن الوقت القريب من الخطي غير مرجح.

2.2 النتائج الخوارزمية

يركز المساهمة الخوارزمية الأساسية على 1-use REWBs (التعبيرات التي تحتوي على متغير واحد يتم استدعاؤه مرة واحدة بالضبط).

• تحويل الشكل المعياري (Canonical Form): يثبت المؤلفون أن أي 1-use REWB يمكن تحويله إلى شكل معياري يتضمن مجموع حدود مثل $A (B)_x C \backslash x D$، حيث $A, B, C, D$ هي تعبيرات نمطية كلاسيكية. يُطلق على هذا اسم مشكلة ABCBD.
• استراتيجية التفكيك: يتم تفكيك مشكلة ABCBD إلى مشكلتين فرعيتين:
  1. مشكلة XYYZ: الحالة التي يكون فيها وجودتا $B$ متجاورين ($w = w_A w_B w_B w_D$). يتم حل هذه الحالة باستخدام تعداد القوة المحلية القصوى لـ Crochemore وخصائص المجموعات دورية النهاية المستمدة من مونويدات الانتقال.
  2. مشكلة ABCBD المتفرعة: الحالة التي يفصل بين وجودتي $B$ عنصر $C$ غير فارغ، وتختلف الأحرف التي تلي وجودتي $B$ مباشرة.
• شجرة اللاحقة (Suffix Tree) وتفكيك الثقل-الخفة (Heavy-Light Decomposition): بالنسبة للحالة المتفرعة، تستخدم الخوارزمية شجرة اللاحقة لسلسلة الإدخال $w$. وهي تستخدم تفكيك الثقل-الخفة لتقسيم فضاء البحث.
• هياكل البيانات:
  • غابات التجزئة (Factorization Forests): تُستخدم لتقييم عضوية التعبيرات النمطية في السلاسل الفرعية في وقت ثابت بعد معالجة مسبقة خطية.
  • مونويدات الانتقال (Transition Monoids): تُستغل لتتبع حالة التعبيرات النمطية $A, B, C, D$ بكفاءة.
  • المعدادات المخصصة (Custom Enumerators): يصمم المؤلفون هياكل بيانات متخصصة (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) للتعامل مع تعداد الانتقال. تستخدم هذه الهياكل تحديثات كسولة (lazy updates) واستراتيجيات اتحاد المجموعات المنفصلة (DSU) لإدارة القيود التي تتغير مع طول السلسلة الفرعية $w_B$.

3. النتائج الرئيسية

الصعوبة

• النظرية 3: مشكلة REWB هي W[2]-hard بمعامل حجم التعبير.
• النظرية 4: بافتراض فرضية كشف المثلث، تتطلب مطابقة 2-use 2-REWB وقتاً فوق خطي (تحديداً، ليست $O(|w|^{1+\delta})$).
• النظرية 5: تحت فرضية $k$-OV، تتطلب مطابقة $k$-REWB زمناً قدره $\Omega(|w|^{2k-\epsilon})$.

الخوارزميات

• النظرية 7 (النتيجة الرئيسية): تقبل مشكلة ABCBD خوارزمية بزمن $O(|w| \log^2 |w|)$. الثابت المخفي يعتمد أسياً على أحجام التعبيرات النمطية $A, B, C, D$ ($2^{O((|A|+|B|+|C|+|D|)^2)}$).
• النظرية 8: وبناءً على ذلك، تقبل مشكلة 1-use REWB matching خوارزمية بزمن $O(|w| \log^2 |w|)$.
• النظرية 9: تقبل مشكلة XY$\alpha$Z (التي تعمم XYYZ إلى تكرارات $\alpha$) خوارزمية بزمن $O(|w| \log |w|)$.

تمثل هذه النتائج تحسيناً كبيراً عن أفضل خوارزمية معروفة سابقاً بزمن $O(|w|^2)$ لمشكلة ABCBD من قبل Nogami و Terauchi (MFCS 2025).

4. الأهمية والادعاءات

يدعي البحث تقديم فهم جوهري للمشهد التعقيدي لمطابقة REWB:

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

يصرح المؤلفون صراحة أن خوارزميتهم موحدة (uniform)، مما يعني أنها تعالج التعبير وسلسلة الإدخال معاً دون نصيحة غير موحدة تعتمد على التعبير الثابت. كما يقرون بأن الاعتماد الأسي على حجم التعبير $|E|$ يظل قيداً، ويتركون مسألاً مفتوحة حول ما إذا كانت توجد خوارزمية زمن خطي حقاً ($O(|w|)$) أو ما إذا كان يمكن إزالة العوامل اللوغاريتمية.

5. القيود والمشكلات المفتوحة

يحدد البحث عدة اتجاهات مفتوحة:

• تعقيد $r$-use 1-REWB: لا يزال تعقيد $r$-use 1-REWBs حيث $r \ge 2$ مفتوحاً.
• الزمن الخطي: ما إذا كان يمكن تحسين حد $O(|w| \log^2 |w|)$ إلى $O(|w|)$.
• الاعتماد على التعبير: تقليل الاعتماد الأسي على $|E|$ إلى اعتماد حدودي مع الحفاظ على الاعتماد القريب من الخطي على $|w|$.
• الميزات الأوسع: توسيع هذه النتائج لتشمل ميزات أخرى عملية للتعابير النمطية مثل الالتفاتات (lookarounds)، والتجميع الذري (atomic grouping)، والنجوم الجشعة/الكسولة (greedy/lazy stars).