Algoritmy komprese dat Úvod
Marcus Hutter (*1967) ANU Canberra
7.10.2015
NSWI072 - 1
Komprese dat Kódování dat s cílem zmenšit jejich objem odstraněním nadbytečné informace. Data musí být možno obnovit dekódovacím algoritmem. Algoritmus komprese = kódování (komprese) + dekódování (dekomprese) Komprese • bezztrátová: obnovená data jsou identická originálu • ztrátová: obnovená data jsou „rozumnou“ aproximací originálu
Metody • statické / adaptivní • symetrické / asymetrické • proudové / blokové 2
Funkce komprese ✓úspora paměti komprese/ dekomprese
✓komunikace odesílatel
komprese
dekomprese
3
příjemce
Jak změřit účinnost komprese? délka vstupních dat délka komprimovaných dat
v bajtů k bajtů (K bitů)
míra
vzorec
příklad
kompresní poměr
k / v * 100%
36%
kompresní faktor
v:k
3:1
kompresní zisk
(v-k)/v*100%
64%
bpc (bits per char) K/v 2.92 b/c bpp (bits per pixel) průměrná délka kódového slova relativní komprese 100 ln (k / k’) 10.5 (percent log ratio) k’ bajtů = délka dat komprimovaných zvoleným standardním alg. 4
Měření účinnosti: datové korpusy Rychlost: CPB (cycles per byte) • pro speciální hardware
Datové korpusy • experimentální měření účinnosti bezztrátové komprese
Calgary Corpus (1987) • 14 souborů: text, grafika, binární soubory
Canterbury Corpus (1997) http://corpus.canterbury.ac.nz
• 11 souborů + artifical c. (4) + large c. (3) + miscellaneous c. (1)
Silesia Corpus (2003)
Sebastian Deorowicz, Politechnika Śląska, Gliwice
http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia
• 18 souborů o velikostech 6 – 51MB
Prague Corpus (2011)
Jan Holub et al., FIT ČVUT, Praha
5
Canterburský korpus
6
Canterburský korpus - pokračování The Artificial Corpus a.txt
The letter 'a'
1
aaa.txt
The letter 'a', repeated 100,000 100000 times. alphabet.txt Enough repetitions of the alphabet 100000 to fill 100,000 characters random.txt 100,000 characters, randomly selected from [a-z|A-Z|0-9|!| ] (alphabet size 64) 7
100000
Canterburský korpus - pokračování The Large Corpus E.coli
Complete genome of the E. Coli 4638690 bacterium bible.txt The King James version of the 4047392 bible world192.txt The CIA world fact book 2473400
The Miscellaneous Corpus pi.txt
The first million digits of pi 8
1000000
Slezský korpus
9
Měření účinnosti: datové korpusy Maximum Compression
http://www.maximumcompression.com
• maximální dosažitelný kompresní poměr pro specifické typy dat (text, .exe, .jpg apod.) • single file compression: 10 souborů 823kB – 20MB • multiple file compression: 510 souborů 301MB celkem • Jan Ondruš: PAQ8PX, http://en.wikipedia.org/wiki/PAQ Pizza & Chili http://pizzachili.dcc.uchile.cl
• • • •
Paolo Ferragina (University of Pisa) Gonzalo Navarro (University of Chile) testování komprimovaného indexu 7 souborů 55.8 MB - 2.21 GB
10
Pizza & Chili
File SOURCES PITCHES PROTEINS PROTEINS.OLD DNA ENGLISH XML
Size 210.9 MB 55.8 MB 1.18 GB 66.8 MB 403.9 MB 2.21 GB 296.1 MB
|⌃| 230 133 27 24 16 239 97
Description concatenated C/Java source code files human readable MIDI files newline-separated protein sequences from the Swissprot database older version of PROTEINS newline-separated gene DNA sequences from Gutenberg Project concatenation of English text files from Gutenberg Project XML formated bibliography from dblp.uni-trier.de.
11
Soutěž o nejúčinnější kompresi Calgary Corpus Compression Challenge (1996) • http://mailcom.com/challenge/ • (777,777.00 - X) / 333 za archiv délky X Byte z původních 14 souborů Calgarského korpusu • nyní (580,170.00 - X) / 111 $
12
Soutěž o nejúčinnější kompresi Calgary Corpus Compression Challenge (1996) Size
Date
Name
759881
09/1997
Malcolm Taylor
692154
08/2001
Maxim Smirnov
680558
09/2001
Maxim Smirnov
653720
11/2002
Serge Voskoboynikov
645667
01/2004
Matt Mahoney
637116
04/2004
Alexander Rhatushnyak
608980
12/2004
Alexander Rhatushnyak
603416
04/2005
Przemysław Skibiński
596314
10/2005
Alexander Rhatushnyak
593620
12/2005
Alexander Rhatushnyak
589863
05/2006
Alexander Rhatushnyak
580170
07/2010
Alexander Rhatushnyak 13
Soutěž o nejúčinnější kompresi II Hutter Prize (2006) http://prize.hutter1.net • archiv prvních 100MB internetové encyklopedie Wikipedia • 500 € za každé 1% zlepšení velikosti archivu autor
datum
dek
vel
komp. faktor
Matt Mahoney
24.3.2006
paq8f
18'324'887
5.46
854MB
5h
Alexander Ratushnyak
25.7.2006
paq8hp5
17'073'018
5.86
900MB
5h
Alexander Ratushnyak
14.5.2007
paq8hp12 16'481'655
6.07
936MB
9h
Alexander Ratushnyak
23.5.2009
decmprs8
6.27
936MB
9h
15'949'688 14
RAM čas
Hutterova cena Motivace: podpořit výzkum v oblasti AI Kolmogorovská složitost (algoritmická teorie informace) Alternativa Turingovy imitační hry Marcus Hutter: being able to compress well is closely related to acting intelligently • M. Hutter, Towards a Universal Theory of Artificial Intelligence based on Algorithmic Probability and Sequential Decisions, Proceedings of the 12th European Conference on Machine Learning, 226-238, 2000 • optimální chování racionálního agenta v neznámém prostředí • interakce 2 Turingových strojů, které se v každém kroku posílají zprávy • cílem agenta je maximalizovat hodnotu účelové funkce, kterou dává prostředí • optimální chování agenta: prostředí řídí nejkratší program, konzistentní se všemi dosud vydanými zprávami 15
Meze bezztrátové komprese Kódování f : {n-bitová slova} → {slova délky < n} | Dom f | = 2n | Im f | ≤ 2n - 1 ⇒ f nemůže být prosté! Buď M ⊆ Dom f tž. ∀w ∈ M, | f(w) | ≤ 0.9n f prosté na M ⇒ |M| ≤ 21+0.9n - 1 n = 100, |M|/ 2n < 2-9 n = 1000, |M|/ 2n < 2-99 ≈ 1.578 ⋅10-30 16
Historie - Braillovo písmo Louis Braille (1820) w pole 3 × 2 bodů w písmena, slova w cca 80% komprese
17
Historie - Baudotův kód J.M.E.Baudot (1880) w telegraf w 5bitový kód pro písmeno/znak w přepínání LTRS,FIGS
18
Historie - Morseova abeceda Samuel Morse (1838) A .H .... O B -... I .. P C -.-. J .--- Q D -.. K -.- R E . L .-.. S F ..-. M -T G --. N -. U
--- V .--. W --.- X .-. Y ... Z ..19
....--..-.---..
Další jednoduché metody Komprese slovníku Adam adaptace adekvátní adept admirál afekt aféra agenda agent
Adam 3ptace 2ekvátní 3pt 2mirál 1fekt 2éra 1genda 4t
R.Nix: Experience with a space efficient way to store a dictionary, Commun. ACM 24(1981), 297-8.
20
Další jednoduché metody Textový editor MacWrite (D.M.Young, 1985) 4bitové kódy znaků • mezera • e,t,n,r,o,a,i,s,d,l,h,c,f,p • <escape>
Ostatní znaky: • <escape><8bitový ASCII kód znaku>
Každý odstavec zvlášť, expanze ⇒ původní ASCII kód Bitový příznak pro každý odstavec 21
