जावा नियमित अभिव्यक्ति बहुत धीमी गति से चल रही है

Question

मैं जावा में Daring Fireball Regular Expression for matching URLs का उपयोग करने की कोशिश कर रहा हूं, और मुझे एक ऐसा URL मिला है जो मूल्यांकन हमेशा के लिए लेता है। मैंने जावा रेनैक्स के साथ काम करने के लिए मूल रेगेक्स को संशोधित किया है।

private final static String pattern = 
"\\b" + 
"(" +       // Capture 1: entire matched URL 
    "(?:" + 
    "[a-z][\\w-]+:" +    // URL protocol and colon 
    "(?:" + 
     "/{1,3}" +      // 1-3 slashes 
     "|" +        // or 
     "[a-z0-9%]" +      // Single letter or digit or '%' 
             // (Trying not to match e.g. "URI::Escape") 
    ")" + 
    "|" +       // 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 (updated to add a 'dash' 
    ")" + 
")"; 

// @see http://daringfireball.net/2010/07/improved_regex_for_matching_urls 
private static final Pattern DARING_FIREBALL_PATTERN = Pattern.compile(pattern, Pattern.CASE_INSENSITIVE | Pattern.UNICODE_CASE); 

यदि मैं निम्नलिखित को चलाने का प्रयास करता हूं, तो यह हमेशा के लिए लेता है। मैंने इसे संतुलित माता-पिता के मिलान में संकुचित कर दिया है (मुझे लगता है)। यदि आप माता-पिता के भीतर टेक्स्ट बदलते हैं, तो यह ठीक काम करता है, लेकिन लगभग 15 वर्णों पर, यह तेजी से धीमा हो जाता है।

final Matcher matcher = pattern.matcher("https://goo.gl/a(something_really_long_in_balanced_parens)"); 
boolean found = matcher.find(); 

क्या इस रेगेक्स को बेहतर बनाने का कोई तरीका है ताकि लाइनें हमेशा के लिए न लें? मेरे पास जुनीट टेस्ट क्लास में लगभग 100 अलग-अलग यूआरएल हैं, और मुझे उन लोगों को भी काम करने की ज़रूरत है।

Answer 1

समस्या यहाँ है:

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

तुम यहाँ क्या मिल गया है नेस्टेड परिमाणकों है। यह किसी भी बैक ट्रैकिंग एल्गोरिथ्म के साथ कहर निभाता है - एक उदाहरण के रूप में, भीतरी परिमाणक a रों के सभी से मेल खाएगी स्ट्रिंग

aaaaaaaaaab 

एक पहला प्रयास के रूप में के खिलाफ regex /^(a+)+$/ मिलान पर विचार करें। फिर रेगेक्स विफल रहता है, इसलिए यह एक से पीछे हट जाता है। फिर बाहरी क्वांटिफायर फिर से मिलान करने की कोशिश करता है, अंतिम a निगलता है, फिर रेगेक्स एक बार फिर विफल हो जाता है। हम मूल रूप से घातीय व्यवहार प्राप्त करते हैं क्योंकि क्वांटिफायर वास्तव में कोई प्रगति किए बिना a एस के रन को विभाजित करने के सभी तरीकों का प्रयास करते हैं।

समाधान अधिकार परिमाणकों (जिसे हम एक परिमाणक के अंत पर एक + टैकिंग द्वारा निरूपित) है - हम भीतरी परिमाणकों की स्थापना की तो एक बार वे एक मैच है, वे न दें कि यह जाना - वे जब तक मैच विफल नहीं हो जाता है या पहले क्वांटिफ़ायर बैक हो जाता है तब तक उस पर पकड़ लेंगे और उन्हें स्ट्रिंग में कहीं और शुरू करना होगा। यदि हमने इसके बजाय /^(a++)+$/ को हमारे रेगेक्स के रूप में उपयोग किया है, तो हम इसे मिलान करने की कोशिश करने वाले घातीय होने के बजाय, उपरोक्त गैर-मिलान वाली स्ट्रिंग पर तत्काल विफल हो जाएंगे।

उन आंतरिक क्वांटिफ़ायर को स्वामित्व बनाने का प्रयास करें और देखें कि यह मदद करता है या नहीं।