Come trovo i bit medi per simbolo usando il codice di Huffman?

Question

Come trovo i bit medi per simbolo usando il codice di Huffman?

#1 da (6 voti)
#2 da (0 voti)

2

Sto provando a scrivere un programma in c per la codifica di Huffman, ma sono bloccato. Per l'input ho:

Sample input:
4      // here I scan how many letters I have
A 00   // and for everyone I scan how they are coded in string down
B 10     
C 01
D 11
001010010101001011010101010110011000 //this is a suboptimal huffman code

Quindi prima devo decodificare questa stringa e scoprire quante volte ogni lettera appare. E lo faccio già. Ma ora devo scoprire quanti bit hanno ogni lettera usando l'albero di huffman, e nell'output devo stampare il bit medio per simbolo.

L'output per questo esempio qui deve essere:

Sample output
1.722

Quindi, ora, come scoprire quanti bit hanno ogni lettera con la codifica di huffman?

compression huffman-encoding

posta Maria 01.05.2014 - 00:50

fonte

2 risposte

Leggi altre domande sui tag compression huffman-encoding

Gestione degli errori di accesso con la classe utente Best practice: separazione delle preoccupazioni e problemi di ereditarietà

score 6 · Answer 1

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

score 0 · Answer 2

Una volta che hai l'albero di codifica di Huffman, il codice ottimale per ogni simbolo è dato dal percorso del simbolo nell'albero.

Ad esempio, prendiamo questo albero e diciamo che left è 0 e right è 1 (questo è arbitrario):

/ \
A  \
   /\
  B  \
     /\
     C D

Path to A è left , quindi il suo codice ottimale è 0, la lunghezza di questo codice è 1 bit. Path to B è right, left , il suo codice è 10, length 2 bit. C è destra, destra, sinistra , codice 110, 3 bit e D destra, destra, destra, destra , codice 1111, 4 bit.

Ora hai la lunghezza di ogni codice e hai già calcolato la frequenza di ciascun simbolo. Il numero medio di bit per simbolo è la media tra queste lunghezze di codice ponderata dalla frequenza dei simboli associati.