Parola di script conteggio frequenza è troppo lento

Question

Sfondo

creato uno script per contare la frequenza delle parole in un file di testo. Le esegue di script le seguenti operazioni:

1. Il conte la frequenza di parole da un corpus.
2. Mantenere ogni parola nel corpus trovato in un dizionario.
3. Creare un file separato da virgole delle frequenze.

Lo script e ': http://pastebin.com/VAZdeKXs

#!/bin/bash

# Create a tally of all the words in the corpus.
#
echo Creating tally of word frequencies...
sed -e 's/ /\n/g' -e 's/[^a-zA-Z\n]//g' corpus.txt | \
  tr [:upper:] [:lower:] | \
  sort | \
  uniq -c | \
  sort -rn > frequency.txt

echo Creating corpus lexicon...
rm -f corpus-lexicon.txt

for i in $(awk '{if( $2 ) print $2}' frequency.txt); do
  grep -m 1 ^$i\$ dictionary.txt >> corpus-lexicon.txt;
done

echo Creating lexicon...
rm -f lexicon.txt

for i in $(cat corpus-lexicon.txt); do
  egrep -m 1 "^[0-9 ]* $i\$" frequency.txt | \
    awk '{print $2, $1}' | \
    tr ' ' ',' >> lexicon.txt;
done

Problema

Le seguenti linee in sequenza continua il dizionario per abbinare parole:

for i in $(awk '{if( $2 ) print $2}' frequency.txt); do
  grep -m 1 ^$i\$ dictionary.txt >> corpus-lexicon.txt;
done

Funziona, ma è lento perché è la scansione delle parole che ha trovato per rimuovere quelle che non sono nel dizionario. Il codice esegue questo compito attraverso la scansione il dizionario per ogni singola parola. (Il parametro -m 1 arresta la scansione quando viene trovata la partita.)

Domanda

Come si ottimizzare lo script in modo che il dizionario non viene scansionato dall'inizio alla fine per ogni singola parola? La maggior parte delle parole non sarà presente nel dizionario.

Grazie!

Answer 1

È possibile utilizzare grep -f per la ricerca di tutte le parole in un solo passaggio su frequency.txt:

awk '{print $2}' frequency.txt | grep -Fxf dictionary.txt > corpus-lexicon.txt

• -F per la ricerca di stringhe fisse.
• -x per abbinare solo linee intere.
• -f a leggere i modelli di ricerca da dictionary.txt

In realtà, si potrebbe anche combinare questo con il secondo ciclo ed eliminare il file corpus-lexicon.txt intermedio. I due cicli for possono essere sostituiti da un unico grep:

grep -Fwf dictionary.txt frequency.txt | awk '{print $2 "," $1}'

Si noti che ho cambiato -x a -w.

Answer 2

Questo è in genere uno di quegli script che devi scrivere in Perl per la velocità. Ma se, come me, odiate linguaggi di programmazione di sola scrittura, si può fare tutto in Awk:

awk '
    BEGIN {
        while ((getline < "dictionary.txt") > 0)
            dict[$1] = 1
    }
    ($2 && $2 in dict) { print $2 }
' < frequency.txt > corpus-lexicon.txt

Non c'è bisogno per la rm -f corpus-lexicon.txt in questa versione.

Answer 3

Usa un vero e proprio linguaggio di programmazione. Tutte le app start up e le scansioni di file che si stanno uccidendo. Per esempio, ecco un esempio ho appena scatenato in Python (minimizzando linee di codice):

import sys, re
words = re.findall(r'(\w+)',open(sys.argv[1]).read())
counts = {}
for word in words:
  counts[word] = counts.setdefault(word,0) + 1
open(sys.argv[2],'w').write("\n".join([w+','+str(c) for (w,c) in counts.iteritems()]))

Test di un file di grandi dimensioni contro un testo che avevo seduto aound (1.4MB, 80.000 parole secondo wc), questo completa in meno di un secondo (18k parole uniche) su un bambino di 5 anni PowerMac.