Bezztrátové komprese datBezztrátové komprese dat

Jan Tejmar

Obsah

• Využití bezztrátové komprese dat

• Používané metody komprese dat

• Srovnání efektivnosti různých typů

Využití bezztrátové komprese• Archivace velkých množství dat

• Zefektivnění datových přenosů

• Zmenšení objemu dat bez ztráty informačního obsahu

• Originální data a data po dekompresi komprimovaného

souboru jsou totožná

Metody komprese dat

• Slovníkové metody

- LZ77 (PNG) - LZ78 - LZW (GIF)

• Statistické metody

- Huffmanovo kódování

- Aritmetické kódování

- Shannon-Fanovo kódování

• RLE – Run lenght encoding – opakování znaků ( PCX)

RLE – Run length encoding

• Použití: zřídka pro kompresi textů, častěji pro obrazovou informaci• Princip: opakující se symboly se kódují dvojicí(počet_opakování , symbol)

Kódování délky se provádí:• u každého znaku je udán počet opakování

Př. Vstup: AAAABBCDDDDABD Výstup: 4A2B1C4D1A1B1D

RLE – Run Length encoding

→ (3,Č),(2,B)→ (1,B), (3,Č), (1,B)→ (2,B), (2,Č), (1,B)→ (5,B)→ (2,B), (3,Č)→ (2,B), (3,Č)

• pro jaké obrázky RLE výhodné?– obrázek s mnoha vodorovnými čarami

• pro jaké obrázky RLE neefektivní?– obrázek se svislými čarami → žádná komprese– obrázek, kde se neopakují hodnoty sousedních pixelů(např. šachovnice) → záporná komprese → zvětšení výsledného souboru

Statistické metodyHuffmanovo kódování• algoritmus navržen v Davidem Huffmanem v roce 1952• využívá optimálního (nejkratšího) prefixového kódu y j (kód žádnéhoznaku není prefixem jiného znaku).• kódové symboly mají proměnnou délkuPrincip: Metoda je založená na stanovení četnosti výskytů jednotlivýchznaků v kódovaném souboru a kódování znaků s největší četnostíslovem s nejkratší délkou.Algoritmus kódování:1. Zjištění četnosti jednotlivých znaků v kódovaném souboru2. Vytvoření binárního stromu (Huffmanova kódu jednotlivých znaků)seřadíme posloupnost postupně zleva doprava3. Uložení stromu4. Nahrazení symbolů jednotlivými kódy (posloupností bitů)

Výhody – velmi rychlá komprese a dekomprese- nepříliš velké nároky na paměť

Nevýhody – nutnost uložení binárního stromu a slabší kompresní poměr

Statistické metody

Příklad:

Statistická metodaAritmetické kódování - reprezentaci vstupního řetězce reálným číslem

R pro které platí 0 R < 1.

Počáteční interval si rozdělíme v poměru četností výskytu znaků. Každý znak je tedy

reprezentován určitým menším podintervalem. Poté v závislosti na aktuálním znaku

vybereme jeden podinterval, který opět rozdělíme v poměru četností a načteme další

znak. Tímto postupem se interval neustále zužuje. Z posledního intervalu vybereme

jedno reprezentující číslo, jehož zápis představuje zkomprimovaný řetězec.

Slovníkové metodyLZ77 (Lempel-Ziv) metodaPrincip metody spočívá v postupném prohledávání celého souboru tak, že vždy část rozdělíme na dvě „okénka“, kde první tvoří historii kterou prohledáváme a druhým okénkem se dívám dopředu a hledám zda v něm není posloupnost znaků, která se už jednou vyskytuje v okénku historie. Pokud takovou posloupnost najdu, nahradím ji uspořádanou dvojicí:

(offset o kolik znaků jdu zpět, délka sekvence)

Např. zápis (10,2) znamená že mám jít o deset znaků zpět a vzít odsud 2 znaky – viz. schéma

Slovníkové metody

LZW (Lempel-Ziv-Welch) metoda- funguje na principu tvorby slovníku, do kterého se ukládají opakující se znaky. - jakmile se znaky objeví v souboru znovu, jsou okamžitě nahrazeny číslem, odkazující na ony znaky ve slovníku. - slovníky se neukládají do zkomprimovaného souboru (jsou většinou velké akomprimace by neměla smysl), nýbrž jsou dělány tak důmyslně, že se při dekódování tvoří znovu ze zakódovaných souborů.

Příklad:

Vstupní abeceda A={a, b, c}

Vstupní řetězec V=abcabcabcbcba

Výstupní řetězec W=1 2 3 4 6 5 9 1

Slovník je po zpracování celého vstupního řetězce zobrazen v tabulce.

Fráze Kódové slovoa 1b 2c 3ab 4bc 5ca 6abc 7cab 8bcb 9bcba 10

Porovnání účinnosti

Porovnání účinnosti

Obrázek Typ Metoda Rozlišení Velikost rastru Velikost po komprimaci Komprimační poměr

1.GIF LZW 256×256 8192 5979 73%

PCX RLE 256×256 8192 8460 103%

PNG LZ77 256×256 8192 6030 74%

2.GIF LZW 354×520 92040 8419 9%

PCX RLE 354×520 92040 14881 16%

PNG LZ77 354×520 92040 7310 8%

3.GIF LZW 624×113 70512 20079 28%

PCX RLE 624×113 70512 27645 39%

PNG LZ77 624×113 70512 17902 25%

4.GIF LZW 256×256 196608 52214 27%

PCX RLE 256×256 196608 221261 113%

PNG LZ77 256×256 196608 107001 54%

1. černo-bílý obrázek: velké změny v obraze2. šestnáctibarevný: velké plochy stejné barvy, málo změn3. 256barevný obrázek: velká stejnobarevná plocha (pozadí), více změn4. true-color obrázek: reálná fotografie, mnoho změn v obraze, barevné přechody