ग्लोब पैटर्न मिलान के लिए रिकर्सिव समाधान

Question

मैं वर्तमान में यूनिक्स-शैली ग्लोब पैटर्न मिलान के कार्यान्वयन का अध्ययन कर रहा हूं। आम तौर पर, fnmatch लाइब्रेरी इस कार्यक्षमता के लिए एक अच्छा संदर्भ कार्यान्वयन है।

the implementations में से कुछ को देखते हुए, साथ ही इसके बारे में विभिन्न ब्लॉग/ट्यूटोरियल पढ़ना, ऐसा लगता है कि यह एल्गोरिदम आमतौर पर पुनरावर्ती रूप से कार्यान्वित किया जाता है।

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

लेकिन मुझे समझ में परेशानी हो रही है कि क्यों विशेष रूप से ग्लोब पैटर्न मिलान करना अक्सर बार-बार लागू किया जाता है। मैं अगर हम एक स्ट्रिंग aabaabxbaab, और एक पैटर्न a*baab, * के बाद पात्रों aa(baab)xbaab की तरह, पहले "Baab" स्ट्रिंग से मेल खाएगी है उदाहरण के लिए, यह विचार है कि कभी कभी वापस ट्रैकिंग जरूरी होगा मिलता है, और फिर असफल मैच के लिए बाकी स्ट्रिंग। इसलिए एल्गोरिदम को बैकट्रैक की आवश्यकता होगी ताकि चरित्र मिलान काउंटर शुरू हो जाए, और हम baab की दूसरी घटना से मेल खा सकते हैं, जैसे: aabaabx(baab)।

ठीक है, लेकिन आम तौर पर रिकर्सन का उपयोग तब किया जाता है जब हमें बैकट्रैकिंग के कई घोंसला वाले स्तरों की आवश्यकता हो सकती है, और मुझे नहीं लगता कि इस मामले में यह कैसे आवश्यक होगा। ऐसा लगता है कि हमें केवल एक समय में एक स्तर का बैकट्रैक करना होगा, जब पैटर्न स्ट्रिंग पर इटरेटर और इनपुट स्ट्रिंग पर इटरेटर मिलान करने में विफल रहता है। इस बिंदु पर, पैटर्न पर इटरेटर को अंतिम "सेव पॉइंट" पर वापस जाने की आवश्यकता होगी, जो या तो स्ट्रिंग की शुरुआत होगी, या अंतिम * जो सफलतापूर्वक कुछ मेल खाती है। इसके लिए एक स्टैक की आवश्यकता नहीं है - केवल एक ही बचत बिंदु।

एकमात्र जटिलता जिसे मैं सोच सकता हूं "ओवरलैपिंग" मैच की स्थिति में है। उदाहरण के लिए यदि हमारे पास इनपुट स्ट्रिंग aabaabaab है, और पैटर्न a*baab है, तो हम मेल नहीं कर पाएंगे क्योंकि अंतिम baab में "बी" पहले मैच या दूसरे मैच का हिस्सा हो सकता है। लेकिन ऐसा लगता है कि यह इनपुट इटरेटर को बैकट्रैक करके हल किया जा सकता है यदि अंतिम पैटर्न इटरेटर बचाता बिंदु और पैटर्न का अंत इनपुट इटरेटर स्थिति और इनपुट स्ट्रिंग के अंत के बीच की दूरी से अधिक है।

तो, जहां तक ​​मैं देख रहा हूं, इसे इस ग्लोब मिलान एल्गोरिदम को कार्यान्वित करने के लिए बहुत अधिक समस्या नहीं होनी चाहिए (एक बहुत ही सरल ग्लोब मैचर मानते हुए, जो केवल * वर्ण का उपयोग करता है "मिलान शून्य । या अधिक वर्ण "इसके अलावा, मिलान रणनीति लालची होगा)

तो, मुझे लगता है मैं निश्चित रूप से इस बारे में गलत हूँ, क्योंकि हर किसी की इस रिकर्सिवली करता है -। कुछ तो मैं याद आ रही किया जाना चाहिए। यह सिर्फ इतना है कि मैं नहीं देख सकता कि मैं यहां क्या खो रहा हूं। इसलिए मैंने सी ++ में एक साधारण ग्लोब मैचर लागू किया (जो केवल * ऑपरेटर का समर्थन करता है), यह देखने के लिए कि क्या मैं यह जान सकता हूं कि मैं क्या खो रहा हूं। यह एक बेहद सरल, सरल पुनरावृत्ति समाधान है जो वाइल्डकार्ड मिलान करने के लिए केवल एक आंतरिक पाश का उपयोग करता है।यह भी सूचकांक जो * चरित्र जोड़े का एक वेक्टर में से मेल खाता रिकॉर्ड:

bool match_pattern(const std::string& pattern, const std::string& input, 
    std::vector<std::pair<std::size_t, std::size_t>>& matches) 
{ 
    const char wildcard = '*'; 

    auto pat = std::begin(pattern); 
    auto pat_end = std::end(pattern); 

    auto it = std::begin(input); 
    auto end = std::end(input); 

    while (it != end && pat != pat_end) 
    { 
     const char c = *pat; 
     if (*it == c) 
     { 
      ++it; 
      ++pat; 
     } 
     else if (c == wildcard) 
     { 
      matches.push_back(std::make_pair(std::distance(std::begin(input), it), 0)); 
      ++pat; 
      if (pat == pat_end) 
      { 
       matches.back().second = input.size(); 
       return true; 
      } 

      auto save = pat; 
      std::size_t matched_chars = 0; 

      while (it != end && pat != pat_end) 
      { 
       if (*it == *pat) 
       { 
        ++it; 
        ++pat; 
        ++matched_chars; 

        if (pat == pat_end && it != end) 
        { 
         pat = save; 
         matched_chars = 0; 

         // Check for an overlap and back up the input iterator if necessary 
         // 
         std::size_t d1 = std::distance(it, end); 
         std::size_t d2 = std::distance(pat, pat_end); 
         if (d2 > d1) it -= (d2 - d1); 
        } 
       } 
       else if (*pat == wildcard) 
       { 
        break; 
       } 
       else 
       { 
        if (pat == save) ++it; 
        pat = save; 
        matched_chars = 0; 
       } 
      } 

      matches.back().second = std::distance(std::begin(input), it) - matched_chars; 
     } 
     else break; 
    } 

    return it == end && pat == pat_end; 
} 

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

test("aabaabaab", "a*b*ab"); 
test("aabaabaab", "a*"); 
test("aabaabaab", "aa*"); 
test("aabaabaab", "aaba*"); 
test("/foo/bar/baz/xlig/fig/blig", "/foo/*/blig"); 
test("/foo/bar/baz/blig/fig/blig", "/foo/*/blig"); 
test("abcdd", "*d"); 
test("abcdd", "*d*"); 
test("aabaabqqbaab", "a*baab"); 
test("aabaabaab", "a*baab"); 

:

INPUT: aabaabaab 
PATTERN: a*b*ab 
INDICES: (1,2) (3,7) 
MATCH: a(a)b(aaba)ab 

INPUT: aabaabaab 
PATTERN: a* 
INDICES: (1,9) 
MATCH: a(abaabaab) 

INPUT: aabaabaab 
PATTERN: aa* 
INDICES: (2,9) 
MATCH: aa(baabaab) 

INPUT: aabaabaab 
PATTERN: aaba* 
INDICES: (4,9) 
MATCH: aaba(abaab) 

INPUT: /foo/bar/baz/xlig/fig/blig 
PATTERN: /foo/*/blig 
INDICES: (5,21) 
MATCH: /foo/(bar/baz/xlig/fig)/blig 

INPUT: /foo/bar/baz/blig/fig/blig 
PATTERN: /foo/*/blig 
INDICES: (5,21) 
MATCH: /foo/(bar/baz/blig/fig)/blig 

INPUT: abcdd 
PATTERN: *d 
INDICES: (0,4) 
MATCH: (abcd)d 

INPUT: abcdd 
PATTERN: *d* 
INDICES: (0,3) (4,5) 
MATCH: (abc)d(d) 

INPUT: aabaabqqbaab 
PATTERN: a*baab 
INDICES: (1,8) 
MATCH: a(abaabqq)baab 

INPUT: aabaabaab 
PATTERN: a*baab 
INDICES: (1,5) 
MATCH: a(abaa)baab 

कोष्ठकों कि "MATCH: " शो के बाद उत्पादन में प्रदर्शित

void test(const std::string& input, const std::string& pattern) 
{ 
    std::vector<std::pair<std::size_t, std::size_t>> matches; 
    bool result = match_pattern(pattern, input, matches); 
    auto match_iter = matches.begin(); 

    std::cout << "INPUT: " << input << std::endl; 
    std::cout << "PATTERN: " << pattern << std::endl; 
    std::cout << "INDICES: "; 
    for (auto& p : matches) 
    { 
     std::cout << "(" << p.first << "," << p.second << ") "; 
    } 
    std::cout << std::endl; 

    if (result) 
    { 
     std::cout << "MATCH: "; 

     for (std::size_t idx = 0; idx < input.size(); ++idx) 
     { 
      if (match_iter != matches.end()) 
      { 
       if (idx == match_iter->first) std::cout << '('; 
       else if (idx == match_iter->second) 
       { 
        std::cout << ')'; 
        ++match_iter; 
       } 
      } 

      std::cout << input[idx]; 
     } 

     if (!matches.empty() && matches.back().second == input.size()) std::cout << ")"; 

     std::cout << std::endl; 
    } 
    else 
    { 
     std::cout << "NO MATCH!" << std::endl; 
    } 

    std::cout << std::endl; 
} 

और मेरी वास्तविक परीक्षण:

यहाँ अपने परीक्षण समारोह है प्रत्येक * द्वारा मिलान/उपभोग किए गए सबस्ट्रिंग्स चरित्र। तो, ऐसा लगता है कि यह ठीक काम करता है, और मुझे लगता है कि यहां कई स्तरों को बैकट्रैक करना आवश्यक नहीं होगा - कम से कम अगर हम केवल * वर्णों को अनुमति देने के लिए हमारे पैटर्न को सीमित करते हैं, और हम लालची मिलान मानते हैं।

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

Answer 1

मैंने आपके कार्यान्वयन के सभी विवरणों की जांच नहीं की है, लेकिन यह निश्चित रूप से सच है कि आप रिकर्सिव बैकट्रैकिंग के बिना मैच कर सकते हैं।

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

क्लासिक fnmatch कार्यान्वयन गति के लिए अनुकूलित नहीं हैं; वे इस धारणा पर आधारित हैं कि पैटर्न और लक्ष्य तार कम हैं। यह धारणा आमतौर पर उचित होती है, लेकिन यदि आप अविश्वसनीय पैटर्न की अनुमति देते हैं, तो आप स्वयं को एक डीओएस हमले में खोल रहे हैं। और उस धारणा के आधार पर, आपके द्वारा प्रस्तुत किए गए एक जैसा एल्गोरिदम, जिसे प्रीकंप्यूशन की आवश्यकता नहीं होती है, शायद किसी भी एल्गोरिदम की तुलना में उपयोग के अधिकांश मामलों में तेजी से तेज़ है, जिसके लिए पैथोलॉजिकल पैटर्न के साथ घातीय ब्लाउप से परहेज करते हुए प्रीकंप्यूटिंग राज्य संक्रमण तालिका की आवश्यकता होती है।