مشاكل التتبع الخلفي أول x+ ستقوم بمطابقة جميع x وعددها 10 عندما ينتقل المحرك لمطابقة x+ الثانية لايجد مطابقات يقوم المحرك بالتخلي عن جزء من مطابقة x+ الأولى بحيث يتم مطابقة 9 فقط عندما ينتقل المحرك لمطابقة x+ الثانية يجد أن هناك تطابق مع x الباقية من الـ 10 يخرج المحرك من المججموعة ولكن يجد أنه بحاجة لتكرار النمط مرة أو أكثر بسبب + يحاول المحرك التكرار ولكنه يفشل، ولكن بينما المجموعة تم مطابقتها مرة فهذا مقبول لأن + تطابق مرة أو أكثر ينتقل المحرك لمطابقة y في النمط مع y في النص فيحدث تطابق ويتطابق النمط بالكامل

هذا كما قلنا لايشكل مشكلة، وإنما تظهر المشكلة عند غياب حرف y، حيث سيقوم المحرك بالآتي:

عندما تفشل y يحتاج المحرك لعمل تتبع خلفي فيعود داخل المجموعة Capturing group يجد المحرك أن x+ الثانية بها x واحدة فقط فلايستطيع عمل تتبع خلفي بها يعود المحرك إلى x+ الأولى فيجد أنها تحتوي على 9 من الحرف x فيقوم بتقليص المطابقة بمقدار 1 ليطابق 8 فقط ينتقل المحرك إلى x+ الثانية لتطابق الإثنين x الباقيتين يحاول المحرك مرة أخرى مطابقة y فيفشل يعود المحرك المجموعة داخل المجموعة يجد أنه يمكن التتبع الخلفي من خلال x+ الثانية التي تحتوي على 2 من x تصبح الآن x+ الثانية عبارة عن x واحدة يحاول المحرك مرة أخرى مطابقة y مع x الناتجة عن التتبع الخلفي فيفشل يحاول المحرك التتبع الخلفي مرة أخرى داخل x+ الثانية لكن لم يتبقى فيها إلى x واحدة ينتقل المحرك إلى x+ الأولى فيجد أن بها من الحرف x فيقوم بتقليص المطابقة بمقدار 1 ليطابق 7 فقط. يعيد الكرة ويستمر في تكرار الخطوات السابقة إلى أن تصبح مطابقة x+ الثانية عبارة عن 9 من الحرف x و x+ الأولى بها x واحدة وفي النهاية يفشل.

هل ترى كم عمليات التتبع الخلفي والخطوات التي يأخذه المحرك حتى يكتشف عدم التطابق، وإذا قمت باختبار ذلك على أحد أدوات التعبيرات المنتظمة وأهمها RegexBuddy ستجد أن المحرك في حالة 10x يحتاج إلى 2558 خطوة لاكتشاف عدم التطابق.

وكلما قمت بإضافة x واحدة فقط سيتضاعف عدد الخطوات أي إذا كان هنا 11x يحتاج المحرك 5118 ,و 12x يحتاج إلى 10238 خطوة لاكتشاف عدم التطابق، وبالطبع هذا يشكل عيب كارثي في أداء البرنامج، لذلك يجب أن يكون هناك حل.

[highlight background=”” color=””]موقع regex101 لايعطي نتائج دقيقة بالنسبة لخطوات المحرك عند التتبع الخلفي الكارثي[/highlight]

التحكم في التتبع الخلفي Backtracking control

يمكن التحكم في التتبع الخلفي عن طريق:

التجميع الذري Atomic grouping باستخدام (?>x+x+)+y والذي سيلغي كل أماكن التتبع الخلفي داخل المجموعة وبالتالي إما تكون المطابقة خطية linear comparison أو لا، بحيث عند مطابقة جميع x ينتقل المحرك إلى المحرك إلى مطابقة y فإن فشل، يحاول المحرك البدء من مكان جديد، فيبدأ مرة أخرى من بعد x الأولى ويفشل أيضاً, وهكذا تتكرر العملية في عدد قليل من الخطوات حتى يكتشف المحرك أنه لايمكن مطابقة النمط نهائياً. وبالتال يكون عدد خطوات التتبع الخلفي لن يزيد عن عدد أحرف x فقط. المحددات الإستحواذية Possessive quantifier باستخدام (x+x+)++y حيث تمنع المحرك من تجربة احتمالات أخرى وبالتالي عندما يقوم المحرك بمطابقة كل x، ثم يفشل النمط، ولايحاول الرجوع لمكان آخر لتجربة احتمال آخر وإنما يقوم بإعادة تجربة النمط من بدايته من مكان جديد كما هو الحال في التجميع الذري.