नियमित अभिव्यक्ति लटकती प्रोग्राम (100% सीपीयू उपयोग)

Question

जावा नियमित रूप से अभिव्यक्ति के लिए इनपुट के रूप में नीचे स्ट्रिंग का उपयोग करते समय 100% CPU उपयोग के साथ लटक रहा है।

रेगुलर एक्सप्रेशन से उपयोग किया:

यहाँ नियमित रूप से अपने आवेदन में वर्णन क्षेत्र के लिए इस्तेमाल किया अभिव्यक्ति है।

^([A-Za-z0-9\\-\\_\\.\\&\\,]+[\\s]*)+ 

स्ट्रिंग के परीक्षण के लिए इस्तेमाल किया:

सास सेवा VLAN Provider_One
डिडिएर SPT के साथ 2 प्रयास से क्योंकि पहले एक वह दिया मुझे

:-(गलत था जब मैं अलग-अलग संयोजनों में एक ही स्ट्रिंग को विभाजित करता हूं तो यह ठीक से काम करता है। "प्रोवाइडर_ऑन से सास सेवा वीएलएएन" की तरह, "पहले उसने मुझे गलत बताया :-(", आदि जावा हैगी केवल उपर्युक्त स्ट्रिंग के लिए ng।

मैंने रेगेक्स को नीचे के रूप में अनुकूलित करने का भी प्रयास किया।

^([\\w\\-\\.\\&\\,]+[\\s]*)+ 

यहां तक ​​कि यह काम नहीं कर रहा है।

Answer 1

सबसे पहले, आपको यह समझने की आवश्यकता है कि आपके regexes आपूर्ति इनपुट स्ट्रिंग से मेल नहीं खा सकते हैं। तारों में एक संख्या वर्ण ('<' '>' '/' ':' और ')') शामिल हैं जो "शब्द" वर्ण नहीं हैं।

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

असल में "विनाशकारी बैकट्रैकिंग"। अधिक विशेष रूप से, आपके रेगेक्स की दोहराने वाली संरचनाओं को घातीय रीजिक्स बैकट्रैकिंग एल्गोरिदम के लिए विकल्पों की संख्या देने का प्रयास करें!

गया है कि आपकी regex का कहना है:

1. एक या अधिक शब्द पात्रों
2. शून्य या अधिक रिक्ति
3. दोहराएँ पिछले 2 पैटर्न के रूप में आप की तरह के रूप में कई बार इसके बाद।

समस्या "शून्य या अधिक स्थान वर्ण" भाग के साथ है। पहली बार, मैचर पहले अप्रत्याशित चरित्र (यानी '<') तक सबकुछ मैच करेगा। फिर यह थोड़ा सा वापस आ जाएगा और एक अलग विकल्प के साथ फिर से प्रयास करें ... जिसमें अंतिम अक्षर से पहले "शून्य रिक्त स्थान" शामिल है, फिर जब यह विफल हो जाता है, तो यह "शून्य रिक्त स्थान" को एक स्थिति में वापस ले जायेगा।

समस्या यह है कि N गैर अंतरिक्ष वर्ण, वहाँ के रूप में N विभिन्न स्थानों के साथ स्ट्रिंग के लिए कि "शून्य रिक्त स्थान" मिलान किया जा सकता है, और उस 2^N विभिन्न संयोजनों में आता है। यह तेजी से N के रूप में एक बड़ी संख्या में बदल जाता है, और अंत परिणाम एक अनंत लूप से अलग करना मुश्किल है।

Answer 2

catastrophic backtracking का एक और क्लासिक केस।

आप नेस्ट परिमाणकों कि क्रमपरिवर्तन की एक विशाल संख्या के कारण जांच की जानी है जब regex अपने इनपुट स्ट्रिंग जो अपने चरित्र वर्ग का हिस्सा (आप .matches() विधि का उपयोग कर रहे कल्पना करते हुए) नहीं है में : पर आता है।

^([^:]+)+$ 

और इस स्ट्रिंग:

के इस regex के लिए समस्या को आसान बनाने चलो

1234: 

regex इंजन

1234 # no repetition of the capturing group 
123 4 # first repetition of the group: 123; second repetition: 4 
12 34 # etc. 
12 3 4 
1 234 
1 23 4 
1 2 34 
1 2 3 4 

जाँच करने की जरूरत है ... और है कि बस के लिए है चार अक्षर आपके नमूना स्ट्रिंग पर, RegexBuddy 1 मिलियन प्रयासों के बाद बंद हो जाता है। जावा खुशी से चिपकने लगेगा ... आखिर में यह स्वीकार करने से पहले कि इनमें से कोई भी संयोजन मिलान करने के लिए निम्नलिखित : को अनुमति देता है।

आप इसे कैसे हल कर सकते हैं?

आप possessive quantifiers का उपयोग करके उलटे पांव लौटने से regex न करे कर सकते हैं:

^([A-Za-z0-9_.&,-]++\\s*+)+ 

regex तेजी से असफल करने की अनुमति देगा। संयोग से, मैंने उन सभी अनावश्यक बैकस्लाश को हटा दिया।

संपादित करें:

कुछ माप:

स्ट्रिंग "was wrong :-)" पर, यह RegexBuddy एक गैर मैच यह पता लगाने की 862 कदम उठाता है।
"me was wrong :-)" के लिए, यह 1,742 कदम है।
"gave me was wrong :-)", 14,014 चरणों के लिए।
"he gave me was wrong :-)", 28,046 चरणों के लिए।
"one he gave me was wrong :-)", 112,222 चरणों के लिए।
"first one he gave me was wrong :-)",> 1,000,000 चरणों के लिए।

Answer 3

आप अन्य पात्रों से अलग-अलग व्हाइटस्पेस क्यों मेल खाते हैं? और आप शुरुआत में मैच क्यों लंगर रहे हैं, लेकिन अंत में नहीं? क्या आप वाकई स्ट्रिंग शुरू करने या खाली स्थान के साथ अंत नहीं है बनाना चाहते हैं, तो आप इस तरह कुछ करना चाहिए:

^[A-Za-z0-9_.&,-]+(?:\s+[A-Za-z0-9_.&,-]+)*$ 

अब केवल एक "पथ" regex इंजन स्ट्रिंग के माध्यम से ले जा सकते हैं। यदि यह अंत तक पहुंचने से पहले [A-Za-z0-9_.&,-] से मेल खाने वाले वर्णों से बाहर हो जाता है, और अगला वर्ण \s से मेल नहीं खाता है, तो यह तुरंत विफल हो जाता है। यदि यह अभी भी व्हाइटस्पेस वर्णों से मेल खाने के अंत तक पहुंचता है, तो यह विफल हो जाता है क्योंकि व्हाइटस्पेस के प्रत्येक भाग के बाद इसे कम से कम एक गैर-व्हाइटस्पेस चरित्र से मिलान करना आवश्यक है।

आप वहाँ ठीक एक खाली स्थान के चरित्र में गैर-सफ़ेद के रन अलग यह सुनिश्चित करना चाहते हैं, तो बस \s+ से परिमाणक निकालें:

^[A-Za-z0-9_.&,-]+(?:\s[A-Za-z0-9_.&,-]+)*$ 

आप परवाह नहीं है कि कहां से व्हाइटस्पेस के संबंध में है गैर-सफ़ेद, बस उन्हें सभी एक ही चरित्र वर्ग के साथ मेल खाते हैं:

^[A-Za-z0-9_.&,\s-]+$ 

मैं यह सोचते करती हूं कि आप जानते हैं कि आपके regex : और SMI में ( की वजह से दिए गए इनपुट से मेल नहीं खाएगी लुई, और आप सिर्फ यह जानना चाहते हैं कि विफल होने में इतना समय क्यों लगता है।

और निश्चित रूप से, आप एक जावा स्ट्रिंग शाब्दिक के रूप में रेगुलर एक्सप्रेशन से बना रहे हैं के बाद से, आपके द्वारा लिखी होगा:

"^[A-Za-z0-9_.&,-]+(?:\\s+[A-Za-z0-9_.&,-]+)*$" 

या

"^[A-Za-z0-9_.&,-]+(?:\\s[A-Za-z0-9_.&,-]+)*$" 

या

"^[A-Za-z0-9_.&,\\s-]+$" 

(मुझे पता है कि मूल प्रश्न में आपको डबल बैकस्लैश था, लेकिन शायद उन्हें उचित रूप से प्रदर्शित करने के लिए ly, क्योंकि आप SO के उत्कृष्ट कोड स्वरूपण सुविधा का उपयोग नहीं कर रहे थे।)