Compresia informatică G23c
Rezolvați foaia de lucru «Formate de imagine»
# Compresie
Compresia încearcă să economisească datele mai eficient, astfel încât să fie utilizat mai puțin spațiu de stocare. Mai ales la transferul de date - de ex. Transmiterea unui film sau telefonie - acest lucru este extrem de important. Distingem două tipuri de compresie fundamental diferite:
# Compresie fără pierderi
Cu compresie fără pierderi, datele pot fi reconstituite complet. Adică ca și codarea - este, cartografiere unică și reversibilă.
Poate fi folosit oriunde nu poate apărea nicio pierdere - un program nu mai rulează dacă lipsesc comenzile! Imagini, audio și video în timpul producției și editării - în caz contrar, calitatea ar scădea cu fiecare salvare (adică codificare). Exemple flac - sunet zip, rar - fișiere gif, png, raw, psd, xcf - grafică
# Compresie cu pierderi
Datele sunt eliminate aici la salvare. Acest lucru permite să câștige o cantitate mare corespunzătoare de memorie, dar datele originale pot fi doar parțial reconstituite. Mai presus de toate, încearcă să lase deoparte date nu importante.
Folosiți la finalizarea suportului, adică atunci când nu mai este editat Exemple mp3 - sunet jpg • grafică mp4, avi, mov • video
# Grafic
Diferitele formate de fișiere oferă toate avantajele și dezavantajele datorită compresiei lor diferite. De asemenea, joacă un rol dacă textul, un logo, o ilustrație sau o fotografie ar trebui comprimate.
Pe foaia de exerciții am aflat deja un tip de compresie, și anume codarea lungimii de rulare sau RLE pe scurt.
Răspunde la următoarele întrebări:
- Acolo unde procedura este foarte eficientă?
- Pentru ce fel de grafică ar putea fi utilizată?
# Codificare Huffman
În 1952, David Huffman a dezvoltat un proces prin care personajele pot fi codate într-o manieră economisitoare de spațiu. Ideea sa este că personajelor care apar frecvent în text primesc un cod mai scurt decât caracterele care apar rar în text.
# Arborele codului
Un arbore de cod este o structură cu un nod de pornire. De aici puteți merge mai jos la stânga sau la dreapta. Un 0 din cod înseamnă a merge la stânga, un 1 înseamnă a merge la dreapta. Când se ajunge la un nod cu o literă, se decodifică un caracter și se pornește din nou de la început.
Arborele Huffman pentru «Anna»
- Decodează următoarea secvență de biți cu arborele de cod de mai sus. (SP) înseamnă un spațiu.
- Acum codificați textul primit fie în Pentacode, fie în ASCII. Cât timp este primită secvența de biți?
- Puteți găsi un cod mai bun decât Pentacode/ASCII?
Pentacod:
12 caractere Г 5 biți = 60 biți
ASCII:
12 caractere Г 7 biți = 84 biți (inițial)
12 caractere Г 8 biți = 96 biți (cu 0 biți)
cod propriu:
Trebuie să se poată codifica doar 4 caractere. 2 biți sunt suficienți pentru asta!
| 00 | (SP) |
| 01 | A. |
| 10 | N |
| 11 | S. |
12 caractere Г 2 biți = 24 biți
# Creați un copac Huffman
Algoritmul Huffman trebuie explicat folosind exemplul de codificare a textului «MISSISSIPPI».
Mai întâi numărați de câte ori apare fiecare caracter în text și creați un tabel de frecvențe.
| Frecvență | 1 | 2 | Al 4-lea | Al 4-lea |
Acum este o chestiune de a crea un copac de codare. Frecvențele literelor formează fiecare un nod. Frecvența este în nod, litera de sub el. Nodurile sunt sortate în funcție de frecvența lor în creștere:
Nod cu frecvența caracterelor
Acum, cele două noduri cu cele mai mici frecvențe sunt atașate unui nou nod. Noul nod conține frecvența acumulată a nodurilor originale:
Combinați nodurile 1
Aceasta se repetă până când toate nodurile sunt conectate între ele. Dacă două noduri au aceeași frecvență, nu contează care este aleasă:
Îmbinați nodurile 2
Este important ca nodurile să fie re-sortate după fiecare pas.
Îmbinați nodurile 3
Când arborele este terminat, toate ramurile care indică spre stânga sunt marcate cu un «0», toate cele care arată spre dreapta cu un «1».
Nume margini
Acum se poate crea un tabel de codare citind codul pentru fiecare caracter din arbore:
| cod | 11 | 100 | 101 | 0 |
Creați un copac Huffman pentru următorul text și codificați textul în consecință:
Câți biți ocupă cuvântul în codificarea Huffman? Cât în pentacod? Cât de mult în ASCII?
# Huffman-Baum pentru germană
În principiu, se creează un copac Huffman pentru fiecare text care trebuie codat. Aceasta tratează proprietățile textului și asigură că caracterelor care apar frecvent li se atribuie un cod scurt. Arborele trebuie totuși salvat împreună cu datele codificate - este utilizat pentru decodare.
Dacă vă uitați la frecvența literelor în limba germană, putem folosi aceste date pentru a crea un copac Huffman care ar fi potrivit pentru texte germane mai lungi.
Arborele Hufmann pentru frecvența caracterelor în limba germană
Puteți răspunde la următoarele întrebări:
- De ce limbajul joacă un rol?
- De ce nu există spațiu de stocare cu Huffman pentru următoarea propoziție?