Finde n häufigste Wörter in einer Datei

Ich möchte beispielsweise die 10 häufigsten Wörter in einer Textdatei finden. Erstens sollte die Lösung für Tastenanschläge optimiert werden (mit anderen Worten - meine Zeit). Zweitens für die Leistung. Folgendes muss ich bisher für die Top 10 tun:

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

Ich könnte ein Java-, Python- usw. Programm erstellen, in dem ich (word, numberOfOccurences) in einem Wörterbuch speichere und den Wert sortiere, oder ich könnte MapReduce verwenden, aber ich optimiere für Tastenanschläge.

Gibt es falsche Positive? Gibt es einen besseren Weg?

Das ist so ziemlich die gebräuchlichste Methode, "N gebräuchlichste Dinge" zu finden, mit der Ausnahme, dass Sie eine verpassen sortund eine unentgeltliche haben cat:

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

Wenn Sie kein sortvor dem uniq -c eingeben, werden Sie wahrscheinlich eine Menge falscher Singleton-Wörter erhalten. uniqNur eindeutige Linienfolgen, keine allgemeine Einheitlichkeit.

EDIT: Ich habe einen Trick vergessen, "Worte anhalten". Wenn Sie sich englischen Text ansehen (sorry, hier einsprachig nordamerikanisch), nehmen Wörter wie "von", "und" die "fast immer die ersten zwei oder drei Plätze ein. Sie wollen sie wahrscheinlich beseitigen. In der GNU Groff-Distribution befindet sich eine Datei mit dem Namen eign, die eine anständige Liste von Stoppwörtern enthält. Meine Arch Distribution hat /usr/share/groff/current/eign, aber ich glaube ich habe auch alte Unixe gesehen /usr/share/dict/eignoder /usr/dict/eignin.

Sie können Stoppwörter wie diese verwenden:

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

Ich vermute, dass die meisten menschlichen Sprachen ähnliche "Stoppwörter" benötigen, die aus den aussagekräftigen Worthäufigkeitszählungen entfernt wurden, aber ich weiß nicht, wo ich vorschlagen soll, Stoppwörterlisten für andere Sprachen zu erhalten.

BEARBEITEN: fgrep sollte den -wBefehl verwenden, der die Ganzwortübereinstimmung ermöglicht. Dies vermeidet Fehlalarme bei Wörtern, die nur kurze Stopp-Werke enthalten, wie "a" oder "i".

Das funktioniert besser mit utf-8:

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

Lass uns AWK benutzen!

Diese Funktion listet die Häufigkeit jedes in der angegebenen Datei vorkommenden Wortes in absteigender Reihenfolge auf:

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
}

Sie können es folgendermaßen in Ihrer Datei aufrufen:

$ cat your_file.txt | wordfrequency

und für die Top 10 Wörter:

$ cat your_file.txt | wordfrequency | head -10

Quelle: AWK-Station Ruby

Lass uns Haskell benutzen!

Das wird zu einem Sprachkrieg, nicht wahr?

import Data.List
import Data.Ord

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

Verwendung:

cat input | wordfreq

Alternative:

cat input | wordfreq | head -10

So etwas sollte mit Python funktionieren, das allgemein verfügbar ist:

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

Dies setzt ein Wort pro Zeile voraus. Wenn es mehr gibt, sollte das Teilen auch einfach sein.

Dies ist ein klassisches Problem, das 1986 einige Resonanz fand, als Donald Knuth eine schnelle Lösung mit Hash-Versuchen in einem 8-seitigen Programm implementierte , um seine literarische Programmiertechnik zu veranschaulichen, während Doug McIlroy, der Pate von Unix-Pipes, mit einem antwortete Einzeiler, das war nicht so schnell, hat aber die Arbeit erledigt:

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

Natürlich hat McIlroys Lösung die Zeitkomplexität O (N log N), wobei N eine Gesamtzahl von Wörtern ist. Es gibt viel schnellere Lösungen. Beispielsweise:

Hier ist eine C ++ - Implementierung mit der oberen zeitlichen Komplexität O ((N + k) log k), typischerweise - nahezu linear.

Im Folgenden finden Sie eine schnelle Python-Implementierung unter Verwendung von Hash-Wörterbüchern und Heap mit Zeitkomplexität O (N + k log Q), wobei Q eine Reihe eindeutiger Wörter ist:

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)

CPU-Zeitvergleich (in Sekunden):

                                     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

Anmerkungen:

• bible32 ist die Bibel, die 32 Mal (135 MB), bible256 - 256 Mal (1,1 GB) mit sich selbst verknüpft ist.
• Die nichtlineare Verlangsamung von Python-Skripten wird allein durch die Tatsache verursacht, dass Dateien vollständig im Speicher verarbeitet werden, sodass der Overhead für große Dateien immer größer wird.
• Wenn es ein Unix-Tool gäbe, das einen Heap konstruieren und n Elemente von der Spitze des Heaps auswählen könnte, könnte die AWK-Lösung eine nahezu lineare Zeitkomplexität erreichen, während sie derzeit O (N + Q log Q) ist.