सबस्ट्रिंग मैच तेजी से?

Question

आरई/एनएफए और डीएफए पर पढ़ने के बाद, ऐसा लगता है कि स्ट्रिंग के भीतर एक सबस्ट्रिंग ढूंढना वास्तव में एक ब्रूट फोर्स ओ (एमएन) खोजने के बजाय आरई का उपयोग करके तेजी से तेजी से हो सकता है। मेरा तर्क यह है कि एक डीएफए वास्तव में राज्य बनाए रखेगा और एक बार से अधिक "घास के मैदान" में प्रत्येक चरित्र को संसाधित करने से बच जाएगा। इसलिए, नियमित अभिव्यक्तियों के साथ किए जाने पर लंबी तारों में खोज वास्तव में बहुत तेज हो सकती है।

बेशक, यह केवल आरई मैचर्स के लिए मान्य है जो एनएफए से डीएफए में परिवर्तित होते हैं।

क्या किसी ने ब्रूट फोर्स मैचर की बजाय आरई का उपयोग करते समय वास्तविक जीवन में बेहतर स्ट्रिंग मैच प्रदर्शन का अनुभव किया है?

Answer 1

सबसे पहले, मैं आपको कई भाषाओं में नियमित अभिव्यक्तियों के आंतरिक के बारे में लेख पढ़ने की सलाह दूंगा: Regular Expression Matching Can Be Simple And Fast।

क्योंकि कई भाषाओं में regexps सिर्फ मेल खाने के लिए नहीं हैं, बल्कि समूह-कैप्चरिंग और बैक-रेफरेंसिंग की संभावना भी प्रदान करते हैं, लगभग सभी कार्यान्वयन दिए गए रेगेक्सपी से बनाए गए एनएफए को निष्पादित करते समय "बैकट्रैकिंग" का उपयोग करते हैं। और इस कार्यान्वयन में घातीय समय जटिलता है (सबसे खराब मामले में)।

डीएफए (समूह कैप्चरिंग के साथ) के माध्यम से आरई कार्यान्वयन हो सकता है, लेकिन इसका ओवरहेड है (लॉरीकर का पेपर NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions देखें)।

सरल सबस्ट्रिंग खोज के लिए आप Knuth-Morris-Pratt एल्गोरिदम का उपयोग कर सकते हैं, जो सबस्ट्रिंग को खोजने के लिए डीएफए बनाते हैं, और इसमें ऑप्टिमाइम ओ (लेन) जटिलता है। लेकिन यह हैई ओवरहेड भी है, और यदि आप वास्तविक दुनिया के शब्दों और वाक्यांशों (जो कि दोहराए जाने वाले नहीं हैं) पर इस इष्टतम एल्गोरिदम के खिलाफ निष्पक्ष दृष्टिकोण (ओ (एनएम)) का परीक्षण करते हैं, तो आप पाते हैं कि निष्क्रिय दृष्टिकोण औसत में बेहतर है।

सटीक सबस्ट्रिंग खोज के लिए आप Boyer–Moore अल्गो भी कोशिश कर सकते हैं, जिसमें ओ (एमएन) सबसे खराब-मामला जटिलता है, लेकिन असली दुनिया डेटा पर औसतन केएमपी से बेहतर काम करता है।

Answer 2

यदि आप अधिकांश भाषाओं के लिए प्रलेखन देखते हैं तो यह उल्लेख करेगा कि यदि आपको रेगेक्स की शक्ति की आवश्यकता नहीं है तो आपको प्रदर्शन कारणों से गैर-रेगेक्स संस्करण का उपयोग करना चाहिए ... उदाहरण: http://www.php.net/manual/en/function.preg-split.php कहता है: "यदि आपको आवश्यकता नहीं है नियमित अभिव्यक्तियों की शक्ति, आप तेजी से (हालांकि सरल) विकल्प चुन सकते हैं जैसे विस्फोट() या str_split()। "

यह एक व्यापार बंद है जो हर जगह मौजूद है। यह अधिक लचीला और सुविधा युक्त समृद्ध है, इसका प्रदर्शन गरीब है।

Answer 3

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

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