जांचें कि एक रेगेक्स किसी अन्य रेगेक्स

Question

को कवर करता है, तो मैं एक टेक्स्ट क्लस्टरिंग एल्गोरिदम लागू करने का प्रयास कर रहा हूं। एल्गोरिदम क्लस्टर को रेगेक्स के साथ बदलकर कच्चे पाठ की समान रेखाएं, और इनपुट पाठ से दोहराव वाले पैटर्न दिखाने के बजाय इनपुट टेक्स्ट का एक साफ सारांश प्रदान करने के लिए प्रत्येक रेगेक्स से मेल खाने वाले पैटर्न की संख्या को जोड़ती है। इस प्रयास में मैंने यह पता लगाने की आवश्यकता में भाग लिया कि क्या एक रेगेक्स दूसरे को कवर करता है।

मान लें हम चिंतित केवल '*' और '+' वाइल्ड कार्ड अर्थात '*' एक वर्णमाला के शून्य या अधिक आवृत्तियां अर्थ, और '+' एक वर्णमाला के 1 या अधिक आवृत्तियां अर्थ के साथ नियमित अभिव्यक्ति के बारे में कर रहे हैं। चरित्र सेट को ASCII भी मानें।

उदाहरण के लिए:

1. AB covers AB 
     This is straightforward. 
2. ABC* covers ABC 
     Because ABC* can generate: ABC, ABCC, ABCCC etc. 
3. A*B+C* covers AB+C* 
     Because A*B+C* can generate ABBC, AABBC, AABBCC etc. which covers 
     all strings generated by AB+C*. 
4. A+M+BC* covers AMM+B+C+M+BC* 
     Similar to case [3] above. 

असल में मैं (एक regex हो सकती है) के बाद विधि है जो अगर Stra बताता है की एक कुशल कार्यान्वयन STRB के लिए शामिल किया गया है के लिए देख रहा हूँ (एक regex हो सकती है)। ध्यान दें कि इनपुट स्ट्रिंग्स stra और strb में regex वर्ण '*' और '+' से बचने का एक तरीका भी होना चाहिए। C++

विधि हस्ताक्षर:

bool isParentRegex(const string& strA, const string& strB) 

मेरे सोच है कि एक पुनरावर्ती दृष्टिकोण कार्यान्वयन के लिए आवश्यक है और यह थोड़ा जटिल हो सकता है। लेकिन मुझे यह जानकर उत्सुकता है कि क्या मैं पहिया को फिर से आविष्कार करने के बजाय मौजूदा कार्यान्वयन का पुन: उपयोग कर सकता हूं या यदि ऐसा करने के लिए कोई अन्य सरल तरीका है।

Answer 1

this perl module source जाँच लेकिन यह सब regexps के लिए काम नहीं होता है (के रूप में यह halting problem को सुलझाने में परिणाम होगा न भूलें।

Answer 2

मैं किसी दिए गए नियमित अभिव्यक्ति से कम से कम DFA को खोजने के लिए एक समारोह को लागू करने की तरह कुछ करना होगा। चलो मान लें

DFA GetMinimalDFA (regex आर 1) कि करता है।

bool isParentRegex(Regex r1, Regex r2) { 
    DFA a = GetMinimalDFA(r1); 
    DFA b = GetMinimalDFA(Regex.OR(r1,r2)) 
    return a.Equals(b); 
} 

Answer 3

सरल regex व्याकरण आप प्रस्ताव को देखते हुए, समाधान काफी तुच्छ है।

अपने और अधिक जटिल उदाहरण लें, A+M+BC* covers AMM+B+C+M+BC* आप इसे फिर से लिखने के रूप में कर सकते हैं A{1,}M{1,}B{1,1}C{0,}A{1,1}M{2,}B{1,}C{1,}M{1,}B{1,1}C{0,}

को शामिल किया गया यह सरल नियम करने के लिए हमें ले जाता है: R1R2 को शामिल किया गया है, तो सभी प्रतीकों एक ही क्रम में दिखाई देते हैं, R1 के सभी निचले सीमा रहे हैं R2 के उनसे कम या बराबर, और R1 की ऊपरी सीमाएं R2 की तुलना में अधिक या बराबर हैं।

अब सरल नियम के साथ एक मामूली समस्या है। AB*CAC को कवर करता है, यानी एक संभावना है कि एक वैकल्पिक प्रतीक R1 में दिखाई देता है और R2 में नहीं। R2 में {0,0} डालने से आप इसे हल कर सकते हैं जब R1 में एक (वैकल्पिक) प्रतीक होता है जो R2 में समतुल्य स्थिति में प्रकट नहीं होता है। जैसे AB*CAB{0,0}C को कवर करता है।

"वैकल्पिक प्रतीक" नियम एक अनुकूलन है। यदि R1 में प्रतीक वैकल्पिक नहीं है, तो R1 निश्चित रूप से R2 को कवर नहीं करता है। जैसे AB+CAC को कवर नहीं करता है।इसलिए B{0,0} डालने की कोई आवश्यकता नहीं है। लेकिन अगर आप ऐसा करेंगे, तो आप देखेंगे कि A{1,1}B{1,}C{1,1}R1 कम B पर बाध्य (1) अधिक है, क्योंकि A{1,1}B{0,0}C{1,1} कवर नहीं करता है कि R2 कम B (0)

Answer 4

पर्ल में, यह बहुत आसान होगा पर बाध्य । चरण एक A+, AA* को A*AAA* को बदलकर प्रत्येक regex को सामान्य बनाने में है, और A*A*A* रहे हैं:

sub normalize_regex($) 
{ 
    local $_ = shift; 
    s/(.)\+/$1$1*/g; 
    1 while s/(.)\*\1(?!\*)/$1$1*/g or s/(.\*)\1/$1/g; 
    return $_; 
} 

चरण दो एक Perl- को एक regex कि तार खुद को मेल खाता से पहले regex कन्वर्ट करने के लिए, है रेगेक्स जो उन तारों से मेल खाने वाले सामान्यीकृत रेगेक्स से मेल खाता है; उदाहरण के लिए, AA*B को ^AA*\*?B$ में परिवर्तित किया जाएगा, जिसका अर्थ है "स्टार्ट-ऑफ-स्ट्रिंग, उसके बाद ए, उसके बाद शून्य या अधिक ए, वैकल्पिक रूप से एक तारांकन के बाद, बी के बाद, अंत-स्ट्रिंग के बाद":

sub regex_to_metaregex($) 
{ 
    local $_ = shift; 
    s/(.)(\*?)/$2 ? "\Q$1\E*(\Q$1\E\\*)?" : "\Q$1"/eg; 
    return qr/^$_$/; 
} 

चरण तीन जरूरतों को कोई स्पष्टीकरण:

sub does_regex1_cover_regex2($$) 
{ 
    my ($r1, $r2) = @_; 
    $r1 = regex_to_metaregex normalize_regex $r1; 
    $r2 = normalize_regex $r2; 
    return scalar $r2 =~ m/$r1/; 
} 

यह आपके मामलों # 1 – 3. यह आपके मामले # 4 के लिए एक झूठी मान देता है के लिए एक सच्चे मान देता है, तथापि, क्योंकि जब तक मैं वास्तव में हूँ कुछ याद आ रहा है, A+M+BC* कवर AMM+B+C+M+BC*?

ध्यान दें कि इनपुट स्ट्रिंग्स stra और strb में regex वर्ण '*' और '+' से बचने का एक तरीका भी होना चाहिए।

मुझे लगता है कि के बारे में उपरोक्त कोड में चिंता नहीं था, लेकिन जब से तुम ASCII के बारे में चिंतित हैं, एक preprocessing कदम \* अर्थ *, \++ अर्थ, और \\\ अर्थ, उन्हें संभाल सकता एकल में अनुवाद द्वारा एएससीआईआई रेंज के बाहर के पात्र:

sub process_escapes($) 
{ 
    local $_ = shift; 
    s/\\\\/\x80/g; 
    s/\\\+/\x81/g; 
    s/\\\*/\x82/g; 
    s/\x80/\\/g; 
    return $_; 
} 

(हालांकि यह स्पष्ट रूप से हैकिश है)।

सी ++ में, आप उसी दृष्टिकोण का उपयोग कर सकते हैं — पुस्तकालय मौजूद हैं जो पर्ल रेगेक्स — की सभी आवश्यक विशेषताओं को लागू करते हैं, हालांकि स्पष्ट रूप से यह थोड़ा और काम होगा।