Codi canònic de Huffman

Un codi canònic de Huffman és un tipus particular de codificació Huffman que té la propietat de poder ser descrit d'una forma molt compacta.

Els compressors de dades generalment treballen d'una de dues maneres possibles. O bé el descompressor pot inferir quin arbre de Huffman utilitza el compressor per a un context anterior, o el compressor ha de dir al descompressor quin és l' arbre de Huffman que utilitzat per construir el codi. Atès que un codi canònic de Huffman pot ser emmagatzemat de manera més eficient, molts compressors comencen generant un arbre de Huffman normal , i el converteixen a un arbre de Huffman canònic abans d'utilitzar-lo.

Algorisme

L'algorisme normal de codificació Huffman assigna un codi de longitud variable a cada símbol en l'alfabet. Els símbols més freqüentment usats tindran assignats codis més curts. Per exemple, suposeu que tenim la següent codificació no -canònica:

A = 11
B = 0
C = 101
D = 100

Aquí a la lletra A se li han assignat 2 bits, 1 bit a la B, i 3 bits tant a la lletra C com a la Sr Per fer un codi canònic de Huffman, els codis són reenumerats. Les longituds de bit que estan en el diccionari de codis s'ordenen primer per la longitud del codi i en segon lloc pel valor alfabètic:

B = 0
A = 11
C = 101
D = 100

Cada un dels codis existents és reemplaçat amb un de nou de la mateixa longitud, usant el següent algorisme:

• El primer símbol de la llista pren un codi que és de la mateixa longitud que el símbol del codi original, però amb tots zeros. Això a vegades només serà un zero ('0 ').
• A cada un dels següents símbols se li assigna el proper nombre binari de la seqüència, assegurant que els següents codis siguin sempre superiors en valor.
• Quan s'arriba al codi més llarg de la llista, després d'haver incrementat, afegir zeros fins que la longitud del nou codi sigui igual que la longitud del codi original. Això es pot interpretar com un desplaçament a l'esquerra.

Seguint les tres regles esmentades anteriorment, la versió canònica del diccionari de codis produïda serà:

B = 0
A = 10
C = 110
D = 111

Codificat el diccionari

L'avantatge d'un arbre canònic de Huffman és que un pot codificar la descripció (el diccionari de codis) en menys bits que en un arbre totalment descrit.

Prenguem un diccionari de codis de Huffman original :

A = 11
B = 0
C = 101
D = 100

Hi ha diverses formes en que podríem codificar aquest arbre de Huffman. Per exemple, podríem escriure cada símbol seguit pel nombre de bits i el codi :

('A', 2,11), ('B', 1,0), ('C', 3,101), ('D', 3,100)

Una vegada que llistem els símbols en ordre alfabètic seqüencial, podem ometre els símbols pròpiament dits, llistant només el nombre de bits i el codi :

(2,11), (1,0), (3,101), (3,100)

Amb la nostra versió canònica tenim el coneixement que els símbols estan en ordre alfabètica seqüencial i que posteriorment el codi serà sempre superior en valor que un codi anterior. L'única cosa que queda transmetre són les longituds dels bits ( nombre de bits ) per a cada símbol. Tingueu en compte que el nostre arbre canònic de Huffman sempre té valors superiors per a les longituds més llargues de bit i que qualsevol símbol de la mateixa longitud de bit ( C i D ) té valor de codi superior per símbols superiors:

A = 10 (code value: 2 decimal, bits:  2 )
B = 0 (code value: 0 decimal, bits:  1 )
C = 110 (code value: 6 decimal, bits:  3 )
D = 111 (code value: 7 decimal, bits:  3 )

Atès que les dues terceres parts de les limitacions són conegudes, només el nombre de bits per a cada símbol necessita ser transmès.

2, 1, 3, 3

Amb aquest coneixement de l'algorisme canònic de Huffman, és llavors possible recrear la taula sencera (símbol i valors de codi) només amb la longitud dels bits. Els símbols inútils són normalment transmesos com bits que tenen longitud zero.

Pseudo codi

El pseudo codi per a la construcció d'una taula canònica de Huffman podria ser semblant al següent:

codi = 0
while hay_mas_simbolos:
imprimir símbol, codi
codi = codi+(1 <<(longitud_bit_actual -1))
if longitud_bit_siguiente> longitud_bit_actual:
codi = codi <<(longitud_bit_siguiente - longitud_bit_actual)