Codificació de Huffman: diferència entre les revisions
Contingut suprimit Contingut afegit
m Robot treu blancs del tag |
m petites correccions |
||
Línia 125:
|-
! rowspan = "3" style = "background: # efefef"|optimalitat
! style = "background: # efefef; font-weight: normal"|Probabilitat <br /> (2 <sup> - '' l '' <sub> {{mida|1= '' i '' }} </sub> </sup
|Align = "center"|1/8
|Align = "center"|1/8
Línia 182:
La codificació Huffman és òptima quan la probabilitat de cada símbol d'entrada és una potència negativa de dos. Els codis prefixos tendeixen a ser lleugerament ineficients en alfabets petits, on les probabilitats normalment es troben entre aquests punts òptims. El "empaquetat", o expansió de la grandària de l'alfabet concatenant múltiples símbols a "paraules" de mida fixa o variable abans de la codificació Huffman, normalment ajuda, especialment quan símbols adjacents estan correlacionats (com en el cas d'un text en llenguatge natural). El pitjor cas per a una codificació Huffman pot donar-se quan la probabilitat d'un símbol excedeix 2 <sup> -1 </sup> = 0.5, fent el límit superior d'ineficiència il limitat. Aquestes situacions sovint responen bé a una forma de paquet anomenada [[Run-length encoding|codificació run-length]].
La codificació aritmètica produeix una lleugera guany sobre la codificació Huffman, però en la pràctica aquest guany rarament ha estat prou gran com per utilitzar la codificació aritmètica que té una complexitat computacional més elevada
== Variacions ==
Línia 260:
En aquest exemple, la mitjana de bits per símbol que es podria esperar d'aquesta codificació, en cadenes de valors més llargues, és de 2,4.
Per a la seva comparació,
És possible, també, apreciar com es poden extreure sense cap ambigüitat els valors originals a partir de la cadena codificada mitjançant Huffman.
| |||