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
3.Ściślezwiązanezostatnimproblememjestpytanie,dlaczego,czyraczejkie-
dyzachodziostranierówność?Kiedynierównośćstajesięrównością?Rozważmy
zbiórodługości{2,3,3,3,4},codaje
2
1
2
+
2
1
3
+
2
1
3
+
2
1
3
+
2
1
4
=
11
16
<
1
Rozważmynastępniezbiór{1,3,3,3,3},któryprowadzido
2
1
1
+
2
1
3
+
2
1
3
+
2
1
3
+
2
1
3
=
8
8
=
1
NierównośćKraftastajesięrównościąwówczas,gdysłówkoduniemożemy
jużskrócić.Powinnotobyćoczywiste,gdyżdłuższesłowakodupowodująelimino-
waniemniejszejliczbyliściprzykonstruowaniukodumetodąprzedstawioną
wdowodzietwierdzenia.
4.Twierdzeniemówi,żedlapewnychdługościsłówkodumożemyznaleźćkod
przedrostkowy,jestjednakmożliwe,żedlatychdługościmożemyskonstruować
kodniemającywłaściwościprzedrostkowej,czylikod,dlaktóregozachodzinie-
równośćKrafta,niekonieczniemusibyćkodemprzedrostkowym.
5.Twierdzeniemówitylkookodzieprzedrostkowym.Jakjednakzostałodo-
wiedzioneprzezBrockwayaMcMillana,nierównośćtęmożemyodnieśćdodowol-
negokodujednoznaczniedekodowalnego.Oznaczato,żeskoncentrowaniesięna
kodachprzedrostkowychjestdobrzeuzasadnioneiniewielesięzyskuje,dyskutując
wszelkiejednoznaczniedekodowalnekody,gdyżjeślidladanegozbiorudługości
istniejejednoznaczniedekodowalnykodniemającywłaściwościprzedrostkowej,to
istniejerównieżkodprzedrostkowy.Tekodysąlepszeodpoprzednich,gdyżsłowa
kodumożemydekodowaćprzyjrzawszysiękażdemutworzącemujesymbolowi
tylkoraz.
1.2.2.Podstawowetwierdzenieokodowaniudyskretnym
NierównośćKraftaumożliwiaokreślenie,czyistniejekodprzedrostkowy,jeślisą
znanedługościsłówkodu.Chcielibyśmyjednakwiedziećniecowięcejotymko-
dzie.Dlakompresjidanychważnejestokreślenieoptymalnegowspółczynnika
kompresji
współ
czynnik
kompresji
=
dł
u
gość
(wejście)
−
dł
u
gość
(wyjście)
⋅
100
%
dł
u
gość
(wejście)
czyliwiększywspółczynnikkompresjioznaczalepsząkompresję.Jeślikompresja
danychosiągnęłapewienpoziom,awspółczynnikkompresjiuważamyzaniezadowa-
lający,toczyjestszansanapoprawieniego?Jeślitak,tonailejesttomożliwe?Poję-
cieentropiinabieratutajbardzopraktycznegoznaczenia,gdyżentropiaźródłana-
23
