Come trovare l'alta frequenza delle parole in un libro, in un ambiente con poca memoria?

StackOverflow https://stackoverflow.com/questions/742125

  •  09-09-2019
  •  | 
  •  

Domanda

Di recente, in un colloquio tecnico, mi è stato chiesto di scrivere un programma per trovare l'alta frequenza delle parole(Parole che appaiono numero massimo di volte) in un libro di testo.Il programma dovrebbe essere progettato in modo che, elabora l'intero libro di testo con un minimo di memoria.Le prestazioni non è un problema.Sono stato in grado di programma per trovare la frequenza di parole, ma consuma un sacco di memoria.

Come si fa a fare questa operazione in meno di memoria per la cpu?Di eventuali strategie/soluzioni?

-Snehal

È stato utile?

Soluzione

Probabilmente si utilizzino le tabelle hash che sono ad alta intensità di memoria, ma hanno un tempo costante di ricerca - in modo che il commercio prestazioni / memoria off è evidente. Con il tempo si raggiunge la fine del libro si sa la risposta. Inoltre, incrementando i contatori per ogni parola è veloce (a causa delle ricerche tabella di hash veloci).

L'altra estremità dello spettro è quello di guardare la prima parola, poi passare attraverso l'intero libro per vedere quante volte si verifica quella parola. Questo richiede memoria minima. Poi fate lo stesso per la parola successiva e passare attraverso l'intero libro. Se questa parola si verifica più volte, si aggiunge che, come la parola superiore (o top parole N). Naturalmente, questo è estremamente inefficiente -. Se la prima e la terza parola sono gli stessi si finirà per passare attraverso l'intero libro di nuovo, anche se hai appena fatto la stessa cosa per la prima parola

Altri suggerimenti

OK, se siete interessati solo le parole più alte n che si verificano, un modo per farlo è in due passaggi, con il primo passaggio sulla base di una versione modificata Bloom Filter . Invece di utilizzare una mappa di bit per monitorare eventi hash, utilizzare un array intero invece - o byte, 16 bit, 32 bit o 64 bit a seconda delle dimensioni di ingresso. Se un filtro di Bloom semplicemente imposta il bit corrispondente a ciascuno dei valori di hash di una parola, si incrementa il conteggio l'indice hash nella matrice.

Il problema di questo approccio è che due parole probabilmente dare gli stessi valori di hash. Quindi è necessario fare un secondo passaggio in cui si ignorano le parole a meno che i loro totali hash sono al di sopra di una certa soglia, riducendo così la quantità di memoria è necessario allocare per fare un conteggio preciso.

Quindi, basta creare una mappa di bit con bit impostati per i valori hash più alto che si verificano. Poi nel secondo passaggio delle parole, se una parola ha "hits" nella bitmap per le sue hash, guardare in alto o aggiungerlo a una tabella di hash e incrementare il suo conteggio. Questo riduce al minimo l'utilizzo della memoria con la creazione di una tabella hash di solo le parole più alte che si verificano.

Io sono un fisico, quindi il mio preferito è un approccio approssimativo. Non c'è bisogno di passare attraverso l'intero testo per ottenere le parole più frequenti.Invece:

  • analizzare un pezzo abbastanza piccolo da consentire per le limitazioni di memoria,
  • saltare una quantità casuale di testo,
  • ripeto, combinando accumulato risultati.
  • Interrompere se la lista è soddisfacente convergenti.

Se si utilizza una memoria algoritmo efficiente per i blocchi più piccoli (es.ordinamento), allora si può ottenere lontano prestazioni più veloci di quanto anche il più efficiente algoritmo che legge ogni parola.

Nota:Questo fa supporre che le parole più frequenti si verificano più frequentemente in tutto il testo, non solo in un luogo nel testo.Per il testo in inglese, questo assunto è vero, a causa della frequenza di parole come 'la' ecc in tutto.Se siete preoccupati di questo requisito, richiedono l'algoritmo per completare almeno il passaggio di un intero testo.

Io probabilmente scendere-votato a favore ...

Se il testo è inglese e si desidera solo trovare i primi 5 parole più frequenti, qui è il tuo programma: 

print "1. the\n";
print "2. of\n";
print "3. and\n";
print "4. a\n";
print "5. to\n";

corre veloce e consuma il minimo!

Se le prestazioni sono davvero di alcuna preoccupazione si può solo passare attraverso ogni parola a sua volta, controlla se è nel vostro "top N" e, se non lo è, contare tutte le sue occorrenze. In questo modo si sta solo memorizzare i valori N. Naturalmente, devi essere contando le stesse parole molte volte, ma, come hai detto, le prestazioni non è un problema - e il codice sarebbe banale (che è generalmente preferibile - tutti parità di altre condizioni).

Un modo potrebbe essere quello di ordinare l'elenco prima.

Possiamo ordinare le parole-luogo senza un sacco di memoria (scambiati con un rallentamento delle prestazioni).

E poi possiamo avere un semplice loop di conteggio che trova le parole con la massima frequenza senza dover salvare tutto in memoria, dato che sono in forma ordinata.

Vuoi dire un sacco di memoria del processo? Se è così, in un modo potrebbe essere quello di utilizzare il disco come memoria virtuale (aka scrivere un wrapper file system).

Una possibile soluzione è quella di utilizzare un trie struttura dati per memorizzare tutte le parole associate al loro numero di occorrenze.

Altre soluzioni possono essere trovate nelle risposte a questa domanda correlata: Space-Efficient struttura dati per la memorizzazione di una lista di parole?

Come molte domande buona intervista, la domanda è formulata un po 'ambigua / impreciso, per forzare l'intervistato di porre domande chiarificatrici e le ipotesi di stato. Credo che un certo numero di altre risposte qui sono buoni, come si spuntano a questi presupposti e dimostrare grande-picture comprensione.

Sono supponendo che il testo viene memorizzato 'in linea' da qualche parte, ma c'è un modo per iterare su ogni parola nel testo senza caricare l'intero testo in memoria.

Poi il # codice F al di sotto trovare le prime N parole. E 'solo struttura di dati è una mappatura di coppie di valori-chiave (word, frequenza), e mantiene solo la parte superiore N di quelli, quindi l'uso di memoria è O (N), che è piccolo. Il tempo di esecuzione è O (numWordsInText ^ 2), che è scarsa, ma accettabile dato i vincoli del problema. Il nocciolo della algoritmo è semplice, per ogni parola nel testo, contare quante volte si verifica, e se è in corsa best-N, quindi aggiungere alla lista e rimuovere la voce minima precedente.

Si noti che il vero programma sotto carica l'intero testo in memoria, solo per comodità di esposizione. 

#light
// some boilerplate to grab a big piece of text off the web for testing
open System.IO 
open System.Net 
let HttpGet (url: string) = 
    let req = System.Net.WebRequest.Create(url) 
    let resp = req.GetResponse() 
    let stream = resp.GetResponseStream() 
    let reader = new StreamReader(stream) 
    let data = reader.ReadToEnd() 
    resp.Close() 
    data 
let text = HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
let words = text.Split([|' ';'\r';'\n'|], System.StringSplitOptions.RemoveEmptyEntries)
// perhaps 'words' isn't actually stored in memory, but so long as we can 
// 'foreach' over all the words in the text we're good
let N = 5  // how many 'top frequency' words we want to find
let FindMin map =
    // key-value pair with mininum value in a map
    let (Some(seed)) = Map.first (fun k v -> Some(k,v)) map
    map |> Map.fold_left 
        (fun (mk,mv) k v -> if v > mv then (mk,mv) else (k,v)) 
        seed
let Main() =
    let mutable freqCounts = Map.of_list [ ("",0) ]
    for word in words do
        let mutable count = 0
        for x in words do
            if x = word then
                count <- count + 1
        let minStr,minCount = FindMin freqCounts
        if count >= minCount then
            freqCounts <- Map.add word count freqCounts
        if Seq.length freqCounts > N then
            freqCounts <- Map.remove minStr freqCounts
    freqCounts 
    |> Seq.sort_by (fun (KeyValue(k,v)) -> -v) 
    |> Seq.iter (printfn "%A")
Main()

Output: 

[the, 75]
[to, 41]
[in, 34]
[a, 32]
[of, 29]

Si potrebbe utilizzare combinazione di merge esterna sort e coda di priorità . Merge sort farà in modo che i vostri limiti di memoria sono onorati e coda di priorità manterranno le ricerche top K. Ovviamente, la coda di priorità deve essere abbastanza piccolo da stare in memoria.

  • In primo luogo, dividere stringhe in ingresso in blocchi, liste ogni blocco e memorizzare nella memoria secondaria (ordinamento esterno) - O (n log n)
  • Leggi ogni blocco e all'interno del pezzo, calcolare la frequenza di parole, quindi al termine di questa fase, ogni blocco è ridotto a (parola unica - count frequenza) all'interno del pezzo. O (n)
  • Avvia elementi attraverso i pezzi e di aggregazione per ogni parola la lettura. Dal momento che pezzi sono ordinati, è possibile farlo in O (n)
  • Ora, mantenere un mucchio min priorità (superiore del mucchio è elemento minimo nel cumulo) di K elementi. Popolare mucchio priorità primi elementi K poi per il prossimo (conteggio -Final parola unica) , se il conteggio è maggiore di elemento superiore nel mucchio, all'inizio pop e spingere parola corrente. O (n log k)

Così il vostro complessità tempo finale è O (n (log K + log n))        -

Beh, se si vuole assolutamente terribile prestazioni ...

Prendere la prima parola del libro, e contare quante volte si verifica. Prendere la seconda parola del libro, contare quante volte si verifica. Se è più che l'ultima parola, scartare l'ultima parola. E così via ... si finirà per contare le stesse parole più volte a meno che non si mantiene una lista di loro da qualche parte, ma se si davvero vuole ridurre al minimo la memoria, questo dovrebbe richiedere solo pochi int. Dovrebbe essere eseguito in O (n ^ 2), dove n è il numero di parole nel libro.

Che ne dite di creare un albero binario di chiavi di parole (come si continua a leggere le parole dal file). Questo aiuta a cercare le parole già ripetuti nel tempo O (log (n)). Così alla fine si ottiene O (nCollegatevi (n)) per la ricerca di parola superiore.

Basic algo sarebbe

per ogni parola in un file:

  1. Creare chiave univoca per una data parola (ascii ponderato char esempio "bat" potrebbe essere 1 * 'b' + 2 * 'a' + 3 * 'c';
  2. Aggiungi questa parola per l'albero. Se la parola è già esistente incremento del nuovo conteggio.
  3. Alimentare la parola e il conteggio corrente per maintainTop5 (parola, conteggio). maintainTop5 () mantiene una lista dinamica di conteggi Top5 e parole associate.

Fine del file avete top 5 parole.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top