मैं वर्तमान में नियमित अभिव्यक्तियों की समस्या को देख रहा हूं जो एक निश्चित इनपुट के साथ मेल खाने पर घातीय समय में चल रहा है, उदाहरण के लिए (a*)* और (a|a)* स्ट्रिंग aaaaab के विरुद्ध मिलान करते समय संभावित रूप से 'catastrophic backtracking' प्रदर्शित करता है - प्रत्येक अतिरिक्त 'ए' के लिए 'मिलान की गई स्ट्रिंग में, स्ट्रिंग युगल से मिलान करने का प्रयास करने के लिए आवश्यक समय। यह केवल तभी होता है जब इंजन विफल होने से पहले पेड़ में सभी संभावित शाखाओं को आजमाने की कोशिश करने के लिए बैकट्रैकिंग/एनएफए दृष्टिकोण का उपयोग करता है, जैसे पीसीआरई में उपयोग किया जाता है।रेगेक्स (ए?) * घातीय नहीं है?
मेरा प्रश्न, यही वजह है कि (a?)* कमजोर नहीं है? बैकट्रैकिंग की मेरी समझ के आधार पर, "aaaab" स्ट्रिंग में क्या होना चाहिए अनिवार्य रूप से (a|a)* के साथ क्या होता है। यदि हम मानक थॉम्पसन एनएफए निर्माण का उपयोग करते हुए एनएफए का निर्माण करते हैं, तो निश्चित रूप से प्रत्येक ईपीएसलॉन संक्रमण के लिए, इंजन को उन्हें लेना और बैकट्रैकिंग करना होगा जैसा कि दो के मामले में होगा? उदाहरण के लिए (कुछ कदम को छोड़ते हुए और @ बदल देता है जहां एप्सिलॉन):
"aaaa" मैचों, लेकिन मेल नहीं खा सकता 'बी', विफल (घटाता)
"aaaa @" से मेल खाता है, 'बी' के असफल (घटाता ह)
"aaa @ एक" मैच, 'बी' के असफल (घटाता)
"aaa @ एक @" से मेल खाता है, 'बी' के असफल (घटाता)
...
"@ एक @ एक @ एक @ एक @ "मैच, 'बी' में विफल रहता है (घटाता)
epsilons के सभी संभव संयोजनों की कोशिश कर रहा है और एक, निश्चित रूप से मार्गों के एक घातीय विस्फोट करने के लिए अग्रणी?
एनएफए से ईपीएसलॉन संक्रमण को हटाने का अर्थ होगा, लेकिन मेरा मानना है कि इसका (a*)* पैटर्न से सभी गैर-निर्धारणा को हटाने का प्रभाव है। हालांकि यह निश्चित रूप से कमजोर है, इसलिए मुझे पूरा यकीन नहीं है कि क्या हो रहा है!
अग्रिम में बहुत बहुत धन्यवाद!
संपादित करें: यह Qtax द्वारा बताया गया है कि epsilons अभी भी मौजूद नहीं हो सकता है जब NFA पारंपरिक बैक ट्रैकिंग के साथ चल रहा है, अन्यथा (@)* हमेशा के लिए मैच के लिए प्रयास करेंगे। तो क्या एनएफए कार्यान्वयन संभवतः (a*)* और (a|a)* घातीय होने के कारण हो सकता है, और (a?)* ऐसा नहीं हो सकता है? यह वास्तव में सवाल का क्रूक्स है।
पीसीआरई और पर्ल रेगेक्स इंजन कई तरीकों से अनुकूलित किए गए हैं। आपके सभी उदाहरण भारी तारों पर भी विनाशकारी बैकट्रैकिंग के बिना जल्दी विफल हो जाएंगे। – Qtax
मुझे इस बारे में पता है, शायद एक बेहतर उदाहरण जावा का रेगेक्स इंजन होगा, जो जल्दी से विफल नहीं होता है। पीसीआरई और पर्ल के शुरुआती संस्करणों में भी वही समस्याएं आईं, और मेरा प्रश्न उन पर लागू किया जा सकता है! हालांकि, उन इंजनों पर जो '(ए *) * '(यानी' जैसे पैटर्न के प्रति संवेदनशील होते हैं।unoptimised इंजन), '(ए?) *' ठीक प्रतीत होता है - क्यों ?! – Jarmex
अनुकूलन। मात्राबद्ध शून्य चौड़ाई अभिव्यक्ति (साइड इफेक्ट्स के बिना) बेकार है, और यदि आप वर्णन करते हैं तो इसका उपयोग किया जाता था (प्रत्येक पुनरावृत्ति के लिए 'ए' से मिलान करने का प्रयास करें) फिर रेगेक्स कभी विफल नहीं होगा, क्योंकि आप'() * ' अस्पष्टता से। – Qtax