temukan n kata yang paling sering dalam file

Saya ingin menemukan, katakanlah, 10 kata yang paling umum dalam file teks. Pertama, solusi harus dioptimalkan untuk penekanan tombol (dengan kata lain - waktu saya). Kedua, untuk kinerja. Inilah yang saya miliki sejauh ini untuk mendapatkan 10 besar:

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

Saya bisa membuat program java, python, dll. Di mana saya menyimpan (kata, numberOfOccurences) dalam kamus dan mengurutkan nilainya atau saya bisa menggunakan MapReduce, tetapi saya mengoptimalkan untuk penekanan tombol.

Adakah yang salah positif? Apakah ada cara yang lebih baik?

Itu cukup banyak cara yang paling umum untuk menemukan "N hal yang paling umum", kecuali Anda melewatkan a sort, dan Anda punya uang gratis cat:

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

Jika Anda tidak memasukkan kata sortsebelum, uniq -c Anda mungkin akan mendapatkan banyak kata tunggal palsu. uniqhanya menjalankan garis yang unik, bukan keseluruhan uniquness.

EDIT: Saya lupa tipuan, "hentikan kata-kata". Jika Anda melihat teks bahasa Inggris (maaf, satu bahasa Amerika Utara satu bahasa di sini), kata-kata seperti "dari", "dan", "yang" hampir selalu menempati posisi dua atau tiga teratas. Anda mungkin ingin menghilangkannya. Distribusi GNU Groff memiliki file bernama eigndi dalamnya yang berisi daftar kata-kata berhenti yang lumayan bagus. Distro Arch saya sudah /usr/share/groff/current/eign, tapi saya pikir saya juga pernah melihat /usr/share/dict/eignatau /usr/dict/eigndi Unix lama.

Anda dapat menggunakan kata-kata berhenti seperti ini:

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

Dugaan saya adalah bahwa sebagian besar bahasa manusia memerlukan "kata-kata berhenti" yang sama dihapus dari penghitungan frekuensi kata yang bermakna, tetapi saya tidak tahu harus menyarankan di mana bahasa lain menghentikan daftar kata-kata yang berhenti.

EDIT: fgrep harus menggunakan -wperintah, yang memungkinkan pencocokan seluruh kata. Ini menghindari kesalahan positif pada kata-kata yang hanya berisi karya berhenti pendek, seperti "a" atau "i".

Ini berfungsi lebih baik dengan utf-8:

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

Mari kita gunakan AWK!

Fungsi ini mencantumkan frekuensi setiap kata yang muncul dalam file yang disediakan dalam urutan menurun:

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
}

Anda dapat menyebutnya di file Anda seperti ini:

$ cat your_file.txt | wordfrequency

dan untuk 10 kata teratas:

$ cat your_file.txt | wordfrequency | head -10

Sumber: Ruby AWK-ward

Mari kita gunakan Haskell!

Ini berubah menjadi perang bahasa, bukan?

import Data.List
import Data.Ord

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

Pemakaian:

cat input | wordfreq

Kalau tidak:

cat input | wordfreq | head -10

Sesuatu seperti ini harus bekerja menggunakan python yang biasanya tersedia:

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

Ini mengasumsikan kata per baris. Jika ada lebih banyak, pemisahan juga harus mudah.

Ini adalah masalah klasik yang mendapat resonansi pada tahun 1986, ketika Donald Knuth menerapkan solusi cepat dengan hash mencoba dalam program sepanjang 8 halaman untuk menggambarkan teknik pemrograman melek hurufnya, sementara Doug McIlroy, ayah baptis pipa Unix, merespons dengan satu-liner, itu tidak secepat, tetapi menyelesaikan pekerjaan:

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

Tentu saja, solusi McIlroy memiliki kompleksitas waktu O (N log N), di mana N adalah jumlah total kata. Ada banyak solusi yang lebih cepat. Sebagai contoh:

Berikut ini adalah implementasi C ++ dengan kompleksitas waktu batas atas O ((N + k) log k), biasanya - hampir linier.

Di bawah ini adalah implementasi Python cepat menggunakan kamus hash dan tumpukan dengan kompleksitas waktu O (N + k log Q), di mana Q adalah sejumlah kata unik:

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)

Perbandingan waktu CPU (dalam detik):

                                     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

Catatan:

• bible32 adalah Alkitab yang digabungkan dengan dirinya sendiri 32 kali (135 MB), bible256 - 256 kali masing-masing (1,1 GB).
• Perlambatan non-linier skrip Python disebabkan murni oleh fakta bahwa ia memproses file sepenuhnya dalam memori, sehingga overhead semakin besar untuk file besar.
• Jika ada alat Unix yang dapat membangun heap dan memilih n elemen dari atas heap, solusi AWK dapat mencapai kompleksitas waktu dekat-linear, sedangkan saat ini adalah O (N + Q log Q).