इनपुट स्ट्रीम में स्ट्रिंग के लिए खोज

Question

मेरे पास एक बड़ी बाइनरी फ़ाइल है (कई गीगाबाइट्स, इसलिए इसे मेमोरी में लोड करना एक विकल्प नहीं है) कि मैं स्ट्रिंग "आईसीपीएफ" की सभी घटनाओं को खोजना चाहता हूं।

मैंने इसके लिए std::search का उपयोग करने का प्रयास किया, लेकिन इस तथ्य से अभी तक काट दिया गया है कि std::search केवल इटरेटर को इनपुट करने के लिए आगे हीटरेटर के लिए काम करता है।

क्या मानक पुस्तकालय इसके लिए एक तेज़ विकल्प प्रदान करता है? या क्या मुझे खोज को हाथ-कोड करने की आवश्यकता है (या तो उन पर std::search पर std::search पर या तो ignore सबकुछ 'i' तक सबकुछ पढ़ने और फिर अगले तीन वर्णों को मैन्युअल रूप से जांचने की आवश्यकता है)?

Answer 1

क्या मानक पुस्तकालय इसके लिए एक तेज़ विकल्प प्रदान करता है?

हालांकि मानक सी ++ लाइब्रेरी टेक्स्ट स्ट्रीम खोजने के तरीके प्रदान करती है, लेकिन यह बाइनरी धाराओं के लिए तुलनात्मक एल्गोरिदम प्रदान नहीं करती है।

या मैं हाथ से कोड के लिए खोज (या तो फिर एक समय में मात्रा में पढ़ने उन पर std::search, या सब कुछ उपेक्षा एक 'i' जब तक और फिर मैन्युअल रूप से अगले तीन वर्णों की जाँच) की आवश्यकता है?

"छोड़ें और खोज" दृष्टिकोण को कोड करना मुश्किल हो सकता है, क्योंकि प्रविष्टियों को छोड़ने वाले समाधान को कोड करना आसान है। उदाहरण के लिए, यदि आप को "icpicpf" वाली फ़ाइल में ढूंढ रहे हैं, तो एक साधारण प्रोग्राम जो एक समय में एक वर्ण को संसाधित करता है "icpi" उपसर्ग को हटाने के बाद "icpf" प्रत्यय को खोजने में विफल रहता है।

यदि आप इसे स्वयं कोड करने जा रहे हैं, तो Knuth–Morris–Pratt algorithm लागू करने पर विचार करें। ऑनलाइन उपलब्ध कई कार्यान्वयन हैं, और यह धाराओं पर सही तरीके से काम करता है, क्योंकि यह एक समय में एक चरित्र को मानता है, और कभी वापस नहीं जाता है।

Answer 2

सबसे तेज़ तरीका पूरी फ़ाइल को स्मृति में लोड करना है, फिर स्मृति को खोजें।

अगला सबसे अच्छा विकल्प हार्ड ड्राइव को गति में रखना है। शायद एक धागा है जो डेटा के हिस्सों को बफर में पढ़ता है और बफर की खोज करने वाला एक और थ्रेड होता है।

सूची में जाकर, डेटा के बड़े हिस्से में एक बफर में पढ़ना, फिर बफर खोजना एक अच्छी तकनीक है, हालांकि पिछली विधियों के रूप में उतनी कुशल नहीं है।

आप std::getline और std::string का उपयोग कर लाइन से लाइन पढ़ सकते हैं। यह ब्लॉक पढ़ने के जितना तेज़ नहीं है क्योंकि इनपुट फ़ंक्शन न्यूलाइन वर्ण (और std::string में मेमोरी आवंटित करने) की खोज कर रहा है।

सबसे खराब मामला शायद चरित्र द्वारा चरित्र पढ़ रहा है। फ़ंक्शन ओवरहेड एक वर्ण पढ़ने के लिए खराब है (आमतौर पर ओवरहेड डेटा के बड़े ब्लॉक को पढ़ने के लिए समान होता है)।

नहीं, फ़ाइलों को खोजने के लिए कोई मानक सी ++ लाइब्रेरी फ़ंक्शन नहीं है। कुछ ऑपरेटिंग सिस्टम में फाइलों को खोजने के लिए उपयोगिताएं होती हैं; शायद आप उनमें से एक का उपयोग कर सकते हैं।

संपादित करें 1:
बाधा डेटा को इनपुट कर रही है। एक बार जब आप डेटा को बफर में प्राप्त कर लेते हैं, तो ब्रूट फोर्स की बजाय कई कुशल खोज एल्गोरिदम होते हैं (पहले अक्षर की खोज करते हैं, फिर अगले अक्षरों की खोज करते हैं)।

"स्ट्रिंग खोज एल्गोरिदम" के लिए इंटरनेट पर खोजें।

Answer 3

मैं किसी भी शुद्ध मानक पुस्तकालय समाधान के बारे में पता नहीं है, लेकिन गिरी पहले से ही प्रीफेचिंग लागू करता है, तो यह आगे के लिए आवश्यक iterators पाने के लिए mmap() फाइल करने के लिए संभव हो जाना चाहिए: (त्रुटि लोप से निपटने)

size_t search(int fd, size_t fileSize) { 
    auto start = reinterpret_cast<char*>(
     ::mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE | MAP_NORESERVE, fd, 0)); 
    ::madvise(start, fileSize, MADV_SEQUENTIAL); 
    auto pattern = "icpf"; 
    auto offset = std::search(start, start+fileSize, pattern, pattern+4); 
    return offset - start; 
} 

यह विश्वास का एक छोटा सा छलांग है, आलसी लोडिंग, prefetching और सही ढंग से हटाने के लिए अपने कर्नेल पर भरोसा करते हैं। दूसरी तरफ, यदि आप इसके साथ किसी पर भरोसा कर सकते हैं, तो यह शायद कर्नेल डेवलपर्स होगा।

अस्वीकरण: मैंने वास्तव में इसे बहु-गीगाबाइट फ़ाइल पर परीक्षण नहीं किया था।