प्रसंस्करण बहुत बड़े पाठ फ़ाइलें

Question

समस्या: मैं एक बहुत बड़ा कच्चे पाठ फ़ाइल है (3gig का मान), मैं फ़ाइल में प्रत्येक शब्द के माध्यम से जाने के लिए और है कि एक शब्द फ़ाइल में कितनी बार आ रहा यह पता करना है ।

मेरा प्रस्तावित समाधान: विशाल फ़ाइल को कई फाइलों में विभाजित करें और प्रत्येक विभाजित फ़ाइल में शब्दों को क्रमबद्ध तरीके से रखा जाएगा। उदाहरण के लिए, "" से शुरू होने वाले सभी शब्द "_a.dic" फ़ाइल में संग्रहीत किए जाएंगे। तो, किसी भी समय हम 26 से अधिक फाइलों से अधिक नहीं होंगे।

इस दृष्टिकोण में समस्या है,

मैं धाराओं का उपयोग फ़ाइल को पढ़ने के लिए कर सकते हैं, लेकिन फ़ाइल के कुछ हिस्से को पढ़ने के लिए धागे का उपयोग करना चाहता था। उदाहरण के लिए, 0-1024 बाइट्स को एक अलग थ्रेड के साथ पढ़ें (कम से कम 4-8 धागे बॉक्स में मौजूद प्रोसेसर के नंबर पर आधारित हैं)। क्या यह संभव है या क्या मैं सपना देख रहा हूं?

कोई बेहतर तरीका?

नोट: यह एक शुद्ध सी ++ या सी आधारित समाधान होना चाहिए। कोई डेटाबेस आदि की अनुमति है।

Answer 1

आप Kernighan और पाईक, और विशेष रूप से अध्याय 3.

सी ++ में से 'The Practice of Programming' को देखने के लिए की जरूरत है, तार और गिनती (std::map<string,size_t>, IIRC) के आधार पर एक मानचित्र का उपयोग। फ़ाइल को पढ़ें (एक बार - यह एक से अधिक बार पढ़ने के लिए बहुत बड़ा है), इसे शब्दों में विभाजित करते हुए (शब्द 'की कुछ परिभाषा के लिए), और प्रत्येक शब्द के लिए मानचित्र प्रविष्टि में गिनती में वृद्धि करना।

सी में, आपको अपना नक्शा बनाना होगा। (या डेविड हैंनसन की "C Interfaces and Implementations" खोजें।)

या आप पर्ल, या पायथन, या Awk (जिनमें से सभी को नक्शा के समतुल्य सहयोगी सरणी हैं) का उपयोग कर सकते हैं।

Answer 2

सी आधारित समाधान?

मुझे लगता है कि इस सटीक उद्देश्य के लिए पेर्ल का जन्म हुआ था।

Answer 3

मुझे लगता है कि फ़ाइल के कुछ हिस्सों को समानांतर में पढ़ने वाले कई धागे का उपयोग करने में नहीं लगता है। मैं उम्मीद करता हूं कि यह एप्लिकेशन बैंडविड्थ और आपके हार्डडिस्क की विलंबता से जुड़ा हुआ है, वास्तविक शब्द गणना नहीं। ऐसा बहु-थ्रेडेड संस्करण वास्तव में खराब प्रदर्शन कर सकता है क्योंकि "अर्ध-यादृच्छिक" फ़ाइल पहुंच आमतौर पर "रैखिक फ़ाइल" पहुंच से धीमी होती है।

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

Answer 4

स्ट्रीम में केवल एक कर्सर है। यदि आप एक समय में एक से अधिक धागे वाले स्ट्रीम तक पहुंचते हैं, तो आप यह सुनिश्चित नहीं करेंगे कि आप कहां चाहते हैं। कर्सर की स्थिति से पढ़ा जाता है।

मैं क्या करूँगा केवल एक धागा (शायद मुख्य एक) है जो स्ट्रीम को पढ़ता है और अन्य थ्रेडों को बाइट पढ़ने के प्रेषण करता है।

उदाहरण द्वारा:

• थ्रेड #I के लिए तैयार है और यह अगले भाग देने के लिए मुख्य थ्रेड से पूछते हैं,
• मुख्य धागा अगले 1 एमबी पढ़ सकते हैं और 1 थ्रेड के लिए उन्हें प्रदान करते हैं
• थ्रेड #I पढ़ 1 एमबी और गिनती शब्द जैसा आप चाहते हैं,
• थ्रेड #i अपने काम को खत्म करता है और अगले 1 एमबी के लिए फिर से पूछता है।

इस तरह से आप धारा विश्लेषण को स्ट्रीम पढ़ने के लिए अलग कर सकते हैं।

Answer 5

जो आप खोज रहे हैं वह RegEx है। ग पर यह Stackoverflow धागा ++ regex इंजन की मदद करनी चाहिए:

C++: what regex library should I use?

Answer 6

सबसे पहले, मैं बहुत यकीन है कि C/C++ सबसे अच्छा तरीका यह संभाल करने के लिए नहीं है हूँ। आदर्श रूप से, आप कुछ नक्शा/समांतरता के लिए भी कम उपयोग करेंगे।

लेकिन, अपनी बाधाओं को मानते हुए, मैं यही करूँगा।

1) टेक्स्ट फ़ाइल को छोटे हिस्सों में विभाजित करें। आपको शब्द के पहले अक्षर से ऐसा करने की ज़रूरत नहीं है। बस, 5000-शब्द भाग में कहें, उन्हें तोड़ दें। स्यूडोकोड में, आप कुछ इस तरह करते हैं:

सूचकांक = 0

NUMWORDS = 0

mysplitfile = OpenFile (सूचकांक-split.txt)

जबकि (bigfile >> शब्द)

mysplitfile << word 

numwords ++ 

if (numwords > 5000) 

    mysplitfile.close() 

    index++ 

    mysplitfile = openfile(index-split.txt) 

2) नए सूत्र अंडे subfiles में से प्रत्येक को पढ़ने के लिए एक साझा नक्शा डेटा संरचना और pthreads का प्रयोग करें। फिर, स्यूडोकोड:

maplock = create_pthread_lock()

sharedmap = std :: नक्शा()

हर सूचकांक-split.txt फ़ाइल के लिए

:

spawn-new-thread(myfunction, filename, sharedmap, lock) 

dump_map (sharedmap)

शून्य माईफंक्शन (फ़ाइल नाम, साझामैप) {

localmap = std::map<string, size_t>(); 

file = openfile(filename) 

while (file >> word) 

    if !localmap.contains(word) 
     localmap[word] = 0 

    localmap[word]++ 

acquire(lock) 
for key,value in localmap 
    if !sharedmap.contains(key) 
     sharedmap[key] = 0 

    sharedmap[key] += value 
release(lock) 

}

वाक्यविन्यास के लिए खेद है। मैं हाल ही में बहुत सारे अजगर लिख रहा हूं।

Answer 7

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

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

समस्या काफी सरल है: आपके द्वारा पढ़ी जा रही फ़ाइल (संभावित रूप से) आपके पास उपलब्ध कैश स्पेस से बड़ी है - लेकिन आपको कैशिंग से कुछ भी प्राप्त नहीं होगा, क्योंकि आप हिस्सों को दोबारा नहीं ले पाएंगे फ़ाइल फिर से (कम से कम अगर आप समझदारी से चीजें करते हैं)। इस प्रकार, आप किसी भी कैशिंग को बाईपास करने के लिए सिस्टम को बताना चाहते हैं, और बस डिस्क ड्राइव से जितनी संभव हो सके डेटा को अपनी मेमोरी में स्थानांतरित करें जहां आप इसे संसाधित कर सकते हैं। यूनिक्स जैसी प्रणाली में, शायद यह open() और read() (और आपको बहुत कुछ नहीं मिलेगा)। विंडोज़ पर, यह CreateFile और ReadFile है, FILE_FLAG_NO_BUFFERINGCreateFile पर ध्वज गुजर रहा है - और यदि आप सही करते हैं तो यह शायद आपकी गति को लगभग दोगुना कर देगा।

आपको कुछ समानांतर संरचनाओं का उपयोग करके प्रसंस्करण करने की वकालत करने वाले कुछ उत्तरों भी मिल गए हैं। मुझे लगता है कि ये मौलिक रूप से गलत हैं। जब तक आप कुछ बेवकूफ नहीं करते हैं, तब तक फ़ाइल में शब्दों को गिनने का समय केवल फ़ाइल को पढ़ने के लिए कुछ मिलीसेकंड लंबा होगा।

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

जब तक आप सुनिश्चित हों कि इसका उपयोग केवल बहु-प्रोसेसर (बहु-कोर) मशीन पर किया जाएगा, वास्तविक धागे का उपयोग ठीक है। यदि एक मौका है तो यह कभी भी एकल-कोर मशीन पर किया जा सकता है, तो आप इसके बजाय ओवरलैप किए गए I/O के साथ एक थ्रेड का उपयोग करके कुछ बेहतर हो जाएंगे।

Answer 8

पहला - शब्दों को सहेजने के लिए डेटास्ट्रक्चर पर निर्णय लें।

स्पष्ट विकल्प मानचित्र है। लेकिन शायद Trie आपको बेहतर सेवा प्रदान करेगा। प्रत्येक नोड में, आप शब्द के लिए गिनती को बचाते हैं। 0 का मतलब है कि यह केवल एक शब्द का हिस्सा है। आप स्ट्रीम का उपयोग करके त्रिभुज में अपनी फ़ाइल विशेषता को पढ़ सकते हैं।

दूसरा - बहुसंख्यक हाँ या नहीं? यह उत्तर देने में आसान नहीं है। आकार के आधार पर डेटास्ट्रक्चर बढ़ता है और आप उत्तर को समानांतर कैसे करते हैं, अलग-अलग हो सकते हैं।

1. सिंगलथ्रेड - स्ट्रेटफॉरवर्ड और कार्यान्वित करने में आसान।
2. एकाधिक पाठक धागे और एक डेटास्ट्रक्चर के साथ बहुप्रचारित। फिर आपको डेटास्ट्रक्चर तक पहुंच को सिंक्रनाइज़ करना होगा। एक ट्री में, आपको केवल उस नोड को लॉक करने की आवश्यकता होती है, जिसमें आप वास्तव में हैं, इसलिए एकाधिक पाठक बिना हस्तक्षेप के डेटास्ट्रक्चर तक पहुंच सकते हैं। एक आत्म-संतुलन वृक्ष अलग हो सकता है, खासकर जब पुनर्वितरण।
3. एकाधिक पाठक धागे के साथ बहुप्रचारित, प्रत्येक अपने स्वयं के डेटास्ट्रक्चर के साथ। प्रत्येक धागे फ़ाइल के एक हिस्से को पढ़ने के दौरान अपने स्वयं के डेटास्ट्रक्चर बनाता है। प्रत्येक के समाप्त होने के बाद, परिणाम संयुक्त किए जाने चाहिए (जो आसान होना चाहिए)।

एक चीज जो आपको सोचनी है - आपको प्रत्येक धागे को शुरू करने के लिए एक शब्द सीमा मिलनी है, लेकिन उसे एक बड़ी समस्या नहीं होनी चाहिए (उदाहरण के लिए प्रत्येक धागा पहली शब्द सीमा तक शुरू होता है और वहां से शुरू होता है , अंत में प्रत्येक थ्रेड उस शब्द को समाप्त करता है जिस पर यह काम कर रहा है)।

Answer 9

जैसा कि अन्य ने संकेत दिया है, बाधा डिस्क I/O होगी। इसलिए मैं सुझाव देता हूं कि आप ओवरलैप्ड I/O का उपयोग करें। यह मूल रूप से प्रोग्राम तर्क को बदल देता है। I/O कब करना है, यह निर्धारित करने के लिए आपके कोड टाइपिंग के बजाय, आप बस अपने कोड को कॉल करने के लिए ऑपरेटिंग सिस्टम को बताएं जब भी यह थोड़ा सा I/O समाप्त हो जाता है। यदि आप I/O completion ports का उपयोग करते हैं, तो आप फ़ाइल खंडों को संसाधित करने के लिए ओएस को कई धागे का उपयोग करने के लिए भी बता सकते हैं।

Answer 10

नहीं सी, और एक सा बदसूरत, लेकिन यह पता टकरा को केवल 2 मिनट लग गए: प्रत्येक पंक्ति के ऊपर -n
स्प्लिट साथ -a
प्रत्येक के साथ @F शब्दों में प्रत्येक पंक्ति

perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a} || $a cmp $b} keys %h) {print "$h{$w}\t$w"}}' file > freq

लूप $_ शब्द वृद्धि हैश %h
file पर
तक पहुंच गया हैsort आवृत्ति द्वारा हैश $h{$b}<=>$h{$a}
दो आवृत्तियों समान, तरह वर्णानुक्रम $a cmp $b
प्रिंट आवृत्ति $h{$w} और शब्द $w
परिणाम 'freq'

दायर करने के लिए मैं एक 3.3 पर इस कोड को दौड़ा पुन: निर्देशित कर रहे हैं 580,000,000 शब्दों के साथ जीबी पाठ फ़ाइल।
पर्ल 5.22 173 सेकंड में पूरा हुआ।

मेरे इनपुट फ़ाइल पहले से ही था विराम चिह्न बाहर छीन लिया, और अपरकेस कोड के इस बिट का उपयोग कर लोअरकेस में परिवर्तित,:
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
(144 सेकंड के क्रम)

---

शब्द गिनती स्क्रिप्ट बारी-बारी से कर सकते थे awk में लिखा जाना चाहिए:
awk '{for (i=1; i<=NF; i++){h[$i]++}} END{for (w in h){printf("%s\t%s\n", h[w], w)}}' file | sort -rn > freq