Per risolvere questo è necessario creare l'albero huffman e calcolare i bit necessari per rappresentare ogni simbolo. Quindi puoi calcolare i bit totali necessari per la stringa originale nella codifica di Huffman e dividere per il numero di caratteri.
Innanzitutto mappare la stringa di input in base alla codifica dei caratteri originale:
00 A
10 B
10 B
01 C
01 C
01 C
00 A
10 B
11 D
01 C
01 C
01 C
01 C
01 C
10 B
01 C
10 B
00 A
Successivamente, contali il numero di occorrenze di ciascun carattere:
3 00,A
9 01,C
5 10,B
1 11,D
Ora creiamo una coda con priorità minima usando la chiave dell'occorrenza, che assomiglia a:
[(1,D), (3,A), (5, B), (9,C)]
Continua ad applicare il processo di huffman ( link ). Quindi per prima cosa combini D e A per creare un nuovo nodo 'DA' che chiave = 1 + 3 = 4. Rimetti questo nella coda di priorità:
[(4, DA), (5, B), (9,C)]
Ora DA e B si combinano per dare DAB:
[(9, DAB), (9,C)]
Ora DAB e C si combinano per fornire il nodo root: 'DABC'
[(18, DABC)]
Ora il processo si interrompe e diamo a ogni personaggio una nuova codifica basata su quanto è lontano dal nodo radice. 'C' è stato combinato l'ultimo in modo da ottenere solo un bit. Diciamo che uso sempre '0' per il secondo elemento (dei due che sono stati prelevati dalla coda di priorità). I bit impliciti sono rappresentati tra parentesi:
C = 0, DAB = 1
B = (1) 0, DA = (1) 1
A = (11) 0, D = (11) 1
Quindi ottieni la codifica:
C = 0
B = 10
A = 110
D = 111
Codifica messaggio originale:
Total bits needed = 9 * 1 + 5 * 2 + 3 * 3 + 3 * 1
= 9 + 10 + 9 + 3
= 31
Number of Characters = 18
Average bits = 31 / 18 = 1.722222