Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
A.Drozdek"Wprowadzeniedokompresjidanych",Warszawa2007,wyd.2,ISBN978-83-204-3309-8©byWNT
1.2.Kodowaniebezszumoweibezpamięciowe
rezerwujączerodlapoziomudrzewapustego).Naprzykładdrzewoopięciupo-
ziomachprzedstawiamynarys.1.7;linieprzerywaneoznaczająkrawędziedodane
dodrzewa,bystałosięonodrzewempełnym.Jeśliwybierzemyterazsłowokodu
odługościli,tonamocywłaściwościprzedrostkowej2
lmax−liliścistaniesięniedo-
stępnych,gdyżjeślibyłybydostępne,towłaściwośćprzedrostkowazostałabynaru-
szona.Narysunku1.7słowokodu00odługości2powoduje,że24−2=4liścistajesię
niedostępne,słowokodu010odługości3odcinadostępdo24−3=2liści.Zatem
Rys.1.7.TworzeniekodówprzyużyciunierównościKrafta
∑
i
=
n
1
2
l
max
−
l
i
<
2
l
max
lub
∑
i
=
n
1
2
−
li
<
1
Drugaczęśćdowodupoleganaskonstruowaniukoduprzedrostkowegoprzyzało-
żeniu,żenierównośćKraftajestprawdziwa.Zaczynamyodpełnegodrzewabinar-
negoolmax+1poziomachi2
lmaxliściach.Ustawmyterazdługościsłówkoduwpo-
rządkuniemalejącym:l1<…<ln−1<ln=lmax.Następniewybierzmydowolnywęzeł
napoziomiel1+1iskonstruujmysłowokodu,przebiegającodkorzeniadotego
węzłaizestawiającrazemnapotkanezeraijedynki.Ponieważwęzełtenstajesię
terazliściem,eliminujeonzdrzewa
2
l
max
−
l
1
liściponiżejwłaśnieobranegowęzła.
Następniewybieramywęzełnapoziomiel2+1iodpowiadającemusłowokodu,co
powodujeeliminację
2
l
max
−
l
2
liściponiżejwłaśniewybranegowęzła.Kontynuujemy
todochwiliprzetworzeniadługościlmax.Powstajejednakpytanie,czymożenam
21
