Algorisme de Huffman

De Viquipèdia
Dreceres ràpides: navegació, cerca

L'algorisme de Huffman és un algorisme per la construcció de codis de Huffman, desenvolupat per David A. Huffman el 1952 i descrit a A Method for the Construction of Minimum-Redundancy Codes.[1]

Aquest algorisme pren un alfabet de n símbols, juntament amb les seves freqüències d'aparició associades, i produeix un codi de Huffman per aquest alfabet i aquestes freqüències.

Descripció[modifica | modifica el codi]

L'algorisme consisteix en la creació d'un arbre binari que té tots els símbols repartits un a cada fulla, i està construït de forma que seguint-lo des de l'arrel a cada una de les fulles s'obtingui el codi de Huffman associat.

  1. Es creen diferents arbres, un per cada símbol de l'alfabet, consistint cada arbre en un node sense fills. Cada arbre s'etiqueta amb el seu símbol associat i la seva freqüència d'aparició.
  2. Es prenen els dos arbres de menor freqüència i s'uneixen creant un nou arbre. L'etiqueta de l'arrel serà la suma de les freqüències de les arrels dels dos arbres que s'uneixen, i aquests dos arbres seran fills del nou arbre. També s'etiqueten les dues branques del nou arbre: amb un 0 la de l'esquerra, i amb un 1 la de la dreta.
  3. Es repeteix el pas 2 fins que només queda un arbre.

Amb aquest arbre es pot conèixer el codi associat a un símbol i també es pot obtenir el símbol associat a un determinat codi.

Per obtenir el codi associat a un símbol s'ha de procedir de la següent manera:

  1. Començar amb un codi buit.
  2. Iniciar el recorregut de l'arbre a la fulla associada al símbol.
  3. Començar un recorregut de l'arbre cap amunt.
  4. Cada vegada que es pugi un nivell, afegir al codi l'etiqueta de la branca que s'ha recorregut.
  5. Després d'arribar a l'arrel, invertir el codi.
  6. El resultat és el codi de Huffman desitjat.

Per obtenir un símbol a partir d'un codi s'ha de fer així:

  1. Començar el recorregut de l'arbre a l'arrel.
  2. Extreure el primer símbol del codi a descodificar.
  3. Davallar per la branca etiquetada amb aquest símbol.
  4. Tornar al pas 2 fins que s'arribi a una fulla, que serà el símbol associat al codi.

A la pràctica, gairebé sempre s'utilitza l'arbre per obtenir tots els codis a la vegada; després es guarden en taules i es deixa l'arbre.

Exemple d'ús[modifica | modifica el codi]

La taula descriu l'alfabet a codificar, juntament amb les freqüències dels seus símbols. En el gràfic es mostra l'arbre construït a partir d'aquest alfabet seguint l'algorisme descrit.

Arbre per construir el codi Huffman de l'exemple.
Símbol Freqüència
A 0,15
B 0,30
C 0,20
D 0,05
E 0,15
F 0,05
G 0,10

Es pot veure amb facilitat quin és el codi del símbol E : pujant per l'arbre es recorren branques etiquetades amb 1 , 1 i 0 , per tant, el codi és 011 . Per obtenir el codi de D es recorren les branques 0 , 1 , 1 i 1 , de manera que el codi és 1110 .

L'operació inversa també és fàcil de realitzar: donat el codi 10 es recorren des de l'arrel les branques 1 i 0 , obtenint el símbol C . Per descodificar 010 es recorren les branques 0 , 1 i 0 , obtenint el símbol A .

Limitacions[modifica | modifica el codi]

Per poder utilitzar l'algoritme de Huffman és necessari conèixer per endavant les freqüències d'aparició de cada símbol, i la seva eficiència depèn del que pròximes a les freqüències reals que siguin les estimades. Algunes implementacions de l'algorisme de Huffman són adaptatives, actualitzant les freqüències de cada símbol acord recorre el text.

L'eficiència de la codificació de Huffman també depèn del balanç que hi hagi entre els fills de cada node de l'arbre, i més eficient acord menor sigui la diferència de freqüències entre els dos fills de cada node.

Exemples:

  • La codificació binària és un cas particular de la codificació de Huffman que passa quan tots els símbols de l'alfabet tenen la mateixa freqüència. S'ha doncs que la codificació binària és la més eficient per a qualsevol nombre de símbols equiprobables.
  • L'algorisme de Huffman aplicat sobre un alfabet de dos símbols assignarà sempre un 1 al primer i un 0 al segon, independentment de la freqüència d'aparició d'aquests símbols. En aquest cas no es realitza compressió de les dades, mentre que altres algorismes si podrien aconseguir-ho.

Una manera de resoldre aquest problema consisteix a agrupar els símbols en paraules abans d'executar l'algorisme. Per exemple, si es té la cadena de longitud 64

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB

L'algoritme de Huffman aplicat únicament als símbols torna el codi:

1111111111111111111111111111111111111111111111111111111111111110

També de longitud 64. No obstant això, si abans d'utilitzar l'algoritme, s'agrupen els símbols en les paraules "AA" , "AB" i "B" (que es codifiquen com 1, 01 i 00), l'algoritme torna la següent cadena:

111111111111111111111111111111101

que té longitud 32, la meitat que si no s'hagués agrupat. Si s'observa l'arbre de Huffman, es pot comprovar que la diferència de freqüències entre les branques de l'arbre és menor que en el cas anterior.

Variacions de l'algorisme[modifica | modifica el codi]

Codis Huffman n -aris[modifica | modifica el codi]

És possible crear codis de Huffman ternaris, quaternaris, i, en general, n -aris. Per a això només cal realitzar dos modificacions a l'algorisme:

  1. Els arbres a crear tindran tants fills com a símbols possibles puguin aparèixer en els codis Huffman. Per exemple, si és ternari es crearan arbres amb tres fills, si és quaternari, amb quatre.
  2. Si s'expressa com s el nombre de símbols en l'alfabet a codificar, i n el nombre de símbols que apareixen en el codi Huffman, llavors s -1 ha de ser múltiple de n -1. És a dir, per a un codi ternari, s ha de valer 3, 5, 7, etc. Si aquesta condició no es compleix, llavors s'han d'afegir símbols "nuls" sovint 0, que serviran només com a farciment a l'hora de construir l'arbre.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]