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
Rozdział1.Informacjaikodowanie
zabraknąćwęzłówdlajakiegośk<n?Zauważmy,żedlawęzłanapoziomielk+1
liczbawyeliminowanychliści
k
n
2
l
max
−
l
1
+
K
+
2
l
max
−
l
k
=
2
l
max
∑
2
−
l
i
<
2
l
max
∑
2
−
l
i
=
2
l
max
i
=
1
i
=
1
spośródwszystkich2lmaxliściwpierwotnympełnymdrzewiebinarnym.Zawsze
zatemistniejąwęzłynapoziomielj+1>lk+1umożliwiającekonstruowaniekolej-
nychsłówkodu.
Narysunku1.7pokazujemyprzykładzastosowaniatejmetody.Zbioremdłu-
gościjest{2,2,3,3,3,4,4}.
Π
Przyjrzyjmysięuważnie,cowłaściwiegłositwierdzenieKrafta.
1.Przyjętopewnezałożeniaraczejcododługościsłówkoduniżcodopostaci
tychsłówiżejestmożliweskonstruowaniekoduprzedrostkowegoodpowiadające-
gotymdługościom.Dowódtwierdzeniajestkonstruktywnyprzezpokazanie,jak
możnautworzyćtakikod.Możliwejestjednak,żeistniejewieleróżnychkodów
spełniającychzałożeniatwierdzenia.Naprzykładnarys.1.8pokazujemydwaze-
stawysłówkoduskonstruowanychdlatychsamychdługości{2,3,3,3,4}.Warto
zauważyć,żedanykodprzedrostkowymożemyprzekształcićłatwowinnykod
przedrostkowy,zamieniającjedynkiwzeraizerawjedynki.
2.Twierdzeniewskazujenaproceskonstrukcjikoduprzedrostkowegodlada-
nychdługościsłówkodowych,leczwtrakcietegoprocesuniezmieniadługościtych
słów,takwięckodmożeniebyćoptymalny.Naprzykładnarys.1.8asłowokodowe
00możemyskrócićdo0,a1000do100,anowesłowakodowesłużyłybyswemu
celowirówniedobrzejakpierwotnesłowa,anawetlepiej,gdyżdwasłowasąkrót-
sze,azatemwymagająmniejzabiegówprzykodowaniu,przesyłaniuidekodowa-
niu.Nicjednakniemożemywtymceluuczynić,gdyżzaczynamyodzestawudługo-
ści{2,3,3,3,4},chociażzbiór{1,3,3,3,3}dałbylepszewyniki.
Rys.1.8.Dwaróżnekodywygenerowanedlatychsamychdługościsłówkodu
22
