नियमित अभिव्यक्ति अनंत लूप

Question

में चला जाता है मैं पार्स करने कर रहा हूँ (प्रजाति) फार्म के नाम:

Parus Ater 
H. sapiens 
T. rex 
Tyr. rex 

जो आम तौर पर दो शब्दों (द्विपद) लेकिन कभी कभी है 3 या उससे अधिक है।

Troglodytes troglodytes troglodytes 
E. rubecula sensu stricto 

मैं

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

जो समय के सबसे अधिक काम किया लेकिन कभी-कभी एक अनंत लूप में चला गया लिखा था। ऐसा नहीं है कि यह रेगुलर एक्सप्रेशन मिलान में था नीचे ट्रैक करने के लिए कुछ समय ले लिया और फिर मुझे एहसास हुआ कि यह एक टाइपो था और मैं

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s+[a-z]+)* 

जो ठीक से प्रदर्शन करती लिखा जाना चाहिए था।

मेरे प्रश्न हैं:

• क्यों इस पाश होता है?
• क्या कोई तरीका है कि मैं प्रोग्राम चलाने से पहले समान रेगेक्स त्रुटियों की जांच कर सकता हूं? अन्यथा प्रग्राम वितरित होने से पहले उन्हें परेशान करना मुश्किल हो सकता है और समस्याएं पैदा होती हैं।

[नोट: मुझे प्रजातियों के लिए अधिक सामान्य अभिव्यक्ति की आवश्यकता नहीं है - प्रजातियों के नामों के लिए औपचारिक 100+ लाइन रेगेक्स विनिर्देशन है - यह केवल प्रारंभिक फ़िल्टर था]।

नोट: समस्या उत्पन्न हुई क्योंकि यद्यपि अधिकतर नाम 2 या कभी-कभी 3/4 शब्दों (जैसे वे इटालिक्स में थे) में निकाले गए थे, कुछ झूठे सकारात्मक थे (जैसे "Homo sapiens lives in big cities like London") और मैच "एल" में विफल रहता है। ]

नोट: डीबगिंग में मैंने पाया है कि रेगेक्स अक्सर पूरा हो रहा था लेकिन बहुत धीमा (उदाहरण के लिए छोटे लक्ष्य तारों पर)। यह मूल्यवान है कि मुझे इस बग को पैथोलॉजिकल केस के माध्यम से मिला। मैंने एक महत्वपूर्ण सबक सीखा है!

Answer 1

अपने प्रश्न के पहले भाग को संबोधित करने के लिए, आपको catastrophic backtracking पर पढ़ना चाहिए। अनिवार्य रूप से, क्या हो रहा है कि आपकी स्ट्रिंग के साथ आपकी नियमित अभिव्यक्ति से मेल खाने के कई तरीके हैं, और पार्सर लगातार काम करने और इसे काम करने के लिए ट्रैकिंग कर रहा है।

आपके मामले में, शायद यह घोंसला हुआ पुनरावृत्ति था: (\s*[a-z]+)* जो संभवतः कुछ बहुत अजीब लूप का कारण बनता है। जैसा कि क्यूटीएक्स ने स्पष्ट रूप से बताया है, बिना किसी जानकारी के बताना मुश्किल है।

दुर्भाग्यवश, आपके प्रश्न का दूसरा भाग उत्तर देना असंभव है। यह मूल रूप से Halting problem है। चूंकि नियमित अभिव्यक्ति अनिवार्य रूप से एक परिमित राज्य मशीन के हैं, जिसका इनपुट एक स्ट्रिंग है, आप एक सामान्य समाधान नहीं बना सकते हैं जो भविष्यवाणी करता है कि नियमित अभिव्यक्ति आपदाजनक रूप से पीछे हट जाएंगी, और कौन नहीं।

जहां तक ​​आपकी नियमित अभिव्यक्तियों को तेजी से चलाने के लिए कुछ सुझाव दिए जाते हैं? यह कीड़े का एक बड़ा हिस्सा है। मैं अपने दम पर नियमित अभिव्यक्ति का अध्ययन बहुत समय बिताया है, और कुछ समय के लिए उन्हें के अनुकूलन, और यहाँ है कि मैं क्या पाया है कि आम तौर पर मदद करता है:

1. अपने छोरों के बाहर अपने रेगुलर एक्सप्रेशन संकलित करें, अपनी भाषा का समर्थन करता है, तो यह।
2. जब भी संभव हो, anchors जोड़ें जब आप जानते हैं कि वे उपयोगी हैं।स्ट्रिंग की शुरुआत के लिए विशेष रूप से ^। यह भी देखें: प्लेग की तरह Word Boundaries
3. बचें नेस्ट पुनरावृत्ति। यदि आपको यह होना है (जो आप करेंगे), इंजन को संकेतों को शॉर्ट सर्किट में किसी भी अनपेक्षित बैकट्रैकिंग के लिए संकेत प्रदान करने के लिए अपना सर्वश्रेष्ठ प्रयास करें।
4. स्वाद का लाभ उठाएं चीजों में तेजी लाने के निर्माण करती है। मैं आंशिक हूं Non-Capturing groups और possessive quantifiers। वे हर स्वाद में प्रकट नहीं होते हैं, लेकिन जब वे करते हैं, तो आपको उनका उपयोग करना चाहिए। Atomic Groups
5. मुझे हमेशा यह सच होने लगता है: आपकी नियमित अभिव्यक्ति जितनी अधिक हो जाती है, उतनी अधिक परेशानी आप इसे कुशल बनाते हैं। नियमित अभिव्यक्ति एक महान और शक्तिशाली उपकरण हैं, वे एक सुपर स्मार्ट हथौड़ा की तरह हैं। Don't fall into the trap of seeing everything as a nail। कभी-कभी जिस स्ट्रिंग फ़ंक्शन को आप ढूंढ रहे हैं वह आपकी नाक के ठीक नीचे है।

आशा यह आप में मदद करता है। सौभाग्य।

Answer 2

पहले regex के लिए:

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

आपत्तिजनक बैक ट्रैकिंग के कारण (\s*[a-z]+)* के रूप में टिप्पणी में बताया होता है। हालांकि, यह केवल सच है अगर आप String.matches() के साथ स्ट्रिंग मान्य कर रहे हैं, के बाद से यह केवल इस मामले में जहां कोई अमान्य वर्ण का सामना नहीं बल्कि एक मैच (Matcher पाश) लौटने से कोशिश करते हैं और पीछे, इंजन कारण बनता है।

हमें (\s*[a-z]+)* के खिलाफ अवैध स्ट्रिंग से मेल करते हैं:

inputstringinputstring; 

(Repetition 1) 
\s*=(empty) 
[a-z]+=inputstringinputstring 
FAILED 

Backtrack [a-z]+=inputstringinputstrin 
(Repetition 2) 
\s*=(empty) 
[a-z]+=g 
FAILED 

(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstri 
(Repetition 2) 
\s*=(empty) 
[a-z]+=ng 
FAILED 

Backtrack [a-z]+=n 
(Repetition 3) 
\s*(empty) 
[a-z]+=g 
FAILED 

(End repetition 3 since all choices are exhausted) 
(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstr 

अब तक, आप समस्या नोटिस होना चाहिए। आइए T(n) को परिभाषित करें क्योंकि लंबाई की स्ट्रिंग को जांचने के लिए काम की मात्रा पैटर्न से मेल नहीं खाती है। बैकट्रैकिंग की विधि से, हम T(n) = Sum [i = 0..(n-1)] T(i) जानते हैं। उस से, हम T(n + 1) = 2T(n) प्राप्त कर सकते हैं, जिसका अर्थ है कि बैकट्रैकिंग प्रक्रिया समय जटिलता में घातीय है!

*+को बदलने, समस्या पूरी तरह से से बचा जाता है के बाद से पुनरावृत्ति का एक उदाहरण केवल एक अंतरिक्ष चरित्र और एक अंग्रेजी वर्णमाला चरित्र के बीच सीमा पर शुरू कर सकते हैं। इसके विपरीत, पहला रेगेक्स पुनरावृत्ति के उदाहरण को किसी भी 2 वर्णमाला वर्णों के बीच शुरू करने की अनुमति देता है।

यह प्रदर्शित करने के लिए, (\s+[a-z]+\s*)* आपको नरक बैकट्रैकिंग देगा जब अमान्य इनपुट स्ट्रिंग में कई शब्द होते हैं जो लगातार कई रिक्त स्थान से अलग होते हैं, क्योंकि यह पुनरावृत्ति उदाहरण के लिए कई स्थानों को अनुमति देता है। यह सूत्र b^d जहां b लगातार रिक्त स्थान की अधिकतम संख्या (शून्य से 1) और d रिक्त स्थान के दृश्यों की संख्या है इस प्रकार है। यह आपके पहले रेगेक्स की तुलना में कम गंभीर है (इसके लिए कम से कम एक अंग्रेजी वर्णमाला और प्रति पुनरावृत्ति प्रति एक स्पेस कैरेक्टर की आवश्यकता होती है, क्योंकि आपके पहले रेगेक्स में दोहराव प्रति एक अंग्रेजी वर्णमाला के विपरीत), लेकिन यह अभी भी एक समस्या है।