Viquipèdia

Algorisme de Huffman: diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
Cap resum de modificació
Línia 1:
El L'''' algorisme de Huffman ''' és un [[algorisme]] per construirla construcció de [[Codificació Huffman|codis de d'Huffman]], desenvolupat per [[David A. Huffman]] ael [[1952]] i descrit ena '' A Method for the Construction of Minimum-Redundancy Codes ''.<ref> [http://compression.graphicon.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes . pdf '' A Method for the Construction of Minimum-Redundancy Codes ''] </ref>
 
Aquest algorisme pren un [[alfabet]] de '' n '' [[símbol]] s, juntament amb elsles seusseves [[freqüència]] sfreqüències d'aparició associades, i produeix un codi de Huffman per a aquest alfabet i aquestes freqüències.
 
== Descripció ==
L'algorisme consisteix en la creació d'un [[arbre binari]] que té cada untots delsels símbols pera fullcada fulla, i està construït de tal maneraforma que seguint-lo des de l'arrel a cadascunacada una de les seves fulles s'obtéobtingui el codi de Huffman associat.
# Es creen diversosdiferents arbres, un per cada un dels símbolssímbol de l'alfabet, consistint cadascuncada dels arbresarbre en un node sense fills,. iCada etiquetatgearbre cadascuns'etiqueta amb el seu símbol associat i la seva freqüència d'aparició.▼
# Es prenenS'agafen 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 cadaaquests un d'aquestsdos arbres serà unseran fillfills 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.▼
# Es repeteix el pas 2 fins que només quediqueda 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.
▲# Es creen diversos arbres, un per cada un dels símbols de l'alfabet, consistint cadascun dels arbres en un node sense fills, i etiquetatge cadascun amb el seu símbol associat i la seva freqüència d'aparició.
▲# 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 cada un d'aquests arbres serà un fill 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.
▲# Es repeteix el pas 2 fins que només quedi un arbre.
 
AmbPer aquest arbre es pot conèixerobtenir el codi associat a un símbol, is'ha obtenirde elprocedir símbolde associatla asegüent un determinat codi.manera:
 
# Començar amb un codi buit.
Per obtenir el codi associat a un símbol s'ha de procedir de la manera següent:
# Iniciar el recorregut de l'arbre ena ella fullfulla associada al símbol.▼
 
# Començar amb un codirecorregut de l'arbre cap buitamunt.
# Cada vegada que es pugi un nivell, afegir al codi l'etiqueta de la branca que s'ha recorregut.▼
▲# Iniciar el recorregut de l'arbre en el full associada al símbol
# Després d'arribar a l'arrel, invertir el codi.▼
# Comença un recorregut de l'arbre cap amunt
# El resultat és el codi d'Huffman desitjat.▼
▲# Cada vegada que es pugi un nivell, afegir al codi l'etiqueta de la branca que s'ha recorregut
▲# Després d'arribar a l'arrel, invertir el codi
▲# El resultat és el codi Huffman desitjat
 
Per obtenir un símbol a partir d'un codi s'ha de fer així:
 
# Començar el recorregut de l'arbre a l'arrel d'aquest.
# Extreure el primer símbol del codi a descodificar.
# BaixarDescendir per la branca etiquetada amb aquest símbol.
# Tornar al pas 2 fins que s'arribi a ununa fullfulla, que serà el símbol associat al codi.
 
A la pràctica, gairebé sempre s'utilitza l'arbre per obtenir tots els codis d'unaa solala vegada; després es guarden en taules i es descartadeixa l'arbre.
 
=== Exemple d'ús ===
Obtingut de «https://ca.wikipedia.org/wiki/Algorisme_de_Huffman»