¿Cómo encontrar palabras de alta frecuencia en un libro en un entorno con poca memoria?

Question

Recientemente, en una entrevista técnica, me pidieron que escribiera un programa para encontrar las palabras de uso frecuente (palabras que aparecen el número máximo de veces) en un libro de texto. El programa debe diseñarse de tal manera que procese todo el libro de texto con la memoria mínima. El rendimiento no es una preocupación. Pude programar para encontrar la frecuencia de palabras, pero consumió mucha memoria.

¿Cómo hace que esta operación requiera menos memoria? ¿Alguna estrategia/solución?

-Snehal

Answer 1

Probablemente haya utilizado tablas hash que requieren mucha memoria pero tienen un tiempo de búsqueda constante, por lo que la compensación de rendimiento/memoria es obvia. Cuando llegue al final del libro, sabrá su respuesta. Además, el incremento de contadores para cada palabra es rápido (debido a las búsquedas rápidas de hashtable).

El otro extremo del espectro es mirar la primera palabra, luego examinar todo el libro para ver cuántas veces ocurre esa palabra. Esto requiere una memoria mínima. Luego haces lo mismo para la siguiente palabra y revisas todo el libro. Si esa palabra aparece más veces, agregue eso como la palabra más alta (o las N palabras superiores). Por supuesto, esto es extremadamente ineficiente: si la primera y la tercera palabra son las mismas, terminarás repasando todo el libro nuevamente aunque hayas hecho lo mismo para la primera palabra.

Answer 2

Una forma sería la primera para ordenar la lista.

Podemos ordenar las palabras in situ sin mucha memoria (comercializadas con rendimiento lento).

Y luego podemos tener un simple bucle de conteo que encuentra palabras con la máxima frecuencia sin tener que guardar todo en la memoria ya que están en forma ordenada.

Answer 3

¿Te refieres a una gran cantidad de memoria de proceso? Si es así, una forma sería usar el disco como memoria virtual (también conocido como escribir un contenedor de sistema de archivos).

Answer 4

Si el rendimiento no es importante, puede revisar cada palabra, verifique si está en su "N superior" y, de lo contrario, cuente todas las ocurrencias. De esta forma solo almacenas N valores. Por supuesto, estarías contando las mismas palabras muchas veces, pero, como dijiste, el rendimiento no es un problema, y ​​el código sería trivial (que generalmente es preferible, en igualdad de condiciones).

Answer 5

Una posible solución es utilizar una estructura de datos trie para almacenar todas las palabras asociadas a su número de apariciones.

Otras soluciones pueden encontrarse en las respuestas a esta pregunta relacionada: Space-Efficient Data Structure for Storing a Word List?

Answer 6

bien, si usted está interesado sólo en el más alto n ocurren palabras, una forma de hacerlo es en dos pasadas, con el primer pase basado en un Bloom Filter modificado. En lugar de utilizar un mapa de bits para rastrear las ocurrencias de hash, utilice una matriz de enteros en su lugar, ya sea byte, 16 bit, 32 bit o incluso 64 bit, dependiendo del tamaño de su entrada. Cuando un filtro Bloom simplemente establece el bit correspondiente a cada uno de los valores hash de una palabra, aumentará el conteo en el índice hash en la matriz.

El problema con este enfoque es que dos palabras probablemente den los mismos valores hash. Por lo tanto, debe hacer una segunda pasada donde ignore las palabras a menos que sus totales de hash estén por encima de un cierto umbral, reduciendo así la cantidad de memoria que necesita asignar para realizar un conteo preciso.

Así que solo cree un mapa de bits con los bits establecidos para los valores de hash más altos que se producen. Luego, en el segundo paso de las palabras, si una palabra tiene "hits" en el mapa de bits para sus hash, búscalo o agrégalo a una tabla hash e incrementa su conteo. Esto minimiza el uso de memoria al crear una tabla hash de solo las palabras más altas que ocurren.

Answer 7

Soy físico, por lo que mi enfoque favorito es aproximarme. No necesita pasar por el texto completo para obtener las palabras más frecuentes. En su lugar:

• analizar un trozo lo suficientemente pequeño como para permitir a sus limitaciones de memoria,
• saltar una cantidad aleatoria de texto,
• repetición, la combinación de resultados acumulados.
• Detener cuando la lista haya convergido satisfactoriamente.

Si utiliza un algoritmo eficiente para memoria de las partes más pequeñas (por ejemplo, clasificación), entonces puede obtener rendimiento mucho más rápido que incluso el algoritmo más eficiente que lee cada palabra.

Nota: Esto supone que las palabras más frecuentes ocurren con mayor frecuencia en todo el texto, no solo en un lugar del texto. Para el texto en inglés, esta suposición es verdadera, debido a la frecuencia de palabras como 'the', etc. Si le preocupa este requisito, solicite que el algoritmo complete al menos una pasada del texto completo.

Answer 8

que probablemente obtendrá abajo votado para este ...

Si el texto es Inglés y lo que desea encontrar los 5 mejores palabras más frecuentes, aquí es su programa:

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

¡Funciona rápido y consume memoria mínima!

Answer 9

Al igual que muchas buenas preguntas de la entrevista, la pregunta se formula de forma un tanto ambigua/imprecisa, para obligar al entrevistado a hacer preguntas aclaratorias y suposiciones del estado. Creo que algunas de las otras respuestas aquí son buenas, ya que abordan estas suposiciones y demuestran una comprensión a gran escala.

Estoy asumiendo que el texto se almacena 'offline' en alguna parte, pero hay una manera de iterar sobre cada palabra en el texto sin cargar todo el texto en la memoria.

Luego el código F # a continuación encuentra las N palabras superiores. Solo la estructura de datos es un mapeo de pares clave-valor (palabra, frecuencia), y solo mantiene el N superior de esos, por lo que el uso de la memoria es O (N), que es pequeño. El tiempo de ejecución es O (numWordsInText^2), que es pobre, pero aceptable dadas las limitaciones del problema. La esencia del algoritmo es simple, para cada palabra en el texto, cuente cuántas veces ocurre, y si está en el mejor N en ejecución, entonces agréguelo a la lista y elimine la entrada mínima anterior.

Tenga en cuenta que el programa actual a continuación carga todo el texto en la memoria, simplemente por comodidad de la exposición.

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

Salida:

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

Answer 10

Bueno, si quieres un rendimiento absolutamente terrible ...

Haga la primera palabra en el libro, y contar cuántas veces se produce. Tome la segunda palabra en el libro, cuente cuántas veces ocurre. Si es más que la última palabra, descarta la última palabra. Y así sucesivamente ... terminará contando las mismas palabras varias veces a menos que guarde una lista de ellas en algún lugar, pero si realmente desea minimizar la memoria, esto solo debería requerir unos pocos intentos. Debe ejecutarse en O (n^2) tiempo, donde n es el número de palabras en el libro.

Answer 11

¿Qué tal crear un árbol binario de teclas de palabras (mientras sigues leyendo las palabras del archivo). Esto ayuda a buscar las palabras ya repetidas en O (Log (n)). Así que finalmente obtienes O (nLog (n)) para la búsqueda de palabras clave.

Básico algo sería

para cada palabra en un archivo:

1. Crear clave única para una palabra dada (ascii ponderada carbón por ejemplo, "bat" podría ser 1 * 'b' + 2 * 'a' + 3 * 'c';
2. Añadir esta palabra al árbol Si la palabra ya existe incremento de la nueva cuenta de
3. Alimentar a la palabra y la cuenta corriente a maintainTop5 (palabra, cuente) maintainTop5 (...) mantiene una lista dinámica de los recuentos top5 y las palabras asociadas.

El final del archivo tiene 5 palabras principales.

Answer 12

Puede usar la combinación de combinación externa ordenar y cola de prioridad. Merge sort se asegurará de que sus límites de memoria se cumplan y la cola de prioridad mantendrá sus principales búsquedas de K. Obviamente, la cola de prioridad debe ser lo suficientemente pequeña como para caber en la memoria.

• En primer lugar, dividir las cadenas de entrada en trozos, una especie cada trozo y almacenar en el almacenamiento secundario (clasificación externa) - O (n log n)
• Leer cada trozo y dentro del trozo, calcular la frecuencia de las palabras, por lo al final de este paso, cada fragmento se reduce a (recuento único de palabras y frecuencia) dentro del fragmento. O (n)
• Comienza a leer los elementos en los trozos y agrega para cada palabra. Como los trozos están ordenados, puede hacerlo en O (n)
• Ahora, mantenga un montón de prioridad mínimo (la parte superior del montón es el elemento mínimo en el montón) de elementos K. Rellene el montón de prioridad con los primeros elementos K y luego con el siguiente (palabra única -contexto final), si su recuento es mayor que el elemento superior en el montón, el encabezado emergente y la palabra actual de inserción. O (n log k)

lo tanto, su complejidad en tiempo final es O (n (log k + log n)) -