Redukce dat C lem redukce dat je zmenit nroky na prostor potebn pro uchovn dat.
Redukce dat
+ +
Pi pohledu na soubory se znaky jako na texty zjist me, e m eme v t chto datech naj t r zn redundance (opakuj c se slova i znaky, zvislost mezi po sob jdouc mi entitami, mal univerzum reprezentovno p li velkm).
1 +
+ +
2 +
Ztr tov redukce Bezeztr tov redukce
dochz ke ztrtm informace (tj. nen monost obnovit data pesn stejn : dochz | nebo m e dochzet | k jist mu zkreslen )
umouje op tnou obnovu p vodn ch dat ) zakdovan soubor mus obsahovat stejn mnostv informace
nazvna t kompakce
n kdy nazvna komprese
vyu vna zejm na pro zmenen objemu dat ur ench k smyslov mu vn mn (obraz, zvuk, video), kdy mal odchylky nemus bt na zvadu, jsou-li vyveny vraznou redukc dat, ani by dochzelo k vrazn j mu sn en kvality vn mn
vdy existuje i reverzibiln proces (dekomprese)
+ +
3 +
+ +
4 +
Vhody a nevhody komprese Pklady komprese Omezen univerza mohou m t ni nroky na prostor
{ slice vyaduj pouze 4 bity ) m eme do jednoho bytu um stit hned dv slice (uet me tak a polovinu m sta)
{ pro ukldn velkch a malch p smen
esk abecedy vysta me se sedmi bity
+
5
Zde je vid t hlavn vhoda: uetil se potebn prostor na m di ch. Klesly tak nroky na syst m: velikost sekundrn pam ti a kapacita penosovch linek. Bu m eme sn it nklady, nebo m e doj t k nr stu vkonu. Tento zp sob komprese nastiuje i nevhody, kter s sebou komprese m e pin st: pro vyu vn dat m eme potebovat jet as a procesorov vkon (stejn jako i pomocnou pam ) pro pravu dat do zpracovvateln podoby. M e to v st ke ztrt vkonu (spotebovv se trochu pam ti a st vkonu procesoru). +
6
mus splovat podm nku jednoznan dekdovatelnosti
Z kladn pojmy Metody redukce dat jsou v tinou zaloeny na kdovn . Zkladn m probl mem bezeztrtov komprese je dekomponovat zdrojov materil (nap. text, obraz) na posloupnost udlost (jednotek v p pad text ), kter se sna me zakdovat tak, aby se spotebovalo co nejm n m sta. Tj. sna me se zakdovat zdrojov jednotky do kdovch slov. Mnoina vech kdovch slov tvo kd.
{ snadno dosaiteln u kdovch slov pevn d lky
{ poznme-li bezprostedn po pijet posledn ho znaku, hovo me o bezprostedn rozhodnutelnosti
{ tato vlastnost je spln na nap. tehdy,
plat -li pro jednotliv kdov slova, e nejsou prexem dn ho jin ho kdov ho slova (kd spluje tzv. prexovou vlastnost, tj. je prexov | existuj vak i kdy, kter jsou jednozna n dekdovateln , ale nejsou prexov )
Sna me se frekventovan j zdrojov jednotky kdovat krat mi kdovmi slovy a naopak.
+ +
7 +
Pojmy komprese
M jme zdrojovou abecedu S velikosti j S j= n. Prvky z S budeme nazvat zprvami. Kdovn zdrojov zprvy budeme nazvat kompres . Algoritmus zajiuj c kdovn zprvy nazveme kompresnm algoritmem (kodrem), obdobn algoritmus zajiuj c operaci opa nou (dekdovn ) dekompresnm algoritmem (dekodrem). C lem komprese je, aby zakdovan zprva (komprimovan zprva), byla men (nap. co do po tu bajt ) ne zprva p vodn . Takto z skan zprva mus bt jednozna n dekdovateln. Jak bylo uvedeno d ve, pi kdovn n kterch dat nemus bt dekdovan data identick s p vodn mi (nap. u obrzk ).
+ +
9
+
+ +
Pojmy komprese (2)
Dopln k kompresn ho pom ru do jedn udv relativn mnostv pam ti ueten zakdovn m. Nazv se zisk komprese a m eme jej vyjdit pom rem O(X ) ; L(X ) O(X ) + +
10 +
Poznatky z teorie informace (2)
Kdy pevn dlky | Pi kdovn m symbol n jednotek abecedy zdrojovch jednotek S m eme jednotliv symboly kdovat kdovmi slovy d lky lw = dlog2 ne:
Kdy promnn dlky | Jsou-li d lky zdrojovch jednotek lwi a pravd podobnosti jejich vskyt pi, pak O(X ) = m Pni=1 lwi pi, L(X ) = m lw, co vede k zisku komprese 2 ne : 1 ; Pndloglw p
+
+
Jedn m z parametr , kterm popisujeme vlastnosti komprese je kompresn pom r. Udv se v procentech, p padn jako slo mezi 0 a 1 (v etn ). Takto vyjden hodnota udv, jakou st p vodn velikosti zprvy zab r zprva komprimovan. Ozna me-li O(X ) velikost p vodn zprvy X , L(X ) velikost zakdovan zprvy, je kompresn pom r vyjden pom rem L(X ) O(X )
Poznatky z teorie informace
i=1 i
8
i
11
Lep ho kompresn ho pom ru lze doc lit kdy prom nn d lky, kdy nej ast ji se vyskytuj c m jednotkm piad me krat kdy a naopak. Ji v roce 1948 opublikoval Shannon v Teorii informace omezen na nejmen pr m rn po et binrn ch symbol nutnch k reprezentaci zdrojov jednotky. Pro mnoinu n udlost s pravd podobnostmi p1 : : : pn, jejich sou et se rovn jedn , navrhl Shannon funkci n X AE (S ) = pi log2 p1i i=1
kter se nazv entropi dan mnoiny udlost . Jej jednotkou je jeden bit. Entropie udv, jak mnoho volby je v pr m ru zahrnuto pi vb ru n jak udlosti. +
12
Poznatky z teorie informace (3) m v ce volby, t m v ce informace je zapoteb ke specikaci vsledk t to volby. Entropie je tedy m ra kvantity informace. Zaj mav j asi bude mnostv informace pro jednotlivou volbu. Je-li jej pravd podobnost pi, pak odpov daj c entropie m hodnotu Ei = log2 p1i : Z toho vyplv, e m ast ji se symbol vyskytuje, t m m n informace nese a m eme jej zakdovat m n bity.
Pozn mka: Pro pi = n1 pro vechna i je en-
tropie rovna log2 n, z eho plyne, e kdovn slovy pevn d lky je ji optimln . + +
13 +
Entropi zdrojov zprvy X d lky m je hodnota E (X ) =
AL(K ) =
n
X
i=1
lwi pi:
L(X ) =
m
X
i=1
lwi
obdr me redundanci zprvy X v kdu K jako rozd l R(X ) = L(X ) ; E (X ) =
m
X
(lwi + pi log2 pi):
i=1
+ +
14 +
Modely
pi(lwi+log2 pi)
Od po tku 80. let je rozd len proces komprese na dv sti: modelovn (piazen pravd podobnosti zdrojovm jednotkm textu) a kdovn.
Kompresn pom r je tak mon vyjdit jako pom r mezi pr m rnou d lkou zdrojov jednotky a o ekvanou d lkou kdov ho slova (AL(K )).
Model textu obsahuje informaci o zdrojovch jednotkch (nap. symbolech nebo slovech) a jejich pravd podobnosti v rmci dan ho textu
i v kontextu kolekce text : : :
AR(K ) = AL(K );AE (S ) =
X
i=1
Pozn mky:
Budou-li S a K zejm z kontextu, budeme tyto parametry vynechvat. 15 +
Modely kone nho kontextu
Kdovn na zklad t chto pravd podobnost pevd jednotky do posloupnosti bit .
+ +
16 +
Dal modely
pravd podobnosti jsou piazovny jednotlivm symbol m i stejn dlouhm skupinm symbol abecedy.
Modely kone nch stav | pou vny pro
pedpokld se, e tyto skupiny jsou nezvisl
Modely s gramatikou | pou vny pro zpr-
s rostouc d lkou kontextu roste innost komprese, ale tak nroky kod ru na prostor a as. d lka kontextu (po et dal ch symbol , k nim pihl me) se n kdy ozna uje jako d modelu
+
pi log2(1=pi):
Zavedeme-li jet hodnotu L(X ) jako dlku zakdovan zprvy X , tj.
pr m rn redundance kdu K :
+ +
i=1
Jsou-li d lky kdovch slov n jak ho kdu K lwi (i = 1 : : : n), je oekvan dlka kdovho slova kdu K
Poznatky z teorie informace (5) m
m
X
t mto model m se tak k Markovsk modely 17
regulrn jazyky (rozpoznateln kone nm automatem) vy generovateln bezkontextovou gramatikou
Oba druhy model jsou pou vny zejm na v oblasti um lch jazyk . V obou p padech je tak mon piadit pravd podobnosti k odvozovac m pravidl m.
Pklad: Nejjednodu model pro et zce DNA obsahuje 3 stavy a 4 pechody z kad ho z nich. +
18
Dlen model
Reprezentace celch sel
statick | vytvoeny pro mnoinu zprv (sta-
Univerzln kd
, aby na obou stranch byl stejn model)
{ pr m rn d lka kdov ho slova omeze-
polostatick | vytvej se pro kadou zpr-
na c1 AE + c2 (c1, c2 konstanty)
vu zvl (pedem) a pos laj se spolu se zakdovanou zprvou
{ optimln
adaptivn | vznikaj v pr b hu kdovn a
vyu vn pro kdovn pirozench sel, kdy d lka zpisu je m rn velikosti sla (nap. u slovn kovch a syntaktickch metod)
dekod r si je vytv automaticky sm" tento model neumouje p m p stup k stem zprvy | je nutn ji dekdovat od za tku.
+ +
19 +
() c1 = 1
+ +
20 +
Fibonacciho kdy (2) Fibonacciho kdy
Pro nezporn sla a jejich binrn reprezentaci plat
zaloeny na Fibonacciho slech du m2
R(N ) =
Fibonacciho sla du m jsou denovna nsledovn : F0 = F;1 = : : : = F;m+1 = 1 Fn = Fn;m + Fn;m+1 + : : : + Fn;1 (n 1)
P: d 2: 1,1,2,3,5,8,13,21, : : : d 3: 1,1,1,3,5,9,17,31, : : : + +
i=1
diFi
kde di 2 0 1, k N a Fi (0 Fibonacciho sla du 2.
i
k) jsou
Fibonacciho kd du 2 pro N F (N ) = d0d1d2 : : : dk 1 kde di 0 i k denovno ve, je opa n
zapsanou Fibonacciho reprezentac ukon enou dal jedni kou. D ky tomu, e binrn reprezentace nem nikdy dv jedni ky bezprostedn za sebou, je vsledn kd prexov.
21 +
+ +
22 +
Fibonacciho kdy | p klad
Fibonacciho kdy | vlastnosti Kd du 2
{ univerzln pro c1 = 2 a c2 = 3 { nen asymptoticky optimln (c1 > 1) Vyuit Fibonacciho kd vy ch d m e v st k lep kompresi.
+
k
X
23
N 1 2 3 4 5 6 7 8 16 32
+
R(N )
1 1 0 1 0 1 21 13 8
1 1 1 0 0 0 5
1 1 0 0 0 0 1 1 3
1 0 0 0 0 1 0 0 0 2
F (N ) 1 11 0 011 0 0011 1 1011 0 00011 1 10011 0 01011 0 000011 0 0010011 0 00101011 1
24
Standardn binrn reprezentace: (1) = 1 (N ) = (M )j , kde N = 2M + j .
Eliasovy kdy posloupnost r znch kd
kd nen jednozna n ( (5) = (2) (1))
n kter z nich univerzln
pouijeme dal symbol pro konec slova: (N ) = (N )#
nejjednodu z nich se nazv unrn (N ) = 00 : : : 0} 1 | {z
m eme vynechat vodn jedni ku:
N ;1
0(1) = " (przdn posloupnost) 0(2N ) = 0(N )0 0(2N + 1) = 0(N )1 0(N ) = 0(N )#
+ +
25 +
+ +
26 +
Eliasovy kdy (3)
Eliasovy kdy (4)
Kad bit binrn ho kdu (N ) je nsledovn bitem unrn ho kdu (j (N ) j). Vynechn m vodn ho bitu kdu (N ) (tj. pouit m 0(N )) a zat d n m t chto bit (po jednom) mezi bity kdu (j (N ) j) dostvme kd .
Vyjd me-li d lku slova funkc m sto , dostaneme kd, kter je pro velk N krat . (N ) = (j (N ) j) 0(N ) Kdovn !:
N (N ) (j (N ) j) 0(N ) (N ) 0(N ) 1 1 1 " 1 1 2 10 01 0 001 010 3 11 01 1 011 011 4 100 001 00 00001 00100 5 101 001 01 00011 00101 6 110 001 10 01001 00110
K
:= 0
WHILE b
log2 N c > 0
DO
BEGIN
K := (N )K N :=blog2 N c
END
Kd 0 vznikl sloen m (j (N ) j) a 0(N ). Kdy a 0 jsou permutac jeden druh ho.
N 1 2 3 4 5 (N ) 1 0010 0011 01100 01101 !(N ) 0 10 0 11 0 10 100 0 10 101 0
+ +
+ +
27 +
28 +
Shannon-Fanovo kdov n vyvinuto nezvisle Shannonem a Weawerem (1949) a Fanem (1949)
F zov n slo 0 1 2 3 4 5 6 7 8
kd 000 001 010 011 100 101 110 1110 1111
nejstar metoda pro statick rozd len pravd podobnost zaloen na rekurzivn procedue piazuj c kad zdrojov jednotce k jej mu kdov mu slovu jednu binrn cifru. Sou et pravd podobnost v dan m seznamu pravd podobnost budeme nazvat kumulativn pravd podobnost (dan ho seznamu).
+
29
+
30
Procedura SF Split PROCEDURE SF-Split(S) BEGIN
Algoritmus Shannon-Fanova kdov n
IF j
S j 2
THEN
BEGIN
Vstup: seznam n zdrojovch jednotek S &i], 1 i n, set d nch podle pravd podobnosti vzestupn
Vstup: n binrn ch kdovch slov
rozd l S na dva podseznamy S1 a S2 tak, e oba maj piblin stejn kumulativn pravd podobnosti" zet z vechna kdov slova pro S1 s 0" zet z vechna kdov slova pro S2 s 1" SF-Split(S1)" SF-Split(S2)"
BEGIN Initialize SF-Split(S) END
END END
+ +
31 +
S-F kdov n | p klad
+ +
M jme dev tiprvkovou abecedu, set d n seznam frekvenc zdrojovch jednotek (1, 1, 1, 1, 3, 3, 3, 3, 7). Odpov daj c pravd podobnosti vyjaduje seznam (1/23, 1/23, 1/23, 1/23, 3/23, 3/23, 3/23, 3/23, 7/23).
+ +
33 +
znmo od r. 1952 dlouho povaovno za nejlep metodu na kompresi text Vstup: seznam n zdrojovch jednotek ke kdovn , uspodan posloupnost p n vah (pravd podobnost ) p&i] (1 i n) jejich vskyt ve zprv
Vstup: kdov slova dan zet zen m ohodnocen hran na cestch od koene k jednotlivm list m binrn ho stromu + +
Statick Hu manovo kdov n (2)
34
Statick Hu manovo kdov n (3)
+
Pozn mky:
BEGIN
pro kadou jednotku i vytvo list o(p&i]) (uzel ohodnocen pravd podobnost p&i])" k := n" WHILE k2 DO
vsledn strom se nazv Human v vsledn kd je prexov
BEGIN
vyber z p dv nejmen nenulov p&r] a p&s], kde r 6= s" q := p&r] + p&s]" vytvo uzel ohodnocen q" hranm < o(q) o(p&r]) > a < o(q) o(p&s]) > pia ohodnocen 0 a 1" p&r] := q" p&s] := 0" k := k-1
m sto pravd podobnost m eme pou t i
etnosti znak ohodnocen hran stromu pomoc 0 a 1 je konvenc " je tud mono pou t i ohodnocen opa n
END
Hu)man v i Shannon-Fan v kd je mon generovat v ase O(n)
END
+
+
Statick Hu manovo kdov n
Tabulka vyjaduje postupn aplikace procedury SF-Split a vsledn kd. zdrojov pravd podobnost kdov krok jednotka slovo S&1] 1/23 1111 8 S&2] 1/23 1110 6 S&3] 1/23 1101 7 S&4] 1/23 1100 4 S&5] 3/23 101 5 S&6] 3/23 100 1 S&7] 3/23 011 3 S&8] 3/23 010 2 S&9] 7/23 00
32
35
+
36
Adaptivn Hu manovo kdov n | FGK
Vznamn varianty:
Vstup: dan Hu)man v strom T1, uzel o Vstup: modif. Hu). strom T2
{ FGK algoritmus
(Faller, Galagher, Knuth)
BEGIN
{ V algoritmus
o
current:=
(Vitter)
=root
WHILE current6
DO
BEGIN
vym podstrom v current s uzlem o0, kter m nejvy poad mezi uzly se stejnou frekvenc "
strom reorganizovn podle toho, jak se m n pravd podobnosti v pr b hu kdovn
current:=predcessor(current)
v obou variantch se na za tku nepedpokldaj dn informace o pravd podobnostech zdrojovch jednotek + +
37 +
Adaptivn Hu manovo kdov n | FGK (2) v druh fzi algoritmu dochz k modikaci frekvenc o hodnotu INCR
END END
+ +
Vitter navrhl pravu FGK s t mito vlastnostmi: po et vm n podstrom je nejve 1 minimalizuje nejen n
X
i=1
+
Aritmetick kdov n
d&i] p&i]
ale i Pni=1 d&i] a maxi d&i]
ALHD 2 ALHS , kde ALHD je pr m rn d lka kdovch slov dynamick ho Hu)manova kdovn a ALHS statick ho
39
+
Adaptivn Hu manovo kdov n | V
INCR se m e v pr b hu kdovn m nit (nap. podle posloupnosti 1 r r2 : : : rn, (r > 1)" pi pepln n libovoln ho ta e se vechny ta e vyd l rn
+ +
38
ALHD ALHS +1 (nejlep hodnota mezi dynamickmi Hu)manovmi metodami) + +
O Hu)mannov kdovn v me, e je optimln pro pravd podobnosti vskyt znak , kter jsou mocninami 1=2.
40 +
Aritmetick kdov n (2)
Data budeme reprezentovat slem z intervalu < 0" 1) tak, e interval, kter bude pro ten kter symbol k dispozici, rozd l me na sti odpov daj c pravd podobnostem jednotlivch symbol abecedy. Symbol, kter se na dan pozici ve zdrojov m textu vyskytuje, ur uje po te n interval pro dal symbol.
Reprezentujeme-li interval dvojic (L S ), kde L je doln mez intervalu a S jeho d lka. Postupn vvoj t chto veli in m eme vyjdit takto:
M jme abecedu a1 : : : an s pravd podobnostmi vskyt jednotlivch symbol p1 : : : pn. Kumulativn pravd podobnost jednotky ai denujeme takto:
Po te n nastaven je L = 0 a S = 1.
cpi = +
i
X
j =1
L := L + S cpi S := S pi
pj 41
+
42
pi ten dokumentu je vytven slovn k a zrove je generovn i c lov kd
Slovnkov metody Existuj dva zkladn druhy slovn kovch metod:
jsou kdovny cel frze (posloupnosti znak )
1. organizuj c slova pirozen ho jazyka
frze ve slovn ku slovny od 0
2. organizuj c et zce (tedy nejen slova)
v kad m kroku se najde nejdel frze shodn se vstupem a jej kd se zap e do c lov ho souboru
Vechny metody, o kterch si budeme pov dat, jsou adaptivn
na konec frze se pid prvn znak dal frze ! mme novou frzi + +
43 +
+ +
44 +
Algoritmus LZW | p klad Vstupn abeceda: fa b c dg Vstupn text: abacdacacadaad
Algoritmus LZW | poznmky po te n nastaven obvykle obsahuje vech 256 hodnot znakov sady (0 ; 255)
Po te n tabulka frz : Frze a b c d Poadov slo 0 1 2 3 Vstup Frze Kd Nov # 1 abacdacacadaad a 0 ab 4 2 bacdacacadaad b 1 ba 5 3 acdacacadaad a 0 ac 6 4 cdacacadaad c 2 cd 7 5 dacacadaad d 3 da 8 6 acacadaad ac 6 aca 9 7 acadaad aca 9 acad 10 8 daad da 8 daa 11 9 ad a 0 ad 12 10 d d 3
bvaj rezervovna dv sla frz : 256 | nov slovn k 257 | konec dat
+ +
45 +
+ +
46 +
Algoritmus LZW | p klad (3) Algoritmus LZW | p klad (2)
Stromov struktura slovn ku:
Dekomprese: Krok Vstup Vstup 1 0 a 2 1 b 3 0 a 4 2 c 5 3 d 6 6 ac 7 9 aca 8 8 da 9 0 a 10 3 d
+
Nov frze | ab ba ac cd da aca acad daa ad
slo ;
4 5 6 7 8 9 10 11 12
47
koen a0 b1 c2 d3 b 4 c 6 d 12 a 5 d 7 a 8 a9 a 11 d 10 Binarizovan struktura slovn ku: koen a0 b1 c2 d3 b 4 c 6 d 12 a 5 d 7 a 8 a9 a 11 d 10 +
48
Algoritmus LZW | p klad (5)
Algoritmus LZW | p klad (4)
Tabulka pro dekompresi:
Tabulka binarizovan ho slovn ku Poadov slo Znak Nsledn k Soused 0 a 4 1 b 5 2 c 7 3 d 8 4 b 6 5 a 6 c 9 12 7 d 8 a 11 9 a 10 10 d 11 a 12 d + +
Poadov slo Znak Pedch dce 0 a 1 b 2 c 3 d 4 b 0 5 a 1 6 c 0 7 d 2 8 a 3 9 a 6 10 d 9 11 a 8 12 d 6
49 +
+ +
50 +
LZ77 LZ podle jmen Lempel, Ziv slovn kem je st ji zakdovan ho textu okno sloeno ze dvou st :
{ hledac | st ji zakdovan posloup-
LZ77 | p klad Pedpokldejme tuto posloupnost: : : : cabracadabrarrarrad: : : Uvaujme situaci:
nosti
{ vhledov | obsah t to sti se hled zprva je kdovna trojicemi < o l c >, kde o je pozice v hledac m okn (po tno od m sta, kam a je zakdovno), l je d lka zprvy a c nov znak + +
51 +
cabraca dabrar
V hledac m okn nen prvn znak z okna vhledov ho, na vstup jde trojice < 0 0 C (d) >.
+ +
LZ77 | p klad (2)
+
LZ77 | dekdovn
Situace ukazovtko o=7 ?
52
pou v se stejn okno jako pri kdovn (tedy je i vhledov st) -
dekduje se do vhledov ho okna | m eme pak dekdovat i ty pase, k jejich zakdovn bylo vyuito i obsahu vhledov ho okna.
cabracadabrarrarrad l=4
Aplikace LZ77
dv kd < 7 4 C (r) >. Je-li ka okna W , rka jeho hledac sti S a po et znak v abeced A, pak pro kadou trojici potebujeme dlog2 S e + dlog2 W e + dlog2 Ae bit .
Na algoritmu LZ77 dopln n m o dal kdovn prom nn d lky jsou zaloeny nap klad programy PKZip, Zip, LHarc a ARJ.
+
+
53
54
Metoda LZR
LZSS
navrena Rodehem
navrena Bellem podle idej Storera a Szymanskiho
vyu v strom obsahuj c vechny pedpony v dosud dekdovan sti
vstupem posloupnost ukazatel a znak
ve, co dosud zakdovno, vyuito jako slovn k
ukazatel | dvojice (i j ) | ob sloky stejn vznam jako u LZ77
ke kdovn hodnoty i v trojici < i j a > pouito kdovn !0
pouze ukazatel pro dostate n dlouh et zce, jinak v kdu p mo jednotliv znaky
potenciln m e strom r st nade vechny meze" v praxi po napln n vyprzdn n
poteba rozliit kop rovan znak a odkaz
+ +
55 +
+ +
56 +
LZH navreno Brentem
LZB navreno Bellem
varianta LZSS
podoba s LZSS
ke kdovn ukazatel vyu v Hu)manovo kdovn
v situac ch, kdy okno nen vyuito cel (tj. na za tku komprese a pi kompresi krtkch dat), vyuito m n bit (ke kdovn posunu vyu v fzovn " d lka et zce kdovna )
vyuita i frekvence jednotlivch prvk slovn ku I. fze: LZSS s hl dn m frekvenc II. fze: Hu)manovo kdovn
+ +
57 +
+ +
58 +
LZ78
LZC
kd sloen ze dvou st :
vyuito v programu compress
{ odkaz na prvek ve slovn ku { znak, o kter byla sekvence prodloue-
vychz z LZW
na
odkazy do slovn ku kdovny s prom nnou d lkou slova
vhoda: u kdovan v ci neute ou z okna
po pepln n slovn ku monitoruje kompresn pom r | kdy za ne kompresn pom r klesat, vymae se slovn k
nevhoda: slovn k roste nade vechny meze +
59
+
60
LZT LZMW
navreno Tischerem
navreno Millerem a Wegmanem
zaloeno na LZC
zaloeno na LZT
frze ve slovn ku uloeny podle posledn ho pouit | prvn v seznamu je posledn se objeviv frze
nov frze nevznik pidn m symbolu k frzi, ale zet zen m posledn ch dvou frz
indexy frz fzovny
+ +
61 +
LZJ
+ +
navreno Fialou a Greenem
modikace LZ78, d lka poloek ve slovn ku omezena h
pro uloen slovn ku pou v stromovou strukturu, kde hrany jsou ohodnoceny et zci tvoen jedn m i v ce symboly a uzly obsahuj ukazatele do okna a identikuj c symboly na cest z koene do tohoto uzlu
kdovn provd no nad lesem strom ( i trie) hloubky h, kde po cest jsou et zce ze vstupu stromy binarizovny
frze kdovny dvojicemi (d n):
pouit omezen prostor pro uzly pi pepln n je mon bu pestat pidvat, nebo vyhodit nejm n pou van poloky | to ale vyaduje m t pro tento el pomocn daje (nap. frekvence vskytu). 63
+
Slovnkov metody s restrukturalizac slovnku U dosud probranch metod se nov poloky pidvaly na konec slovn ku. Existuj vak i metody, kter si pr b n upravuj poad poloek ve slovn ku. To umouje, aby se asto pou van poloky dostaly na za tek slovn ku a mohly tak m t krat kdy (tj. jejich indexy mohou bt kdovny men m po tem bit | samozejm za pedpokladu, e pouijeme kdovn pirozench sel s prom nnou d lkou kdu).
+
+
LZFG
Jacobsson, 1985
+ +
62
65
d ... po et symbol shodnch s et zcem z ohodnocen hrany vedouc do uzlu n n ... identikace uzlu + +
64 +
Slovnkov metody s restrukturalizac slovnku (2) Slovn ky se v tinou reorganizuj podle n kter z t chto heuristik (li c ch se nakldn m s prv nalezenou polokou): pesun na za tek vm na s pedch dcem pesun vped o k zven etnosti a zaazen podle nov hodnoty +
66
zaloena na heuristice 'pesun na za tek' a na prom nn d lce kd sel (Elias v kd , p padn Fibonacciho kdy) kd sloen z index poloek ve slovn ku a p padnch novch slov
Kdovan text: KA+D, SOFSEMISTA MUS- KA+D, DEN BD-T CEL, DEN Stav slovn ku:
za kad slovo je posln jeho index ve slovn ku (existuje-li) nebo slo o 1 vy ne je po et prvk ve slovn ku
kad sofsemista kad mus sofsemista kad kad mus sofsemista den kad mus sofsemista bd t den kad mus sofsemista cel bd t den kad mus sofsemista den cel bd t kad mus sofsemista
v obou p padech se poloka pesune na za tek seznamu
Vsledn zprva: 1 kad 2 sofsemista 3 mus 3 4 den 5 bd t 6 cel 3
na za tku slovn k prdn
+ +
67 +
+ +
Pedn komprese
+
Zadn kompakce
pou v se pro zmenen objemu index
pou v se pro zmenen objemu index
vyu v toho, e v abecedn set d n m seznamu bvaj za sebou slova se stejnou pedponou
ponechv pouze pedn sti poloek, kter sta na odlien jednotlivch prvk
tato pedpona zaznamenna jednou, ostatn poloky obsahuj pouze zbytek 'slova'
nen mon p mo zrekonstruovat p vodn data (pokud je to teba, jsou v zznamech) vhodn je kombinovat tuto metodu s pedn kompres
vhodn je kombinovat tuto metodu se zadn kompakc + +
69 +
Komprese bitovch map Pedpokldejme, e mme bitovou mapu, v n je pravd podobnost vskytu "0" na libovoln pozici p a pravd podobnost vskytu "1" je 1 ; p" Bity jsou nezvisl jeden na druh m. Budeme-li kdovat bloky pevn d lky (k), bude takovchto blok 2k. Ozna me i po et "0" v dan m bloku. Pak pravd podobnost vskytu takov hoto bloku je pi(1 ; p)k;i. Jednotlivm blok m bit tak m eme staticky piadit Hu)manovy kdy prv dle t chto pravd podobnost . Toto sch ma kdovn ozna ujeme Hufb(p" k). +
68
71
+ +
70 +
Komprese bitovch map (2)
Je tak mon kdovat tzv. b hy { posloupnosti nul zakon en jedni kou, p padn posloupnosti nul samotnch. Parametrem metody je m udvaj c maximln d lku b hu. Pravd podobnost b hu s j nulami a jedni kou je pj (1 ; p), pravd podobnost b hu s m nulami je pm. T mto zdrojovm jednotkm op t m eme staticky piadit Hu)manovy kdy. Toto sch ma se ozna uje Hufr(p" m). Pro p ! 1 se pro m = 5 8 10 dosahuje zisku komprese o d vy ho ne u kdovn pevnch blok . I kdovn m pevnch blok lze doshnout vy ho stupn komprese, ale za cenu vy ch nrok na pam (pro k = 15 je potebujeme zakdovat v ce ne 32 000 blok ). +
72
Redukce indexu pomoc bitov mapy Redukce indexu parci lnho atributu Je p pustn , aby n kter z atribut zznamu nem l zadnu (vypln nu) hodnotu. Je-li takovchto zznam s nevypln nm atributem v ce, je vhodn indexovat pouze ty zznamy, pro n je hodnota dan ho atributu znma. Takovouto situaci m eme eit nap klad pomoc n kter z uvedench metod: bitov mapa, kdovn b h , kdovn pomoc hlavi ky.
+ +
73 +
Pln poloky kdujeme pomoc "1" v bitov map a ulo me i hodnotu" przdn poloky jen pomoc "0" v bitov map . M jme posloupnost hodnot (a 'ne-hodnot'): aba,0,0,0,gv,0,0,0,0,cx. Poslupnost zakdujeme pomoc bitov mapy 1000100001 a et zce hodnot aba,gv,cx. Nro nost kdovn i dekdovn je linern k po tu bit v bitov map (tj. k po tu hodnot a przdnch poloek). + +
74 +
Redukce indexu pomoc hlavi ky
Redukce indexu pomoc kdov n bh
Hlavi ka je posloupnost ta udvaj c ch st dav kumulovan po ty hodnot a przdnch pozic. Na zklad t chto daj a posloupnosti hodnot (fyzick zprvy) je mon zrekonstruovat p vodn dk seznam hodnot.
B hem se zde rozum maximln posloupnost przdnch jednotek. Kad b h se nahrad trojic odd lova , symbol przdn jednotky, d lka b hu.
P vodn zprvu
Vyhledvn je m rn d lce zprvy.
je mon zakdovat hlavi kou 2,3,3,7,6 a fyzickou zprvou
da,aba,0,0,0,gv,0,0,0,0,cx,go,si
da,aba,gv,cx,go,si. Ob zobrazen je mon provd t v ase O(log h), kde h je velikost hlavi ky. + +
75
+ +
Redukce dat | z vr inn j kopresn metody m vaj zpravidla vy nroky na zdroje (prostor, as) vhodnost metody nen dna jen dosahovanm kompresn m pom rem, ale i odolnost v i chybm, rychlost komprese, nroky na zdroje pi dekompresi, atd. velmi zaj mavou skupinou metod jsou specializovan metody pro vybran typy dat
+
77
76
