Regular Expressions
बैक ट्रैकिंग

Backtracking का क्या कारण है?

एक मैच खोजने के लिए, रेगेक्स इंजन एक-एक करके पात्रों का उपभोग करेगा। जब एक आंशिक मैच शुरू होता है, तो इंजन स्टार्ट की स्थिति को याद रखेगा ताकि यह वापस जा सके, अगर निम्नलिखित अक्षर मैच पूरा नहीं करते हैं।

• यदि मैच पूरा हो गया है, तो कोई पीछे नहीं है
• यदि मैच पूरा नहीं होता है, तो इंजन एक पूरे मैच को खोजने की कोशिश करने के लिए स्ट्रिंग को पीछे कर देगा (जैसे जब आप एक पुराने टेप को रिवाइंड करते हैं)।

उदाहरण के लिए: \d{3}[az]{2} स्ट्रिंग के खिलाफ abc123def को इस तरह ब्राउज किया जाएगा:

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does match \d (third one)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

अब एक ही स्ट्रिंग ( abc123def ) के खिलाफ regex को \d{2}[az]{2} बदलने देता है:

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does not match [a-z]
abc123def
    ^ BACKTRACK to catch \d{2} => (23)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

क्यों जाल एक जाल हो सकता है?

बैकट्रैकिंग वैकल्पिक क्वांटिफायर या वैकल्पिक निर्माणों के कारण हो सकती है, क्योंकि रेगेक्स इंजन हर पथ का पता लगाने की कोशिश करेगा। यदि आप aaaaaaaaaaaaaa खिलाफ रेगेक्स a+b चलाते हैं तो कोई मुकाबला नहीं है और इंजन इसे बहुत तेज लगेगा।

लेकिन अगर आप रेगेक्स को (aa*)+b एए (aa*)+b में बदलते हैं, तो संयोजनों की संख्या बहुत तेजी से बढ़ेगी, और सबसे (अनुकूलित नहीं) इंजन सभी रास्तों का पता लगाने की कोशिश करेंगे और एक मैच खोजने या फेंकने की कोशिश करने के लिए अनंत काल लेंगे टाइमआउट अपवाद। इसे भयावह बैकट्रैकिंग कहा जाता है ।

बेशक, (aa*)+b एक नौसिखिया त्रुटि लगती है, लेकिन यह यहाँ बिंदु को चित्रित करने के लिए है और कभी-कभी आप एक ही मुद्दे के साथ लेकिन अधिक जटिल पैटर्न के साथ समाप्त करेंगे।

भयावह बैकट्रैकिंग का एक और चरम मामला रेगेक्स (x+x+)+y (आप शायद इसे यहां और यहां से पहले देख चुके हैं ) के साथ होता है, जिसे यह पता लगाने के लिए घातीय समय की आवश्यकता होती है कि एक स्ट्रिंग जिसमें x s और कुछ नहीं है (जैसे xxxxxxxxxxxxxxxxxxxx ) इससे मेल नहीं खाता।

इससे कैसे बचा जाए?

जितना संभव हो उतना विशिष्ट बनें, जितना संभव हो उतना संभव पथ कम करें। ध्यान दें कि कुछ रेगेक्स मैचर्स बैकट्रैकिंग की चपेट में नहीं आते हैं, जैसे कि वे awk या grep में शामिल हैं क्योंकि वे थॉम्पसन एनएफए पर आधारित हैं।