Algoritme de Huffman

El algoritme de Huffman és un algoritme per a la construcció de còdics de Huffman, desenrollat per David A. Huffman en 1952 i descrit en A Method for the Construction of Minimum-Redundancy Codes.

Este algoritme pren un alfabet de n símbols, junt en les seues freqüèncias d'aparició associades, i produïx un còdic de Huffman per a eixe alfabet i eixes freqüències.

Descripció

L'algoritme consistix en la creació d'un arbre binario que té cada u dels símbols per full, i construït de tal forma que seguint-ho des de la raïl a cada una dels seus fulls s'obté el còdic Huffman associat a ell.

1. Es creen varis arbres, un per cada u dels símbols de l'alfabet, consistint cada u dels arbres en un nodo sense fills, i etiquetat cada u en el seu símbol associat i la seua freqüència d'aparició.
2. Es prenen els dos arbres de menor freqüència, i s'unixen creant un nou arbre. L'etiqueta de la raïl serà la suma de les freqüències de les raïls dels dos arbres que s'unixen, i cada u d'estos arbres serà un fill del nou arbre. També s'etiqueten les dos branques del nou arbre: en un 0 la de l'esquerra, i en un 1 la de la dreta.
3. Es repetix el pas 2 fins que solament quede un arbre.

En este arbre es pot conéixer el còdic associat a un símbol, aixina com obtindre el símbol associat a un determinat còdic.

Per a obtindre el còdic associat a un símbol es deu procedir del següent modo:

1. Començar en un còdic buit
2. Iniciar el recorregut de l'arbre en el full associat al símbol
3. Començar un recorregut de l'arbre cap a dalt
4. Cada volta que es puge un nivell, afegir al còdic l'etiqueta de la branca que s'ha recorregut
5. Despuix d'aplegar a la raïl, invertir el còdic
6. El resultat és el còdic Huffman desijat

Per a obtindre un símbol a partir d'un còdic es deu fer aixina:

1. Començar el recorregut de l'arbre en la raïl d'este
2. Extraure el primer símbol del còdic a descodificar
3. Descendir per la branca etiquetada en eixe símbol
4. Tornar al pas 2 fins que s'aplegue a un full, que serà el símbol associat al còdic

En la pràctica, casi sempre s'utilisa l'arbre per a obtindre tots els còdics d'una sola volta; després es guarden en taules i es descarta l'arbre.

Eixemple d'us

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

Archiu:ArbolCodigoHuffman.svg

Arbre per a construir el còdic Huffman de l'eixemple.

Símbol	Freqüència
A	0,15
B	0,30
C	0,20
D	0,05
I	0,15
F	0,05
G	0,10

Es pot vore en facilitat quin és el còdic del símbol I: pujant per l'arbre es recorren branques etiquetades en 1, 1 i 0; per lo tant, el còdic és 011. Per a obtindre el còdic de D es recorren les branques 0, 1, 1 i 1, per lo que el còdic és 1110.

L'operació inversa també és fàcil de realisar: donat el còdic 10 es recorren des de la raïl les branques 1 i 0, obtenint-se el símbol C. Per a descodificar 010 es recorren les branques 0, 1 i 0, obtenint-se el símbol A.

Llimitacions

Per a poder utilisar l'algoritme de Huffman és necessari conéixer de bestreta les freqüències d'aparició de cada símbol, i la seua eficiència depén de lo pròximes a les freqüències reals que siguen les estimades. Algunes implementacions de l'algoritme de Huffman són adaptatives, actualisant les freqüències de cada símbol conforme recorre el text.

L'eficiència de la codificació de Huffman també depén del balanç que existixca entre els fills de cada nodo de l'arbre, sent més eficient conforme menor siga la diferència de freqüències entre els dos fills de cada nodo.

Eixemples:

• La codificació binaria és un cas particular de la codificació de Huffman que ocorre quan tots els símbols de l'alfabet tenen la mateixa freqüència. Es té puix que la codificació binaria és la més eficient per a qualsevol número de símbols equiprobables.
• L'algoritme 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ó de dits símbols. En este cas mai es realisa compressió de les senyes, mentres que atres algoritmes sí podrien conseguir-ho.

Una manera de resoldre este problema consistix en agrupar els símbols en paraules abans d'eixecutar l'algoritme. Per eixemple, si es té la cadena de llongitut 64

 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB

L'algoritme de Huffman aplicat únicament als símbols torna el còdic:

 1111111111111111111111111111111111111111111111111111111111111110

També de llongitut 64. No obstant, si abans d'utilisar 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é llongitut 33, la mitat que si no s'haguera agrupat. Si 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.

Vore també

• Codificació Huffman