Komprese dat [ KMI/KOM ]
V předmětu jsou představeny základní i moderní metody bezeztrátové komprese dat. Metody ztrátové komprese multimediálních dat jsou probírány v předmětu Multimediální systémy.
Zkouška
- požadované znalosti dány seznamem přednášek, přesněji odpřednášenou látkou a obsahem slajdů k přednáškám
- průběh ústním zodpovězením vylosovaných otázek, jedné včetně příkladu, s písemnou přípravou
Zápočet
- požadováno vypracování zápočtového programu implementujícího zvolený algoritmus komprese (a dekomprese)
- požadavky na program: textové řádkové rozhraní (CLI), vstupní/výstupní data načítána/zapisována ze/do standardního vstupu/výstupu nebo souboru zadaného jako parametr při spuštění, libovolná vstupní data (pokud není při zadání vypracování programu řečeno jinak)
- algoritmy: porovnání velikostí kódů čísel pro narůstající číslo, Shannon-Fanovo kódování, binární adaptivní Huffmanovo kódování, neceločíselné semi-adaptivní aritmetické kódování, celočíselné adaptivní aritmetické kódování, neceločíselné QM kódování, celočíselné QM kódování, PPMA, PPMB, PPMC, BWT (+ MTF + RLE), kódování n-gramů, LZ77, LZSS, LZ78, LZFG (varianta A1), LZW, LZAP
- další info na stránkách cvičícího
Materiály
Přednášky
- Úvod:
Taxonomie kompresních metod, modely dat (pravděpodobnostní, Markovův).
slajdy - Úvod:
Potřebné pojmy z teorie informace a kódování (entropie, optimální
prefixový kód),
slajdy - Úvod:
Základní techniky (RLE, MTF) a kódování čísel (Eliasovy kódy).
slajdy - Statistické metody:
Shannon-Fanovo a Huffmanovo kódování, principy a implementace.
slajdy - Statistické metody:
Aritmetické a QM kódování, principy a implementace.
slajdy - Kontextové metody:
Metody PPM a PAQ (context mixing), principy a implementace.
slajdy - Kontextové metody:
Blokové třídění (Burrows-Wheelerova transformace, BWT), principy a implementace.
slajdy - Slovníkové metody:
Rodina metod LZ77 a varianta Deflate, principy a implementace.
slajdy - Slovníkové metody:
Rodina metod LZ78 a varianta LZW, principy a implementace.
slajdy - Další bezeztrátové metody: Gramatické, statistické a jiné vybrané metody.
Cvičení
Literatura
- Sayood K.: Introduction to Data Compression, Fifth Edition. Morgan Kaufmann, 2018. ISBN 978-0128094747.
- Salomon D., Motta G.: Handbook of Data Compression, 5th edition. Springer, 2010. ISBN 978-1848829022.
- McAnlis C., Haecky A.: Understanding Compression: Data Compression for Modern Developers. O'Reilly, 2016. ISBN 878-1491961537
- Mengyi Pu I.: Fundamental Data Compression. Butterworth-Heinemann, 2006. ISBN 978-0750663106.
- Salomon D.: Data Compression: The complete Reference, 4th edition. Springer, 2006. ISBN 978-1846286025.
- Hankerson D. C., Harris G. A., Johnson P. D.: Introduction to Information Theory and Data Compression, Second Edition (Applied Mathematics). Chapman and Hall/CRC, 2003. ISBN 978-1584883135.
- Sayood K.: Lossless compression handbook. Academic Press, 2003. ISBN 0126208611.