इनपुट लंबाई

Question

के आधार पर एक regexp के साथ 100% CPU उपयोग, मैं पाइथन में एक regexp के साथ आने की कोशिश कर रहा हूं जिसे किसी भी चरित्र से मेल खाना पड़ेगा लेकिन तीन या अधिक लगातार कॉमा या सेमीकॉलन से परहेज करना होगा। दूसरे शब्दों में, केवल दो लगातार कॉमा या सेमीकॉलन की अनुमति है।

^(,|;){,2}([^,;]+(,|;){,2})*$ 

और यह अपेक्षा के अनुरूप काम करने लगता है:

>>> r.match('') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, a') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, ,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, ,,a') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, ,,,') 
>>> r.match('foo, ,,,;') 
>>> r.match('foo, ,, ;;') 
<_sre.SRE_Match object at 0x7f23af840750> 

लेकिन जैसा कि मैंने इनपुट पाठ की लंबाई बढ़ाने के लिए शुरू करते हैं, regexp लगता

तो यह मैं वर्तमान में क्या है प्रतिक्रिया देने के लिए और अधिक समय की आवश्यकता है।

>>> r.match('foo, bar, baz,, foo') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,') 
<_sre.SRE_Match object at 0x7f23af8407e8> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,') 
<_sre.SRE_Match object at 0x7f23af840750> 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,') 
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,,') 
>>> r.match('foo, bar, baz,, fooooo, baaaaar, baaaaaaz,,,,') 

और आखिरकार यह इस चरण में पूरी तरह से अटक गया और सीपीयू उपयोग 100% तक चला गया।

मुझे यकीन नहीं है कि regexp को अनुकूलित किया जा सकता है या इसमें कुछ और शामिल है, किसी भी मदद की सराहना की।

Answer 1

आप catastrophic backtracking में चल रहे हैं।

इस का कारण यह है कि आप विभाजक वैकल्पिक बना दिया है, और इसलिए [^,;]+ हिस्सा (जो अपने आप एक दोहराई समूह में है) अपने रेगुलर एक्सप्रेशन के अंत में जब असफलता स्वीकार करने के लिए होने से पहले (baaaaaaaz का) क्रमपरिवर्तन का भार की कोशिश करेंगे है दो से अधिक अल्पविरामों के साथ सामना करना पड़ा।

RegexBuddy आपके अंतिम परीक्षण स्ट्रिंग के साथ रेगेक्स इंजन के 1.000.000 चरणों के बाद मैच प्रयास को रोकता है। पाइथन कोशिश कर रहे हैं।

स्ट्रिंग baaz,,, कल्पना कीजिए:

अपने रेगुलर एक्सप्रेशन से कोशिश कर रहा है, regex इंजन की जाँच करने के है सब इन:

1. baaz,,<failure>
2. baa + z,,<failure>
3. ba + az,,<failure>
4. ba + a + z,,<failure>
5. b + aaz,,<failure>
6. b + aa + z,,<failure>
7. b + a + az,,<failure>
8. b + a + a + z,,<failure>

समग्र विफलता की घोषणा से पहले। देखें कि यह प्रत्येक अतिरिक्त चरित्र के साथ तेजी से कैसे बढ़ता है?

व्यवहार इस तरह अधिकार परिमाणकों या परमाणु समूहों, जो दोनों के दुर्भाग्य से अजगर की वर्तमान regex इंजन द्वारा समर्थित नहीं हैं से बचा जा सकता। लेकिन आप आसानी से एक व्यस्त जांच कर सकते हैं:

if ",,," in mystring or ";;;" in mystring: 
    fail() 

बिल्कुल रेगेक्स की आवश्यकता के बिना। यदि ,;, और पसंद भी हो सकती है और इसे बाहर रखा जाना चाहिए, तो एंड्रयू के समाधान का उपयोग करें।

Answer 2

इस नियमित अभिव्यक्ति का प्रयास करें: यह बार-बार मेल खाता

^([^,;]|,($|[^,]|,[^,])|;($|[^;]|;[^;]))*$ 

:

• एक ही चरित्र है कि न तो , है और न ही ;, या
• एक , कि या तो नहीं एक और , द्वारा पीछा किया या ,, जिसके बाद कोई अन्य ,, या
नहीं है
• एक ; कि या तो नहीं एक और ; या एक ;; द्वारा पीछा किया है कि एक और ;

द्वारा पीछा नहीं कर रहा है जब तक अंत तक पहुँच जाता है। यह बहुत ही कुशल है क्योंकि यह बहुत पीछे हटने के बिना जल्दी विफल रहता है।

Answer 3

मुझे लगता है कि निम्नलिखित आप क्या चाहते हैं करना चाहिए:

^(?!.*[,;]{3}) 

यह अगर स्ट्रिंग तीन या अधिक , या एक पंक्ति में ; शामिल असफल हो जायेगी। यदि आप वास्तव में एक चरित्र से मेल खाना चाहते हैं तो अंत में . जोड़ें।

यह negative lookahead का उपयोग करता है, जो पूरे मैच को विफल कर देगा यदि regex .*[,;]{3} मिलान करेगा।

Answer 4

कैसे आप ".+,,," अजगर में सिर्फ उन है कि मेल नहीं खाते रखने नहीं करना चाहती इस विचार वाले पैटर्न से मेल खाने वाले के बारे में। तेजी