Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
14
20Informacjaikodowanie
Przykład204
MamysymboleA,B,C,Doprawdopodobieństwachwystąpieniaodpowiednio[001,002,003,004]0
Łączącwęzłyodpowiadającesymbolom(A)i(B)otrzymujemy(A+B)=0.3,(C)=0.3,(D)=0.4.Teraz
łączymywęzłyodpowiadającedrzewu(A+B)i(C)uzyskując((A+B)+C)=0.6i(D)=0.4.Łączymy
węzłyodpowiadającedrzewku((A+B)+C)i(D)otrzymującwęzełkońcowy(((A+B)+C)+D)=1.0.
Obliczamykodyznaków(L=lewo,P=prawo):A=LLL=000,B=LLP=001,C=LP=01,D=P=10
Średniadługośćkoduwyniesiel=p(A)l3+p(A)l3+p(A)l3+p(A)l3=003+006+006+004=1090
Jesttomniejniż2bitypotrzebnewkodowaniuostałejdługościznaku.Entropiaźródławynosi:
E=-0.1log2001-0.2log2002-0.3log2003-0.4log2004=108464-takapowinnabyćśredniadługośćkodu
optymalnego.Faktycznadługośćkodujestwiększa,ajegoefektywnośćE/L=108464/109=009720
0i1
A
0i2
B
0i3
C
0i4
D
0i1
A
000
0i3
00
001
0i2
0i6
B
0
01
1i0
0i3
C
1
0i4
D
Praktycznezastosowanie
GłównąwadąstatycznegoalgorytmuHuffmanajestkoniecznośćprzesłania
całejtablicyprawdopodobieństwlubdrzewawporządkupreorder.Wewnętrzny
węzełmożnazapisaćnajednymbicie(mazawsze2gałęzie),zaśliściewymagają
takiejliczbybitów,jakajestpotrzebnadozapamiętaniasymbolu(np.8bitów)
plus1.Itak,drzewozprzykładumożebyćzapisanejako:(1,0,'d',1,0,'c',1,0,
'b',0,'a'),czyli7+4l8=39bitów.Lepsząkompresję,kosztemdużegowzrostu
zapotrzebowanianapamięć,uzyskujesiękodującgrupykolejnychznaków.
Przykład205
Kodowaniepo2znakinaraz(jeśliliczbasymbolijestnieparzysta,dołączamysymbolpusty).
SymboleA,B,C,Doprawdopodobieństwachwystąpieniaodpowiednio[0.1,0.2,0.3,0.4].
Symbolewparachsąniezależne,więcp(XY)=p(X)p(Y).Prawdopodobieństwawystąpieniapar
symboliAA,AB,AC,AD,BA,BB,BC,BD,CA,CB,CC,CD,DA,DB,DC,DDsązatemrówne
odpowiednio0001,0002,0003,0004,0002,0004,0006,0008,0003,0006,0009,0012,0004,0008,0012,0016,
akolejnewęzłydrzewa(wgrosnącegoprawdopodobieństwa)tworzązestawienia:
(AA+AB)=0003,(BA+AC)=0005,(CA+(AA+AB))=0006,(BB+AD)=0008,
(DA+(BA+AC))=0009,(BC+CB)=0012,((CA+(AA+AB))+BD)=0014,
(DB+(BB+AD))=0016,((DA+(BA+AC))+CC)=0018,(CD+DC)=0024,
((BC+CB)+((CA+(AA+AB))+BD))=0026,(DD+(DB+(BB+AD)))=0032,
(((DA+(BA+AC))+CC)+(CD+DC))=0042,
(((BC+CB)+((CA+(AA+AB))+BD))+(DD+(DB+(BB+AD)))
)=0058,
(((
(DA+(BA+AC))+CC)+(CD+DC))+(((BC+CB)+((CA+(AA+AB))+BD))+(DD+(DB+(BB+AD)))
))=100
Paromznakówpokazanychnaponiższymschemaciekodowaniaodpowiadajązatemkody:
AA–101010
AB–101011
AC–00011
AD-11111
BA–00010
BB–11110
BC–1000
BD-1011
CA–10100
CB–1001
CC–001
CD-010
DA–0000
DB–1110
DC–011
DD-110
Średnialiczbabitówprzypadającanaparęsymbolito3.73,więcśrednialiczbabitównasymbol
to1.865.Jesttoznacznielepszakompresjaniżpoprzednio(6.75%zamiast5%przymaksymalnej
równej1-1/1.8464=7.68%).Używającwiększejliczbyznakówmożnadowolnieprzybliżyćsiędo
kompresjimaksymalnej,jednakznaczniewcześniejwyczerpiesiępamięć,ponieważwymagania
pamięciowerosnąwykładniczowzgledemliczbykompresowanychjednocześniesymboli.
