Kompresná informatika G23c

Vyriešte pracovný hárok „Formáty obrázkov“

# Kompresia

Kompresia sa snaží efektívnejšie ukladať údaje, aby sa využilo menej úložného priestoru. To je mimoriadne dôležité, najmä pri prenose údajov - napríklad streamovaní filmu alebo telefonovaní -. Rozlišujeme dva zásadne odlišné typy kompresie:

# Bezstratová kompresia

Vďaka bezstratovej kompresii je možné údaje kompletne rekonštruovať. To znamená, že „je„ ako kódovanie “ jedinečné a reverzibilné mapovanie.

Použiteľné všade tam, kde nesmie dôjsť k strate - program už nebeží, ak chýbajú príkazy! Obrázky, zvuk a video počas výroby a úprav - inak by sa kvalita znižovala s každým ukladaním (tj. Kódovaním). Príklady flac - zvuk zip, rar súbory gif, png, raw, psd, xcf - grafika

# Stratová kompresia

Dáta sa tu pri ukladaní odstránia. To umožňuje získať zodpovedajúce veľké množstvo pamäte, ale pôvodné údaje je možné rekonštruovať iba čiastočne. Snaží sa predovšetkým vynechať nie dôležité údaje.

Použiť pri dokončovaní médií, t. J. Keď ich už nie je potrebné upravovať. Príklady mp3 • zvuk jpg • grafika mp4, avi, mov • video

# Grafika

Rôzne formáty súborov ponúkajú všetky výhody a nevýhody vďaka rozdielnej kompresii. Zohráva tiež úlohu pri komprimácii textu, loga, ilustrácie alebo fotografie.

g23c
Porovnanie rôznych grafických formátov [2]

Na cvičebnom liste sme už poznali typ kompresie, konkrétne kódovanie dĺžky behu, alebo skrátene RLE.

Odpovedaj na nasledujúce otázky:

  • Ak je postup veľmi efektívny?
  • Na aký druh grafiky by sa dal použiť?

# Huffmanovo kódovanie

V roku 1952 David Huffman vyvinul proces, pomocou ktorého je možné kódovať znaky spôsobom, ktorý šetrí miesto. Jeho myšlienkou je, že znakom, ktoré sa v texte objavujú často, sa poskytne kratší kód ako znakom, ktoré sa v texte vyskytujú zriedka.

# Kódový strom

Kódový strom je štruktúra so štartovacím uzlom. Odtiaľto môžete pokračovať doľava alebo doprava dole. 0 v kóde znamená ísť doľava, 1 znamená ísť doprava. Keď sa do uzla dostane písmeno, jeden dekódoval znak a jeden sa začína odznova.

Huffmanov strom pre „Annu“

  1. Dekódujte nasledujúcu bitovú postupnosť pomocou vyššie uvedeného kódového stromu. (SP) znamená priestor.

  1. Teraz kódujte prijatý text buď v Pentacode alebo v ASCII. Aká dlhá je bitová sekvencia?
  2. Nájdete lepší kód ako Pentacode/ASCII?

Pentacode:
12 znakov × 5 bitov = 60 bitov

ASCII:
12 znakov × 7 bitov = 84 bitov (pôvodne)

12 znakov × 8 bitov = 96 bitov (s 0 bitmi)

vlastný kód:
Musí byť možné kódovať iba 4 znaky. Na to stačia 2 bity!

Znak kódu
00 (SP)
01 A.
10 N
11 S.

12 znakov × 2 bity = 24 bitov

# Vytvorte Huffmanov strom

Huffmanov algoritmus by sa mal vysvetliť na príklade kódovania textu „MISSISSIPPI“.

Najprv spočítate, koľkokrát sa každý znak v texte objaví, a vytvorte tabuľku frekvencií.

Frekvencia znakov «MISSISSIPPI» Znak M P I S
Frekvencia 1 2 4 4

Teraz je potrebné vytvoriť kódovací strom. Frekvencie písmen tvoria každé uzol. Frekvencia je v uzle, písmeno pod ním. Uzly sú zoradené podľa ich rastúcej frekvencie:

Uzol s frekvenciou znakov

Teraz sú dva uzly s najnižšími frekvenciami pripojené k novému uzlu. Nový uzol obsahuje akumulovanú frekvenciu pôvodných uzlov:

Kombinácia uzlov 1

Toto sa opakuje, kým nie sú všetky uzly spojené dohromady. Ak majú dva uzly rovnakú frekvenciu, nezáleží na tom, ktorý z nich je vybraný:

Zlúčiť uzly 2

Je dôležité, aby sa uzly po každom kroku znova roztriedili.

Zlúčiť uzly 3

Keď je strom hotový, všetky vetvy, ktoré smerujú doľava, sú označené znakom „0“, všetky tie, ktoré smerujú doprava, znakom „1“.

Pomenujte okraje

Tabuľku kódovania je teraz možné vytvoriť načítaním kódu pre každý znak zo stromu:

Kódovací stôl «MISSISSIPPI» Znak I M P S
kód 11 100 101 0

Vytvorte Huffmanov strom pre nasledujúci text a podľa toho text kódujte:

Koľko bitov slovo zaberá v Huffmanovom kódovaní? Koľko v pentacode? Koľko v ASCII?

# Huffman-Baum pre nemčinu

V zásade sa pre každý text, ktorý sa má kódovať, vytvorí Huffmanov strom. Toto sa zaoberá vlastnosťami textu a zabezpečuje, aby sa často sa vyskytujúcim znakom priradil krátky kód. Strom musí byť uložený spolu s kódovanými údajmi - slúži na dekódovanie.

Ak sa pozriete na frekvenciu písmen v nemeckom jazyku, môžeme z týchto údajov vytvoriť Huffmanov strom, ktorý by bol vhodný pre dlhšie nemecké texty.

Hufmannov strom pre frekvenciu znakov v nemeckom jazyku

Môžete odpovedať na nasledujúce otázky:

  • Prečo jazyk hrá rolu?
  • Prečo s Huffmanom nie je k dispozícii úložný priestor pre nasledujúcu vetu?