मैं इस नियमित अभिव्यक्ति को "विनाशकारी बैकट्रैकिंग" के परिणामस्वरूप कैसे बना सकता हूं?

Question

मैं एक यूआरएल नियमित अभिव्यक्ति मिलान कि मैं another question को http://daringfireball.net/2010/07/improved_regex_for_matching_urls

(?xi) 
\b 
(      # Capture 1: entire matched URL 
    (?: 
    https?://    # http or https protocol 
    |      # or 
    www\d{0,3}[.]   # "www.", "www1.", "www2." … "www999." 
    |       # or 
    [a-z0-9.\-]+[.][a-z]{2,4}/ # looks like domain name followed by a slash 
) 
    (?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 
    (?:      # End with: 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
    |        # or 
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]  # not a space or one of these punct chars 
) 
) 

से मिला जवाब के आधार पर उपयोग करने के लिए कोशिश कर रहा हूँ, ऐसा लगता है ऐसे मामले हैं कि backtrack catastrophically को यह regex का कारण रहे हैं। उदाहरण के लिए:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA)") 

... एक बहुत लंबे समय निष्पादित करने के लिए (उदाहरण के लिए क्रोम में) ले जा सकते हैं

मुझे ऐसा लगता है कि इस समस्या कोड के इस हिस्से में निहित है:

(?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 

... जो मोटे तौर पर (.+|\((.+|(\(.+\)))*\))+ के बराबर होने का है, जो लगता है कि यह (.+)+

शामिल इसमें कोई परिवर्तन मैं कर सकते हैं कि उस से बचने जाएगा है लगता है?

Answer 1

निम्नलिखित करने के लिए इसे बदलने आपत्तिजनक बैक ट्रैकिंग रोकने चाहिए:

(?xi) 
\b 
(      # Capture 1: entire matched URL 
    (?: 
    https?://    # http or https protocol 
    |      # or 
    www\d{0,3}[.]   # "www.", "www1.", "www2." … "www999." 
    |       # or 
    [a-z0-9.\-]+[.][a-z]{2,4}/ # looks like domain name followed by a slash 
) 
    (?:      # One or more: 
    [^\s()<>]+     # Run of non-space, non-()<> 
    |       # or 
    \(([^\s()<>]|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
)+ 
    (?:      # End with: 
    \(([^\s()<>]|(\([^\s()<>]+\)))*\) # balanced parens, up to 2 levels 
    |        # or 
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]  # not a space or one of these punct chars 
) 
) 

केवल परिवर्तन यह है कि पहले बनाया गया था [^\s()<>] "संतुलित कोष्ठक" regex के कुछ भागों में से प्रत्येक में के बाद + दूर करने के लिए किया गया था।

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA") 

मूल regex की समस्या भाग संतुलित कोष्ठकों खंड है, क्यों बैक ट्रैकिंग होता है मैं पूरी तरह से करने जा रहा हूँ की व्याख्या सरल करने के लिए:

यहाँ जे एस के साथ परीक्षण के लिए एक लाइन संस्करण है इसके बारे में नेस्टेड कोष्ठकों हिस्से को हटाने, क्योंकि यह यहाँ प्रासंगिक नहीं है:

\(([^\s()<>]+|(\([^\s()<>]+\)))*\) # original 
\(([^\s()<>]+)*\)      # expanded below 

\(    # literal '(' 
(    # start group, repeat zero or more times 
    [^\s()<>]+  # one or more non-special characters 
)*    # end group 
\)    # literal ')' 

विचार करें कि स्ट्रिंग '(AAAAA' के साथ यहाँ होता है, शाब्दिक ( से मेल खाते हैं और फिरसमूह द्वाराउपभोग किया जाएगा, और ) मिलान करने में विफल रहेगा। इस बिंदु पर समूह A छोड़ देगा, AAAA को छोड़कर इस बिंदु पर मैच जारी रखने का प्रयास कर रहा है। चूंकि समूह के पास * है, तो समूह कई बार मिलान कर सकता है, इसलिए अब ([^\s()<>]+)*AAAA से मेल खाता है, और फिर दूसरे पास पर A होगा। जब यह विफल रहता है तो A मूल कैप्चर द्वारा छोड़ा जाएगा और दूसरे कैप्चर द्वारा उपभोग किया जाएगा।

इस के लिए पर जाना होगा एक लंबे निम्नलिखित प्रयास मिलान करने के लिए है, जहां प्रत्येक अल्पविराम से अलग समूह में एक अलग समय है कि समूह मिलान किया जाता है इंगित करता है, और कितने अक्षर हैं जो उदाहरण का मिलान नहीं हुआ, जिसके परिणामस्वरूप, जबकि:

AAAAA 
AAAA, A 
AAA, AA 
AAA, A, A 
AA, AAA 
AA, AA, A 
AA, A, AA 
AA, A, A, A 
.... 

मैंने गलत गिनती की हो सकती है, लेकिन मुझे यकीन है कि यह निर्धारित होने से पहले 16 चरणों तक जोड़ता है कि रेगेक्स मेल नहीं खा सकता है। जैसे ही आप स्ट्रिंग में अतिरिक्त वर्ण जोड़ना जारी रखते हैं, इसे समझने के लिए चरणों की संख्या तेजी से बढ़ती है।

+ को हटाकर और इसे \(([^\s()<>])*\) पर बदलकर, आप इस बैकट्रैकिंग परिदृश्य से बचेंगे।

नेस्टेड कोष्ठक की जांच करने के लिए विकल्प को वापस जोड़ने से कोई समस्या नहीं आती है।

ध्यान दें कि आप क्योंकि वर्तमान में "http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA" बस से पहले ( से मेल खाएगा, स्ट्रिंग के अंत करने के लिए लंगर किसी प्रकार का जोड़ सकते हैं, तो re.test(...)true क्योंकि http://google.com/?q= मैचों लौट आते हैं।