नियमित अभिव्यक्ति के माध्यम से केस-प्रेरक आदेश शब्द खोज

Question

मैंने अभी पेर्ल में नियमित अभिव्यक्ति के साथ शुरुआत की। विभिन्न ऑनलाइन ट्यूटोरियल्स के माध्यम से खेलने के बाद, मैं एक नियमित अभिव्यक्ति लिखना चाहता था जो आदेश निर्दिष्ट केस असंवेदनशील शब्द मिलान से मेल खाता है।

मैं यह निर्धारित करने की कोशिश कर रहा हूं कि स्ट्रिंग "ए" में एक शब्द या स्ट्रिंग "बी" के शब्दों का अनुक्रम होता है, और मैं इस मामले को असंवेदनशील रूप से करना चाहता हूं।

उदाहरण के लिए, यदि स्ट्रिंग "बी" "जॉन वॉन न्यूमैन" है, तो "जॉन", "वॉन न्यूमैन", "वॉन", "जॉन Neumann" एक मैच होगा, लेकिन "Joh" की तरह तार , "NeumaNn VoN", "वॉन" एक मैच नहीं होगा।

मुझे यकीन नहीं है कि नियमित अभिव्यक्तियों के साथ ऐसा कैसे करें, कोई विचार?

Answer 1

चलो एक दूसरे के मामले को अनदेखा करते हैं।

sub true_indexes { 
    my ($n) = @_; 
    my $i = 0; 
    my @indexes; 
    while ($n) { 
     push @indexes, $i if $n & 1; 
     ++$i; 
     $n >>= 1; 
    } 
    return @indexes; 
} 

my @words = split(' ', 'John Von Neumann'); 

my @patterns; 
unshift @patterns, join ' ', @words[ true_indexes($_) ] 
    for 1 .. (2**@words)-1; 

:

John Von Neumann 

द्वारा

John Von Neumann 1 1 1 
John Von   1 1 0 
John  Neumann 1 0 1 
John    1 0 0 
    Von Neumann 0 1 1 
    Von   0 1 0 
     Neumann 0 0 1 

मिलान किया जा सकता तो regex पैटर्न आप देख रहे हैं जिसके लिए

/^(?:John Von Neumann|John Von|John Newmann|John|...)\z/i 

यहाँ आप कैसे सूची बना सकते हैं है और अंत में, हम पैटर्न उत्पन्न कर सकते हैं:

my $pat = join '|', map quotemeta, @patterns; 
my $re = qr/$pat/i; 

आप इस तरह है जैसे कि यह प्रयोग करना होगा: (प्रत्येक शब्द स्ट्रिंग स्टोर करने के लिए के लिए

if ($input =~ /^$re\z/) { 
    print "match\n"; 
} else { 
    print "no match\n"; 
} 

Answer 2

Ikegami के समाधान घातीय स्थान ले जाएगा इससे पहले कि यह regex में बदल गया है दिखाई देगा 2 ^{n - 1} बार, जहां n शब्दों की संख्या है, इसलिए कुल स्थान कम से कम 2 ^{n - 1} * योग (शब्दों की लंबाई) है)। यह रेगेक्स इंजन से संबंधित नहीं है - चूंकि स्ट्रिंग को रेगेक्स में बदलने से पहले समस्या है।

---

एक regex निर्माण बराबर Ikegami के समाधान के लिए (तार के सेट है कि यह मेल खाता है की अवधि में) होगा:

^(?=[^ ])(?:(?: |^)John(?= |\z))?+(?:(?: |^)Von(?= |\z))?+(?:(?: |^)Neumann(?= |\z))?+\z 

यह केवल शब्दों की संख्या की अवधि में रेखीय स्थान में समा जाता, और सभी शब्दों की कुल लंबाई।

स्पष्टता के लिए: मिलान किया जा रहा से रिक्त स्ट्रिंग को रोकने, और सुनिश्चित करें पहला वर्ण एक अंतरिक्ष चरित्र नहीं है:

^ 
(?=[^ ]) 
(?:(?: |^)John(?= |\z))?+ 
(?:(?: |^)Von(?= |\z))?+ 
(?:(?: |^)Neumann(?= |\z))?+ 
\z 

लुक-आगे जोर (?=[^ ]) 2 प्रयोजनों है।

नोट ?+, जो परिमाणक अधिकार (या परमाणु) बना देता है के बाद से हम यहाँ उलटे पांव लौटने की जरूरत नहीं है। क्यों? अगर हम इसे सामान्य रूप से करना चाहते थे, तो हम शब्दों की सूची के माध्यम से लूप करेंगे और इनपुट में बाईं ओर सबसे अधिक शब्द की तुलना करेंगे। एक मैच खोजने के बाद, हम लूप को इनपुट में अगले शब्द के साथ तुलना करने के लिए जारी रखेंगे, जब तक कि इनपुट में सभी शब्द नहीं मिलते हैं या हमने शब्दों की सूची को लूप करना समाप्त कर दिया है।

स्वामित्व क्वांटिफायर भी नरक को होने से पीछे हटने से रोकता है। यदि एक शब्द को एक मैच माना जाता है, तो इसे फिर से पुनर्विचार नहीं किया जाएगा।

प्रत्येक शब्द के लिए, वे किसी स्थान से पहले हो सकते हैं, या यह स्ट्रिंग की शुरुआत है। लुक-आगे दावा (?= |\z) का यह सुनिश्चित करने का उद्देश्य है कि पहले उपसर्ग के साथ शब्दों को गलत तरीके से मिलान नहीं किया जाता है (उदा। "John Von Vone", "John Vone" से मिलान करने का प्रयास करें)।

चूंकि कोई बैकट्रैकिंग नहीं है, इसलिए सबसे खराब केस प्रदर्शन सभी शब्दों की लंबाई और इनपुट स्ट्रिंग की लंबाई (जैसा कि आप इसे रेगेक्स के बिना कैसे करेंगे) की अवधि में रैखिक है।

---

हम लचीला रिक्ति अनुमति देने के लिए रेगुलर एक्सप्रेशन से एक छोटा सा बदल सकते हैं:

^(?= *+[^ ])(?: *+John(?= |\z))?+(?: *+Von(?= |\z))?+(?: *+Neumann(?= |\z))?+ *+\z 

स्पष्टता के लिए (प्रमुख अंतरिक्ष महत्वपूर्ण है):

^ 
(?= *+[^ ]) 
(?: *+John(?= |\z))?+ 
(?: *+Von(?= |\z))?+ 
(?: *+Neumann(?= |\z))?+ 
*+ 
\z 

में लुक-आगे (?= *+[^ ]) शुरुआत सुनिश्चित करता है कि इनपुट स्ट्रिंग में केवल रिक्त स्थान नहीं हैं।

रेगेक्स को किसी शब्द की तुलना में किसी भी रिक्त स्थान (पिछली मात्रात्मक द्वारा अस्वीकृत बैकट्रैकिंग) की अनुमति देने के लिए बदला जाता है। 0 या अधिक क्वांटिफायर * का उपयोग किया जाता है, यदि शब्द स्ट्रिंग की शुरुआत में सही है। (?= |\z) देखें आगे बढ़ने के कारण, 2 शब्दों को टकराव करने का कोई मौका नहीं है।

स्ट्रिंग का निर्माण करते समय यह अभी भी रैखिक स्थान लेता है (इसे रेगेक्स इंजन में दर्ज करने से पहले)। सबसे खराब मामला प्रदर्शन भी रैखिक है।

---

चरम मामलों

1. मूल शब्द:

   aaaaaaaaaaaaaaaaaaa0 aaaaaaaaaaaaaaaaaaa1 ... aaaaaaaaaaaaaaaaaaa9 aaaaaaaaaaaaaaaaaaaa ... aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaaA ... aaaaaaaaaaaaaaaaaaaZ 
   

   (प्रत्येक शब्द 20 वर्ण, 0-9 से अंतिम वर्ण परिवर्तन, तो a-z, तो A-Z है)

   स्ट्रिंग्स (नहीं मिलान) के लिए खोज करने के लिए:

   aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaay 
   

   (y केवल z से पहले आ सकता है)

2. मूल शब्द:

   patterns used in Perl pattern matching evolved from those supplied 
   

   (कुछ सामान्य शब्द)

   खोजने के लिए स्ट्रिंग्स (मिलान नहीं):

   patterns used in Perl pattern matching evolved from those suppliedd 
   

3. मूल शब्द (अतिरिक्त अंत में d):

   aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaa 
   

   (। वर्ड केवल a अलग लंबाई के साथ होता है,)

   स्ट्रिंग्स के लिए खोज करने के लिए (मिलान नहीं):

   aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaaa 
   

   (अतिरिक्त a अंत)

4. मूल शब्द में:

   performance abc xyz performance 456 !@# performance 
   

   (एक ही शब्द प्रदर्शित होने के एक से अधिक बार)

   स्ट्रिंग्स (नहीं मिलान) के लिए खोज करने के लिए:

   performance performance performance performance