encontre n palavras mais frequentes em um arquivo

Quero encontrar, digamos, 10 palavras mais comuns em um arquivo de texto. Em primeiro lugar, a solução deve ser otimizada para pressionar as teclas (em outras palavras - o meu tempo). Em segundo lugar, pelo desempenho. Aqui está o que eu tenho até agora para obter o 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

Eu poderia criar um programa em java, python etc. onde armazeno (palavra, numberOfOccurences) em um dicionário e classifico o valor ou posso usar o MapReduce, mas otimizo para pressionar as teclas.

Existem falsos positivos? Existe uma maneira melhor?

Essa é a maneira mais comum de encontrar "N coisas mais comuns", exceto que você está perdendo um sorte recebe um brinde cat:

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

Se você não escrever sortantes, uniq -c provavelmente terá muitas palavras falsas em singleton. uniqsomente executa linhas únicas, não a exclusividade geral.

EDIT: esqueci um truque, "pare palavras". Se você estiver visualizando o texto em inglês (desculpe, monolíngue na América do Norte aqui), palavras como "of", "e", "the" quase sempre ocupam os dois ou três primeiros lugares. Você provavelmente deseja eliminá-los. A distribuição GNU Groff tem um arquivo nomeado eign, que contém uma lista bastante decente de palavras de parada. Minha distro Arch tem /usr/share/groff/current/eign, mas acho que também vi /usr/share/dict/eignou /usr/dict/eignnos Unixes antigos.

Você pode usar palavras de parada assim:

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

Meu palpite é que a maioria das línguas humanas precisa de "palavras de parada" semelhantes removidas das contagens significativas de frequência de palavras, mas não sei onde sugerir a obtenção de outras línguas nas listas de palavras de parada.

EDIT: fgrep deve usar o -wcomando, que permite a correspondência de palavras inteiras. Isso evita falsos positivos em palavras que apenas contêm trabalhos de parada curta, como "a" ou "i".

Isso funciona melhor com o utf-8:

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

Vamos usar o AWK!

Esta função lista a frequência de cada palavra que ocorre no arquivo fornecido em ordem decrescente:

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
}

Você pode chamá-lo em seu arquivo assim:

$ cat your_file.txt | wordfrequency

e para as 10 principais palavras:

$ cat your_file.txt | wordfrequency | head -10

Fonte: Ruby da ala AWK

Vamos usar o Haskell!

Isso está se transformando em uma guerra de idiomas, não é?

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

Algo assim deve funcionar usando python, que é comumente disponível:

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

Isso assume a palavra por linha. Se houver mais, a divisão também deve ser fácil.

Esse é um problema clássico que teve alguma ressonância em 1986, quando Donald Knuth implementou uma solução rápida com tentativas de hash em um programa de 8 páginas para ilustrar sua técnica de programação, enquanto Doug McIlroy, o padrinho dos pipes Unix, respondeu com uma one-liner, que não foi tão rápido, mas fez o trabalho:

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

Obviamente, a solução da McIlroy possui complexidade de tempo O (N log N), onde N é um número total de palavras. Existem soluções muito mais rápidas. Por exemplo:

Aqui está uma implementação C ++ com a complexidade de tempo limite superior O ((N + k) log k), normalmente - quase linear.

Abaixo está uma implementação rápida do Python usando dicionários de hash e heap com complexidade de tempo O (N + k log Q), onde Q é um número de palavras exclusivas:

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)

Comparação de tempo de CPU (em 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 é a Bíblia concatenada consigo mesma 32 vezes (135 MB), bible256 - 256 vezes respectivamente (1,1 GB).
• A desaceleração não linear dos scripts Python é causada puramente pelo fato de processar arquivos completamente na memória, de modo que as despesas gerais estão aumentando para arquivos enormes.
• Se houvesse uma ferramenta Unix que pudesse construir uma pilha e selecionar n elementos da parte superior da pilha, a solução AWK poderia atingir uma complexidade de tempo quase linear, enquanto atualmente ela é O (N + Q log Q).