Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
16
20Informacjaikodowanie
WalgorytmieVitteryzaostrzonoostatniezałożenie–otrzymujesięrównież
ciągliczbnierosnących,leczwobrębiepodciągówotychsamychwartościachna
początkusątepochodzącezwęzłówwewnętrznych,anakońcuzliści.
Gdylicznikwliściuzwiększysię,algorytmymodyfikująniewielkifragment
drzewa(przemieszczającniektórewęzły),zachowującpodanewyżejwłasności.
BardziejzłożonyalgorytmVitterydajekrótszekodyniżalgorytmFGK.
2.2.3.KodyLempela-Ziva
AlgorytmbezstratnejkompresjidanychopracowanyprzezLempelaiZiva
wytwarzakodopartynasłownikuadaptacyjnym[85]0Kompresjapolegatuna
zastępowaniupowtarzającychsięciągówbitów,bajtów,albosłówliczbami
wskazującymirozmiarilokalizacjętakiegociągu.Takiewykrytepowiązania
tworząsłownikorozmiarzekilkudziesięciukilobajtówdanych.Jeśliciągsię
powtórzy,tojestzastąpionyprzezliczbypodającejegopozycjęwsłowniku
idługośćciągu.Zawartośćsłownikajestnabieżącoodtwarzanaprzezdekoder.
AlgorytmkompresjiLempela-Ziva
Buforwejściowyzawierasłownik,przechowującykostatnioprzetwarzanych
symboli(indeksowanyod0dok–1)orazbuforkodowania,przechowującyn
symbolidozakodowaniaindeksowanychodkdok+N–1
słownikjestwypełnianypierwszymsymbolemwejściowymitensymbol
jestzapisywanynawyjście,
dobuforawejściowegowstawianejestnpierwszychsymbolizwejścia.
Dopókiwbuforzewejściowymsąjakieśdane:
wsłownikuwyszukiwanyjestnajdłuższypodciągrównypoczątkowi
buforakodowania(najdłuższyprefiks);nadawanyjestmuindeksP<k-1
początkuwyszukanegopodciąguijegodługośćCŚn-1;jeślipodciągunie
udasięznaleźć,toC=0zaśPjestdowolne,
nawyjściewyprowadzanajesttrójka(P,C,S),gdzieStosymbolzbufora
wejściowegonastępującypodopasowanympodciągu,
okno(słownik+buforwejściowy)przesuwanejestwlewooC+1pozycji
iuzupełnianekolejnymisymbolamizwejścia(oilejeszczesąjakieś).
Algorytmdekompresji
Takjakpodczaskompresji,buforwejściowyzawierak-pozycyjnysłownik,który
jestwypełnianypoczątkowymsymbolem,orazn-pozycyjnybuforkodowania0
Dekompresjajestwykonywanadlakażdejtrójki(PiCiS)wgprocedury:
kopiujzesłownikadobuforawyjściowegosymbolezzakresuPłP+C-1,
doklejnakoniecbuforawyjściowegosymbolS,
wyprowadźC+1początkowychsymbolizbuforawyjściowego,
przesuńzawartośćbuforaoC+1pozycjiwlewo0
Opisanapodstawowawersjaalgorytmumawielemodyfikacji,którychcelem
jestpoprawieniestopniakompresji[32]0
