पायथन

Question

के साथ प्रभावी 1-5 ग्राम निष्कर्षण मेरे पास 3,000,000 लाइनों की एक बड़ी फाइलें हैं और प्रत्येक पंक्ति में 20-40 शब्द हैं। मुझे कॉर्पस से 1 से 5 एनजीआरएम निकालना है। मेरे इनपुट फ़ाइलें सादा पाठ tokenized कर रहे हैं, उदाहरण के लिए:

This is a foo bar sentence . 
There is a comma , in this sentence . 
Such is an example text . 

वर्तमान में, मैं इसे नीचे के रूप में कर रहा हूँ, लेकिन यह एक कारगर तरीका 1-5grams निकालने के लिए होने लगते नहीं है:

#!/usr/bin/env python -*- coding: utf-8 -*- 

import io, os 
from collections import Counter 
import sys; reload(sys); sys.setdefaultencoding('utf-8') 

with io.open('train-1.tok.en', 'r', encoding='utf8') as srcfin, \ 
io.open('train-1.tok.jp', 'r', encoding='utf8') as trgfin: 
    # Extract words from file. 
    src_words = ['<s>'] + srcfin.read().replace('\n', ' </s> <s> ').split() 
    del src_words[-1] # Removes the final '<s>' 
    trg_words = ['<s>'] + trgfin.read().replace('\n', ' </s> <s> ').split() 
    del trg_words[-1] # Removes the final '<s>' 

    # Unigrams count. 
    src_unigrams = Counter(src_words) 
    trg_unigrams = Counter(trg_words) 
    # Sum of unigram counts. 
    src_sum_unigrams = sum(src_unigrams.values()) 
    trg_sum_unigrams = sum(trg_unigrams.values()) 

    # Bigrams count. 
    src_bigrams = Counter(zip(src_words,src_words[1:])) 
    trg_bigrams = Counter(zip(trg_words,trg_words[1:])) 
    # Sum of bigram counts. 
    src_sum_bigrams = sum(src_bigrams.values()) 
    trg_sum_bigrams = sum(trg_bigrams.values()) 

    # Trigrams count. 
    src_trigrams = Counter(zip(src_words,src_words[1:], src_words[2:])) 
    trg_trigrams = Counter(zip(trg_words,trg_words[1:], trg_words[2:])) 
    # Sum of trigram counts. 
    src_sum_trigrams = sum(src_bigrams.values()) 
    trg_sum_trigrams = sum(trg_bigrams.values()) 

क्या यह और अधिक कुशलता से करने का कोई और तरीका है?

कैसे बेहतर विभिन्न एन ngrams एक साथ निकालने के लिए? trigrams के लिए

zip(src_words,src_words[1:]) 

और है यह, n=3:

Fast/Optimize N-gram implementations in python से

, अनिवार्य रूप से इस:

zip(*[words[i:] for i in range(n)]) 

हार्ड-कोडेड Bigrams के लिए यह है जब, n=2

zip(src_words,src_words[1:],src_words[2:]) 

Answer 1

मैं आपको एक गुच्छा दे रहा हूँ सामान्य समस्याओं के बारे में पॉइंटर्स जिन्हें आप हल करने का प्रयास कर रहे हैं .. इनमें से एक या अधिक आपके लिए उपयोगी होना चाहिए और इसे समझने में आपकी सहायता करें।

आप जो कर रहे हैं उसके लिए (मैं किसी प्रकार के मशीन अनुवाद प्रयोग का अनुमान लगा रहा हूं) आपको वास्तव में दो फ़ाइलों को srcfin और trgfin को स्मृति में लोड करने की आवश्यकता नहीं है (कम से कम आपके पास कोड नमूना के लिए नहीं है प्रदान किया गया) .. उन्हें किसी भी समय स्मृति में रखने के लिए आवश्यक सामानों की मात्रा के मामले में अलग-अलग प्रोसेसिंग कम महंगी होगी।

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

एक बिंदु से परे, यह आपके लिए स्मृति में सभी डेटा को पकड़ने के लिए अब संभव नहीं होगा। आपको इसे तोड़ने में मदद के लिए मानचित्र-कम देखने पर विचार करना चाहिए। Mrjob python पैकेज देखें जो आपको पाइथन में नौकरियों को कम करने के लिए नक्शा लिखने देता है। मैपर चरण में, आप टेक्स्ट को अपने एनजीआरएम में तोड़ देंगे, और रेड्यूसर चरण में आप अपनी कुल गणना प्राप्त करने के लिए प्रत्येक एनजीआरएम को देखे जाने की संख्या की गणना करेंगे। mrjob भी स्थानीय रूप से चलाया जा सकता है जो स्पष्ट रूप से आपको कोई समांतरता लाभ नहीं देगा, लेकिन अच्छा कारण होगा mrjob अभी भी आपके लिए भारी भारोत्तोलन करेगा।

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

परिणामी डेटा वस्तु है मेरा मानना ​​है कि:

Answer 2

मान लिया जाये कि आप लाइनों के बीच ngrams गिनती करने के लिए नहीं करना चाहते, और अनुभवहीन tokenization संभालने:

def ngrams(n, f): 
    deque = collections.deque(maxlen=n) 
    for line in f: 
     deque.clear() 
     words = ["<s>"] + line.split() + ["</s>"] 
     deque.extend(words[:n-1]) # pre-seed so 5-gram counter doesn't count incomplete 5-grams 
     for word in words[n-1:]: 
      deque.append(word) 
      yield tuple(str(w) for w in deque) # n-gram tokenization 
counters = [collections.Counter(ngrams(i, open('somefile.txt'))) for i in range(5)] 

संपादित जितना संभव हो उतना स्पैस। 40 शब्दों के साथ 3 एम लाइन ~ 120 मीटर टोकन है। अंग्रेजी में ~ 1 एम शब्दों के साथ (हालांकि आमतौर पर कम इस्तेमाल किया जाता है), आपको शायद एक लंबी पूंछ मिल जाएगी। विनिमय योग्यता धारणा आराम कुशल छंटाई के लिए Tregoreg के जवाब की तरह कुछ की आवश्यकता होगी

def ngrams(n, f, prune_after=10000): 
    counter = collections.Counter() 
    deque = collections.deque(maxlen=n) 
    for i, line in enumerate(f): 
     deque.clear() 
     words = ["<s>"] + line.split() + ["</s>"] 
     deque.extend(words[:n-1]) 
     for word in words[n-1:]: 
      deque.append(word) 
      ngram = tuple(str(w) for w in deque) 
      if i < prune_after or ngram in counter: 
       counter[ngram] += 1 
    return counter 

, लेकिन ज्यादातर मामलों में विनिमय योग्यता धारण करना चाहिए: आप अपने डेटा कल्पना कर सकते हैं, तो विनिमय/आईआईडी होने के लिए है, तो आप कुछ छंटाई बीच में जोड़ सकते हैं ।

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

Answer 3

यदि आप केवल सबसे आम (लगातार) n-ग्राम (जो आपका मामला मुझे लगता है) में रुचि रखते हैं, तो आप Apriori algorithm के केंद्रीय विचार का पुन: उपयोग कर सकते हैं। s_min दिया गया, एक न्यूनतम समर्थन जिसे n-ग्राम दिए गए लाइनों की संख्या के रूप में सोचा जा सकता है, यह कुशलतापूर्वक ऐसे सभी n-ग्राम के लिए खोज करता है।

विचार इस प्रकार है: एक क्वेरी फ़ंक्शन लिखें जो n-ग्राम लेता है और परीक्षण करता है कि यह कॉर्पस में कितनी बार निहित है। आपके पास ऐसा फ़ंक्शन तैयार करने के बाद (बाद में चर्चा के रूप में अनुकूलित किया जा सकता है), पूरे कॉर्पस को स्कैन करें और सभी 1-ग्राम, यानी बेयर टोकन प्राप्त करें, और कम से कम s_min बार वाले लोगों का चयन करें। यह आपको 1-ग्राम के F1 सबसेट देता है। फिर F1 से सभी 1 -ग्राम को जोड़कर सभी संभव 2-ग्राम का परीक्षण करें। दोबारा, उन लोगों का चयन करें जो s_min मानदंड रखते हैं और आपको F2 मिल जाएगा। सभी 2-F2 से ग्रामों को संयोजित करके और लगातार -ग्राम का चयन करके, आपको F3 मिल जाएगा। Fn तक खाली न होने के लिए दोहराएं।

कई अनुकूलन यहां किए जा सकते हैं। जब Fn से n -grams के संयोजन, आप तथ्य यह है कि nx -grams और y केवल (यदि उचित हैशिंग प्रयोग किया जाता है किसी भी n के लिए निरंतर समय में जाँच की जा सकती) x[1:] == y[:-1] iff (n+1) -gram के रूप में जोड़ा जा सकता है दोहन कर सकते हैं। इसके अलावा, यदि आपके पास पर्याप्त रैम है (आपके कॉर्पस के लिए, कई जीबी), तो आप क्वेरी फ़ंक्शन को बहुत तेज कर सकते हैं। प्रत्येक 1-ग्राम के लिए, दिए गए 1-ग्राम युक्त लाइन इंडेक्स का हैश-सेट स्टोर करें। -ग्राम को (n+1)-ग्राम में संयोजित करते समय, दो संबंधित सेटों के चौराहे का उपयोग करें, लाइनों का एक सेट प्राप्त करें जहां (n+1) -gram शामिल हो सकता है।

समय जटिलता s_min घट जाती है।सौंदर्य यह है कि कम से कम (और इसलिए अनिच्छुक) n -ग्राम पूरी तरह से फ़िल्टर किए जाते हैं क्योंकि एल्गोरिदम चलता है, केवल लगातार लोगों के लिए कम्प्यूटेशनल समय बचाता है।