2012-08-23 19 views
15

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

कुछ अजगर प्रोग्रामिंग मैंने देखा है कि निम्न आदेश करते समय:

re.sub("a*((ab)*)b", r"\1", "aabb") 

रिटर्न रिक्त स्ट्रिंग। लेकिन sed में एक समकक्ष कमांड:

echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/" 

ab देता है।

यह मुझे समझ में आता है कि पायथन रेगेक्स की शुरुआत में "ए *" निर्देश a दोनों से मेल खाता है, जिससे "(एबी) *" शून्य बार मेल खाता है, लेकिन मुझे नहीं पता कि कैसे sed आता है ab के साथ। क्या किसी को पता है कि दो रेगेक्स इंजनों के बीच अंतर क्या है? मेरा मानना ​​है कि वे दोनों डिफ़ॉल्ट रूप से लालच से सितारों से मेल खाते हैं, लेकिन यह मेरे लिए हुआ कि sed बाईं ओर दाईं ओर से मिल सकता है। किसी भी जानकारी की काफी सराहना की जाएगी।

+0

कहीं मैंने पढ़ा "sed/awk एक DFA का उपयोग करें" और "अजगर/पर्ल/जावा एक NFA का उपयोग करें"। यह alternations (backtracking?) के साथ semantics बदलता है .. क्या यह संबंधित हो सकता है? –

+1

@pst: शायद मैं आपको गलत समझ रहा हूं, लेकिन ऐसा लगता है कि किसी भी बैकट्रैकिंग-आधारित दृष्टिकोण डीएफए का उपयोग करेगा; एनएफए का उपयोग करने का प्रभाव बैकट्रैकिंग की आवश्यकता को खत्म करना होगा, क्योंकि सभी शाखाओं की एक साथ जांच की जाती है। तो, मैं पर्ल/पायथन/जावा/आदि की अपेक्षा करता हूं। एक डीएफए का उपयोग करने के लिए। क्या यह संभव है कि आपने जो लिखा है उसके विपरीत आप पढ़ लें: शायद आप पढ़ सकते हैं कि एक एनएफए और पर्ल/पायथन/जावा इत्यादि का उपयोग करते हुए एक डीएफए का उपयोग करें? – ruakh

+1

@pst: और यह * देखे गए व्यवहार को समझाएगा, अगर sed/awk एक एनएफए का उपयोग करें, और उसके बाद चयन करें कि मिलान के किसी भी तरीके से सबसे लंबा मैच दिया गया है। इस मामले में, '\ (\ (ab \) * \)' match 'ab' एक लंबा समग्र मिलान, 'अब्बा' उत्पन्न करता है, उसके बाद यह खाली स्ट्रिंग से मेल खाता है, क्योंकि बाद वाला मतलब यह होगा कि पूरी तरह से रेगेक्स केवल 'एएबी' से मेल खाएगा। – ruakh

उत्तर

2

आपके द्वारा बनाई गई दिलचस्प पहेली। मैंने जो पढ़ा है, उससे दोनों पायथन और sed के regexp इंजन हेनरी स्पेंसर की रेगेक्स लाइब्रेरी (जैसा कि पर्ल है) पर आधारित हैं, जो बैकट्रैकिंग पर निर्भर करता है।(दुर्भाग्यवश मुझे वह लेख नहीं मिल रहा है जिसे मैं इस पर आधारित कर रहा हूं)। अजगर के व्यवहार POSIX मानक है, जो जल्द से जल्द संभव बिंदु पर करने के लिए (क) मैच आर ई की आवश्यकता के खिलाफ जाता है, और (ख) सबसे लंबे समय तक संभव से मेल खाते हैं:

वैसे भी, इस नहीं कुछ है कि एक कार्यान्वयन विस्तार होना चाहिए है स्ट्रिंग जो उस बिंदु से शुरू होती है। (man 7 regex (लिनक्स पर) और इसके लिए बहुत कुछ देखें।)

सबसे लंबा मैच खोजने के लिए, बैकट्रैकिंग ("एनएफए-टाइप") रेगेक्स इंजन को एक मैच मिलने के बाद विकल्पों की जांच जारी रखना चाहिए। तो यह आश्चर्य की बात नहीं है कि कार्यान्वयन करने वालों ने कोनों को काट दिया। जाहिर है, पाइथन का व्यवहार गैर-अनुरूप है क्योंकि यह सबसे लंबा मैच खोजने में विफल रहता है। Sed मैनुअल पेज के अनुसार, sed हमेशा "प्रदर्शन कारणों के लिए" अनुरूप नहीं है। लेकिन जाहिर है यह इस मामले को सही हो जाता है।

संयोग से, अपने आदेश पूरी तरह से समान नहीं होते हैं: re.sub संभव के रूप में रूप में कई बार एक प्रतिस्थापन प्रदर्शन करेंगे, जबकि sed के s/a/b/ केवल प्रदर्शन करेंगे यह once.The sed संस्करण किया जाना चाहिए था:

echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/g" 

यही कारण है कि बताते हैं हमें पायथन में खाली स्ट्रिंग मिलती है: आरई aab पहली बार और शेष b दूसरी बार हटा देता है, क्योंकि प्रत्येक भाग को हटाकर a* और रेगेक्सपी के अंतिम b से मेल खाता है)। आप नीचे दिए गए संस्करण से यह देख सकते हैं:

>>> re.sub("a*((ab)*)b", r"X\1Y", "aabb") 
'XYXY' 
+0

पर्ल इस मामले में पायथन के समान ही है: '$ perl -E '$ _ =" aabb "; एस/ए * ((एबी) *) बी/<\1>/जी; प्रिंट $ _, "\ n"; 'परिणाम' <><> 'btw। गैर लालची '... एस/ए *? ... परिणाम' '। – hynekcer

+0

तो क्या? सादा तीन * इंजनों में लालची है। यह एक संयोग है कि गैर-लालची संस्करण इस मामले में एक ही परिणाम देता है। – alexis

+0

कूल।एफडब्ल्यूआईडब्ल्यू, एक बार मैच करने के लिए अजगर को बता रहा है, ताकि दोनों आदेश समकक्ष हों, ऐसा लगता है कि मिलान करने वाले समूह का उपयोग नहीं किया जाता है ('re.sub (" a * ((ab) *) b "," [\ 1] "," अब्ब ") ->" [] बी "'), लेकिन यह एक अच्छा मुद्दा है। – maths

4

दोनों अजगर और एसईडी डिफ़ॉल्ट लेकिन द्वारा लालची हैं ... अजगर regex, सभी परिस्थितियों में बाएं से दाएं मूल्यांकन करने के लिए कोशिश करता है के बावजूद यह अगर शाखा मुकदमा चल रहा जारी नहीं रख सकते पहले वाली स्थिति अंततः एक पश्व-अनुरेखन करना चाहिए मिलान करके। रेडिक्स को एक और निर्धारिती रूप में फिर से लिखकर, अनावश्यक बैकट्रैस को रोकने के लिए इसके विपरीत सेड रेगेक्स को अनुकूलित करने से पहले ऑप्टिमाइज़ किया गया है। इसलिए संयुक्त वैकल्पिक पैटर्न "एएबी" शायद सादा "ए" से पहले परीक्षण किया जाता है क्योंकि सबसे विशिष्ट संभव स्ट्रिंग पहले कोशिश की जाती है।

:

अजगर पैटर्न स्ट्रिंग "aabb" दो बार के रूप में "AAB" + "ख" ("< >" के बीच में चिह्नित)

>>> re.sub("a*((ab)*)b", r"<\1>", "aabb") 
'<><>' 

जबकि sed एक प्रतिस्थापन द्वारा पूरी "aabb" से मेल खाता से मेल खाता है

$ echo "aabb" | sed "s/a*\(\(ab\)*\)b/<\1>/" 
<ab> 

पायथन रेगेक्स बैकट्र्रेस एल्गोरिदम को regex howto - Repeating Things में "पैरा-दर-चरण उदाहरण ..." शब्दों द्वारा पेश किए गए दो अनुच्छेदों में अच्छा समझाया गया है। यह आईएमओ को वास्तव में regex docs का वर्णन करता है: "चूंकि लक्ष्य स्ट्रिंग स्कैन की जाती है, आरईएस '|' से अलग होती है। बाएं से दाएं से प्रयास किया जाता है। "

प्रदर्शन

के आदेश "(| एक | आ)" btw। "(आ | एक |)" अजगर

>>> re.sub("(?:|a|aa)((ab)*)b", r"<\1>", "aabb") 
'<ab>' 
>>> re.sub("(?:aa|a|)((ab)*)b", r"<\1>", "aabb") 
'<><>' 

द्वारा सम्मान किया जाता है, लेकिन इस क्रम क्योंकि sed नियमित अभिव्यक्ति का अनुकूलन sed द्वारा नजरअंदाज कर दिया है। मिलान "एएबी" + "बी" पैटर्न से "ए" विकल्प को पुन: उत्पन्न किया जा सकता है।

$ echo "aabb" | sed "s/\(\|a\|aa\)\(\(ab\)*\)b/<\2>/g" 
<ab> 
$ echo "aabb" | sed "s/\(aa\|a\|\)\(\(ab\)*\)b/<\2>/g" 
<ab> 
$ echo "aabb" | sed "s/\(aa\|\)\(\(ab\)*\)b/<\2>/g" 
<><> 

संपादित: मैं DFA/NFA के बारे में सब कुछ क्योंकि मैं इसे वर्तमान ग्रंथों से साबित नहीं कर सकते हटा दिया।

संबंधित मुद्दे