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
c
i
1
c
i
2
K
c
i
k
=
c
j
1
c
j
2
K
c
j
k
,
todlakażdegos,is=js,czyli
c=
i
s
c
j
s
Π
DEFINICJA1.4.Kodmawłaściwośćprzedrostkową(jestkodemprzedrostkowym),
jeśliniemożemyotrzymaćżadnegosłowakoduzinnegosłowakoduprzezdodanie
doniegozerlubjedynek;innymisłowy,żadnesłowokoduniejestprzedrostkiem
żadnegoinnegosłowakodu.
Π
Kodyprzedrostkowestanowiąpodzbiórkodówjednoznaczniedekodowalnych.
Właściwośćprzedrostkowaoznacza,żeprzydekodowaniuciągusłówkodu
niepotrzebnejestprzeglądaniezwyprzedzeniem,bydekodowaniebyłojedno-
znaczne.Ponieważprzydekodowaniuunikamyprzeglądaniazwyprzedzeniem,po
wczytaniuzeralubjedynkijestmożliweokreślenie,czyjesttoostatnisymbolsłowa
kodukodującegoliterędanegoprzekazu.Ponieważzatemżadnesłowokodunie
jestprzedrostkiemżadnegoinnegosłowakodu,niepotrzebnejestużycieprzecin-
kówoddzielającychsłowakodunależącedozakodowanegoprzekazu.
DEFINICJA1.5.Kodemoptymalnymnazywamykod,dlaktóregoliczbaLśrjestnaj-
mniejszaspośródwszystkichkodówdladanegorozkładuprawdopodobieństwaP.
Wpraktycemożeistniećwieletakichkodów.
Π
Woptymalnymsystemiekodowaniadłuższychsłówkoduużywamytylkowów-
czas,gdywszystkiekrótszesłowakoduzostałyjużużyte.
Rozważmynastępująceczteryzbiorysłówkoduużytychdokodowanialiter
A,B,C:
litera
A
B
C
kod
01
0
1
1
kod
11
01
0
2
kod
00
01
10
3
kod
00
01
1
4
Dogodnejestprezentowaniezbiorusłówkoduzapomocądrzewabinarnego,
wktórymkażdalewakrawędźjestoznaczonazerem,aprawakrawędź–jedynką.
Przyprzeglądaniudrzewaodkorzeniadodanegowęzławszystkienapotkanepo
drodzezeraijedynkisązestawionerazem,tworzącsłowokodu.Drzewaodpowia-
dającekodomkod1,…,kod4pokazujemynarys.1.6.Pierwszykodumożliwiazde-
kodowaniesłowakodu01jakoABalboC,zatemkod1niejestjednoznaczniede-
kodowalny.Drugikodniematejniejednoznaczności,wymagajednakprzeglądania
19
