मैच नियमित अभिव्यक्ति

Question

मैं, नियमित अभिव्यक्ति का एक टन धारण करने के लिए के रूप में कुंजी, तो मैं पाठ की एक स्ट्रिंग लेने की जरूरत डेटा ऑब्जेक्ट के कुछ प्रकार (मैं एक शब्दकोश में सोच रहा हूँ) के लिए कोशिश कर रहा हूँ और शब्दकोश से वास्तविक मूल्य प्राप्त करने के लिए उनके खिलाफ मैच। मुझे डेटा के बड़े सेट के लिए ऐसा करने का एक प्रभावी तरीका चाहिए।

मैं सी # में हूं और मुझे यकीन नहीं है कि कहां से शुरू किया जाए।

Answer 1

LINQ का उपयोग क्यों नहीं करें?

Dictionary<string, string> myCollection = new Dictionary<string, string>(); 

myCollection.Add("(.*)orange(.*)", "Oranges are a fruit."); 
myCollection.Add("(.*)apple(.*)", "Apples have pips."); 
myCollection.Add("(.*)dog(.*)", "Dogs are mammals."); 
// ... 

string input = "tell me about apples and oranges"; 

var results = from result in myCollection 
       where Regex.Match(input, result.Key, RegexOptions.Singleline).Success 
       select result; 

foreach (var result in results) 
{ 
    Console.WriteLine(result.Value); 
} 

// OUTPUT: 
// 
// Oranges are a fruit. 
// Apples have pips. 

Answer 2

मुझे यकीन है कि अगर आप वास्तव में इस के लिए नियमित अभिव्यक्ति की जरूरत नहीं कर रहा हूँ - यदि आप एक trie इस्तेमाल कर सकते हैं। शब्दकोशों का प्रतिनिधित्व करना एक trie के लिए एक आम आवेदन है। (मुझे लगता है कि आप शब्दों की सूची में एक शब्दकोश का मतलब है, न कि "सहयोगी सरणी" अर्थ)।

Answer 3

आप regexes के खिलाफ एक स्ट्रिंग एक regex मैच पाने के लिए मेल खाते हैं मतलब है? या सिर्फ एक पाठ मैच? दूसरे शब्दों में, क्या वह स्ट्रिंग है जिसे आप उन रेगेक्स में से एक बनने जा रहे हैं, या कुछ डेटा को रेगेक्स लागू करने के लिए?

यह एक regex है और आप सूची में प्राप्त करना चाहते हैं, तो आप एक शब्दकोश की जरूरत नहीं है, उन 2 हिस्सा कंटेनर हैं। आप केवल एक सूची या स्ट्रिंग कोलेक्शन का उपयोग कर सकते हैं, और इंडेक्सऑफ (mytString), -1 के लिए पूछ सकते हैं जिसका अर्थ है कि यह वहां नहीं है।

Answer 4

अपने regexps तुच्छ एकल तार नहीं कर रहे हैं, और आप दक्षता के लिए देखभाल हैं, तो आप अंतिम राज्यों में मूल्यों के साथ, एक भी NFA (nondeterministic finite-state automaton में उन्हें प्रतिनिधित्व करना चाहते हैं। यदि एक से अधिक regexp से मेल खाने के लिए इनपुट के लिए संभव है, तो अंतिम राज्यों को मूल्यों के एक सेट की आवश्यकता होगी।

इस बिंदु पर, आप automaton अनुकूलित करने पर विचार करने के लिए तैयार कर रहे हैं। यदि इसे व्यावहारिक रूप से निर्धारित किया जा सकता है (यह आपको एक डीएफए देता है जो एनएफए की तुलना में तेजी से बड़ा हो सकता है), तो हर तरह से ऐसा करें। एक बार आपके पास एक डीएफए हो, तो आप कुशलतापूर्वक (और विशिष्ट रूप से आइसोमोर्फिज्म तक) इसे कम कर सकते हैं (लेकिन चूंकि आपके पास अपने अंतिम राज्यों में मूल्य हैं, usual algorithm का एक स्पष्ट संशोधन आवश्यक है)।

एनएफए को कम करने के लिए तकनीक भी हैं। उदाहरण के लिए, यदि दो राज्यों में एक ही प्रत्यय सेट हैं ({(स्ट्रिंग, मान का बाकी)}) वे बराबर हैं और संयुक्त किए जा सकते हैं। एक विश्वकोश एनएफए में समानता अंतिम राज्यों से शुरू होने वाले hash-consing के माध्यम से की जा सकती है।

Answer 5

याद रखें कि यदि आप रेगेक्स का उपयोग करने की योजना बना रहे हैं तो एक बार आप रेगेक्स ऑब्जेक्ट को संकलित के रूप में बना सकते हैं और ओवरहेड को कम करने के लिए इसका पुनः उपयोग कर सकते हैं।

Regex RegexObject = new Regex(Pattern, RegexOptions.Compiled); 

इस मॉडल आप सबसे अच्छा होगा पैटर्न स्ट्रिंग एक regex वस्तु के बजाय भंडारण का उपयोग करना।