encontrar n palabras más frecuentes en un archivo

34

Quiero encontrar, digamos, las 10 palabras más comunes en un archivo de texto. En primer lugar, la solución debe optimizarse para las pulsaciones de teclas (en otras palabras, mi tiempo). En segundo lugar, por el rendimiento. Esto es lo que tengo hasta ahora para llegar al top 10:

cat test.txt | tr -c '[:alnum:]' '[\n*]' | uniq -c | sort -nr | head  -10
  6 k
  2 g
  2 e
  2 a
  1 r
  1 k22
  1 k
  1 f
  1 eeeeeeeeeeeeeeeeeeeee
  1 d

Podría hacer un programa java, python, etc. donde almaceno (word, numberOfOccurences) en un diccionario y ordenar el valor o podría usar MapReduce, pero optimizo para las pulsaciones de teclas.

¿Hay algún falso positivo? ¿Hay una mejor manera?

Lukasz Madon
fuente
¿por qué pondrías un -10 al final? : P
anu

Respuestas:

47

Esa es más o menos la forma más común de encontrar "N cosas más comunes", excepto que te falta una sort, y tienes un servicio gratuito cat:

tr -c '[:alnum:]' '[\n*]' < test.txt | sort | uniq -c | sort -nr | head  -10

Si no pone un sortantes uniq -c , probablemente obtendrá muchas palabras únicas falsas. uniqsolo ejecuta líneas únicas, no uniquness general.

EDITAR: Olvidé un truco, "deja de palabras". Si está buscando texto en inglés (lo siento, aquí en América del Norte monolingüe), palabras como "de", "y", "el" casi siempre ocupan los primeros dos o tres lugares. Probablemente quieras eliminarlos. La distribución GNU Groff tiene un archivo llamado eignque contiene una lista bastante decente de palabras de detención. Mi distribución de Arch sí /usr/share/groff/current/eign, pero creo que también he visto /usr/share/dict/eigno /usr/dict/eignen viejos Unixes.

Puede usar palabras de detención como esta:

tr -c '[:alnum:]' '[\n*]' < test.txt |
fgrep -v -w -f /usr/share/groff/current/eign |
sort | uniq -c | sort -nr | head  -10

Supongo que la mayoría de los idiomas humanos necesitan "palabras de detención" similares eliminadas de los recuentos significativos de frecuencia de palabras, pero no sé dónde sugerir que otros idiomas detengan las listas de palabras.

EDITAR: fgrep debe usar el -wcomando, que permite la coincidencia de palabras completas. Esto evita falsos positivos en palabras que simplemente contienen trabajos de parada corta, como "a" o "i".

Bruce Ediger
fuente
2
¿ catAgrega alguna sobrecarga de rendimiento significativo? Me gusta la sintaxis de la tubería. ¿Qué hace el * en '[\ n *]'?
Lukasz Madon
1
Si te gusta el "cat test.txt", entonces úsalo. Leí un artículo en algún lugar en el que Dennis Ritchie dice que la sintaxis "gato algo | alguna cosa" se usa más ampliamente, y que la sintaxis '<algo' fue un error, ya que tiene un solo propósito.
Bruce Ediger
¿Qué sucede si quiero encontrar el nombre de directorio más común en una findsalida? Es decir, dividir palabras en /lugar de caracteres de espacio en blanco y similares.
erb
1
@erb - probablemente harías algo como:find somewhere optoins | tr '/' '\n' | sort | uniq -c | sort -k1.1nr | head -10
Bruce Ediger
1
@erb: hazlo como una pregunta, no en un comentario. Tendrá más espacio para formular su pregunta, a fin de obtener la respuesta que necesita. Dé ejemplo de entrada y salida deseada. Puede obtener algunos puntos de reputación por hacer una buena pregunta, y obtendré puntos por dar una mejor respuesta de la que puedo en un comentario.
Bruce Ediger
8

Esto funciona mejor con utf-8:

$ sed -e 's/\s/\n/g' < test.txt | sort | uniq -c | sort -nr | head  -10
Vladislav Schogol
fuente
7

¡Usemos AWK!

Esta función enumera la frecuencia de cada palabra que aparece en el archivo proporcionado en orden descendente:

function wordfrequency() {
  awk '
     BEGIN { FS="[^a-zA-Z]+" } {
         for (i=1; i<=NF; i++) {
             word = tolower($i)
             words[word]++
         }
     }
     END {
         for (w in words)
              printf("%3d %s\n", words[w], w)
     } ' | sort -rn
}

Puede llamarlo en su archivo así:

$ cat your_file.txt | wordfrequency

y para las 10 palabras principales:

$ cat your_file.txt | wordfrequency | head -10

Fuente: AWK-ward Ruby

Sheharyar
fuente
4

¡Usemos Haskell!

Esto se está convirtiendo en una guerra de idiomas, ¿no?

import Data.List
import Data.Ord

main = interact $ (=<<) (\x -> show (length x) ++ " - " ++ head x ++ "\n")
                . sortBy (flip $ comparing length)
                . group . sort
                . words

Uso:

cat input | wordfreq

Alternativamente:

cat input | wordfreq | head -10
Alondra
fuente
una versión modificada ignorando el caso: pastebin.com/57T5B6BY
Axel Latvala
Funciona mucho más lento que el clásico sort | uniq -c | sort -nr.
Andriy Makukha
@AndriyMakukha El cuello de botella es que las cadenas son listas vinculadas de caracteres en Haskell. Podríamos obtener C-como las velocidades de conmutación a Text, o ByteStringen lugar, lo cual es tan simple como su importación calificado y anteponiendo las funciones con el calificador.
BlackCap
pastebin.com/QtJjQwT9 versión significativamente más rápida, escrita para
facilitar la
3

Algo como esto debería funcionar usando Python, que está comúnmente disponible:

cat slowest-names.log | python -c 'import collections, sys; print collections.Counter(sys.stdin);'

Esto supone palabra por línea. Si hay más, la división también debería ser fácil.

Reut Sharabani
fuente
Python3 y salida más agradablecat README.md | python -c 'import collections, sys, pprint; pprint.pprint(collections.Counter(sys.stdin));'
Lukasz Madon
1

Este es un problema clásico que tuvo cierta resonancia en 1986, cuando Donald Knuth implementó una solución rápida con pruebas hash en un programa de 8 páginas para ilustrar su técnica de programación alfabetizada, mientras que Doug McIlroy, el padrino de las pipas de Unix, respondió con un one-liner, eso no fue tan rápido, pero hizo el trabajo:

tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed 10q

Por supuesto, la solución de McIlroy tiene una complejidad de tiempo O (N log N), donde N es un número total de palabras. Hay soluciones mucho más rápidas. Por ejemplo:

Aquí hay una implementación de C ++ con la complejidad de tiempo límite superior O ((N + k) log k), típicamente, casi lineal.

A continuación se muestra una implementación rápida de Python usando diccionarios hash y montón con complejidad de tiempo O (N + k log Q), donde Q es una cantidad de palabras únicas:

import collections, re, sys

filename = sys.argv[1]
k = int(sys.argv[2]) if len(sys.argv)>2 else 10

text = open(filename).read()
counts = collections.Counter(re.findall('[a-z]+', text.lower()))
for i, w in counts.most_common(k):
    print(i, w)

Comparación de tiempo de CPU (en segundos):

                                     bible32       bible256
C++ (prefix tree + heap)             5.659         44.730  
Python (Counter)                     10.314        100.487
Sheharyar (AWK + sort)               30.864        251.301
McIlroy (tr + sort + uniq)           60.531        690.906

Notas:

  • bible32 es una Biblia concatenada consigo misma 32 veces (135 MB), bible256 - 256 veces respectivamente (1.1 GB).
  • La ralentización no lineal de los scripts de Python se debe únicamente al hecho de que procesa los archivos por completo en la memoria, por lo que los gastos generales son cada vez mayores para los archivos de gran tamaño.
  • Si hubiera una herramienta Unix que pudiera construir un montón y seleccionar n elementos desde la parte superior del montón, la solución AWK podría lograr una complejidad temporal casi lineal, mientras que actualmente es O (N + Q log Q).
Andriy Makukha
fuente