Estrazione efficace da 1-5 grammi con pitone

Question

Ho un file enorme di 3.000.000 di righe e ogni riga contiene 20-40 parole. Devo estrarre da 1 a 5 ngram dal corpo. I miei file di input vengono tokenized testo normale, ad esempio:

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

Attualmente, sto facendo come qui sotto, ma questo non sembra essere un modo efficace per estrarre i 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()) 

C'è qualche altro modo per farlo in modo più efficiente?

Come estrarre in modo ottimale N Ngram diversi contemporaneamente?

Da Fast/Optimize N-gram implementations in python, essenzialmente questo:

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

quando hard-coded è questo per bigrammi, n=2:

zip(src_words,src_words[1:]) 

ed è questo per trigrammi, n=3:

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

Answer 1

Ti sto dando un sacco di puntatori relativi ai problemi generali che stai cercando di risolvere. Uno o più di questi dovrebbero essere utili per te e aiutarti a capirlo.

Per quello che stai facendo (sto indovinando un qualche tipo di esperimento di traduzione automatica) non hai davvero bisogno di caricare i due file srcfin e trgfin in memoria contemporaneamente (almeno non per il codice di esempio che hai fornito) .. Elaborandoli separatamente sarà meno costoso in termini di quantità di cose che è necessario tenere in memoria in un dato momento.

Si sta leggendo una tonnellata di dati in memoria, elaborarlo (che prende anche più memoria), e quindi tenendo i risultati in alcuni dati in memoria-strutture. Invece di farlo, dovresti sforzarti di essere più pigro. Scopri i generatori Python e scrivi un generatore che trasmette tutti gli ngram di un determinato testo senza dover tenere in memoria l'intero testo in un dato momento. Il pacchetto itertools python sarà probabilmente utile durante la scrittura di questo.

Al di là di un punto, sarà più fattibile per voi di tenere tutti questi dati in memoria. Dovresti prendere in considerazione la possibilità di esaminare la mappa-riduci per aiutarti a risolvere questo problema. Scopri il pacchetto python mrjob che permette di scrivere mappare ridurre posti di lavoro in pitone. Nella fase di mappatura, si interromperà il testo nei suoi ngram e, nella fase di riduzione, si contano il numero di volte in cui si vede ogni ngram per ottenere il conteggio complessivo. mrjob del possono essere eseguiti anche a livello locale, che, ovviamente, non vi darà alcun beneficio di parallelizzazione, ma sarà bello causa mrjob sarà ancora fare un sacco di sollevamento di carichi pesanti per voi.

Se si è costretti a tenere tutti i conteggi in memoria contemporaneamente (per una quantità enorme di testo), quindi implementare una strategia di eliminazione per eliminare ngram molto rari o considerare l'utilizzo di una ricerca persistente basata su file. tabella tale sqlite per contenere tutti i dati per voi.

Answer 2

Supponendo che non si vuole contare ngrams tra le linee, e assumendo tokenizzazione ingenua:

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

modificare: aggiunto linea di inizio/fine gettoni

L'oggetto dati risultante è credo su il più scarso possibile Le linee da 3 m con 40 parole equivalgono a token da 120 m. Con le parole ~ 1m in inglese (anche se meno comunemente usate), probabilmente otterrai una coda piuttosto lunga. Se si può immaginare i vostri dati per essere intercambiabile/IID, allora si può aggiungere un po 'di potatura nel mezzo:

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 

l' ipotesi scambiabilità richiederebbe qualcosa come la risposta di Tregoreg per la potatura efficiente, ma nella maggior parte dei casi intercambiabilità dovrebbe tenere .

Per quanto riguarda la velocità raw, penso che lo zip (come il codice originale) vs deque sia la domanda fondamentale. zip rimuove il ciclo più interno, quindi è probabile che sia già molto veloce. deque richiede il ciclo più interno, ma consuma anche i dati in modo iterativo, quindi il suo footprint di memoria di lavoro dovrebbe essere molto più piccolo. Probabilmente ciò dipenderà dalla tua macchina, ma immagino che per le grandi macchine/i piccoli dati lo zip sia più veloce. Una volta che si inizia a esaurire la memoria (specialmente se si inizia a parlare di potatura), tuttavia, deque ottiene alcuni ulteriori vantaggi.

Answer 3

Se sei interessato solo ai più comuni (frequenti) n -gram (che è il tuo caso, suppongo), puoi riutilizzare l'idea centrale di Apriori algorithm. Dato s_min, un supporto minimo che può essere considerato come il numero di linee in cui è contenuto un dato n -gram, cerca in modo efficiente tutti i tipi di tali n -gram.

L'idea è la seguente: scrivere una funzione di query che prende un n -gram e verifica quante volte è contenuto nel corpus. Dopo aver preparato tale funzione (può essere ottimizzata come discusso più avanti), eseguire la scansione dell'intero corpus e ottenere tutti i 1 -gram, cioè i token nudi e selezionare quelli che sono contenuti almeno s_min volte. Questo ti dà sottoinsieme F1 di frequenti 1 -grams. Quindi prova tutti i possibili 2 -gram combinando tutti i 1 -grams da F1. Ancora una volta, seleziona quelli che hanno il criterio s_min e otterrai F2. Combinando tutti i 2 -grams da F2 e selezionando il frequente 3 -grams, riceverai F3. Ripeti fino a quando lo Fn non è vuoto.

Qui è possibile eseguire molte ottimizzazioni. Quando si combinano n -grams da Fn, si può sfruttare il fatto che n -grams x e y possono essere combinati solo per formare (n+1) -gram sse x[1:] == y[:-1] (può essere controllato in tempo costante per qualsiasi n se viene utilizzata una corretta hashing). Inoltre, se hai abbastanza RAM (per il tuo corpus, molti GB), puoi velocizzare la funzione di query. Per ogni 1 -gram, memorizzare un hash-set di indici di riga contenente il dato 1 -gram. Quando si combinano due n -gram in un (n+1) -gram, utilizzare l'intersezione dei due set corrispondenti, ottenendo un insieme di linee in cui è possibile contenere il valore (n+1) -gram.

La complessità temporale aumenta al diminuire di s_min.Il bello è che raramente (e quindi poco interessante) i parametri n vengono completamente filtrati mentre l'algoritmo viene eseguito, risparmiando tempo computazionale solo per quelli frequenti.