Metodele de comprimare a informațiilor textuale au o istorie destul de lungă. În centrul algoritmilor de comprimare pentru astfel de informații este principiul minimizării redundanței. Teorema fundamentală a lui Shannon despre sursele de codare spune că costul codării nu este întotdeauna mai mic decât entropia sursei, deși poate fi în mod arbitrar apropiat de ea [1]. Această declarație stabilește limitele teoretice ale comprimării datelor.
Aici folosim conceptul de bază al teoriei informației - entropia. care pot fi tratate informal ca măsură a cantității de informații din mesaj. Costul de codare este lungimea medie a cuvântului de cod (în biți) pe caracterul textului sursă. Apoi, redundanța codificării este egală cu diferența dintre costul de codare și entropia mesajului original în termeni de un singur caracter.
De interes practic sunt algoritmii de codificare cu o singură trecere care comprimă nu doar un fișier de acces direct, ci un flux. și anume fișier care nu permite poziționarea și rebobinarea.
Codificarea se referă la un flux de simboluri într-un anumit alfabet, iar frecvențele apariției simbolurilor sunt diferite. Scopul codificării este de a converti un flux de caractere într-un flux minim de lungime de biți. Acest lucru se realizează prin reducerea redundanței fluxului de ieșire prin luarea în considerare a frecvenței apariției simbolurilor la intrare: lungimea codului ar trebui să fie proporțională cu informațiile conținute în fluxul de intrare.
Dacă este cunoscută distribuția frecvenței simbolurilor, atunci este posibilă construirea unei codări optime. Sarcina devine mai complicată dacă această distribuție nu este cunoscută în prealabil. În acest caz, există două abordări diferite.
A doua abordare. utilizați un coder adaptabil (coder adaptiv). Ideea este să schimbați schema de codare în funcție de datele sursă. Un astfel de algoritm este o singură trecere și nu necesită transferul de informații despre codificarea utilizată într-o formă explicită. În schimb, decodorul, care citește fluxul codificat, în mod sincron cu codificatorul, schimba schema de codificare, începând cu unele predefinite. Codarea adaptivă oferă un grad ridicat de comprimare, deoarece sunt luate în considerare schimbările de frecvență locale. Un exemplu este codarea dinamică a lui Huffman.
Codificarea statică Huffman coincide cu caracterele de intrare reprezentate de șiruri de lungime de biți de aceeași lungime (de exemplu, de octeți pe 8 biți), un lanț de biți de lungime variabilă. Lungimea codului pentru simbol este proporțională (rotunjită la cel mai apropiat număr întreg) cu logaritmul binar al frecvenței sale, luată cu un semn negativ. Această codificare este prefix. ceea ce îl face ușor să o decodifice folosind un algoritm cu o singură trecere. În codificarea prefixelor, orice cod de caractere nu este un prefix de cod al unui alt caracter. Codul de prefix convenabil reprezentat ca un arbore binar, în care personajele sunt în frunze și arce etichetate 0 sau 1. Apoi, codul de caractere poate fi setat ca o cale de la rădăcină la frunza ce conține acel caracter.
Exemplul 3. Luați în considerare implementarea metodei Huffman atunci când codificați următorul text:
Acesta este un exemplu simplu de codificare HUFFMAN.
1. Să numărăm numărul de repetiții ale fiecărei litere ale alfabetului în textul sursă:
3. Începem construcția arborelui din simbolul din dreapta în listă. Frecvențele celor două simboluri cele mai rar întâlnite sunt însumate, iar rezultatul este scris în nodul copacului, așa cum se arată în Fig. 1. Frecvențele inițiale sunt acum copiii noii frecvențe totale. Dacă există mai mult de două caractere cu o rată minimă de repetare, atunci trebuie doar să creați perechi independente de ele. Dacă există un număr imparat dintre cele mai scăzute valori ale frecvenței, vom uni valoarea neprotejată cu următoarea frecvență inferioară.
Pe măsură ce procesul de construire a unui copac continuă, copiii devin nepoți, strănepoți - și așa mai departe până când întregul copac este terminat. Numărul total de caractere din textul sursă va fi reprezentat în partea de sus a arborelui primit. Astfel, este posibil să se verifice în mod eficient corectitudinea construcției arborelui de codificare.
4. Codul final Huffman pentru fiecare caracter al textului sursă poate fi obținut adăugând un anumit atribut binar fiecărei ramuri a arborelui. Toate părăsit ramurile care provin de la toate nodurile vor fi marcate cu 1, și toată ramura din dreapta - 0. Astfel, codul de fiecare literă poate fi obținută prin deplasarea de-a lungul ramurile copacului din partea de sus a unei scrisori de interes și înregistrarea ordinea de sucursale binare atribute. Rezultatele sunt rezumate într-un tabel, pe care îl vom folosi ca un "dicționar" pentru codificarea și apoi restaurarea textului sursă:
Tabela de codificare rezultată
De exemplu, cuvântul "THIS" va fi codificat în secvența 00010 0110 1100 0111. Lungimea totală a codului cuvântului a fost redusă de la 32 biți la 17 biți. Pentru întreaga propoziție, raportul de compresie este de 175/352 "0,497.
Comprimarea fără pierderi de informații grafice găsit metoda de aplicare a lungimii de execuție de codificare este RLE (Run Length Encoding), a cărei esență constă în faptul că fișierul de imagine comprimat este „tras“ într-un lanț de octeți de linii raster. Compresia însăși în RLE se datorează faptului că în imaginea sursă există lanțuri de octeți identici. Înlocuirea acestora cu perechi <счетчик повторений, значение> Reduce redundanța datelor.
De exemplu, secvența "AAAAAAA" folosind algoritmul RLE va fi codificată ca "(A, 7)".
În acest algoritm, contorul este indicat de unitățile din cei doi biți cei mai buni ai fișierului citit. În consecință, restul de 6 biți sunt cheltuite pe contor, care poate lua valori de la 1 la 64. Noi convertim un șir de 64 octeți repetiți în doi octeți, adică vom stoarce în 32 de ori.
Acest algoritm este implementat în format PCX.
Există, de asemenea, oa doua versiune a algoritmului care implementează metoda RLE, care are un raport de compresie mai mare. Un semn al unei repetări în acest algoritm este o unitate în cel mai înalt bit al octetului corespunzător. După cum puteți calcula cu ușurință, în cel mai bun caz acest algoritm comprimă fișierul de 64 de ori (și nu 32 de ori, ca în versiunea anterioară), în cel mai rău caz crește cu 1/128. Raportul mediu de compresie al acestui algoritm se situează la nivelul primei opțiuni. O schemă similară de comprimare este folosită ca unul dintre algoritmii susținuți de formatul TIFF. precum și în format TGA.
O metodă mai eficientă de comprimare a informațiilor fără pierderi este metoda Lempella-Ziva (LZ), numită după doi matematicieni israelieni care au propus-o în 1977. Metoda se bazează pe faptul că în fiecare fișier, de regulă, există mai multe combinații binare repetate frecvent. De exemplu, în textul programului într-o programare de nivel înalt va confruntat întotdeauna cu combinații de caractere (și fișier cu textul - o combinație a corespunzătoare octet) referitoare la operatori, procedurile și funcțiile limbajului. Evident, puteți selecta astfel de combinații, alcătuiți lista lor și, prin urmare, ridicați orice combinații mai scurte. Apoi înlocuiți combinațiile lungi cu cele scurte și scrieți un tabel fișierului care l-a înlocuit. Despachetarea fișierului este redusă la funcționarea substituțiilor, inversul produs de scriere.
În practică, o masă de tip hash este utilizată pentru a stoca masa. constând din elemente care nu depășesc 8192 (2 13). Fiecare element al tabelului conține o înregistrare:
<код предыдущей подстроки; добавленный символ; код этой строки> .
Cheia pentru căutarea cu o lungime de 20 de biți este formată folosind primele două elemente stocate în tabel ca o singură cheie. Cele mai tinere 12 biți din acest număr sunt date sub cod și următorii 8 biți sub valoarea simbolului.
Funcția hash este:
Index (cheie) = ((cheie >> 12) Å cheie) 8191,
unde >> este schimbarea de biți dreapta; Å - funcționarea logică a sistemului OR, - bitul logic I.
Un exemplu de utilizare a metodei LZ este formatele grafice GIF și TIFF.
Articole similare
Trimiteți-le prietenilor: