यह मिलान करने में इतना लंबा क्यों लगता है? क्या यह एक बग है?

Question

मैं पैटर्न मिलान करने के लिए, वेब अनुप्रयोग में कुछ URL से मेल करने के /123,456,789 यानी की जरूरत है, और लिखा इस regex:

r'(\d+(,)?)+/$' 

मैंने देखा है कि यह जब पैटर्न का परीक्षण कई मिनट के बाद भी मूल्यांकन करने के लिए प्रतीत नहीं होता:

re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523') 

अपेक्षित परिणाम यह होगा कि कोई मिलान नहीं था।

यह अभिव्यक्ति, तथापि, कार्यान्वित लगभग तुरंत (ध्यान दें स्लैश):

re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523/') 

यह एक बग है?

Answer 1

कुछ catastrophic backtracking पर जा रहा है जो गैर-मिलान स्ट्रिंग कितनी देर तक निर्भर करता है, इस पर निर्भर करता है कि प्रोसेसिंग की घातीय मात्रा होगी। इसे आपके नेस्टेड दोहराव और वैकल्पिक कॉमा के साथ करना है (भले ही कुछ रेगेक्स इंजन निर्धारित कर सकें कि यह सभी बाहरी पुनरावृत्ति के प्रयास के साथ एक मैच नहीं होगा)। यह अभिव्यक्ति को अनुकूलित करके हल किया जाता है। [\d,]+/$:

---

सबसे आसान तरीका है यह पूरा करने के लिए सिर्फ 1 + अंक या अल्पविराम एक स्लेश और स्ट्रिंग के अंत के बाद देखने के लिए है। हालांकि, यह सही नहीं है क्योंकि यह ,123,,4,5/ जैसे कुछ की अनुमति देगा।

इसके लिए आप अपने शुरुआती प्रयास के थोड़ा अनुकूलित संस्करण का उपयोग कर सकते हैं: (?:\d,?)+/$। सबसे पहले, मैंने आपका दोहराया समूह non-capturing ((?:...)) बनाया जो आवश्यक नहीं है लेकिन यह "क्लीनर मैच" प्रदान करता है। अगला, और एकमात्र महत्वपूर्ण कदम, समूह के अंदर \d को दोहराना बंद कर दिया क्योंकि समूह पहले ही दोहरा रहा है। अंत में, मैंने वैकल्पिक , के आसपास अनावश्यक समूह को हटा दिया है क्योंकि ? केवल अंतिम वर्ण को प्रभावित करता है। बहुत अधिक यह एक अंक, शायद एक अल्पविराम, फिर दोहराएगा, और आखिरकार पीछे पीछे / देखेंगे।

---

यह अभी भी एक अजीब स्ट्रिंग 1,2,3,/ मिलान कर सकते हैं, तो यह की बिल्ली के लिए मैं एक negative lookbehind के साथ अपने मूल regex सुधार: (?:\d,?)+(?<!,)/$। यह जोर देकर कहता है कि पीछे / से पहले कोई अल्पविराम नहीं है।

Answer 2

सबसे पहले, मुझे कहना होगा कि यह एक BUG नहीं है। इसकी वजह से, यह सभी संभावनाओं की कोशिश करता है, इसमें समय और कंप्यूटिंग संसाधन लगते हैं। कभी-कभी यह बहुत समय तक घूम सकता है। जब यह वास्तव में खराब हो जाता है, तो इसे आपदाजनक बैकट्रैकिंग कहा जाता है।

यह python source कोड में findall समारोह का कोड है:

def findall(pattern, string, flags=0): 
    """Return a list of all non-overlapping matches in the string. 
    If one or more groups are present in the pattern, return a 
    list of groups; this will be a list of tuples if the pattern 
    has more than one group. 
    Empty matches are included in the result.""" 
    return _compile(pattern, flags).findall(string) 

जैसा कि आप देख यह सिर्फ compile() समारोह, कि वास्तव में Traditional NFA का उपयोग करने वाले अपने रेगुलर एक्सप्रेशन मिलान के लिए अजगर उपयोग तो _compile() कार्य के आधार पर उपयोग करते हैं, और पर बेस में नियमित अभिव्यक्ति में बैकट्रैकिंग के बारे में यह संक्षिप्त व्याख्या जेफरी ईएफ फ्राइडल द्वारा मास्टरिंग नियमित अभिव्यक्तियां, तीसरा संस्करण!

एक NFA इंजन का सार यह है: यह बदले में प्रत्येक उपसूचक या घटक समझता है, और जब भी यह बाद में अगर जरूरत पर लौटने के लिए, दो समान रूप से व्यवहार्य विकल्पों के बीच तय करने के लिए यह एक का चयन करता है की जरूरत है और अन्य को याद रखता है हो। ऐसी स्थिति जहां इसे कार्रवाई के पाठ्यक्रमों में निर्णय लेना है, क्वांटिफ़ायर (तय करें कि कोई अन्य मैच आज़माएं या नहीं) के साथ कुछ भी शामिल है (तय करें कि कौन से कोशिश करने के लिए देशी बदलते हैं, और बाद में छोड़ने के लिए)। जो भी सफल होता है, यदि यह सफल होता है और शेष रेगेक्स भी सफल होता है, तो मैच समाप्त हो जाता है। यदि शेष रेगेक्स में कुछ भी विफलता का कारण बनता है, तो रेगेक्स इंजन जानता है कि यह पहले विकल्प को चुनने के लिए बैकट्रैक कर सकता है, और दूसरे विकल्प को आजमाकर मैच के साथ जारी रख सकता है। इस तरह, यह अंततः रेगेक्स के सभी संभावित क्रमिक प्रयासों (या कम से कम की आवश्यकता होती है जब तक कोई मिलान नहीं मिलता)।

के अपने पैटर्न अंदर चलते हैं: तो आप इस स्ट्रिंग '12345121,223456,123123,3234,4523,523523' साथ r'(\d+(,)?)+/$' है हम इस चरणों है:

• सबसे पहले, अपने स्ट्रिंग के पहले भाग (12345121) \d+ साथ मिलान किया जाता है, तो ,(,)? से मेल खाता है।
• तो पहला कदम के आधार पर, पूरी स्ट्रिंग समूह ((\d+(,)?)+) के बाद + की वजह से मैच है
• फिर अंत में, वहाँ के लिए /$ मिलान किया जा के लिए कुछ नहीं है। इसलिए, (\d+(,)?)+ को /$ के लिए चेक के लिए अंतिम से पहले एक वर्ण में "बैकट्रैक" की आवश्यकता है। दोबारा, यह कोई उचित मिलान नहीं मिलता है, उसके बाद यह (,) बैकट्रैक पर बदल जाता है, फिर \d+ बैकट्रैक होगा, और यह बैकट्रैकिंग तब तक जारी रहेगी जब तक यह None वापस नहीं आती। तो आपकी स्ट्रिंग की लंबाई के आधार पर इसमें समय लगता है, जो इस मामले में बहुत अधिक है, और यह नेस्टेड क्वांटिफायर पूरी तरह से बनाता है!

लगभग बेंचमार्किंग के रूप में, इस मामले में, आप चरित्र ताकि आप 3^39 की जरूरत प्रयास (हम घटाता के लिए तरीकों) उलटे पांव लौटने की है।

अब बेहतर समझ के लिए, मैं इस कार्यक्रम के क्रम को मापने स्ट्रिंग की लंबाई बदलते समय:

:

'12345121,223456,123123,3234,4523,' 3^33 = 5.559060567×10¹⁵ 
~/Desktop $ time python ex.py 

real 0m3.814s 
user 0m3.818s 
sys  0m0.000s 

'12345121,223456,123123,3234,4523,5' 3^24 = 1.66771817×10¹⁶ #X2 before 
~/Desktop $ time python ex.py 

real 0m5.846s 
user 0m5.837s 
sys  0m0.015s 

'12345121,223456,123123,3234,4523,523' 3^36= 1.500946353×10¹⁷ #~10X before 
~/Desktop $ time python ex.py 

real 0m15.796s 
user 0m15.803s 
sys  0m0.008s 

तो इस समस्या को आप नीचे दिए गए तरीके में से एक का उपयोग कर सकते से बचने के लिए

• Atomic grouping
• कमी बक की संभावना (वर्तमान में अजगर में समर्थन नहीं करता है, एक RFE अजगर में जोड़ने के लिए 3 बनाया गया था) नेगेड समूहों को तोड़ने के लिए नेस्टेड समूहों को तोड़कर क्रैकिंग।

Answer 3

आपत्तिजनक बैक ट्रैकिंग से बचने के लिए मेरा सुझाव है

r'\d+(,\d+)*/$'