वाइल्डकार्ड मिलान स्ट्रिंग

Question

सबसे कारगर वाइल्डकार्ड स्ट्रिंग मिलान एल्गोरिथ्म क्या है? मैं केवल एक विचार के बारे में पूछ रहा हूं, वास्तविक कोड प्रदान करना आवश्यक नहीं है।

मैं सोच रहा हूँ कि इस तरह के एल्गोरिथ्म क्रमबद्ध प्रत्यय सरणियों, जो (लॉग (एन)) हे के प्रदर्शन उपज कर सकते हैं के साथ बनाया जा सकता है।

क्या मैं सही हूँ?

संपादित:

मैं "A*B", "*sip*" या "A?B" जहां स्टार प्रतीकों में से किसी भी संख्या का मतलब है और प्रश्न चिह्न एकल प्रतीक का मतलब है की तरह पैटर्न मतलब है।

Answer 1

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

वाइल्डकार्ड आप किस तरह के मन में क्या है? एक एक चरित्र-वाइल्डकार्ड (जैसे regex में .), या एक बहु-चरित्र-वाइल्डकार्ड (जैसे .*)? क्या सीमाएं हैं? अपेक्षित पैटर्न की लंबाई क्या है, और क्या आपके पास डेटा की जांच करने के लिए यादृच्छिक या सीरियल पहुंच है?

Answer 2

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

आप एक मैच हे में कुछ स्ट्रिंग foo (च (एन)) समय निर्धारित कर सकते हैं, तो क्वेरी foo_0*foo_1*foo_2*...*foo_m हे (एम * च (एन)) समय जहां मीटर * वाइल्डकार्ड की संख्या है ले जाएगा।

Answer 3

वाइल्डकार्ड "भाषा" के आधार पर, मैं (शायद) एक वाइल्डकार्ड-> regexp कंपाइलर लिखूंगा और वास्तविक मिलान करने के लिए (आमतौर पर प्रदत्त) regexp इंजन का उपयोग करूंगा। यह थोड़ा आलसी है, लेकिन जब तक कि वहाँ एक वास्तविक प्रदर्शन इसे उस तरह से कर रही है समस्या है, यह काफी तेजी से होगा।

Answer 4

आप एक नियमित अभिव्यक्ति में अपने वाइल्डकार्ड जिज्ञासा को बदलने और का उपयोग करें कि मैच के लिए कर सकता है; एक आरई हमेशा एक DFA (असतत परिमित automaton) के रूप में तब्दील किया जा सकता है और उन कुशल (lineair समय) और एक छोटे से लगातार कर रहे हैं।

Answer 5

एक कागज यहाँ http://swtch.com/~rsc/regexp/regexp1.html विशेष रूप से सबसे तेजी से विकल्पों पर चर्चा यह आप अनुभवहीन एल्गोरिदम कि विकृतिविज्ञानी धीमी गति से जब लंबे पैटर्न इस्तेमाल कर रहे हैं हो जाते हैं से बचने के लिए अनुमति देता है नहीं है।

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

Answer 6

O (n मीटर लॉग इन करें) सही है। मैं एक साधारण वाइल्डकार्ड मिलान एल्गोरिथ्म जो बहुपद समय में चलाता है के लिए देख रहा था देखें http://www.cs.bris.ac.uk/Publications/Papers/2000602.pdf

आशा इस मदद करता है ...

Answer 7

। जैसे यह एक सरल है, लेकिन बहुपद समय में नहीं चलता है जब पैटर्न सारे तारे (*) शामिल हैं: http://www.codeproject.com/Articles/188256/A-Simple-Wildcard-Matching-Function नीचे कोड है जो गतिशील प्रोग्रामिंग का उपयोग करता हे के समय जटिलता (एन * मी) जहां n लंबाई है कम करने के लिए है पाठ और एम पैटर्न की लंबाई है।

#include <string> 
#include <vector> 
#include <algorithm> 
using namespace std; 

const int UNKNOWN = -1; 
const int NOMATCH = 0; 
const int MATCHES = 1; 

class Wildcard { 
    string _text; 
    string _pattern; 
    vector<vector<int>> _mf; 
    int F(int n, int m) { 
     if (_mf[n][m] >= 0) return _mf[n][m]; 
     if (n == 0 && m == 0) { 
      _mf[n][m] = MATCHES; 
      return _mf[n][m]; 
     } 
     if (n > 0 && m == 0) { 
      _mf[n][m] = NOMATCH; 
      return _mf[n][m]; 
     } 
     // m > 0 
     int ans = NOMATCH; 
     if (_pattern[m - 1] == '*') { 
      ans = max(ans, F(n, m-1)); 
      if (n > 0) { 
       ans = max(ans, F(n - 1, m)); 
      } 
     } 
     if (n > 0) { 
      if (_pattern[m - 1] == '?' || _pattern[m - 1] == _text[n - 1]) { 
       ans = max(ans, F(n - 1, m - 1)); 
      } 
     } 
     _mf[n][m] = ans; 
     return _mf[n][m]; 
    } 
public: 
    bool match(string text, string pattern) { 
     _text = text; 
     _pattern = pattern; 
     _mf.clear(); 
     for (int i = 0; i <= _text.size(); i++) { 
      _mf.push_back(vector<int>()); 
      for (int j = 0; j <= _pattern.size(); j++) { 
       _mf[i].push_back(UNKNOWN); // not calculated 
      } 
     } 
     int ans = F(_text.size(), _pattern.size()); 
     return ans == MATCHES; 
    } 
}; 

Answer 8

अपने पैटर्न केवल * वाइल्ड कार्ड शामिल कर सकते हैं, तो तुच्छ कार्यान्वयन के रूप में तेजी से संभव के रूप में है। इस मामले में एहसास करने की मुख्य बात यह है कि आपको केवल एक बार प्रत्येक कार्ड (सितारों के बीच कार्ड = सेगमेंट) की आवश्यकता होती है।

#include <cstddef> 
#include <cstring> 
#include <algorithm> 
#include <string> 
#include <vector> 
#include <iostream> 

using namespace std; 

class wildcard_pattern { 
public: 
    explicit wildcard_pattern(const string& text); 

    bool match(const char* begin, const char* end) const; 

    bool match(const char* c_str) const; 

private: 
    string m_text; 

    struct card { 
     size_t m_offset, m_size; 
     card(size_t begin, size_t end); 
    }; 

    // Must contain at least one card. The first, and the last card 
    // may be empty strings. All other cards must be non-empty. If 
    // there is exactly one card, the pattern matches a string if, and 
    // only if the string is equal to the card. Otherwise, the first 
    // card must be a prefix of the string, and the last card must be 
    // a suffix. 
    vector<card> m_cards; 
}; 


wildcard_pattern::wildcard_pattern(const string& text): 
    m_text(text) 
{ 
    size_t pos = m_text.find('*'); 
    if (pos == string::npos) { 
     m_cards.push_back(card(0, m_text.size())); 
     return; 
    } 
    m_cards.push_back(card(0, pos)); 
    ++pos; 
    for (;;) { 
     size_t pos_2 = m_text.find('*', pos); 
     if (pos_2 == string::npos) 
      break; 
     if (pos_2 != pos) 
      m_cards.push_back(card(pos, pos_2)); 
     pos = pos_2 + 1; 
    } 
    m_cards.push_back(card(pos, m_text.size())); 
} 

bool wildcard_pattern::match(const char* begin, const char* end) const 
{ 
    const char* begin_2 = begin; 
    const char* end_2 = end; 

    size_t num_cards = m_cards.size(); 
    typedef string::const_iterator str_iter; 

    // Check anchored prefix card 
    { 
     const card& card = m_cards.front(); 
     if (size_t(end_2 - begin_2) < card.m_size) 
      return false; 
     str_iter card_begin = m_text.begin() + card.m_offset; 
     if (!equal(begin_2, begin_2 + card.m_size, card_begin)) 
      return false; 
     begin_2 += card.m_size; 
    } 

    if (num_cards == 1) 
     return begin_2 == end_2; 

    // Check anchored suffix card 
    { 
     const card& card = m_cards.back(); 
     if (size_t(end_2 - begin_2) < card.m_size) 
      return false; 
     str_iter card_begin = m_text.begin() + card.m_offset; 
     if (!equal(end_2 - card.m_size, end_2, card_begin)) 
      return false; 
     end_2 -= card.m_size; 
    } 

    // Check unanchored infix cards 
    for (size_t i = 1; i != num_cards-1; ++i) { 
     const card& card = m_cards[i]; 
     str_iter card_begin = m_text.begin() + card.m_offset; 
     str_iter card_end = card_begin + card.m_size; 
     begin_2 = search(begin_2, end_2, card_begin, card_end); 
     if (begin_2 == end_2) 
      return false; 
     begin_2 += card.m_size; 
    } 

    return true; 
} 

inline bool wildcard_pattern::match(const char* c_str) const 
{ 
    const char* begin = c_str; 
    const char* end = begin + strlen(c_str); 
    return match(begin, end); 
} 

inline wildcard_pattern::card::card(size_t begin, size_t end) 
{ 
    m_offset = begin; 
    m_size = end - begin; 
} 


int main(int, const char* argv[]) 
{ 
    wildcard_pattern pat(argv[1]); 
    cout << pat.match(argv[2]) << endl; 
}