znajdź n najczęstszych słów w pliku

Chcę znaleźć, powiedzmy, 10 najczęstszych słów w pliku tekstowym. Po pierwsze, rozwiązanie powinno być zoptymalizowane pod kątem naciśnięć klawiszy (innymi słowy - mojego czasu). Po drugie, za występ. Oto, co mam do tej pory, aby uzyskać 10 najlepszych:

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

Mógłbym stworzyć program Java, Python itp., W którym przechowuję (słowo, liczbaOfOccurences) w słowniku i sortuję wartość lub mogę użyć MapReduce, ale optymalizuję naciśnięcia klawiszy.

Czy są jakieś fałszywe alarmy? Czy jest lepszy sposób?

To prawie najczęstszy sposób na znalezienie „N najczęstszych rzeczy”, z tym wyjątkiem, że brakuje sortCi i masz za darmo cat:

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

Jeśli nie wpiszesz sortwcześniej uniq -c , prawdopodobnie uzyskasz wiele fałszywych singletonów. uniqrobi tylko unikalne przebiegi linii, a nie ogólną unikalność.

EDYCJA: Zapomniałem sztuczki „stop words”. Jeśli patrzysz na tekst w języku angielskim (przepraszam, jednojęzyczny tutaj w Ameryce Północnej), słowa takie jak „of”, „and”, „the” prawie zawsze zajmują pierwsze dwa lub trzy miejsca. Prawdopodobnie chcesz je wyeliminować. W dystrybucji GNU Groff znajduje się plik o nazwie eign, który zawiera całkiem przyzwoitą listę słów kluczowych. Moja dystrybucja Arch ma /usr/share/groff/current/eign, ale myślę, że widziałem też /usr/share/dict/eignlub /usr/dict/eignw starych Uniksach.

Możesz użyć takich słów zatrzymania:

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

Domyślam się, że większość ludzkich języków potrzebuje podobnych „słów kluczowych” usuniętych z liczącej częstotliwości słów, ale nie wiem, gdzie sugerować, aby uzyskać listy słów kluczowych innych języków.

EDYCJA: fgrep należy użyć -wpolecenia, które umożliwia dopasowanie całego słowa. Pozwala to uniknąć fałszywych trafień w słowach, które zawierają jedynie krótkie zatrzymania, takie jak „a” lub „i”.

Działa to lepiej z utf-8:

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

Użyjmy AWK!

Ta funkcja wyświetla częstotliwość każdego słowa występującego w dostarczonym pliku w porządku malejącym:

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
}

Możesz wywołać go w swoim pliku w następujący sposób:

$ cat your_file.txt | wordfrequency

i dla 10 najważniejszych słów:

$ cat your_file.txt | wordfrequency | head -10

Źródło: AWK-ward Ruby

Użyjmy Haskell!

To zamienia się w wojnę językową, prawda?

import Data.List
import Data.Ord

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

Stosowanie:

cat input | wordfreq

Alternatywnie:

cat input | wordfreq | head -10

Coś takiego powinno działać przy użyciu powszechnie dostępnego Pythona:

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

To zakłada słowo w wierszu. Jeśli jest ich więcej, podział również powinien być łatwy.

Jest to klasyczny problem, który zyskał rezonans w 1986 roku, kiedy Donald Knuth wdrożył szybkie rozwiązanie z hashami w 8-stronicowym programie ilustrującym jego umiejętność programowania, podczas gdy Doug McIlroy, ojciec chrzestny uniksowych rur, odpowiedział: one-liner, to nie było tak szybkie, ale wykonało zadanie:

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

Oczywiście rozwiązanie McIlroya ma złożoność czasową O (N log N), gdzie N jest całkowitą liczbą słów. Istnieją znacznie szybsze rozwiązania. Na przykład:

Oto implementacja C ++ z górną granicą złożoności czasowej O ((N + k) log k), zwykle - prawie liniowa.

Poniżej znajduje się szybka implementacja Pythona z użyciem słowników mieszających i sterty o złożoności czasowej O (N + k log Q), gdzie Q jest liczbą unikalnych słów:

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)

Porównanie czasu procesora (w sekundach):

                                     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

Uwagi:

• Biblia 32 jest połączona z Biblią 32 razy (135 MB), Biblia 256 - 256 razy (1,1 GB).
• Nieliniowe spowolnienie skryptów w języku Python wynika wyłącznie z faktu, że pliki są przetwarzane całkowicie w pamięci, więc koszty rosną w przypadku dużych plików.
• Gdyby istniało narzędzie uniksowe, które mogłoby zbudować stertę i wybrać n elementów z wierzchu sterty, rozwiązanie AWK mogłoby osiągnąć złożoność czasową prawie liniową, podczas gdy obecnie jest to O (N + Q log Q).