trouve n mots les plus fréquents dans un fichier

Je veux trouver, disons, 10 mots les plus courants dans un fichier texte. Premièrement, la solution doit être optimisée pour les frappes au clavier (autrement dit, à mon heure). Deuxièmement, pour la performance. Voici ce que j'ai jusqu'à présent pour faire partie du 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

Je pourrais créer un programme java, python, etc. dans lequel je stockerais (mot, numberOfOccurences) dans un dictionnaire et trierais la valeur, ou je pourrais utiliser MapReduce, mais j'optimisais pour les frappes au clavier.

Y a-t-il des faux positifs? Y a-t-il un meilleur moyen?

C'est à peu près la façon la plus courante de trouver "N choses les plus communes", sauf qu'il vous manque un sort, et vous avez un gratuit cat:

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

Si vous ne le mettez pas sortavant, uniq -c vous obtiendrez probablement beaucoup de faux mots singleton. uniqne fait que des longueurs de lignes uniques, pas uniques.

EDIT: J'ai oublié un truc, "mots d'arrêt". Si vous regardez le texte anglais (désolé, monolingue nord-américain ici), des mots comme "of", "and", "the" prennent presque toujours les deux ou trois premières places. Vous voulez probablement les éliminer. La distribution GNU Groff a un fichier nommé eignqui contient une liste assez décente de mots vides. Ma distribution Arch a /usr/share/groff/current/eign, mais je pense que j'ai aussi vu /usr/share/dict/eignou /usr/dict/eigndans les anciens Unix.

Vous pouvez utiliser des mots vides comme celui-ci:

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

Mon hypothèse est que la plupart des langues humaines ont besoin de "mots vides" similaires supprimés du nombre de mots significatifs, mais je ne sais pas où suggérer d'obtenir d'autres langues une liste de mots vides.

EDIT: fgrep devrait utiliser la -wcommande, qui active la correspondance de mot entier. Cela évite les faux positifs sur les mots qui contiennent uniquement des arrêts brefs, tels que "a" ou "i".

Cela fonctionne mieux avec utf-8:

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

Utilisons AWK!

Cette fonction répertorie la fréquence de chaque mot apparaissant dans le fichier fourni par ordre décroissant:

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
}

Vous pouvez l'appeler sur votre fichier comme ceci:

$ cat your_file.txt | wordfrequency

et pour le top 10 des mots:

$ cat your_file.txt | wordfrequency | head -10

Source: AWK-ward Ruby

Utilisons Haskell!

Cela se transforme en une guerre de la langue, n'est-ce pas?

import Data.List
import Data.Ord

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

Usage:

cat input | wordfreq

Alternativement:

cat input | wordfreq | head -10

Quelque chose comme cela devrait fonctionner avec Python, qui est couramment disponible:

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

Cela suppose mot par ligne. S'il y en a plus, le fractionnement devrait également être facile.

C’est un problème classique qui a trouvé un écho en 1986, lorsque Donald Knuth a implémenté une solution rapide avec essais de hachage dans un programme de 8 pages pour illustrer sa technique de programmation, alors que Doug McIlroy, parrain des tubes Unix, répondait par un one-line, ce n’était pas aussi rapide, mais le travail était fait:

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

Bien entendu, la solution de McIlroy a une complexité temporelle O (N log N), où N est un nombre total de mots. Il existe des solutions beaucoup plus rapides. Par exemple:

Voici une implémentation C ++ avec la complexité temporelle supérieure O ((N + k) log k), généralement - presque linéaire.

Ci-dessous, une implémentation rapide de Python utilisant des dictionnaires de hachage et des tas avec une complexité temporelle O (N + k log Q), où Q est un nombre de mots uniques:

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)

Voici une solution extrêmement rapide dans Rust par Anders Kaseorg.

Comparaison du temps de calcul (en secondes):

                                     bible32       bible256
Rust (prefix tree)                   0.632         5.284
C++ (prefix tree + heap)             4.838         38.587
Python (Counter)                     9.851         100.487
Sheharyar (AWK + sort)               30.071        251.301
McIlroy (tr + sort + uniq)           60.251        690.906

Remarques:

• bible32 est concaténé par la Bible 32 fois (135 Mo), bible256 - 256 fois (1,1 Go).
• Le ralentissement non linéaire des scripts Python est uniquement dû au fait qu'il traite les fichiers complètement en mémoire, de sorte que les frais généraux augmentent pour les fichiers volumineux.
• S'il existait un outil Unix capable de construire un segment de mémoire et de sélectionner n éléments dans la partie supérieure du segment, la solution AWK pourrait atteindre une complexité temporelle quasi linéaire, alors qu'actuellement il s'agit de O (N + Q log Q).