एक कुशलता से किसी भी नियमित अभिव्यक्ति के खिलाफ एक इनपुट स्ट्रिंग से मेल खाता है?एक बार में कई नियमित अभिव्यक्तियों के खिलाफ इनपुट स्ट्रिंग को कुशलता से कैसे मिलान करें?
एक परिदृश्य जहां यह उपयोगी हो सकता है आरईएसटी वेब सेवाओं के साथ है।
/user/with-id/{userId}/user/with-id/{userId}/profile/user/with-id/{userId}/preferences- : मान लेते हैं कि मैं एक बाकी वेब सेवा के सार्वजनिक इंटरफेस के लिए URL प्रतिमानों की संख्या के साथ आए हैं चलो
/users /users/who-signed-up-on/{date}/users/who-signed-up-between/{fromDate}/and/{toDate}- ...
जहां {…} (नियमित अभिव्यक्ति पर कब्जा समूह) के प्लेसहोल्डर नाम हैं।
ध्यान दें: यह सवाल इसके बाद के संस्करण REST इंटरफ़ेस अच्छी तरह से डिजाइन है या नहीं के बारे में नहीं है। (यह शायद नहीं है, लेकिन है कि इस सवाल का के संदर्भ में कोई फर्क नहीं करना चाहिए।)
यह माना जा सकता है कि प्लेसहोल्डर आम तौर पर एक पैटर्न के बहुत शुरुआत में दिखाई नहीं है (लेकिन वे कर सकते थे)। इसे सुरक्षित रूप से माना जा सकता है कि किसी भी स्ट्रिंग के लिए एक से अधिक पैटर्न से मिलान करना असंभव है।
अब वेब सेवा को एक अनुरोध प्राप्त होता है। बेशक, कोई अनुक्रमिक रूप से अनुरोधित यूआरआई से एक यूआरएल पैटर्न के खिलाफ मिलान कर सकता है, फिर अगले के खिलाफ, और इसी तरह; लेकिन संभवतः उन बड़ी संख्या में पैटर्न के लिए अच्छी तरह से स्केल नहीं किया जाएगा जिन्हें जांचना चाहिए।
क्या इसके लिए कोई कुशल एल्गोरिदम हैं?
इनपुट:
- एक इनपुट स्ट्रिंग
- "परस्पर अनन्य" नियमित अभिव्यक्ति (यानी कोई इनपुट स्ट्रिंग एक से अधिक एक्सप्रेशन से मेल कर सकते हैं।)
आउटपुट का एक सेट :
- नियमित अभिव्यक्ति (यदि कोई है) कि इनपुट स्ट्रिंग के खिलाफ मिलान किया गया है।
क्या किसी भी मौके से इसका सी ++ कार्यान्वयन है? – nurettin
http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm में कुछ कार्यान्वयन के लिंक हैं। मुझे याद है http://sourceforge.net/projects/snort/ को सी में कहीं भी कार्यान्वित किया गया था, लेकिन यह कई साल पहले था, मैं गलत हो सकता था। –
मुझे पता चला कि Google की री 2 लाइब्रेरी अहो-कोरासिक एल्गोरिदम – nurettin