नियमित अभिव्यक्तियों की सूक्ष्मता। भाग 2: रिफंड और उनकी मात्रा

भाग 1: चरित्र वर्गों के अंदर और बाहर मेटाचैकर्स ।



इस भाग में, मैं इस बारे में बात करना चाहूंगा कि नियमित अभिव्यक्ति इंजन कैसे काम करते हैं, क्यों कुछ लोगों को लगता है कि नियमित अभिव्यक्ति बहुत धीमी है, और क्यों कई इंजनों के लेखक POSIX मानक का पालन नहीं करते हैं।



कई समस्याओं के रूप में, "नियमित अभिव्यक्ति के लिए एक स्ट्रिंग में एक मैच खोजने" की समस्या को हल करने के लिए कई दृष्टिकोण और सिद्धांत हैं। इस मामले में मूल सिद्धांत 2 हैं: एक नियमित अभिव्यक्ति द्वारा नियंत्रित खोज मिलान, और एक स्ट्रिंग द्वारा नियंत्रित खोज मिलान। आइए, इन सिद्धांतों में से प्रत्येक का क्या अर्थ है, इस पर ध्यान दें।

स्ट्रिंग ड्रिविंग मैचिंग

इस प्रकार का रेगेक्स इंजन तथाकथित डीएफए ( निर्धारक परिमित राज्य मशीन ) का उपयोग करके कार्यान्वित किया जाता है। मुख्य लाभ मैच खोजने की विशाल गति (किसी अन्य सिद्धांत की तुलना में) है। स्वाभाविक रूप से, इस सिद्धांत में दोषों का एक गुच्छा है (अन्यथा यह दिलचस्प नहीं होगा, ठीक है?)।



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



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



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



तो DKA अभी भी कैसे काम करता है? इंजन को "लाइन संचालित" कहा जाता है क्योंकि यह बस उसी तरह से काम करता है। राज्य मशीन उस रेखा को पढ़ती है जिसमें मैचों को खोजने के लिए, और पैटर्न के साथ रेखा की तुलना करता है। समय के प्रत्येक क्षण में, एल्गोरिथ्म "जानता है" पैटर्न के किन हिस्सों और स्ट्रिंग से मेल खाता है। जब एल्गोरिथ्म पूरी तरह से पूरी लाइन को स्कैन करता है, तो यह केवल सबसे लंबे मैच का चयन करने के लिए रहता है, जो लाइन की शुरुआत के करीब है और इसे उत्तर के रूप में देता है।



निश्चितता के लिए, हम मानते हैं कि हमारे पास नियमित अभिव्यक्ति ^abc\w+e$



और दो लाइनें abcde



और abce



। यह स्पष्ट है कि अभिव्यक्ति पहली पंक्ति से मेल खाती है, लेकिन दूसरी नहीं।



आइए विचार करें कि डीकेए तंत्र में संयोग की खोज कैसे होती है। पहली पंक्ति के लिए निम्नलिखित अनुक्रम हैं:

• स्ट्रिंग "ए" का पहला चरित्र - मेटाचेचर ^
  
  
  
  साथ स्थिति में मेल खाता है। 1 आंशिक मैच मिला।
• स्ट्रिंग "ए" का पहला चरित्र - पैटर्न के दूसरे चरित्र के मूल्य से मेल खाता है। एल्गोरिथ्म 1 आंशिक मैच का नेतृत्व करना जारी रखता है।
• स्ट्रिंग "बी" का दूसरा चरित्र - पैटर्न के तीसरे चरित्र के साथ मूल्य में मेल खाता है। एल्गोरिथ्म 1 आंशिक मैच का नेतृत्व करना जारी रखता है।
• स्ट्रिंग "सी" का तीसरा वर्ण - पैटर्न के चौथे चरित्र के साथ मूल्य में मेल खाता है। एल्गोरिथ्म 1 आंशिक मैच का नेतृत्व करना जारी रखता है।
• स्ट्रिंग "घ" का चौथा चरित्र - पैटर्न के पांचवें मेटाचैकर \w
  
  
  
  मूल्य से मेल खाता है। क्वांटिफायर के लिए आवश्यक है कि मेटाचैकर मैच कम से कम एक बार हो। हालत संतुष्ट है। एल्गोरिथ्म 1 आंशिक मैच का नेतृत्व करना जारी रखता है।
• स्ट्रिंग "ई" के पांचवें चरित्र - पैटर्न के आठवें चरित्र के साथ मूल्य में मेल खाता है। पिछले मेटाचैकर के लिए मात्रात्मक स्थिति पूरी हो गई है; हम पैटर्न के आठवें वर्ण के साथ संयोग के रूप में "ई" प्रतीक की गिनती कर सकते हैं, या \w
  
  
  
  मेटाचैकर के साथ एक संयोग के रूप में। एल्गोरिथ्म यह और वह दोनों करता है, और 2 आंशिक मैचों का नेतृत्व करना जारी रखता है। इस बिंदु को याद रखें, एक अन्य सिद्धांत में एक बहुत महत्वपूर्ण अंतर होगा।
• लाइन का छठा वर्ण गायब है - यह $
  
  
  
  मेटाचचर के साथ स्थिति में मेल खाता है। एक पूरा मैच मिला, और दूसरा आंशिक उम्मीदों पर खरा नहीं उतरा और उसे छोड़ दिया गया।
• लाइन खत्म हो गई है, हम परिणाम लौटाते हैं।

दूसरे मामले में क्या होगा:

• एल्गोरिथ्म की शुरुआत बिल्कुल समान है, तुरंत स्ट्रिंग "ई" के चौथे चरित्र पर जाएं
• स्ट्रिंग "ई" का चौथा चरित्र पैटर्न \w
  
  
  
  के पांचवें मेटाचैकर के साथ मूल्य में मेल खाता है। मात्रात्मक स्थिति के लिए आवश्यक है कि किसी वर्ण के लिए कम से कम एक मैच मौजूद हो। इसलिए, "ई" को \w
  
  
  
  मेटाचचर द्वारा कैप्चर किया जाता है। 1 आंशिक मैच।
• लाइन का पाँचवाँ पात्र गायब है - "ई" अक्षर से मेल खाने वाला कोई पैटर्न नहीं है। जाहिर है कि स्ट्रिंग मेल नहीं खाती।
• लाइन समाप्त हो गई है, कोई मैच नहीं हैं, हम परिणाम लौटाते हैं।

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



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



फिलहाल, DKA इंजन का उपयोग grep उपयोगिता में इंजन चयन तंत्र के भाग के रूप में और Tcl भाषा में संकर इंजन के भाग के रूप में किया जाता है, यह संभवतः अन्यत्र उपयोग किया जाता है, लेकिन मुझे इसके बारे में पता नहीं है।

नियमित अभिव्यक्ति मिलान

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



सबसे पहले, ऑपरेटिंग समय बेहद लंबा हो सकता है (किसी अन्य सिद्धांत की तुलना में)। इनपुट स्ट्रिंग की लंबाई के घातीय स्पर्शोन्मुख तक। कई लोकप्रिय इंजनों को भी इस से सुरक्षा मिलती है, जिससे खोज बाधित होती है।



दूसरे, एनकेए बहुत कुछ इस बात पर निर्भर करता है कि नियमित अभिव्यक्ति कैसे लिखी जाती है। यदि DFA रिकॉर्डिंग के रूप में बिल्कुल समान है: समय और खोज परिणाम किसी भी समकक्ष अभिव्यक्तियों के लिए बिल्कुल समान होंगे, तो NKA के लिए यह पूरी समस्या है। एक अभिव्यक्ति घातीय स्पर्शोन्मुख दे सकती है, और दूसरी लगभग रैखिक है। तदनुसार, पैटर्न के अनुकूलन का सवाल पूर्ण विकास में उठता है। वर्तमान में एनकेए का उपयोग अधिकांश नियमित अभिव्यक्ति इंजनों में किया जाता है।



क्लासिक एनकेए की एक प्रमुख विशेषता यह है कि यह खोज को बाधित करता है जैसे ही यह पहला पूर्ण मैच पाता है। यानी कुछ मामलों में खोज परिणाम DKA से बहुत भिन्न होंगे। यह एल्गोरिथ्म की एक विशेषता है।



तो क्यों इंजन के लेखक POSIX का पालन करने के लिए जल्दी में नहीं हैं? तथ्य यह है कि डीकेए खोज के शब्दार्थ मानक में तय किए गए हैं। यानी बेशक, यह शाब्दिक रूप से नहीं कहा गया है कि डीकेए का उपयोग किया जाना चाहिए, लेकिन यह "सबसे बड़ी लंबाई के सबसे बाईं संयोग" के बारे में कहा जाता है। लेकिन एनकेए सबसे पहले वापस आता है, और सबसे बड़ी लंबाई नहीं। और क्या करना है? POSIX का अनुपालन करने के लिए, वे एल्गोरिथ्म के एक संशोधन के साथ आए, जिसे आमतौर पर POSIX NKA कहा जाता है। और यह सिर्फ एक एनसीए की तुलना में अधिक समय तक काम करता है। क्योंकि मानक को पूरा करने के लिए, सभी को उन सभी विकल्पों से गुजरना पड़ता है जो एक नियमित अभिव्यक्ति की अनुमति देती है। आगे मैं समझाऊंगा कि यह अधिक लंबा क्यों है।



संकलित (अर्थ डीएफए के लिए समान है) एनकेए एक अनुक्रमिक एल्गोरिदम है, पैटर्न के आधार पर निर्देश। एनसीए की एक प्रमुख विशेषता "रिटर्न" है। खोज की गति सीधे उनकी संख्या पर निर्भर करती है।



उदाहरण के द्वारा कौन से रिटर्न को सबसे अच्छा समझाया गया है। आइए उन्हीं दो पंक्तियों को लेते हैं जो डीएफए के लिए उदाहरण में इस्तेमाल की गई थीं और वही नियमित अभिव्यक्ति।



पहली पंक्ति के लिए:

• पैटर्न का पहला मेटाचैकर ^
  
  
  
  - लाइन की शुरुआत के साथ स्थिति में मेल खाता है। रिटर्न स्टैक खाली है।
• पैटर्न का दूसरा चरित्र "ए" - स्ट्रिंग के पहले चरित्र के साथ मूल्य में मेल खाता है। रिटर्न स्टैक खाली है।
• पैटर्न "बी" का तीसरा वर्ण - स्ट्रिंग के दूसरे वर्ण के साथ मूल्य में मेल खाता है। रिटर्न स्टैक खाली है।
• पैटर्न "सी" का चौथा चरित्र - स्ट्रिंग के तीसरे चरित्र के साथ मूल्य में मेल खाता है। रिटर्न स्टैक खाली है।
• पाँचवाँ स्ट्रिंग मेटाचैकर \w
  
  
  
  - स्ट्रिंग के चौथे वर्ण के मान से मेल खाता है। एक क्वांटिफायर के लिए कम से कम एक वर्ण की आवश्यकता होती है, इसलिए कोई रिटर्न नहीं हो सकता है। रिटर्न स्टैक खाली है।
• स्ट्रिंग \w
  
  
  
  का पांचवा मेटाचैकर - स्ट्रिंग के पांचवें चरित्र के मूल्य से मेल खाता है। एक क्वांटिफायर के लिए कम से कम एक चरित्र की आवश्यकता होती है जो पहले ही कब्जा कर लिया गया है। इस बिंदु पर धनवापसी हो सकती है। रिटर्न स्टैक में 1 तत्व होता है।
  
  इस मध्यवर्ती स्तर पर, एनसीए ने पूरी लाइन को "एबेक्यूड" के रूप में पाया, लेकिन पैटर्न अभी तक अंत तक नहीं आया है। लाइन में वर्तमान स्थिति प्रतीक "ई" के पीछे स्थित है, हालांकि पैटर्न से प्रतीक "ई" अभी तक संयोग नहीं हुआ है। यह इस बिंदु पर है कि मज़ा शुरू होता है। अपने हाथ देखो।
• पैटर्न "ई" का आठवां चरित्र स्ट्रिंग के छठे वर्ण के साथ मूल्य में मेल नहीं खाता है (यह बस मौजूद नहीं है)। कोई मेल नहीं मिला। रिटर्न स्टैक की जाँच - एक रिकॉर्ड है। हम वापसी करते हैं। लौटने के बाद, हम लाइन में "ई प्रतीक से पहले" और पैटर्न में "ई प्रतीक से पहले" स्थिति में हैं। रिटर्न स्टैक खाली है।
  
  जब एनसीए को मैच नहीं मिलता है, तो यह रिटर्न स्टैक की जांच करता है। रिटर्न करते समय, लाइन में स्थिति बहाल हो जाती है और स्टैक से रिटर्न को हटा दिया जाता है। यदि रिटर्न स्टैक खाली है और कोई मैच नहीं है, तो माना जाता है कि लाइन में इस शुरुआती स्थिति से कोई मैच नहीं हैं।
  
  
• पैटर्न "ई" के आठवें चरित्र - स्ट्रिंग के पांचवें चरित्र के साथ मूल्य में मेल खाता है। रिटर्न स्टैक खाली है।
• पैटर्न $
  
  
  
  का नौवां मेटाचैकर - लाइन के अंत के साथ स्थिति में मेल खाता है। रिटर्न स्टैक खाली है।
• पैटर्न खत्म हो गया है, फिलहाल एक मैच है। हम इसे वापस करते हैं।

दूसरे मामले में क्या होगा:

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

एक बेहतर समझ के लिए, मैं आपको बताऊंगा कि क्वांटिफायर +



हमेशा उतने ही पंक्ति वर्णों को पकड़ता है जितना कि यह हो सकता है। इसलिए, इसे अधिकतम कहा जाता है। शुरुआती लोगों द्वारा की गई एक सामान्य गलती इसके साथ जुड़ी हुई है। पैटर्न \(.+\)



लाइन में मेल करेगा "यहां टेक्स्ट (ब्रैकेट) है और यहां टेक्स्ट (अभी भी ब्रैकेट) है और यहां टेक्स्ट" भाग के साथ "(ब्रैकेट) है और यहां टेक्स्ट (अभी भी ब्रैकेट) है, लेकिन" () के साथ नहीं है ब्रैकेट) ”। सिर्फ इसलिए कि प्रोसेसिंग स्टेज पर .+



पूरी लाइन अंत तक कैप्चर की जाएगी, और जैसे ही हमें "") का सिंबल मिलेगा, हम तुरंत एक पूरा मैच पाएंगे। आइए regex को थोड़ा बदलें: \([^)]+\)



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



वास्तव में, मैं थोड़ा चालाक था जब मैंने वर्णन किया कि एल्गोरिदम विशेष रूप से कैसे काम करता है। तथ्य यह है कि यह इस तरह से काम करेगा यदि इंजन अनुकूलन लागू करता है (यह स्पष्ट है कि यदि पैटर्न ^



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



पोसिक्स एनकेए इंजन के बीच अंतर यह होगा कि पहले मामले में (जब एक मैच पाया गया था) या तो खोज को रोका नहीं जाएगा, लेकिन सभी 5 खोजों का प्रदर्शन किया जाएगा, जैसे कि एक मैच की अनुपस्थिति में, जो निश्चित रूप से बहुत लंबा होगा।



अब जब हमने रिटर्न करने की तकनीक की जांच की है, तो हम अनुमान लगा सकते हैं कि घातीय खोज समय कहां से आता है। कुछ स्थितियों में, एल्गोरिथ्म जाल में पड़ जाता है, जिससे भारी संख्या में रिटर्न मिलता है। उदाहरण के लिए, अभिव्यक्ति (\w+)*a



। यदि आप इसे "bbb" लाइन पर लागू करते हैं, तो क्या होगा? पहला, पहला क्वांटिफायर +



पूरे स्ट्रिंग को पकड़ता है और दूसरा क्वांटिफायर पर नियंत्रण स्थानांतरित करता है। चूंकि लाइन में अधिक वर्ण नहीं हैं, इसलिए हम पैटर्न के "ए" वर्ण पर जाते हैं। जो लाइन में नहीं है, हम एक चरित्र से लौटते हैं, एक नए समूह में खाली चरित्र को रोकते हैं, "ए" की जांच करते हैं, फिर से मैच नहीं होता है। इसके अलावा, अर्थ स्पष्ट होना चाहिए। एल्गोरिथ्म दो क्वांटिफायर द्वारा कब्जा करने के लिए सभी संभावित लाइन ब्रेक पर पुनरावृति करेगा। स्ट्रिंग "bbb" के लिए ये विकल्प होंगे: "[bbb]", "[bb] [b]", "[b] [bb]", "[b] [b] [b]"। जहां वर्ग कोष्ठक सशर्त रूप से कैप्चर किए गए समूह को इंगित करते हैं। विभाजन की संख्या इस मामले में स्ट्रिंग की लंबाई से तेजी से बढ़ती है।



एक और स्थिति। 1 मेगाबाइट पाठ और एक दृश्य पैटर्न की कल्पना करें .*a



जब आप खोज करते हैं तो क्या होता है? प्रत्येक चरण में, स्ट्रिंग के पूरे मेगाबाइट पर कब्जा कर लिया जाएगा और "रिटर्न" वर्ण मिलने तक अनुक्रमिक रिटर्न किया जाएगा। और अगर स्ट्रिंग में ऐसा कोई चरित्र नहीं है? तो यह सिर्फ कुछ किया जाएगा 1000001 खोज प्रदर्शन किया। जो हर बार वर्तमान चरित्र से अंत तक पूरी रेखा को कैप्चर करेगा और उस पर तब तक लौटेगा जब तक कि वह "a" (जो नहीं है) वर्ण नहीं मिल जाता। इससे बचने के लिए, इस मामले में यह लिखना पर्याप्त होगा [^a]*a



। लेकिन यह इस मामले के लिए है। सामान्य मामले में (कोष्ठक के साथ उदाहरण में) यह पर्याप्त नहीं है।



रिटर्न के लिए अनुकूलन तकनीकों के बारे में लिखने के लिए बहुत कुछ है। अगला लेख मैं इसे समर्पित करने की योजना बना रहा हूं।



जेफरी फ्रीडल, मास्टेरिंग रेगुलर एक्सप्रेशंस नामक पुस्तक पर आधारित है।