50
स्ट्रिंग लम्बाई के संबंध में जटिलता क्या है जो स्ट्रिंग पर नियमित अभिव्यक्ति तुलना करने के लिए होती है?नियमित अभिव्यक्ति की जटिलता क्या है?
A
उत्तर
41
उत्तर "नियमित अभिव्यक्तियों" से आपका क्या मतलब है इस पर निर्भर करता है। क्लासिक रेगेक्स compiledDeterministic Finite Automata में हो सकता है जो O(N) समय में लंबाई N की एक स्ट्रिंग से मेल खा सकता है। रेगेक्स भाषा में कुछ एक्सटेंशन बदतर के लिए बदलते हैं।
आपको निम्न रुचि का दस्तावेज़ मिल सकता है: Regular Expression Matching Can Be Simple And Fast।
+5
मुझे वह लेख पसंद है। – tchrist
+0
मुझे नहीं लगता कि उस आलेख के लिए उपयोग किए गए परीक्षण डेटा को प्राप्त करना संभव होगा? मेरा काम स्थान हर समय perl regex का उपयोग करता है। क्या वे वास्तव में धीमे थे, हमारे हार्डवेयर पूरी तरह विफल हो जाएंगे। – DeepDeadpool
7
असंबद्ध - आप एक नियमित अभिव्यक्ति बना सकते हैं जो खाली इनपुट स्ट्रिंग पर कभी समाप्त नहीं होता है।
+0
जिज्ञासा से बाहर, क्या आप एलेक्स उदाहरण दे सकते हैं? –
+4
आदमी perlre देखें - "'foo' = ~ m {(o?) *} X;"। पर्ल के पास इस मामले में अनंत रिकर्सन का पता लगाने और ब्रेक आउट करने के लिए विशेष कोड है। –
5
यदि आप सामान्य (टीसीएस: कोई बैक्रेफरेंस, कॉन्सटेनेशन, ऑक्लेशनेशन, क्लेन स्टार) का उपयोग करते हैं तो regexp और regexp पहले ही संकलित है तो यह ओ (एन) है।
1
यदि आप RegEx (अभिव्यक्ति के संबंध में बिना) पर तंग एसिम्प्टोटिक सीमाओं की तलाश में हैं, तो कोई नहीं है। जैसा कि एलेक्स बताता है, आप एक रेगेक्स बना सकते हैं जो ओ (1) या रेगेक्स है जो ओमेगा (अनंतता) है। पूरी तरह से गणितीय एल्गोरिदम के रूप में, एक नियमित अभिव्यक्ति इंजन औपचारिक एसिम्प्टोटिक विश्लेषण करने के लिए बहुत जटिल होगा (इस तथ्य से कि इस तरह का विश्लेषण मूल रूप से बेकार होगा)।
किसी विशेष अभिव्यक्ति की वृद्धि दर (तब से, वास्तव में, एक एल्गोरिदम का गठन करती है, वैसे भी) अधिक अर्थपूर्ण होगी, हालांकि विश्लेषण करने के लिए जरूरी नहीं है।
+0
वह औपचारिक नियमित अभिव्यक्तियों के विस्तार पर विचार कर रहा है। सामान्य संरचनाओं (उदाहरण के लिए कोई आगे/पीछे पैटर्न) शामिल नियमित अभिव्यक्तियों को ओ (इनपुट स्ट्रिंग की लंबाई) समय में किसी भी इनपुट पर हमेशा समाप्त होने के लिए सिद्ध किया जा सकता है। –
+0
@clement यहां तक कि अधिकांश एक्सटेंशन आरई को डीएफए से परे नहीं दबाते हैं। उदाहरण के लिए, पायथन रेगेक्स को हमेशा डीएफए द्वारा मॉडलिंग किया जा सकता है। हालांकि, जैसे ही आप पर्ल रेगेक्स के साथ काम करना शुरू करते हैं (और मैं जावास्क्रिप्ट पर विश्वास करता हूं?) यह एक अलग जानवर बन जाता है जो इसके बजाय एक टीएम के बराबर होता है। – BlackVegetable
संबंधित मुद्दे
- 1. उपसर्ग नियमित अभिव्यक्ति क्या है?
- 2. OrderedDictionary की जटिलता क्या है?
- 3. नियमित अभिव्यक्ति "शामिल है" एक और नियमित अभिव्यक्ति
- 4. नियमित अभिव्यक्ति (? <! -) का अर्थ क्या है
- 5. नियमित अभिव्यक्ति?
- 6. नियमित अभिव्यक्ति \\ s *, \\ s * क्या करती है?
- 7. नियमित अभिव्यक्ति में '?: `का अर्थ क्या है
- 8. नियमित अभिव्यक्ति
- 9. नींद की तरह की जटिलता क्या है?
- 10. क्या सभी नियमित अभिव्यक्ति रोकें?
- 11. नियमित अभिव्यक्ति?
- 12. नियमित अभिव्यक्ति
- 13. नियमित अभिव्यक्ति
- 14. नियमित अभिव्यक्ति
- 15. नियमित अभिव्यक्ति
- 16. नियमित अभिव्यक्ति
- 17. नियमित अभिव्यक्ति?
- 18. नियमित अभिव्यक्ति
- 19. नियमित अभिव्यक्ति
- 20. नियमित अभिव्यक्ति
- 21. क्या करता है \ डी पर्ल नियमित अभिव्यक्ति
- 22. यह नियमित अभिव्यक्ति भाग क्या जोड़ता है?
- 23. रेगेक्स/"नियमित अभिव्यक्ति" में नियमित रूप से क्या मतलब है?
- 24. अच्छे नियमित अभिव्यक्ति क्या हैं?
- 25. नियमित अभिव्यक्ति
- 26. नियमित अभिव्यक्ति:
- 27. नियमित अभिव्यक्ति
- 28. क्या वेक्टर की जटिलता :: स्पष्ट अनिर्दिष्ट है?
- 29. ग्रुपबी ऑपरेशन की एसिम्प्टोटिक जटिलता क्या है?
- 30. लॉग फ़ंक्शन की जटिलता क्या है?
जटिलता स्ट्रिंग की लंबाई की तुलना में रेगेक्स की प्रकृति पर अधिक निर्भर करती है। – LukeH
@LukeH वैकल्पिक रूप से, यह प्रयुक्त प्रोग्रामिंग भाषा पर निर्भर करता है। उदाहरण के लिए, पायथन रेगेक्स कभी भी डीएफए की कंप्यूटर पावर से अधिक नहीं हो सकता है, लेकिन पर्ल रेगेक्स ट्यूरिंग पूर्ण हो सकता है। – BlackVegetable
[रेगेक्स प्रतिस्थापन की जटिलता] के संभावित डुप्लिकेट (http://stackoverflow.com/questions/21669/complexity-of-regex-substitution) – Kevin