रेगुलर एक्सप्रेशंस में कैटैस्ट्रॉफिक बैकट्रैकिंग

क्या एक सरल और उचित रूप से निर्दोष नियमित दिनचर्या के साथ एक प्रणाली को मारना संभव है? हाँ आप कर सकते हैं।

उदाहरण के लिए:

>>> r = '(a+)*b' 

बस हां। निर्दोष - हाँ की तरह। बेशक यह नासमझ है, क्योंकि कोष्ठक और तारांकन बहुत ही शानदार हैं, लेकिन यह काम करना चाहिए। आइए कोशिश करते हैं:

 >>> re.findall('(a+)*b', 'aaaaaab') ['aaaaaa'] 

कूल, वर्किंग, आइए चलते हैं बीयर पीने।

लेकिन नहीं ...

यदि हम जिस लाइन की तलाश कर रहे हैं, उसमें वांछित पैटर्न नहीं है, उदाहरण के लिए, बस 'आआआ' , कंपाइलर इसे निम्नलिखित एल्गोरिदम के साथ खोजने की कोशिश करेगा:

1. सभी अपवाह 'ए +' को संतुष्ट करते हैं, लेकिन हम एक कदम पीछे 'बी' नहीं पाते हैं।
2. अब A + ' केवल ' आआआ ' (पिछले एक को छोड़कर सब कुछ) को संतुष्ट करता है, बाद वाला दोहराव ' * 'को संतुष्ट करता है, ' b ' अभी भी नहीं पाया जा सकता है, एक कदम पीछे।
3. पहला 'a +' केवल 'aaaa ' को संतुष्ट करता है, अंतिम दो 'aa' को दोहराने '*' को संतुष्ट करता है, 'b' हमें अभी भी नहीं मिल रहा है, एक कदम पीछे।
4. पहला 'a +' संतुष्ट करता है 'आआआ' , तपस्या 'a' एक बार फिर से संतुष्ट '*' , अगला 'a' से दूसरे रिपीट '*' , 'b' का अस्तित्व नहीं है ...

ठीक है, आप समझते हैं - और इसी तरह। एक पंक्ति की पूरी खोज तक।

कुछ आँकड़े:

 >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*20)", number=1) 0.24741506576538086 >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*22)", number=1) 0.99283289909362793 >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*24)", number=1) 3.9849259853363037 

जैसा कि आप देख सकते हैं, निष्पादन समय तेजी से बढ़ रहा है। बड़े स्ट्रिंग्स के लिए, फ्रीबीएसडी पर पायथन 2.6 एक समयबद्ध तरीके से एक रनटाइमएयर को फेंकता है, लेकिन विंडोज पर वही पायथन सभी संयोजनों के माध्यम से ख़ुशी से खोजता है। 30 से अधिक वर्णों की रेखाओं ने परीक्षण करने की हिम्मत नहीं की :)

पोस्ट आज के स्टैकओवरफ़्लो प्रश्न और लंबे समय से पढ़े गए और सफलतापूर्वक भूल गए रेगुलर एक्सप्रेशंस: कैटास्ट्रॉफ़िक बैकट्रैकिंग से प्रेरित था।

पुनश्च यह पता चलता है कि हबेरा में पहले से ही बैकट्रैकिंग और परमाणु समूहों के बारे में एक लेख है, वर्णित समस्या को वहां अधिक गहरा और अधिक गंभीर रूप से माना जाता है - परमाणु समूहन, या वापस कदम नहीं! :)