Esiste un modo migliore per calcolare la frequenza di tutti i simboli in un file?

Question

Ok, quindi, diciamo che ho un file di testo (non necessariamente contenente tutti i possibili simboli) e vorrei calcolare la frequenza di ciascun simbolo e, dopo aver calcolato la frequenza, devo quindi accedere a ciascun simbolo e alla sua frequenza da più frequente o meno frequente. I simboli non sono necessariamente caratteri ASCII, potrebbero essere sequenze di byte arbitrarie, anche se tutte della stessa lunghezza.

stavo considerando di fare qualcosa di simile (in pseudocodice):

function add_to_heap (symbol) 
    freq = heap.find(symbol).frequency 
    if (freq.exists? == true) 
     freq++ 
    else 
     symbol.freq = 1 
     heap.insert(symbol) 

MaxBinaryHeap heap 
while somefile != EOF 
    symbol = read_byte(somefile) 
    heap.add_to_heap(symbol) 
heap.sort_by_frequency() 

while heap.root != empty 
    root = heap.extract_root() 
    do_stuff(root) 

mi chiedevo: esiste un modo migliore e più semplice per calcolare e memorizzare quante volte ogni simbolo si verifica in un file?

Answer 1

È sempre possibile utilizzare una versione HashMap dell'heap. In questo modo eseguirai operazioni che si trovano in O (1) per ogni simbolo trovato invece di O (log n) dove n è il numero di elementi attualmente presenti nell'heap.

Tuttavia, se il numero di simboli distinti è limitato da un numero ragionevole (1 byte è ideale, 2 byte dovrebbe essere ancora valido), è possibile utilizzare solo un array di tale dimensione e di nuovo avere O (1) ma con un costo costante significativamente inferiore.

Answer 2

Se siete alla ricerca di una soluzione "migliore" in base a tempi di esecuzione, ecco cosa mi suggeriscono:

Quando stai leggendo il file, si dovrebbe avere i vostri simboli ordinati (o hash) per il valore dei simboli stessi, non le loro frequenze. Questo ti permetterà di trovare rapidamente il simbolo corrente nella tua lista di simboli già visti, piuttosto che dover cercare nell'intero elenco. Dovresti anche fare in modo che quella struttura iniziale sia in grado di eseguire inserimenti veloci - mi raccomando un albero binario di un hash.

Una volta letti tutti i simboli, è necessario commutare l'ordine in base ai conteggi di frequenza. Leggerò tutto in un array e poi eseguirò un ordinamento sul posto, ma ci sono un sacco di modi equivalenti per farlo.

Spero che questo aiuti!