المقارنة الخطية Linear comparison

إذا كان التعبير المنتظم لا يحتوي على محددات كميات Regex quantifiers أو اختيارات Regex Alternations (نتحدث عنها في موضوع خاص)، فسيقوم محرك التعبير المنتظم بتنفيذ البحث بشكل خطي. بمعنى أن المحرك يقوم بمطابقة الرمز الأول في النمط بالرمز الأول في النص، ثم الرمز التالي في النمط مع الرمز التالي في النص وهكذا إلى أن ينجح التطابق أو يفشل. بهذا الشكل فالمحرك يتحرك خطوة بخطوة داخل النص والنمط على التوازي.

مثلاً النمط e{2}\w\b يبحث عن حرفين e متبوعات برمز كلمة Word Character ثم حد كلمة Word boundary، وبالرغم أن النمط يحتوي على {2} وهو أحد محددات الكميات إلا أنه سيعمل بشكل خطي لأنها تبحث عن إثنان بالضبط من الحرف e، أي بدون خيارات.

وعند تطبيق النمط على النص [ien]needing a reed[/ien] يأخذ المحرك الخطوات التالية:

• المحرك يقف قبل n في بداية النص [ien]needing a reed[/ien]
• هل e في النمط تتطابق مع n ؟ لا
• ينتقل المحرك في النص بعد n، أي [ien]eeding a reed[/ien]
• هل e في النمط تتطابق مع e ؟ نعم. يعرف المحرك أنه يوجد احتمال تطابق
• ينتقل المحرك في النص بعد e الأولى، أي [ien]eding a reed[/ien]
• مطلوب من المحرك البحث عن e أخرى فهل بعد e الأولى يوجد e ثانية؟ نعم. يعرف المحرك أنه يوجد احتمال تطابق
• ينتقل المحرك في النص بعد e الثانية وينتقل في النمط إلى \wأي [ien]ding a reed[/ien]
•  هل \w تتطابق مع d؟ نعم
• ينتقل المحرك في النص بعد d وينتقل في النمط إلى \bأي [ien]ing a reed[/ien]
• هل \b تتطابق مع i؟ لا. هنا يفشل المحرك في مطابقة النمط وليس عنده خيارات، فيقرر البدء من مكان آخر غير الذي بدء من عنده، فيبدأ من بعد e التي حدث عندها أول تطابق ليصبح النص الآن [ien]eding a reed[/ien]
• الآن المحرك يقف قبل e في بداية النص
• هل e في النمط تتطابق مع e ؟ نعم. يعرف المحرك أنه يوجد احتمال تطابق
• ينتقل المحرك في النص بعد e الأولى ding a reed
• مطلوب من المحرك البحث عن e أخرى فهل بعد e الأولى يوجد e ثانية؟ لا (يوجد d). هنا يفشل المحرك في مطابقة النمط وليس عنده خيارات، فيقرر البدء من مكان آخر غير الذي بدء من عنده، فيبدأ من بعد e التي حدث عندها تطابق (قبل d) ليصبح النص الآن [ien]ding a reed[/ien]
• هل e في النمط تتطابق مع d ؟ لا
• هل e في النمط تتطابق مع i ؟ لا
• هل e في النمط تتطابق مع n ؟ لا
• هل e في النمط تتطابق مع g ؟ لا
• هل e في النمط تتطابق مع المسافة البيضاء ؟ لا
• هل e في النمط تتطابق مع a ؟ لا
• هل e في النمط تتطابق مع المسافة البيضاء ؟ لا
• هل e في النمط تتطابق مع r ؟ لا
• هل e في النمط تتطابق مع e ؟ نعم. يعرف المحرك أنه يوجد احتمال تطابق
• مطلوب من المحرك البحث عن e أخرى فهل بعد e الثالثة يوجد e أخرى؟ نعم
• ينتقل المحرك في النص بعد e الرابعة وينتقل في النمط إلى \wأي [ien]d[/ien]
• هل \w تتطابق مع d؟ نعم
• هل \b تتطابق مع حدود الكلمة؟ نعم. يحدث هنا التطابق الكامل.

وكما لاحظت في المثال السابق فالمحرك عندما يحذث تطابق في جزء من النمط ثم يفشل باقي النمط، يقوم بالرجوع لما بعد النقطة التي حدث عندها آخر تطابق. أي في كل مرة يبدأ من مكان ويحدث تطابق ثم يفشل يعود مرة أخرى ليبدأ من جديد ولكن من بعد هذه المكان. ولكن هذا يحدث إذا لم يكن للمحرك خيارات أخرى لتجربتها قبل الفشل.

الجدول التالي يوضح خطوات المحرك

التتيع الخلفي باستخدام محددات الكميات والبدائل

في حالة وجود أي من محددات الكميات regex quantifiers أو البدائل Regex alternations لاتصبح عملية المطابقة خطية، لأنه بسبب الخيارات يصبح أداء المحرك مبني على الحالات المنتهية الغير محسوبة NFA والتي بدورها تعتمد على النمط لتحديد المتطابقات وليس النص. وعندما يقوم المحرك بمطابقة رمز اختياري أو رمز كميته اختيارية في النمط ثم ينجح، ثم يؤدي هذا النجاح الجزئي إلى فشل الرمز التالي في النمط، يقوم المحرك بالتخلي عن جزء من المطابقة الإختيارية أو تجربة بديل آخر في حالة البدhئل Regex alternations. وهذا يعني أن المحرك يقوم بالرجوع لآخر حالة تم تخزينها في المحرك (آخر حالة نجحت في المطابقة) للتخلي عن جزء من المطابقة أو تجربة بديل آخر بهدف مطابقة كامل النص.

عملية الرجوع لحالة تم تخزينها في المحرك بهدف مطابقة كامل النص تسمى التتبع الخلفي Backtracking. وخلال التتبع الخلفي يتم التخلي عن جزء من مطابقة الرمز السابق في النمط إن كان محدد الكمية أو اختيار بديل آخر في حالة وجود بدائل.

مثلاً النمط .*(es) يقوم بمطابقة es وأي مجموعة من الرموز/الأحرف تسبقها، وعند تطبيقها على [ien]Essential services are provided by regular expressions[/ien] يأخذ المحرك الخطوات التالي:

لاحظ في الجدول السابق:

• قامت .* بمطابقة كامل النص في الخطوة رقم 1
• ينتقل المحرك لمحاولة مطابقة e مع نهاية السطر فيفشل النمط
• نتيجة لأن مطابقة جزء من النمط قامت بمطابقة كامل النص مما يؤدي إلى فشل الرموز بالبقاية في النص، يعود المحرك للحالة السابقة، وهي الحالة التي سيبدأ المحرك في مطابقة الرمز .* لكي يطابقه من جديد ولكن هذه المرة لن يجلب كامل النص
• ثم بدأ المحرك بالرجوع إلى الخلف حرف حرف إلى أن وصل للتطابق في الخطوة رقم 9،
• ثم بدأ عملية مطابقة جديدة على ما تبقى من النص بداية من الخطوة 10 فتقوم .* مرة أخرى بمطابقة باقي النص بالكامل، مما يؤدي إلى فشل النمط مرة أخرى
• يكرر المحرك التراجع للخلف حرف حرف محاولاً البحث عن e لكن يفشل في النهاية.

أما بالنسبة للبدائل Regex Alternations فهي الأخرى تجعل المحرك يقوم بعمل تتبع خلفي إذا تسبب أحد البدائل في فشل باقي رموز النمط،ولكن نتحدث عن التتبع الخلفي Backtracking في الموضوع الخاص بالبدائل.