सी #: अन्य तारों के अवसरों के लिए कुशलतापूर्वक एक बड़ी स्ट्रिंग को खोजें

Question

मैं बड़े स्ट्रिंग्स के भीतर लगातार कई स्ट्रिंग "कीवर्ड" की खोज करने के लिए सी # का उपयोग कर रहा हूं, जो> = 4kb हैं। यह कोड लगातार लूपिंग कर रहा है, और नींद उचित गति को बनाए रखने के दौरान पर्याप्त CPU उपयोग को कम नहीं कर रही है। बोग-डाउन कीवर्ड मिलान विधि है।

मुझे कुछ संभावनाएं मिली हैं, और वे सभी समान दक्षता देते हैं।

1) http://tomasp.net/articles/ahocorasick.aspx - मेरे पास सबसे कुशल एल्गोरिदम होने के लिए पर्याप्त कीवर्ड नहीं हैं।

2) रेगेक्स। एक आवृत्ति स्तर का उपयोग, संकलित regex। - मुझे आवश्यकतानुसार अधिक कार्यक्षमता प्रदान करता है, और पर्याप्त दक्षता नहीं है।

3) स्ट्रिंग.इंडेक्सऑफ। -मुझे इसके लिए "स्मार्ट" संस्करण करने की आवश्यकता होगी क्योंकि यह पर्याप्त दक्षता प्रदान करता है। प्रत्येक कीवर्ड के माध्यम से लूपिंग और इंडेक्सऑफ को कॉल करना इसे काट नहीं देता है।

क्या कोई भी मेरे एल्गोरिदम या विधियों के बारे में जानता है जिनका उपयोग मैं अपने लक्ष्य को प्राप्त करने के लिए कर सकता हूं?

Answer 1

क्या आप हमेशा एक ही कीवर्ड खोज रहे हैं? Boyer-Moore आज़माएं। इसके लिए कीवर्ड के लिए कुछ प्री-प्रोसेसिंग की आवश्यकता होती है, लेकिन बाद में गति प्राप्त होती है।

Answer 2

मैंने कोशिश नहीं की है, लेकिन क्या आपने Rabin-Karp पर देखा है? जाहिर है, यह एक बुरी स्थिति-मामला जटिलता है, लेकिन आमतौर पर काफी अच्छा होता है।

आपके कीवर्ड कैसा दिखते हैं? विशेष रूप से, क्या वे हमेशा रिक्त स्थान (या कुछ समान) द्वारा सीमित होते हैं? यदि ऐसा है, तो आप मूल रूप से "शब्दों" की तलाश में स्ट्रिंग को देख सकते हैं और फिर या तो उस शब्द के इंडेक्स की सूची में किसी शब्द से नक्शा बना सकते हैं, या शायद केवल उन कीवर्ड के लिए ऐसा करें जो आप रुचि रखते हैं।

यदि आप सटीक स्थिति (जैसे कि कीवर्ड, डिलीमीटर और आपको अपनी खोज के परिणाम की आवश्यकता होती है) के बारे में अधिक जानकारी दे सकती है जो इससे मददगार होंगी।

Answer 3

मैं इस सवाल के लिए indexOf के कुशल उपयोग विकसित:

A better way to replace many strings - obfuscation in C#

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

Answer 4

असल में मुझे इसे हल करना पड़ा, यह थोड़ी मजेदार थी। मेरे पास 20k एचटीएमएल पेज थे, प्रत्येक शीर्षक के साथ, और उस शीर्षक के साथ पृष्ठ से लिंक करने के लिए अन्य पृष्ठों पर शीर्षक की अन्य सभी घटनाएं चाहता था। आप जो करने की कोशिश कर रहे हैं उसके समान ही लगता है।

दृष्टिकोण:

1. प्रक्रिया यह {वर्ड, व्हाइटस्पेस} का एक लिंक्ड सूची जहां वचन में कुछ विशेष वर्ण के साथ एक सन्निहित अल्फा-न्यूमेरिक अनुक्रम के रूप में पहचान की गई थी में बदल कर एक फ़ाइल का पाठ, और व्हाइटस्पेस सबकुछ था जो अगले शब्द तक पहुंचा।
2. उन पृष्ठों के प्रत्येक 'शीर्षक' के लिए चरण 1 में प्रक्रिया को दोहराया जिन्हें मैं लिंक करना चाहता था।
3. चरण 1 में लिंक की गई सूची में नोड से प्रत्येक शब्द को बाइनरी-क्रमबद्ध सूची में जोड़ा गया था।
4. अब आपको केवल चरण 2 से प्रत्येक शीर्षक से जुड़ी सूची से पहला शब्द चलना होगा और चरण 3 से बाइनरी सॉर्टेड सूची में जाना होगा। जब आप शब्द बहुवचन करते हैं तो आपको कई हिट या यहां तक ​​कि मुलायम-हिट मिल सकती हैं ताकि आप शायद आपके पास परीक्षण करने की आवश्यकता वाली बाइनरी सूची से कई प्रारंभिक नोड्स हैं।
5. चरण 1 में वर्णित रूप में दस्तावेज़ को संसाधित करने के बाद, यह वास्तव में नए नोड्स डालने और/या व्हाइटस्पेस मान को संशोधित करके संशोधित करना बहुत आसान है। एक बार पूरा होने के बाद आप पूरी सूची में चले जाते हैं और इसे सब एक स्ट्रीम में डंप करते हैं।

यह इससे अधिक जटिल लगता है, इसे अच्छी तरह से काम करने में लगभग दो दिन लग गए।

लेकिन अगर आप इसे हल, इसके साथ मस्ती :)

Answer 5

मैं सिर्फ एक समान धागे पर इस पोस्ट है, लेकिन यह शायद यहाँ अधिक प्रासंगिक है।

मैं एक समान खोज कर रहा हूं, मूल रूप से लगभग 45-50 बाइट्स के पाठ के भीतर लगभग 10-50 बाइट्स के कीवर्ड की तलाश में हूं। मैं 9 मिलियन से अधिक ग्रंथों के बारे में 1 9 00 कीवर्ड खोजता हूं ताकि इसे यथासंभव तेज़ी से प्राप्त करना भी इसी तरह की प्राथमिकता हो।

तो, .NET 4 का उपयोग करके मैंने पाया सबसे तेज़ तरीका समानांतर Regex IsMatch है।

needles.AsParallel ().Sum (l => Regex.IsMatch (haystack , Regex.Escape (l)) ? 1 : 0); 

यह मेरा परिदृश्य (ऊपर) के लिए काम करता है, यह 55% डेटा आकार मैं की तरह के लिए कम से कम मेरी परीक्षणों में क्रमसूचक indexOf समानांतर तुलना की तुलना में तेजी है -

यहाँ हो रही कुल मैचों का एक उदाहरण है उपयोग कर रहा हूँ मैं यह भी कल्पना करता हूं कि गति सुधार केवल तभी होता है जब आप बहु-कोर मशीनों का उपयोग कर रहे हों।

कोई दिलचस्पी लेगा यदि कोई भी तेज विधि ढूंढ सके?