Scopul prelegerii. pentru a studia principalele tipuri și algoritmi de compresie a datelor și pentru a afla cum să rezolvați problemele de compresie a datelor folosind metoda Huffman și folosind copaci cod.
Fondatorul științei comprimării informațiilor este considerat a fi Claude Shannon. Teorema sa privind codarea optimă arată ce trebuie să depunem atunci când codificăm informațiile și cât de multe informații sunt comprimate. În plus, a efectuat experimente pe baza unei evaluări empirice a redundanței textului în limba engleză. Shenon a sugerat că oamenii ghicesc următoarea literă și evaluează probabilitatea de ghicire corectă. Pe baza unui număr de experimente, el a ajuns la concluzia că numărul de informații din textul în limba engleză variază de la 0,6 la 1,3 biți pe simbol. În ciuda faptului că rezultatele cercetării lui Shannon au fost într-adevăr solicitate decenii mai târziu, este dificil să se supraestimeze semnificația lor.
Comprimarea datelor este un proces care reduce cantitatea de date prin reducerea redundanței. Comprimarea datelor este asociată cu aranjamentul compact al porțiunilor de date cu mărime standard. Comprimarea datelor poate fi împărțită în două tipuri principale:
Algoritmul comprimării datelor (algoritmul de arhivare) este un algoritm. care elimină redundanța înregistrării datelor.
Introducem o serie de definiții care vor fi utilizate ulterior în prezentarea materialului.
Alfabetul de cod este setul tuturor simbolurilor fluxului de intrare. Când comprimați textele în limba engleză, utilizați de obicei o mulțime de 128 de coduri ASCII. Atunci când se comprimă imagini, o multitudine de valori ale pixelilor pot conține 2, 16, 256 sau alt număr de elemente.
Simbolul de cod este cea mai mică unitate de date care trebuie comprimată. De obicei, un simbol este de 1 octet. dar poate fi un pic, un trit, sau altceva.
Un cuvânt de cod este o secvență de simboluri de cod din alfabetul de cod. Dacă toate cuvintele au aceeași lungime (numărul de caractere), atunci acest cod este numit uniform (lungime fixă). și dacă sunt permise cuvinte de diferite lungimi, atunci - inegale (lungime variabilă).
Un cod este un set complet de cuvinte.
Token este o unitate de date scrise în fluxul comprimat prin algoritmul de compresie. Un jeton constă din mai multe câmpuri de lungime fixă sau variabilă.
O frază este o piesă de date plasată într-un dicționar pentru o utilizare ulterioară în comprimare.
Codificarea este procesul de comprimare a datelor.
Decodificarea este inversul procesului de codificare în care datele sunt restabilite.
Raportul de compresie este una dintre cele mai frecvent utilizate valori pentru a indica eficacitatea metodei de compresie.
O valoare de 0,6 înseamnă că datele ocupă 60% din volumul original. Valori mai mari de 1 înseamnă că fluxul de ieșire este mai mare decât intrarea (compresie negativă sau extindere).
Raportul de compresie este reciproc al raportului de compresie.
Valorile mai mari decât 1 denotă compresia, iar valorile mai mici de 1 denotă extinderea.
Lungimea medie a unui cuvânt de cod este o valoare care este calculată ca suma ponderată cu probabilitate a lungimilor tuturor cuvintelor de cod.
unde - probabilitatea cuvintelor cod;
Există două modalități principale de a comprima.
Metodele statistice sunt metode de comprimare care atribuie codurilor de lungime variabilă simbolurilor fluxului de intrare, cu coduri mai scurte atribuite simbolurilor sau grupurilor de simboluri care au o probabilitate mare de a apărea în fluxul de intrare. Cele mai bune metode statistice aplică codificarea Huffman.
Vocabularul de compresie este o metodă de comprimare care stochează fragmente de date într-un "dicționar" (oarecare structură de date). Dacă șirul de date noi care sosesc la intrare este identic cu orice fragment deja din dicționar, un indicator cu acest fragment este plasat în fluxul de ieșire. Metodele celor mai bune dicționare aplică metoda Ziva-Lempel.
Luați în considerare mai multe algoritmi cunoscuți pentru comprimarea datelor în detaliu.
Metoda Huffman
Acest algoritm pentru codificarea informațiilor a fost propus de D.A. Huffman în 1952. Codificarea Huffman (compresie) este o metodă de comprimare utilizată pe scară largă care atribuie coduri de lungime variabilă simbolurilor alfabetice, pe baza probabilităților apariției acestor simboluri.
Ideea algoritmului este următoarea: cunoașterea probabilității de apariție a simbolurilor în textul sursă, puteți descrie procedura de construire a codurilor de lungime variabilă constând dintr-un număr întreg de biți. Persoanelor cu caractere li se atribuie mai multe coduri mai scurte. Astfel, în această metodă, atunci când datele sunt comprimate, un cod prefix optim este atribuit fiecărui caracter. bazată pe probabilitatea apariției acestuia în text.
Un cod de prefix este un cod în care niciun cuvânt de cod nu este un prefix al oricărui alt cuvânt de cod. Aceste coduri au o lungime variabila.
Codul prefixului optim este codul de prefix. având o lungime medie minimă.
Algoritmul Huffman poate fi împărțit în două etape.
- Determinați probabilitatea apariției caracterelor în textul sursă.
Inițial, este necesar să se citească complet textul sursă și să se calculeze probabilitatea apariției simbolurilor în acesta (câteodată se contorizează de câte ori apare fiecare simbol). Dacă acest lucru ia în considerare toate cele 256 de caractere, atunci nu va fi nici o diferență în comprimarea unui fișier text sau a unui fișier de alt format.
Apoi, există două simboluri a și b cu cea mai mică probabilitate de apariție și sunt înlocuite cu un simbol inactiv x. care are o probabilitate de apariție egală cu suma probabilităților apariției simbolurilor a și b. Apoi, folosind această procedură recursiv, există un cod de prefix optim pentru un set mai mic de simboluri (unde simbolurile a și b sunt înlocuite cu un singur caracter x). Codul pentru setul original de simboluri este obținut din codurile de simbol înlocuire prin adăugarea a 0 sau 1 înainte de codul de simbol înlocuit, iar cele două noi coduri sunt acceptate ca coduri de caractere de înlocuire. De exemplu, codul de caractere a se va potrivi cu codul x cu zero adăugat înainte de acest cod, iar pentru caracterul b înainte de codul caracterului x, se va adăuga unul.
Codurile Huffman au un prefix unic. care le permite să decodeze în mod unic, în ciuda lungimii lor variabile.
Exemplul 1. Implementarea software a metodei Huffman.
Algoritmul Huffman este universal, poate fi folosit pentru a comprima date de orice tip, dar este ineficient pentru fișiere de dimensiuni mici (datorită necesității salvării dicționarului). În prezent, această metodă nu este practic folosită în forma sa pură, este de obicei folosită ca una dintre etapele de comprimare în scheme mai complexe. Acesta este singurul algoritm. care nu mărește dimensiunea datelor sursă în cel mai rău caz (cu excepția necesității de a stoca tabelul de conversie împreună cu fișierul).
Articole similare
Trimiteți-le prietenilor: