Komprese Dat

Garant: Snášel

prednasejici:

Lukas Vojacek

Jiri Dvorsky

http://www.cs.vsb.cz/dvorsky/KODKomb.html

Zapocet

22. dubna 2011, 23:59

poslat e-mail jiri.dvorsky@vsb.cz

jsou dve moznosti jak ziskat zapocet:

• 1. vypracovani prace na tema na 5 A4

  2. implementace knihovny ktera umi komprimovat a dekomprimovat

Zkouska

formou pisemneho testu

• • eliasovo kodovani

  • move to front

  • fibonaciho kodovani

Odkazy

Materialy z webu

• • Benes strnaky predmetu Komprese dat - http://www.cs.vsb.cz/benes/vyuka/pte/texty/komprese/

  • Popis a Java Aplet ukazky - http://www.stringology.org/DataCompression/obsah.html

  • Jan Holub CVUT http://service.felk.cvut.cz/courses/X36KOD/

• http://www.booring.net/data/komprese/index.php

• http://voho.cz/wiki/huffmanovo-kodovani/

• http://atrey.karlin.mff.cuni.cz/~tnovak/compress/huffman/

• http://en.wikipedia.org/wiki/Huffman_coding

• http://wikipedia.infostar.cz/h/hu/huffman_coding.html

• http://cs.wikipedia.org/wiki/Huffmanovo_kódování

• http://ksvi.mff.cuni.cz/~dvorak/vyuka/NSWI072/

• http://ksvi.mff.cuni.cz/~dvorak/vyuka/NSWI072/Huffman.pdf

  • http://tom-ash.net/blogs/Blog.aspx?File=Programming/20090602_HuffmanCompression.blog\

• http://patisoners.vakoveverky.net/sinclair/files/jhcon_formaty_komprese_2008sirk_rev15.pdf

• http://www.martinvseticka.eu/index.php?sekce=browse&page=175

• http://www.codepedia.com/1/Art_Huffman_p1

• http://www.codepedia.com/1/Art_Huffman_p2

Testovaci soubory (Compressions Corpus)

• http://corpus.canterbury.ac.nz

• http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia

http://sites.google.com/site/datacompressionguide/

prezentace o kodovani

• http://eamos.pf.jcu.cz/amos/kat_inf/externi/kat_inf_09509/ADS2-09.pdf

2010 - Prednaska 7.5.2010

Bezstratove algoritmy

RLE kodovani

opakovaci bajt zacinal 0xC0

Huffmanovo kodovani

udelam si seznam znaku a jejich cetnosti

vybernu dva znaky s nejmensi cetnosti z nich udelam prvni dva prvky stormu spojim je korenem ktery ma cetnost = soucet cetnosti tech dvou prvku

Ternarni kod(strom)

0 1 2

lepsi pro troj hodnotove pocitace, na binarnich pocitacich je ale lepsi huffmanovo

Komprimace malych souboru

Komprimace DNA abeceda obasuje 4 znaky

LZW

inicializace slovniku abecedy pouzite v vstupmin datovem souboru

muzeme si hrat s optimalizaci slovniku, pri dekompresi se muze objevit kod ktery neni ve slovniku

Ukazka LZW komprimace:

vstup a b a c d a c a c a d a a d

vystup 0 1 0 2 3 6 9 8 0 3

tabulka

a 0

b 1

c 2

d 3

ab 4

ba 5

ac 6

cd 7

da 8

aca 9

acad 10

eof ... priznak konce souboru, pridekompresi vim ze jsem na konci

reset ... pri dekompresi muze znamenat promazani slovniku

BitStream

pole

write(int code, length)

close() ulozi po bajtech na disk

pro dekomprimaci taulku mit v n-arnim stromu

|pismeno|potomek|next|

|a|...|1|b|null|2|c..... algoritmus pro kompresi disku

Stratove algoritmy

Vector quantization(kvantovani vektoru)

komprimace obrazku, zvuku

obrazek rozdelime na ctverecky a ty vkladame do kodove knihy

slovnik je kodova kniha v ni mam vektor ten mohu zakodovat bezstratovym algoritmem LZW, Huff

kodovou knihu kodujeme

Komprese čísel

Fibonacciho komprese čísel

vyplaci se pro komprimaci malych cisel, protoze nasobky 2 rostou rychleji. 32b cislo binrne ve vetsi nez 40b cislo fibonacciho

aa

prevod cisla 60 do finbonacciho 60 = 100001000F

otocime cislo 0001000011F fibonacciho kod

1... 11F, 3 ... 0011F, 8 ... 0000011F

Projekt:

naprogramovat algoritmus, pohrat si s vlastnim algoritmem

zkuit zkombinovat RLE s ..., Huffmanem ale do nej pridat specialni znak 1

a porovnat s klasckym huffmenenm jaky byl kompresni pomer co je lepsi, porovnat s winzipem, winrarem, rychlost, kompresni pomer

1 prezentace

2 text s popisem a vysledky

strucne co je to za algoritmus

muj napad experimentu

3 experimenty tabulka soubor velikost kompresni pomer

4 zaver a hodnoceni