Czy istnieje lepszy sposób obliczania częstotliwości wszystkich symboli w pliku?

Question

Okej, więc, powiedzmy, że mam plik tekstowy (niekoniecznie zawierający każdy możliwy symbol) i chciałbym obliczyć częstotliwość każdego symbolu i, po obliczeniu częstotliwości, muszę uzyskać dostęp do każdego symbolu i jego częstotliwości od najczęstsze lub najmniej częste. Symbole nie muszą być znakami ASCII, mogą to być dowolne sekwencje bajtów, choć wszystkie o tej samej długości.

Zastanawiałem się robi coś takiego (w Pseudokod):

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) 

zastanawiałem się: czy istnieje lepszy, prostszy sposób obliczyć i przechowywać, ile razy każdy symbol występuje w pliku?

Answer 1

Zawsze możesz użyć HashMap isntead of Heap. W ten sposób będziesz wykonywać operacje, które są w O (1) dla każdego znalezionego symbolu zamiast O (log n), gdzie n jest liczbą przedmiotów aktualnie na stercie.

Jeśli jednak liczba różnych symboli jest ograniczona rozsądną liczbą (1 bajt jest idealny, 2 bajty powinny nadal być w porządku), wystarczy użyć tablicy o tym rozmiarze i ponownie mieć O (1), ale z znacznie niższy stały koszt.

Answer 2

Jeśli szukasz „najlepszego” rozwiązania opartego na czas działa, oto co sugeruję:

Gdy czytasz plik należy mieć swoje symbole sortowane (lub mieszany) przez wartość samych symboli, a nie ich częstotliwości. Umożliwi to szybkie znalezienie aktualnego symbolu na liście już widzianych symboli, bez konieczności przeszukiwania całej listy. Powinieneś również mieć tę początkową strukturę zdolną do szybkiego wstawiania insertów - poleciłbym binarne drzewo hash.

Po przeczytaniu wszystkich symboli należy zmienić kolejność na podstawie liczby częstotliwości. Przeczytałem wszystko w tablicy, a następnie dokonałem sortowania na miejscu, ale istnieje wiele równoważnych sposobów na zrobienie tego.

Mam nadzieję, że to pomoże!