9
क्या हम नियमित अभिव्यक्तियों के बीच एक प्रकार की दूरी की गणना कर सकते हैं?नियमित अभिव्यक्ति के बीच दूरी
विचार यह है कि किस तरह से दो नियमित अभिव्यक्ति समान होती है।
A
उत्तर
5
मैट्रिक्स के कुछ ही आप इस्तेमाल कर सकते हैं कर रहे हैं:
एक वैध मैच की लंबाई। कुछ regexs एक निश्चित आकार है, कुछ ऊपरी सीमा और कुछ निचली सीमा है। तुलना करें कि उनकी लंबाई या संभावित लंबाई कितनी समान है।
मिलान करने वाले वर्ण। किसी भी रेगेक्स में वर्णों का एक सेट होगा जिसमें एक मैच हो सकता है (शायद सभी वर्ण)। शामिल वर्णों के सेट की तुलना करें।
एक बड़े दस्तावेज़ का उपयोग करें और देखें कि प्रत्येक रेगेक्स कितने मेल खाता है और उनमें से कितने समान हैं।
क्या आप सख्त समकक्ष की तलाश में हैं?
+1
+1: मैं वर्तमान उत्तर-वोट के लिए यह उत्तर पसंद करता हूं क्योंकि आपने कंक्रीट सुझावों की एक बहुत ही व्यावहारिक सूची बनाई है जो आसानी से लागू हो सकती हैं। –
1
मुझे लगता है कि आपको पहले खुद को समझने की आवश्यकता है कि आप दो अभिव्यक्तियों के बीच "अंतर" कैसे देखते हैं। असल में, एक दूरी मीट्रिक परिभाषित करें।
सामान्य स्थिति में, यह बनाने के लिए काफी अलग होगा। आपको जो करने की ज़रूरत है उसके आधार पर, आप किसी भिन्न स्थान को किसी भिन्न स्थान के रूप में एक अलग अंतर की अनुमति दे सकते हैं। दूसरे मामले में, किसी भी संख्या के परिणामस्वरूप अनुमति देने की अनुमति देने से बहुत अंतर नहीं मिल सकता है।
मैं सामान्य रूप से जोर देना चाहूंगा कि आम तौर पर जब वे दूरी कार्यों के बारे में बात करते हैं, तो वे उन्हें लागू करते हैं ..., ठीक है, चलो उन्हें कॉल करें, टोकन। हमारे मामले में, चरित्र अनुक्रम। आप जो करना चाहते हैं, वह इस विधि को उन टोकनों पर लागू नहीं करना है, लेकिन नियमों के लिए टोकन की भीड़ मिल जाएगी। मुझे पूरा यकीन नहीं है कि यह भी समझ में आता है।
फिर भी, मुझे विश्वास है कि हम कुछ के बारे में सोच सकते हैं, लेकिन आम तौर पर नहीं, बल्कि एक विशेष और काफी प्रतिबंधित मामले के लिए। क्या आपको दिखाने के लिए आपके पास कुछ प्रकार का उदाहरण है?
5
आप नियमित अभिव्यक्तियों और संक्रमणों की तुलना करने के लिए deterministic finite-state machines बना सकते हैं। इन संक्रमणों की दूरी को मापने के लिए दोनों संक्रमणों का अंतर तब उपयोग किया जा सकता है।
+0
शायद एक कदम आगे बढ़ें, राज्य मशीन को ग्राफ प्रतिनिधित्व में परिवर्तित करें और आइसोमोर्फिज्म की तलाश करें? –
+0
आप इस विधि का उपयोग करते हुए दो उचित समान नियमित अभिव्यक्तियों '\ w + \ d +' और '[a-zA-Z] {1,63} [1-9] [0-9] {, 3}' की तुलना कैसे करेंगे? आप कैसे बता सकते हैं कि अलग-अलग एफएसएम में दो राज्य "समकक्ष" या "समान" हैं? –
+0
@ नोफल इब्राहिम: हाँ, मुझे वास्तव में ऐसा कुछ मतलब था। एल्गोरिदम भी हैं जो बता सकते हैं कि दो परिमित-राज्य मशीन समकक्ष हैं या नहीं। – Gumbo
2
यदि आपके पास दो नियमित अभिव्यक्तियां हैं और उदाहरण इनपुट का एक सेट है तो आप प्रत्येक रेगेक्स के खिलाफ प्रत्येक इनपुट से मिलान करने का प्रयास कर सकते हैं। प्रत्येक इनपुट के लिए:
- अगर वे दोनों मैच या दोनों से मेल नहीं खाते, 0.
- एक तो मैचों स्कोर और अन्य नहीं, अधिक स्कोर 1.
योग इस स्कोर करता है सभी इनपुट, और यह आपको नियमित अभिव्यक्तियों के बीच 'दूरी' देगा। यह आपको एक विचार देगा कि सामान्य इनपुट के लिए कितनी बार दो नियमित अभिव्यक्ति अलग-अलग होंगी। यदि आपका नमूना इनपुट सेट बड़ा है तो गणना करना बहुत धीमा होगा। यह बिल्कुल काम नहीं करेगा अगर दोनों regexes लगभग सभी यादृच्छिक तारों के लिए मिलान करने में विफल रहता है और आपका अपेक्षित इनपुट पूरी तरह से यादृच्छिक है। उदाहरण के लिए रेगेक्स 'sgjlkwren' और regex 'ueuenwbkaalf' शायद यादृच्छिक इनपुट पर परीक्षण किए जाने पर कभी भी कुछ भी मेल नहीं खाएगा, इसलिए यह मीट्रिक कहता है कि उनके बीच की दूरी शून्य है। वह हो सकता है जो आप चाहते हैं (शायद नहीं)।
आप रेगेक्स की संरचना का विश्लेषण करने में सक्षम हो सकते हैं और जानबूझकर स्ट्रिंग्स को हिट करने के लिए पक्षपातपूर्ण यादृच्छिक नमूनाकरण का उपयोग कर सकते हैं जो पूरी तरह से यादृच्छिक इनपुट की तुलना में अधिक बार मेल खाता है। उदाहरण के लिए, यदि दोनों रेगेक्स की आवश्यकता होती है कि स्ट्रिंग 'foo' से शुरू होती है, तो आप यह सुनिश्चित कर सकते हैं कि आपके परीक्षण इनपुट हमेशा फू के साथ शुरू होते हैं, ताकि समय परीक्षण तारों को बर्बाद करने से बचने के लिए आप दोनों के लिए असफल हो जाएंगे।
तो निष्कर्ष में: जब तक आपके पास सीमित इनपुट सेट और/या प्रतिबंधित नियमित अभिव्यक्ति भाषा के साथ एक बहुत ही विशिष्ट स्थिति न हो, तो मैं कहूंगा कि यह संभव नहीं है। यदि आपके इनपुट पर और नियमित अभिव्यक्ति पर आपके कुछ प्रतिबंध हैं, तो यह संभव हो सकता है। कृपया निर्दिष्ट करें कि ये प्रतिबंध क्या हैं और शायद मैं कुछ बेहतर तरीके से आ सकता हूं।
2
मुझे लगता है कि आप वास्तविक नियमित एक्सपर्सियन स्ट्रिंग के बीच Levenshtein Distance की गणना कर सकते हैं। यह निश्चित रूप से दो अलग-अलग नियमित अभिव्यक्ति तारों के बीच "दूरी" को मापने का एक तरीका है।
बेशक, मुझे लगता है कि यह संभव है कि नियमित अभिव्यक्तियों की आवश्यकता यहां नहीं है, और वास्तविक "मूल्य" तारों की लेवेनशेटिन दूरी की गणना करना जो नियमित अभिव्यक्तियों को अन्यथा लागू किया जाएगा, बेहतर परिणाम प्राप्त कर सकते हैं।
+1
ध्यान दें कि नियमित अभिव्यक्तियों के लिए दूरी माप तारों के लिए दूरी माप के बाद पूरी तरह से अलग है। जैसे 'दूरी (regex (" a | b "), regex (" b | a ")' परिभाषा 0 है। और कुछ बदलाव दूसरों की तुलना में अधिक महत्वपूर्ण हैं। 'abcde' 'bacde' के समान हो सकता है, केवल दो अक्षर swapped लेकिन '^ [0-9]' पूरी तरह से '[^ 0-9]' के विपरीत है – MSalters
1
SO: Generating strings from regexes पर पहले के प्रश्न में छिपा एक उत्तर है। आप एक रेगेक्स का उपयोग करके स्ट्रिंग्स उत्पन्न करके और अन्य रेगेक्स से मेल खाने वाले लोगों की जांच करके एक (असममित) दूरी माप की गणना कर सकते हैं।
इसे साझा उपसर्ग/प्रत्यय को अलग करके अनुकूलित किया जा सकता है। जैसे a[0-9]* और a[0-7]*a उपसर्ग साझा करें, ताकि आप [0-9]* और [0-7]* के बीच की दूरी की गणना कर सकें।
आप क्या करने की कोशिश कर रहे हैं? – ghostdog74
और आप उस दूरी को कैसे मापेंगे? – Gumbo
@ गम्बो: मुझे लगता है कि यह सवाल का हिस्सा है। –