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

1964 में, ब्रोज़ोज़ोव्स्की ने रेगुलर एक्सप्रेशंस के डेरिवेटिव्स के बारे में पहला पेपर प्रकाशित किया । यह मेरे पसंदीदा एल्गोरिदम में से एक है। रेगुलर एक्सप्रेशन के डेरिवेटिव का उपयोग करके, हम रेगुलर एक्सप्रेशन मैचिंग करने के लिए एक एल्गोरिथम लागू कर सकते हैं। यह एल्गोरिदम बहुत है:

• सरल
• कार्यात्मक
• अपने स्वयं के ऑपरेटरों के साथ आसानी से विस्तार योग्य

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

नियमित अभिव्यक्तियों का पुनर्कथन

सबसे पहले, यह सुनिश्चित करने के लिए कि हम एक ही पृष्ठ पर हैं, रेगुलर एक्सप्रेशन की त्वरित समीक्षा करते हैं। अभिव्यक्ति a(a|b)*एक स्ट्रिंग से मेल खाती है जो a से शुरू होती है a, जिसके बाद किसी भी संख्या में a's' और b's' होते हैं।

• तार abमेल खाएगा a(a|b)*। हम इसे एक खाद्य नीले भूत के साथ इंगित करेंगे।
• स्ट्रिंग aabbbaभी मेल खाती a(a|b)*है क्योंकि यह a से शुरू होती है aऔर उसके बाद कई a's' और b's' आते हैं।
• अगला, स्ट्रिंग acमेल नहीं खाती है a(a|b)*, क्योंकि रेगेक्स किसी से मेल नहीं खाता है cऔर हमारा रेगेक्स कोई सबस्ट्रिंग मिलान नहीं करता है। हम पीएसी-मैन का पीछा कर रहे लाल भूत का उपयोग करके इसका संकेत देंगे।
• अंत में, स्ट्रिंग baभी मेल नहीं खाती a(a|b)*क्योंकि यह एक से शुरू नहीं होती है a।

एल्गोरिथ्म का अवलोकन

विवरण में तल्लीन करने से पहले, आइए देखें कि यह एल्गोरिथम कैसे काम करता है। मैंने पीएसी-मैन का एक अजीब खेल तैयार किया है जहां आप भूतों को खाने के लिए केवल तभी प्राप्त कर सकते हैं जब आप रेगेक्स से मेल खाने वाले क्रम में फल खाते हैं। हमारा पीएसी-मैन रेगेक्स का प्रतिनिधित्व करता है aba*। इसमें खाने के लिए निम्नलिखित फल हैं: एक सेब, फिर एक केला, और फिर एक सेब: aba.

1. जब हम शुरू करते हैं, तो भूत हमारा पीछा कर रहा होता है, और मैच के लिए हमने जो रेगुलर एक्सप्रेशन छोड़ा है वह है aba*।
2. हम पहला सेब खाते हैं, और नियमित अभिव्यक्ति जो अब हमारे पास मेल खाने के लिए बची है ba*। भूत अभी भी हमारा पीछा कर रहा है क्योंकि अब तक हमने जो फल खाया है, सेब रेगेक्स से मेल नहीं खाता है।
3. अगला, हम केला खाते हैं। फिर हमने जो रेगेक्स मैच के लिए छोड़ा है वह है a*। अब भूत भागने लगता है क्योंकि तकनीकी रूप से abपहले से ही मेल खाता aba*है।
4. हम घोस्ट को खाने की कोशिश कर सकते हैं या दूसरा सेब खा सकते हैं, इस मामले में मिलान करने के लिए हमने जो रेगुलर एक्सप्रेशन छोड़ा है वह अभी भी है a*। भूत अभी भी भाग रहा है क्योंकि abaरेगुलर एक्सप्रेशन से भी मेल खाता है aba*।

यहां काम का एक और फंक्शन है। फ़ंक्शन जाँचता है कि क्या भूत पीएसी-मैन का पीछा कर रहा है या पीएसी-मैन पहले से ही रेगेक्स से मेल खा चुका है और भूत का पीछा कर रहा है। इस फ़ंक्शन को अशक्त फ़ंक्शन कहा जाता है; यह जांचता है कि मिलान करने के लिए छोड़ा गया रेगेक्स खाली स्ट्रिंग से मेल खाता है या नहीं। यह ऐसा कर सकता है क्योंकि अगर रेगेक्स जो मैच के लिए छोड़ दिया गया है, खाली स्ट्रिंग से मेल खाता है, तो जो फल उसने खाया है वह पहले से ही रेगेक्स को संतुष्ट करने के लिए पर्याप्त होना चाहिए।

व्युत्पन्न-मिलान एल्गोरिथम

इसका मतलब है कि व्युत्पन्न मिलान एल्गोरिदम लिखने के लिए हमें केवल दो कार्यों की आवश्यकता है:

1. व्युत्पन्न कार्य
2. अशक्त कार्य

अनिवार्य प्रोग्रामर्स के लिए गोलंग में एक:

और दूसरा कार्यात्मक प्रोग्रामर के लिए हास्केल में:

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

अब, आइए गहराई से जानें कि कैसे अशक्त और व्युत्पन्न कार्यों को लागू किया जाए।

पीएसी-मैन मूल कहानी विषयांतर

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

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

यह बताता है कि लाश हमेशा इंसानों का पीछा क्यों कर रही है। जैसा कि डेविड एटनबरो ने एक बार कहा था:

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

बेसिक ऑपरेटर्स

अशक्त और व्युत्पन्न कार्यों के कार्यान्वयन के लिए हमें सबसे पहले अपने नियमित भावों में उपलब्ध बुनियादी संचालकों को परिभाषित करने की आवश्यकता होती है।

स्ट्रिंग्स के एक सेट का वर्णन करने के रूप में हम एक नियमित अभिव्यक्ति के बारे में सोच सकते हैं।

• इसका मतलब है कि खाली सेट एक ऐसे ऑपरेटर का प्रतिनिधित्व करता है जो बिना तार के मेल खाता है।
• खाली स्ट्रिंग एकल स्ट्रिंग के सिंगलटन सेट का प्रतिनिधित्व करती है जो केवल खाली स्ट्रिंग से मेल खाता है।
• वर्ण एक सिंगलटन सेट का भी प्रतिनिधित्व करता है जो केवल एकल वर्ण से मेल खाता है a।
• इसके बाद हम इन आधार रेगुलर एक्सप्रेशन को ऑपरेटरों का उपयोग करके जोड़ सकते orहैं जैसे:concatenationKleene starrs

अशक्त कार्य

हम अशक्त कार्य से शुरू कर सकते हैं। आइए कुछ उदाहरण देखें और जानें कि इनमें से कौन सा रेगुलर एक्सप्रेशन खाली स्ट्रिंग से मेल खाता है ताकि यह पता चल सके कि यह फ़ंक्शन कैसे लागू होता है।

• a*खाली स्ट्रिंग से मेल खाता है क्योंकि शून्य या अधिक में शून्य शामिल है।
• (a*|b)के बाईं ओर से खाली स्ट्रिंग से मेल खाता है या खाली स्ट्रिंग से मेल खाता है।
• abखाली स्ट्रिंग से मेल नहीं खाता, क्योंकि यह केवल स्ट्रिंग से मेल खाता हैab
• ab*खाली स्ट्रिंग से भी मेल नहीं खाता है, क्योंकि ab*एक स्ट्रिंग की आवश्यकता होती है जो एक से शुरू होती हैa
• (a|b)रिक्त स्ट्रिंग से मेल नहीं खाता, क्योंकि न तो बाएँ और न ही दाईं ओर orखाली स्ट्रिंग से मेल खाता है।

यहाँ अशक्त कार्य का कार्यान्वयन है। बाईं ओर उन मानों का प्रतिनिधित्व करता है जो फ़ंक्शन में पारित किए जाते हैं, और दाईं ओर उस स्थिति में फ़ंक्शन के कार्यान्वयन का प्रतिनिधित्व करता है। लाल भूत असत्य का प्रतिनिधित्व करते हैं, और नीले भूत सत्य का प्रतिनिधित्व करते हैं:

• खाली सेट खाली स्ट्रिंग से मेल नहीं खाता क्योंकि यह किसी भी स्ट्रिंग से मेल नहीं खाता।
• खाली स्ट्रिंग खाली स्ट्रिंग से मेल खाती है क्योंकि यह केवल खाली स्ट्रिंग से मेल खाती है।
• चरित्र aखाली स्ट्रिंग से मेल नहीं खाता क्योंकि यह केवल चरित्र से मेल खाता है a।
• यदि हमारे पास तार्किक है or, तो हमें दोनों पक्षों की जाँच करनी होगी। यदि या तो खाली स्ट्रिंग से मेल खाता है, तो तार्किक orखाली स्ट्रिंग से मेल खाता है।
• खाली स्ट्रिंग से मिलान करने के लिए concatenationदो नियमित अभिव्यक्तियों के लिए, दोनों को खाली स्ट्रिंग से मेल खाना होगा।
• और अंत में, अगर हमारे पास zero or moreकुछ है, तो इसमें शून्य शामिल है, जिसका अर्थ है कि यह हमेशा खाली स्ट्रिंग से मेल खाता है।

1. हमारा शीर्ष ऑपरेटर orइसका मतलब है कि हमें बाएँ और दाएँ पक्षों की अशक्तता की जाँच करनी है: bऔर a*।
2. हम जाँचते हैं और देखते हैं कि bबाईं ओर का वर्ण अशक्त नहीं है false:।
3. फिर हम जांचते हैं और देखते हैं कि a*दाईं ओर शून्य है true:।
4. अब हम वापस आ गए हैं falseऔर trueहम orउन्हें प्राप्त करने के लिए कर सकते हैं true।

निरर्थक व्यायाम

कार्यान्वयन के माध्यम से चलने का प्रयास करें और जांचें कि क्या निम्नलिखित रेगुलर एक्सप्रेशन अशक्त हैं। आप अपना उत्तर जांचने के लिए उन पर क्लिक कर सकते हैं:

1. एक
2. ए*(बी*|∅)
3. हाँ
4. ∅*
5. (∅|बी)*(एबीसी|ε)

इससे पहले कि हम फ़ंक्शन के कार्यान्वयन को देखें, आइए व्युत्पन्न के उदाहरण देखें। यहां हम चरित्र के संबंध में कुछ नियमित अभिव्यक्तियों के व्युत्पन्न लेने जा रहे हैं a:

• a*एक सेब खाने के बाद मेल खाने के लिए छोड़ी गई रेगुलर एक्सप्रेशन aअभी भी है a*।
• ab*के संबंध में व्युत्पन्न aहै b*, क्योंकि हम पहले ही उपसर्ग से मेल खा चुके हैं a।
• (a|b)bके संबंध में व्युत्पन्न aहै b।
• b|(a*b)के संबंध में व्युत्पन्न aहै a*b। बायाँ bमेल नहीं खाता था, इसलिए हम इसे फेंक सकते थे और दाईं ओर के aद्वारा खा लिया गया था zero or more a।
• अगला, हमारे पास है ab*, यह थोड़ा मुश्किल है। सेब खाने के बाद, नियमित अभिव्यक्ति जो मैच के लिए छोड़ी जाती है वह है b(ab)*। चूंकि हमने केवल का मिलान किया है a, हम कम से कम एक और देखने की उम्मीद कर रहे हैं b।

• खाली सेट का व्युत्पन्न हमेशा खाली सेट होता है। पुनर्प्राप्त करने का कोई तरीका नहीं है क्योंकि खाली सेट कुछ भी मेल नहीं खाता।
• किसी भी वर्ण से संबंधित खाली स्ट्रिंग का व्युत्पन्न खाली सेट है। यह एक चरित्र से मेल खाने की उम्मीद नहीं कर रहा था। यह केवल खाली स्ट्रिंग से मेल खाएगा।
• एक समान वर्ण (इस मामले में, pple) के लिए एक वर्ण का व्युत्पन्न aखाली स्ट्रिंग है क्योंकि इसके मिलान के बाद, मिलान करने के लिए जो कुछ बचा है वह खाली स्ट्रिंग है।
• एक अलग चरित्र के संबंध में एक चरित्र का व्युत्पन्न जो समान नहीं है, इस मामले में, bअना, खाली सेट है क्योंकि हम विशिष्ट चरित्र से मेल नहीं खाते हैं।
• orव्यंजक का अवकलज अवकलज का orहोता है। यह बस समस्या को अपने बच्चों तक पहुँचाता है।
• अभिव्यक्ति के व्युत्पन्न को concatयह विचार करना होगा कि क्या वह पहली अभिव्यक्ति को छोड़ सकता है। यह केवल पहली अभिव्यक्ति को छोड़ सकता है यदि पहली अभिव्यक्ति खाली स्ट्रिंग से मेल खाती है और अशक्त है। तो सबसे पहले हम इसे चेक करते हैं। आइए उस मामले के बारे में सोचें जहां यह पहली अभिव्यक्ति को छोड़ नहीं सकता है जब अभिव्यक्ति rअशक्त नहीं है। concatenatedफिर व्युत्पन्न दूसरी अभिव्यक्ति के साथ पहली अभिव्यक्ति का व्युत्पन्न है s। यदि हम पहले रेगेक्स को छोड़ सकते हैं, तो हमें एक ऐसे विकल्प पर विचार करना होगा जो केवल दूसरी अभिव्यक्ति का व्युत्पन्न हो। इसके बाद हम स्किपिंग ओवर और orनॉट ओवर स्किप करने के दो विकल्प कर सकते हैं और परिणामस्वरूप उसे वापस कर सकते हैं।rr
• अंत में, हमारे पास starऑपरेटर है। यह शून्य या अधिक बार एक अभिव्यक्ति से मेल खाता है। चूंकि हमें एक पात्र पारित किया जा रहा है, यह शून्य मामला नहीं है। इसलिए हमें one or moreमामले पर विचार करना होगा। इसका मतलब है कि हमें अभिव्यक्ति के व्युत्पन्न को अंदर लेना होगा starऔर concatenateइसे फिर से zero or moreअभिव्यक्ति के साथ लेना होगा।

व्युत्पन्न उदाहरण 1

(ab)*के संबंध में व्युत्पन्न लेते हैं a।

(ab)*एक zero or moreअभिव्यक्ति है, इसलिए हम zero or moreनियम को देखते हैं। हम देखते हैं कि इसके अंदर अभिव्यक्ति के व्युत्पन्न को लेने की आवश्यकता है star।

यह और concatenationका है । इसलिए हम जाँचते हैं कि क्या बाईं ओर अशक्त है, और वर्ण अशक्त नहीं है। इसका मतलब है कि हम इसे छोड़ नहीं सकते हैं। हमें के संबंध में व्युत्पन्न करना होगा । लेकिन वह खाली स्ट्रिंग है, इसलिए यदि हम खाली स्ट्रिंग को दाईं ओर रखते हैं, जो था , तो हमें मिलता है ।abaaaconcatenatebb

अब, हम पर वापस लौटते हैं , याद रखें कि हमने इसके संबंध zero or moreमें डेरिवेटिव लिया और वापस प्राप्त किया । अब हम इसे फिर से जोड़ सकते हैं और हम प्राप्त कर सकते हैं ।abab(ab)*b(ab)*

व्युत्पन्न उदाहरण 2

(a*ba)के संबंध में व्युत्पन्न लेते हैं b।

• a*के साथ जुड़ा हुआ है baइसलिए हम संयोजन नियम पर एक नज़र डालते हैं।
• हम जाँचते हैं कि क्या बाईं ओर a*अशक्त है, जो कि है। इसका मतलब है कि हम इसे छोड़ सकते हैं, जिसका अर्थ यह भी है कि हमें orदो डेरिवेटिव बनाने होंगे।
• बायां पक्ष मेल नहीं खाता है, क्योंकि a*मेल नहीं खाता है b।
• सौभाग्य से हमारे पास एक विकल्प है ba। is और baके संबंध में व्युत्पन्न ।ba

मैंने यहां कुछ विवरण छोड़े हैं। इसे स्वयं समारोह में चलकर मेरे काम की जांच करने की कवायद समझें।

व्युत्पन्न अभ्यास

कार्यान्वयन के माध्यम से चलने का प्रयास करें और जांचें कि निम्नलिखित नियमित अभिव्यक्तियों के डेरिवेटिव्स के संबंध में क्या है b। आप अपना उत्तर जांचने के लिए उन पर क्लिक कर सकते हैं:

1. बी
2. बी * (बी | सी)
3. ए * (बी | सी)
4. bεb
5. ∅*ख

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

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

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

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

शुक्रिया

• मुझे इस एल्गोरिथम को समझाने के लिए समय निकालने के लिए Brink van der Merwe ।

• ब्रोज़ोज़ोव्स्की, जानूस ए। "नियमित अभिव्यक्ति के डेरिवेटिव्स।" जर्नल ऑफ द एसीएम (जेएसीएम) 11.4 (1964): 481-494।
• ओवेन्स, स्कॉट, जॉन रेप्पी और आरोन ट्यूरोन। "रेगुलर-एक्सप्रेशन डेरिवेटिव्स की फिर से जांच की गई।" कार्यात्मक प्रोग्रामिंग जर्नल 19.2 (2009): 173-190।