मेरे पास नियमित अभिव्यक्तियों का एक कंटेनर है। मैं उनका विश्लेषण करना चाहता हूं कि यह निर्धारित करने के लिए कि क्या उनमें से एक से अधिक मिलान करने वाली स्ट्रिंग उत्पन्न करना संभव है या नहीं। इस उपयोग के मामले में मेरे स्वयं के रेगेक्स इंजन को लिखने के लिए, क्या इस समस्या को हल करने के लिए सी ++ या पायथन में कोई आसान तरीका है?आप कैसे पता लगा सकते हैं कि तारों में दो नियमित अभिव्यक्ति ओवरलैप हो सकती हैं या नहीं?
कोई आसान तरीका नहीं है।
जब तक आपके नियमित अभिव्यक्ति केवल मानक विशेषताओं का उपयोग करते हैं (पर्ल आपको मिलान में मनमाने ढंग से कोड एम्बेड करने देता है, मुझे लगता है), आप प्रत्येक को nondeterministic finite-state automaton (NFA) से उत्पादित कर सकते हैं जो आरई मैचों के सभी तारों को कॉम्पैक्टली एन्कोड करता है।
एनएफए की किसी भी जोड़ी को देखते हुए, यह निर्णय लेता है कि उनका चौराहे खाली है या नहीं। यदि छेड़छाड़ खाली नहीं है, तो कुछ स्ट्रिंग जोड़ी में (और इसके विपरीत) दोनों आरईएस से मेल खाती है।
मानक डिकिडेबिलिटी सबूत उन्हें DFA के पहले में निर्धारित करने के लिए है, और उसके बाद एक नया डीएफए बनाएं जिसका राज्य दो डीएफए राज्यों के जोड़े हैं, और जिनके अंतिम राज्य ठीक हैं, जिनमें जोड़ी दोनों राज्य अंतिम हैं अपने मूल डीएफए में। वैकल्पिक रूप से, यदि आप पहले ही दिखा चुके हैं कि एनएफए के पूरक की गणना कैसे करें, तो आप (डीमोर्गन की कानून शैली) को complement(union(complement(A),complement(B))) द्वारा चौराहे प्राप्त कर सकते हैं।
दुर्भाग्यवश, एनएफए-> डीएफए में संभावित रूप से घातीय आकार विस्फोट शामिल है (क्योंकि डीएफए में राज्य एनएफए में राज्यों के उप-समूह हैं)। Wikipedia से:
नियमित भाषाओं के कुछ वर्गों केवल नियतात्मक परिमित ऑटोमेटा जिसका आकार कम से कम बराबर नियमित भाव के आकार में तेजी से बढ़ता है द्वारा वर्णित किया जा सकता है। मानक उदाहरण भाषाएं L_k में शामिल हैं जो वर्णमाला {ए, बी} पर सभी स्ट्रिंग्स हैं जिनकी केथ-अंतिम पत्र एक बराबर है।
वैसे, आपको निश्चित रूप से OpenFST का उपयोग करना चाहिए। आप ऑटोमाटा को टेक्स्ट फाइलों के रूप में बना सकते हैं और कम से कम परिचालन, छेड़छाड़ इत्यादि जैसे संचालन के साथ खेल सकते हैं ताकि यह देखने के लिए कि वे आपकी समस्या के लिए कितने कुशल हैं। ओपन सोर्स regexp-> nfa-> dfa compilers (मुझे एक पर्ल मॉड्यूल याद है) पहले से मौजूद है; OpenFST automata फ़ाइलों को आउटपुट करने और चारों ओर खेलने के लिए एक को संशोधित करें।
सौभाग्य से, यह सबसेट के- राज्यों विस्फोट से बचने, और दो NFA एक दूसरे को काटना करने के लिए सीधे DFA के लिए के रूप में ही निर्माण का उपयोग संभव है:
अगर A ->a B (एक NFA में, आप राज्य एक से बी करने के लिए जा सकते हैं चौराहे
(C,Z) में पत्र 'एक')
और X ->a Y (अन्य NFA में)
तो (A,X) ->a (B,Y) outputting अंतिम iff सी है एक एनएफए में अंतिम है और जेड दूसरे में अंतिम है।
प्रक्रिया शुरू करने के लिए, आप दो एनएफए के लिए प्रारंभिक राज्यों की जोड़ी शुरू करते हैं उदा। (A,X) - यह चौराहे-एनएफए की प्रारंभिक स्थिति है। प्रत्येक बार जब आप पहली बार किसी राज्य की यात्रा करते हैं, तो दो राज्यों को छोड़कर आर्क की प्रत्येक जोड़ी के लिए उपर्युक्त नियम द्वारा एक चाप उत्पन्न करें, और फिर उन सभी (नए) राज्यों पर जाएं जो उन आर्कों तक पहुंचते हैं। आप इस तथ्य को स्टोर करेंगे कि आपने एक राज्य के आर्कों का विस्तार किया है (उदा।एक हैश तालिका में) और शुरुआत से ही पहुंचने वाले सभी राज्यों की खोज समाप्त हो जाती है।
यदि आप अनुमति देते हैं एप्सिलॉन संक्रमण (कि उत्पादन एक पत्र नहीं करते हैं), यह ठीक है:
अगर पहले NFA में A ->epsilon B, तो हर राज्य (A,Y) आप तक पहुँचने के लिए, चाप (A,Y) ->epsilon (B,Y) में epsilons के लिए जोड़ सकते हैं और इसी तरह दूसरी स्थिति एनएफए।
एनएफए में रेगेक्सपी का अनुवाद करते समय दो एनएफए के संघ को लेने में ईपीएसलॉन संक्रमण उपयोगी (लेकिन आवश्यक नहीं) होते हैं; जब भी आपके पास regexp1|regexp2|regexp3 विकल्प होता है, तो आप संघ लेते हैं: एक एनएफए जिसका प्रारंभिक राज्य प्रत्येक एनएफए में एक ईपीएसलॉन संक्रमण होता है जो वैकल्पिक रूप से रेगेक्सप्स का प्रतिनिधित्व करता है।
एनएफए के लिए खालीपन का निर्णय करना आसान है: यदि आप कभी भी प्रारंभिक स्थिति से गहराई से पहली खोज करने में अंतिम स्थिति तक पहुंचते हैं, तो यह खाली नहीं है।
यह एनएफए-चौराहे परिमित राज्य ट्रांसड्यूसर संरचना के समान है (एक ट्रांसड्यूसर एक एनएफए है जो प्रतीकों के जोड़े को आउटपुट करता है, जो एक इनपुट और आउटपुट स्ट्रिंग दोनों से मेल खाने के लिए जोड़ीदार जोड़ों को जोड़ता है, या आउटपुट में दिए गए इनपुट को बदलने के लिए) ।
उत्कृष्ट उत्तर, हालांकि यह काफी सटीक है कि मैं खुद को कोड करने की आवश्यकता से बचने की उम्मीद कर रहा था;) ओपनएफएसटी हालांकि काफी साफ दिखता है। –
सिद्धांत रूप में, आपके द्वारा वर्णित समस्या असंभव है।
प्रैक्टिस में, यदि आपके पास नियमित रूप से अभिव्यक्तियों की एक प्रबंधित संख्या है जो सीमित सबसेट या रीगेक्सपी सिंटैक्स का उपयोग करती है, और/या नियमित अभिव्यक्ति के कंटेनर के खिलाफ मिलान करने के लिए उपयोग किए जा सकने वाले तारों का सीमित चयन हो सकता है, तो हो सकता है कि आप हो इसे हल करने में सक्षम।
मान लीजिए कि आप अमूर्त सामान्य मामले को हल करने की कोशिश नहीं कर रहे हैं, तो व्यावहारिक अनुप्रयोग को हल करने के लिए आप कुछ कर सकते हैं। शायद अगर आपने रेगेक्सप्स का एक प्रतिनिधि नमूना प्रदान किया है, और उन स्ट्रिंग्स का वर्णन किया है जिनके साथ आप मेल खाते हैं, समस्या को हल करने के लिए एक ह्युरिस्टिक बनाया जा सकता है।
"regexps" जो संदर्भ-मुक्त या बदतर भाषाओं को पहचानते हैं, यह साबित करना असंभव बनाता है कि चौराहे में कोई स्ट्रिंग नहीं है। जाहिर है ये वास्तव में "नियमित अभिव्यक्ति" नहीं हैं बल्कि कुछ प्रेरित हैं। लेकिन पूर्ण नियमित अभिव्यक्ति भाषा को डब्ल्यू/एनएफए पर कब्जा कर लिया जा सकता है, और अधिकांश लोग वास्तव में "regexp" से उपयोग करते हैं। –
मैं मानता हूं कि रेगेक्स को एनएफए में विघटित किया जा सकता है, मैं बस यह सोच रहा हूं कि मूल पोस्टर का एक और विशिष्ट उपयोग केस है, जैसे कि "सी [एईओयू] टी" और "डी [एईओयू] जी" जैसे रेगेक्स, और स्वीकार्य तार एक अंग्रेजी शब्दकोश हैं। – ironchefpython
This regex inverter (पाइपर्सिंग का उपयोग करके लिखा गया) री सिंटैक्स के सीमित सबसेट (उदाहरण के लिए, * या + स्वीकृत) के साथ काम करता है - आप दो रे को दो सेट में घुमा सकते हैं, और उसके बाद एक सेट चौराहे की तलाश कर सकते हैं।
इस प्रश्न को हल करने के प्रयोजनों के लिए, नियमित अभिव्यक्ति से आपका क्या मतलब है, यह जानना महत्वपूर्ण हो सकता है। क्या आप किसी विशेष प्रोग्रामिंग भाषा द्वारा उपयोग किए गए रेगेक्सपी सिंटैक्स के बारे में बात कर रहे हैं? या फिर केवल "सच्चाई" नियमित अभिव्यक्ति केवल concatenation, alternation, और क्लेन स्टार का उपयोग कर? – PeterAllenWebb
मुझे सबसे शक्तिशाली नियमित अभिव्यक्ति प्रकार जानने के लिए दिलचस्पी होगी जिसके लिए यह संभव है। –
हाय जोसेफ, मैं वास्तव में इस समस्या से संबंधित पीएचडी थीसिस पर काम कर रहा हूं। मैं सोच रहा था कि क्या आप संभवतः विस्तार से बता सकते हैं कि आप किस आवेदन का पीछा कर रहे थे। यदि आवश्यकता हो, तो हम ईमेल के माध्यम से आगे चर्चा कर सकते हैं: mwarar at buffalo dot edu। –