it-swarm-eu.dev

najděte n nejčastějších slov v souboru

Chci najít, řekněme, 10 nejběžnějších Word v textovém souboru. Za prvé, řešení by mělo být optimalizováno pro stisknutí kláves (jinými slovy - můj čas). Za druhé, za představení. Zde je to, co mám zatím, abych získal 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

Mohl bych vytvořit program Java, python atd.), Kde uložím (Word, numberOfOccurences) do slovníku a třídí hodnotu nebo mohu použít MapReduce, ale optimalizuji pro stisknutí kláves.

Existují nějaké falešné pozitivy? Existuje lepší způsob?

command-lineshell-script
34
Lukasz Madon

To je téměř nejběžnější způsob, jak najít "N nejběžnějších věcí", kromě toho, že vám chybí sort, a máte bezdůvodné cat:

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

Pokud nezadáte sort před uniq -c, Pravděpodobně dostanete spoustu falešných singletonových slov. uniq provádí pouze jedinečné běhy linek, ne celkově uniquness.

EDIT: Zapomněl jsem trik, "stop slova". Pokud se díváte na anglický text (promiňte, jednojazyčný severoameričan zde), slova jako „z“, „a“, „“ „téměř vždy zaujmou horní dvě nebo tři místa. Pravděpodobně je chcete odstranit. Distribuce Groff GNU Groff) obsahuje soubor s názvem eign, který obsahuje docela slušný seznam stop slov. Můj Arch distro má /usr/share/groff/current/eign, Ale myslím, že jsem Také jsem viděl /usr/share/dict/eign nebo /usr/dict/eign ve starých Unixech.

Můžete použít zastavovací slova jako je tato:

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

Domnívám se, že většina lidských jazyků potřebuje podobná „zastavovací slova“ odebraná z významného počtu slov, ale nevím, kde navrhnout získání dalších jazykových seznamů zastavovacích slov.

EDIT:fgrep by měl použít příkaz -w, Který umožňuje porovnávání celého slova. Tím se zabrání falešně pozitivním slovům, která obsahují pouze krátké zastávky, například „a“ nebo „i“.

50
Bruce Ediger

Toto funguje lépe s utf-8:

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

Pojďme použít AWK!

Tato funkce uvádí frekvenci každého slova vyskytujícího se v poskytovaném souboru v sestupném pořadí:

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
}

Můžete to nazvat do svého souboru takto:

$ cat your_file.txt | wordfrequency

a pro prvních 10 slov:

$ cat your_file.txt | wordfrequency | head -10

Zdroj: AWK-ward Ruby

7
Sheharyar

Pojďme použít Haskell!

Z toho se stává jazyková válka, že?

import Data.List
import Data.Ord

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

Používání:

cat input | wordfreq

Alternativně:

cat input | wordfreq | head -10
4
BlackCap

Toto je klasický problém, který dostal určitou rezonanci v roce 1986, kdy Donald Knuth implementoval rychlé řešení s hashovými pokusy v 8stránkovém programu, který ilustruje jeho gramotnou programovací techniku, zatímco Doug McIlroy, kmotr trubek Unixu, odpověděných jednostrannou vložkou, to nebylo tak rychlé, ale práce byla dokončena:

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

Řešení společnosti McIlroy má samozřejmě časovou složitost O (N log N), kde N je celkový počet slov. Existuje mnohem rychlejší řešení. Například:

Zde je implementace C++ s horní časovou složitostí O ((N + k) log k), obvykle - téměř lineární.

Níže je uvedena rychlá implementace Python implementace pomocí hash slovníků a haldy s časovou složitostí O (N + k log Q), kde Q je množství jedinečných slov:

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)

Here je extrémně rychlé řešení v Rust) od Anders Kaseorg.

Porovnání času procesoru (v sekundách):

                                     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

Poznámky:

  • bible32 je Bible zřetězená sama sebou 32krát (135 MB), bible256 - 256krát (1,1 GB).
  • Nelineární zpomalení skriptů Pythonu je způsobeno čistě skutečností, že zpracovává soubory zcela v paměti, takže režijní náklady se pro velké soubory zvětšují.
  • Pokud by existoval nástroj Unix, který by mohl sestavit haldu a vybrat n prvků z vrcholu haldy, mohlo by řešení AWK dosáhnout téměř lineární složitosti času, zatímco v současné době je to O (N + Q log Q).
3
Andriy Makukha

Něco takového by mělo fungovat při použití python, který je běžně k dispozici:

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

Toto předpokládá slovo na řádek. Pokud jich je více, mělo by být rozdělení také snadné.

3
Reut Sharabani