Codificació de Huffman: diferència entre les revisions
Contingut suprimit Contingut afegit
m Format |
m Format |
||
Línia 71:
==== Descripció formalitzada ====
''' Entrades '''. <br
L'alfabet <math> A = \left \{a_{1}, a_{2}, \cdots, a_{n}\right \}</math>, que és l'alfabet de símbols de mida <math> n </math>. <br
El conjunt <math> W = \left \{w_{1}, w_{2}, \cdots, w_{n}\right \}</math>, que és el conjunt de pesos (positius) dels símbols (normalment proporcionals a probabilitats), és a dir <math> w_{i}= \mathrm{pes}\left (a_{i}\right), 1 \leq i \leq n </math>. <br
<br
''' Sortida '''. <br
El codi <math> C \left (A, W \right) = \left \{C_{1}, C_{2}, \cdots, C_{n}\right \}</math>, que és el conjunt d'elements del codi (binari), on <math> C_{i}</math> és la paraula del codi per <math> a_{i}, 1 \leq i \leq n </math>. <br
<br
''' Objectiu '''. <br
Sigui <math> L \left (C \right) = \sum_{i = 1}^{num}{w_{i}\times \mathrm{longitud}\left (C_{i}\right)}</math> la longitud del camí ponderat del codi <math> C </math>. Condició: <math> L \left (C \right) \leq l \left (T \right) </math> per a qualsevol codi <math> T \left (A, W \right) </math>.
Línia 109:
|Rowspan = "2"|
|-
! style = "background: # efefef; font-weight: normal"|Longitud de la paraula (en bits) <br
|Align = "center"|3
|Align = "center"|3
Línia 116:
|Align = "center"|2
|-
! style = "background: # efefef; font-weight: normal"|Longitud del camí ponderat <br
|Align = "center"|0,30
|Align = "center"|0,45
Línia 125:
|-
! rowspan = "3" style = "background: # efefef"|optimalitat
! style = "background: # efefef; font-weight: normal"|Probabilitat <br
|Align = "center"|1/8
|Align = "center"|1/8
Línia 133:
|Align = "center"|= 1.00
|-
! style = "background: # efefef; font-weight: normal;"|Quantitat d'informació (en bits) <br
|Align = "center"|3.32
|Align = "center"|2.74
Línia 141:
|Align = "center"|
|-
! style = "background: # efefef; font-weight: normal;"|Entropia <br
|Align = "center"|0.332
|Align = "center"|0.411
| |||