Effektive 1-5 Gramm Extraktion mit Python

Question

Ich habe eine riesige Dateien von 3.000.000 Zeilen und jede Zeile haben 20-40 Wörter. Ich muss 1 bis 5 Negramme aus dem Korpus extrahieren. Meine Eingabedateien werden in Token aufgeteilt Klartext, zB:

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

Derzeit mache ich es wie unten aber das scheint nicht ein effizienter Weg zu sein, um die 1-5grams zu extrahieren:

#!/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()) 

Gibt es eine andere Möglichkeit, dies effizienter zu tun?

Wie kann man verschiedene N-ngrams gleichzeitig optimal extrahieren?

Von Fast/Optimize N-gram implementations in python, im Wesentlichen diese:

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

wenn hartcodiert ist dies für Bigramme, n=2:

zip(src_words,src_words[1:]) 

und das ist für Trigramme, n=3:

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

Answer 1

Ich gebe dir eine Menge Hinweise zu den allgemeinen Problemen, die Sie zu lösen versuchen. Einer oder mehrere davon sollten für Sie nützlich sein und Ihnen helfen, dies herauszufinden.

Für das, was Sie tun (ich vermute eine Art maschinelles Übersetzungsexperiment), müssen Sie die beiden Dateien srcfin und trgfin nicht gleichzeitig in den Speicher laden (zumindest nicht für das Codebeispiel, das Sie haben) vorausgesetzt) ​​.. Die Verarbeitung separat ist weniger teuer in Bezug auf die Menge der Sachen, die Sie im Speicher zu einem bestimmten Zeitpunkt halten müssen.

Sie lesen eine Menge Daten in den Speicher, verarbeiten sie (was noch mehr Speicher benötigt) und halten dann die Ergebnisse in einigen In-Memory-Datenstrukturen. Stattdessen sollten Sie sich anstrengen, faul zu sein. Erfahren Sie mehr über Python-Generatoren und schreiben Sie einen Generator, der alle Ngramme aus einem gegebenen Text ausgibt, ohne dass der gesamte Text zu einem bestimmten Zeitpunkt im Speicher gehalten werden muss. Das Python-Paket von iertools wird wahrscheinlich nützlich sein, wenn Sie dies schreiben.

Über einen Punkt hinaus ist es nicht mehr möglich, all diese Daten im Speicher zu halten. Sie sollten sich die Map-Reduction ansehen, um das Problem zu lösen. Sehen Sie sich das mrjob-Python-Paket an, mit dem Sie map reduce-Jobs in Python schreiben können. Im Mapper-Schritt werden Sie den Text in seine ngrams zerlegen, und in der Reducer-Phase werden Sie zählen, wie oft Sie jedes ngram sehen, um seine Gesamtanzahl zu erhalten. mrjobs kann auch lokal ausgeführt werden, was offensichtlich keine Parallelisierungsvorteile bringt, aber es wird nett sein, denn mrjob wird immer noch viel schweres Heben für euch machen.

Wenn Sie gezwungen sind, alle Zähler gleichzeitig im Speicher zu halten (für eine große Menge an Text), implementieren Sie entweder eine Beschneidungsstrategie, um sehr seltene Ngramme zu entfernen, oder überlegen Sie sich eine dauerhafte dateibasierte Suche Tabelle so sqlite, um alle Daten für Sie zu halten.

Answer 2

Angenommen, Sie wollen nicht ngrams zwischen den Zeilen zählen und naive tokenization vorausgesetzt:

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)] 

bearbeiten: hinzugefügt Anfang/Ende-Leitungs Token

Das resultierende Datenobjekt Ich glaube, über so spärlich wie möglich. 3m Zeilen mit 40 Wörtern sind ~ 120m Token. Mit ~ 1 Mio. Wörtern in Englisch (obwohl weniger häufig verwendet), werden Sie wahrscheinlich einen ziemlich langen Schwanz bekommen. Wenn Sie Ihre Daten vorstellen können austauschbar/iid sein, dann können Sie einige Beschneidung in der Mitte hinzu:

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 

die Austauschbarkeit Annahme Relaxing würde für eine effiziente Beschneidung etwas wie Tregoreg Antwort erfordern, aber in den meisten Fällen sollte die Austauschbarkeit halten .

Soweit rohe Geschwindigkeit, denke ich, Zip (wie der ursprüngliche Code) vs Deque ist die grundlegende Frage. Zip entfernt die innerste Schleife, also ist es wahrscheinlich schon sehr schnell. deque benötigt die innerste Schleife, verbraucht aber auch die Daten iterativ, so dass ihr Arbeitsspeicherbedarf viel kleiner sein sollte. Was besser ist, wird wahrscheinlich von Ihrer Maschine abhängen, aber ich würde mir vorstellen, dass bei großen Maschinen/kleinen Daten die Zip-Geschwindigkeit höher wäre. Wenn Sie nicht mehr genügend Speicher zur Verfügung haben (vor allem, wenn Sie anfangen, über das Beschneiden zu sprechen), bekommt Deque ein paar weitere Vorteile.

Answer 3

Wenn Sie nur an den häufigsten (häufigen) n-Grammen interessiert sind (was Ihrer Fall ist, nehme ich an), können Sie die zentrale Idee der Apriori algorithm wiederverwenden. Mit s_min, einer minimalen Unterstützung, die man sich als die Anzahl der Zeilen vorstellen kann, die ein gegebenes n -gram enthält, sucht es effizient nach allen solchen n-Grammen.

Die Idee ist wie folgt: Schreiben Sie eine Abfrage-Funktion, die ein n -gram und testet, wie oft es im Korpus enthalten ist. Nachdem Sie eine solche Funktion vorbereitet haben (können optimiert werden, wie später besprochen), scannen Sie den gesamten Korpus und erhalten Sie alle 1-Gramme, d. H. Nackten Token, und wählen Sie diejenigen, die mindestens s_min mal enthalten sind. Dies gibt Ihnen die Untergruppe F1 von häufigen 1-Grammen. Testen Sie dann alle möglichen 2-Gramme durch Kombinieren aller 1-Gramme von F1. Wählen Sie wiederum diejenigen aus, die das s_min-Kriterium enthalten, und Sie erhalten F2. Wenn Sie alle -gramme von F2 kombinieren und die häufigen 3 -grams auswählen, erhalten Sie F3. Wiederholen Sie dies so lange, wie Fn nicht leer ist.

Viele Optimierungen können hier vorgenommen werden. Wenn n -grams von Fn kombinieren, können Sie die Tatsache ausnutzen, dass n -grams x und y nur kombiniert werden kann (n+1) -Gramm iff x[1:] == y[:-1] zu bilden (kann für jeden n in konstanter Zeit überprüft werden, wenn die entsprechende Hashing verwendet wird). Außerdem, wenn Sie genug RAM haben (für Ihr Korpus, viele GBs), können Sie die Abfragefunktion extrem beschleunigen. Speichern Sie für jedes 1 -gram einen Hash-Satz von Linienindizes, die das angegebene 1 -gram enthalten. Wenn Sie zwei n -gramme in ein (n+1) -gramm kombinieren, verwenden Sie den Schnittpunkt der beiden entsprechenden Mengen und erhalten Sie eine Reihe von Zeilen, in denen das (n+1) -gram enthalten sein kann.

Die Zeit Komplexität wächst als s_min abnimmt.Die Schönheit ist, dass selten (und daher uninteressant) n-Gramme vollständig gefiltert werden, wie der Algorithmus ausgeführt wird, spart Rechenzeit nur für die häufigen.