रेगेक्स आश्चर्यजनक रूप से लंबे समय ले रहा है

Question

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

हालांकि मैंने अपने लिए तारों को विभाजित करने के लिए एक सभ्य रेगेक्स को हथियार दिया था, लेकिन यह निष्पादित करने के लिए एक आश्चर्यजनक रूप से लंबा समय ले रहा है (> मेरी मशीन पर 2 सेकंड)। मैंने यह पता लगाने के लिए इसे तोड़ दिया कि हिचकी कहाँ थी, और यह भी दिलचस्प बात यह है कि पिछले Match मिलान के बाद ऐसा लगता है (संभवतः, इनपुट के अंत में)। कम समय में स्ट्रिंग मैच के अंत तक सभी मैचों में मैं कैप्चर कर सकता हूं, लेकिन वह आखिरी मैच (यदि यह है तो यह है - कुछ भी रिटर्न नहीं) लगभग 2 सेकंड लेता है।

मुझे आशा थी कि किसी को इस बारे में कुछ अंतर्दृष्टि हो सकती है कि मैं इस रेगेक्स को थोड़ा सा कैसे बढ़ा सकता हूं। मुझे पता है कि मैं एक असंबद्ध क्वांटिफायर के साथ एक नज़र डालने का उपयोग कर रहा हूं, लेकिन जैसा कि मैंने कहा, ऐसा लगता है कि आखिरी मैच के मिलान होने तक यह किसी भी प्रदर्शन के मुद्दों का कारण नहीं है।

कोड

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Text.RegularExpressions; 

namespace RegexSandboxCSharp { 
    class Program { 
     static void Main(string[] args) { 

      string l_input1 = "# one \"two three\" four five:\"six seven\" eight \"nine ten\""; 

      string l_pattern = 
       @"(?<=^([^""]*([""][^""]*[""])?)*)\s+"; 

      Regex l_regex = new Regex(l_pattern); 

      MatchCollection l_matches = l_regex.Matches(l_input1); 
      System.Collections.IEnumerator l_matchEnumerator = l_matches.GetEnumerator(); 

      DateTime l_listStart = DateTime.Now; 
      List<string> l_elements = new List<string>(); 
      int l_previousIndex = 0; 
      int l_previousLength = 0; 
      //  The final MoveNext(), which returns false, takes 2 seconds. 
      while (l_matchEnumerator.MoveNext()) { 
       Match l_match = (Match) l_matchEnumerator.Current; 
       int l_start = l_previousIndex + l_previousLength; 
       int l_length = l_match.Index - l_start; 
       l_elements.Add(l_input1.Substring(l_start, l_length)); 

       l_previousIndex = l_match.Index; 
       l_previousLength = l_match.Length; 
      } 
      Console.WriteLine("List Composition Time: " + (DateTime.Now - l_listStart).TotalMilliseconds.ToString()); 

      string[] l_terms = l_elements.ToArray(); 

      Console.WriteLine(String.Join("\n", l_terms)); 

      Console.ReadKey(true); 

     } 
    } 
} 

आउटपुट
(यह मैं वास्तव में क्या हो रहा है है।)

एक
"दो से तीन "
चार
पाँच:" छह से सात "
आठ
" नौ दस "

Answer 1

निम्नलिखित करने के लिए अपने regex बदलने का प्रयास करें:

(?<=^((?>[^"]*)(["][^"]*["])?)*)\s+ 

यहाँ केवल परिवर्तन करने के लिए है [^"]* को atomic group पर डालें, जो catastrophic backtracking से उत्पन्न होता है जो होता है।

नोट: regex ऊपर जाहिर है सी # regex स्ट्रिंग वाक्य रचना है, जो मैं के साथ अपरिचित हूँ उपयोग नहीं करता है, लेकिन मुझे लगता है कि निम्नलिखित होगा:

@"(?<=^((?>[^""]*)([""][^""]*[""])?)*)\s+"; 

क्यों आपत्तिजनक बैक ट्रैकिंग होती है:
एक बार सभी वैध मैचों को मिलने के बाद अगला मैच मिल गया है जो अंतिम उद्धृत खंड के अंदर की जगह है। देखो दिमाग विफल हो जाएगा क्योंकि अंतरिक्ष से पहले उद्धरणों की एक विषम संख्या है।

इस बिंदु पर दिखने के अंदर रेगेक्स बैकट्रैक शुरू हो जाएगा। एंकर का मतलब है कि यह हमेशा स्ट्रिंग की शुरुआत में शुरू होगा, लेकिन यह अभी भी मिलान किए गए कार्यों के अंत से तत्वों को छोड़कर बैकट्रैक कर सकता है।lookbehind के अंदर regex को देखने की सुविधा देता है:

^([^"]*(["][^"]*["])?)* 

के बाद से उद्धृत वर्गों वैकल्पिक हैं, वे के रूप में regex backtracks छोड़ा जा सकता है। गैर-उद्धरण वर्णों के प्रत्येक खंड के लिए जो उद्धृत खंड के अंदर नहीं हैं, प्रत्येक चरित्र को बैकट्रैक करने से पहले रीगेक्स की शुरुआत में [^"]* के हिस्से के रूप में मेल किया गया होगा। चूंकि उस खंड पर बैकट्रैकिंग शुरू होती है, इसलिए अंतिम चरित्र मिलान से हटा दिया जाएगा, और बाहरी पुनरावृत्ति द्वारा उठाया जाएगा। इस बिंदु पर यह उपरोक्त आपदाजनक बैकट्रैकिंग लिंक में उदाहरण के समान ही हो जाता है।