Komprese dat
kompresní algoritmy
typy komprese:
- bezeztrátová - lze obnovit původní data
- ztrátová - nelze obnovit původní data (větší zmenšení, snížení kvality)
komprese textu:
- vyhledání opakované sekvence a nahrazení kratšími sekvencemi...
presteat seat precleater weat ......... 26 b
eat .... "○"
pre ... "□"
□st○s○□cl○erw○ ............ 14 b
příklad 2: to be or not to be, that is the question....... to ...... be ....... th - uložení tabulky se změnami, které počítač provedl, aby mohl rekonstruovat originál
- vložení metadat (data poskytující informaci o jiných datech)
algoritmus LZW84
- bezeztrátový kompresní algoritmus
- Abraham Lempel
Jacobs Ziv
Terry Welchen
1984 - data dále nekompromovatelná
- nepotřebuje žádný slovník
- při kompresi a dekompresi vytváří pomocný seznam frází
- + informaci o seznamu znaků (typicky 256 znaků ASCII)
- vhodný pro přenos dat po síti
- komprese: abacdacacadaad
krok | text vstupu | nalezená fráze | výstup | nová fráze | index nf
- na vstupu najde nejdelší frázi zapsanou v nových frázích, index zapíše na výstup
- nalezenou frázi odstraní ze vstupu
- nová f. = nalezená f. + 1. znak
a 0
b 1
c 2
d 3
1 aba......daad a 0 ab 4
2 ba... daad b 1 ba 5
3 acd ...daad a 0 ac 6
4 cda ... daad c 2 cd 7
5 dac ...daad d 3 da 8
6 aca ...daad 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
=> 0102369803
- dekomprese: 0102369803
najprve všechny znaky abecedy
- ze vstupu se odstraní číslo a na výstup se přidá odpovídající fráze
- nová f. -> ta z minulého kroku + 1. znak
krok | vstup | výstup | nová fráze | index n. f.
a 0
b 1
c 2
d 3
1 0 a
2 1 b ab 4
3 0 a ba 5
4 2 c ac 6
5 3 d cd 7
6 6 ac da 8
7 9 aca aca 9
vloží se znovu na vsup poslední výstup
+ jeho 1,. znak
to stejné do nf
8 8 da acad 10
9 0 a daa 11
10 3 d ad 12
=> abacdacacadaad
komprese obrázku
kompresní algoritmus: kódování délkou běhu (RLE)
reprezentace obrázku - bitová mapa (viz dříve
RLE kompresní algoritmus: 000001111100000
místo "nula" "nula" "nula" "nula" "nula" "jedna" "jedna" "jedna" "jedna" "jedna" "nula" "nula" "nula" "nula" "nula"
"pět nul" "pět jedniček" .....
řádek obsahuje 3 × "1", 2 × "0", 5 × "1", 2× "0", 4 × "1" ( tj. 111001111001111)
začíná vždy počtem bílých ...
3, 2, 5, 2, 4
v případě 000110000011111100 ................... 0, 3, 2, 5, 6, 2
- mnoho opajkování
- menší počet barev
fotografie neobsahuje mnoho sekvencí stejné barvy!
Huffmannova komprese
bezeztrátová komprese
4 znaky A, C, G, T (sekvence DNA)
původní text: A G C T T T T C A T T C T (4.6 mil znaků)
stačí dva bity
A 00
C 01
G 10
T 11
00100111111111010011110111 ..... 26 b
"T" 7× 1
"C" 3× 00
"A" 2× 010
"G" 1× 011
0100110011110001011001 ..... 22 b ...... - 4b
Ztrátová komprese
odstraníme méně důležité informace
foto, video, zvuk
obrázky: zachovat jas, sladit barvu (jas vnímáme lépe, rozdíly v barvách hůř)