Ion Ivan & Daniel Verniş
Interesul pentru reducerea spaţiului ocupat de fişiere pe suporţii magnetici a impus constituirea algoritmilor de comprimare. Comprimarea este un proces prin care se transferă un fişier iniţial într-un fişier a cărui lungime este cu mult mai mică decât a celui iniţial. Decomprimarea este procesul invers comprimării. În continuare se prezintă algoritmi de comprimare şi unele consideraţii asupra performanţelor. Programele care implementează aceşti algoritmi utilizează un set de 10 fişiere generate astfel încât, să se includă atât situaţiile de structurare a textelor cât şi cazurile particulare( texte ce conţin un singur simbol sau texte de lungime n octeţi ce conţin n simboluri diferite).
În toate programele FişierSursă reprezintă o variabilă cu care se identifică fişierul de intrare, care face obiectul comprimării. Variabila FişierCodificat identifică fişierul comprimat. Pentru o mai mare omogenitate a programelor se vor folosi în programe acelaşi nume de variabile globale:
NumeSursă – numele fişierului ce este destinat comprimării
NumeCodificat – numele fişierului rezultat după comprimare
ExtensieCodificare – extensia pe care o va primi fişierul comprimat
ExtensieDecodificare – extensia fişierului după decomprimare
Programele, elaborate în C, au fost testate de autori.
Coduri de lungime fixă
Se
consideră un alfabet
,
fiecare simbol fiind reprezentat pe suport ca un şir de biţi de lungime k.
De exemplu, pentru codul ASCII k=8. Se consideră un alt alfabet
având simbolurile reprezentate pe suportul magnetic sub
forma unui şir de biţi de lungime p. Dacă p<k se caută un procedeu de
punere în corespondenţă a simbolurilor din alfabetul A cu simbolurile din
alfabetul B. Se transformă textul conţinut de un fişier cu simboluri din
alfabetul A, într-un text comprimat ce conţine simboluri din alfabetul B.
Gradul de comprimare se defineşte:
g=1-p/k (1)
Algoritmul RLE
(Run Length Encoding)
Se consideră constanta r ca fiind pasul algoritmului. În funcţie de valoarea lui r( r>3) se disting două alternative:
a) Pentru succesiuni de simboluri identice, cu lungimi mai mari decât r, se aplică algoritmul astfel:
în fişierul comprimat
se va trece succesiunea
unde:
s1 - caracter special;
s2 – lungimea succesiunii de simboluri( factor de multipliciate);
s3 – simbolul.
b) Pentru succesiunile de simboluri l<r nu se va aplica procedeul de mai sus, ele rămânând identice. Algoritmul RLE este un caz special, operând în realizarea de transformări pe text. Comprimarea la nivel de simbol este nulă. Gradul cel mai mare de comprimare se înregistrează când textul iniţial este de lungime foarte mare şi are un singur simbol. Gradul de comprimare este nul atunci când textul de lungime L simboluri este format din tot atâtea caractere sau L/r succesiuni de simboluri diferite. Programele ce realizează comprimarea şi decomprimarea cu ajutorul RLE se pot găsi pe BBS( RLEc.C şi RLEd.C).
Acest algoritm realizează o analiză pe text din aproape în aproape şi construieşte dinamic fişierul comprimat. Fişierele grafice conţin imagini reprezentate sub forma unor matrice liniarizate, ce conţin informaţii referitoare la pixeli. Aici se regăsesc succesiuni stabile de pixeli identici, iar comprimarea folosind algoritmul RLE se dovedeşte eficientă.
Algoritmul DS( Dinamic Stack)
Acest algoritm presupune traversarea de două ori a fişierului de comprimat. Se execută următorii paşi:
1. Se construieşte stiva simbolurilor diferite;
2. Se contorizează frecvenţa de apariţie a simbolurilor diferite;
3. Se stabileşte lungimea stivei de simboluri L;
4. Se stabileşte k – lungimea codului comprimat, 2k>L, unde k este cel mai mic întreg pentru care are loc inegalitatea;
5. Se generează codurile comprimate pe biţi pentru simbolurile din stivă;
6. Se înscrie în fişierul comprimat lista simbolurilor din stivă. Dacă există un algoritm de generare a codurilor comprimate reproductibil, codurile comprimate nu vor mai fi înscrise într-o listă în fişier;
7. Se traversează fişierul original şi se crează fişierul comprimat, prin înlocuire.
Eficienţa acestui algoritm constă în primul rând în manipularea de şiruri de biţi de lungime mai mică decât opt. Concatenarea codurilor comprimate se reduce la efectuarea unor manipulări la nivel de biţi. De exemplu, pentru k=5 şi pentru textul:
T = < a b c a a b b c a > (2)
se construieşte textul comprimat:
T’ = < 11011 11100 10001 11011 11011 11100 11100 10001 11011 >
unde algoritmul de generare al codurilor presupune că a realizat pe stivă următoarele perechi:
(a;11011) , (b;11100) , (c;10001).
Înscrierea pe suport revine la a manipula octeţii, adică la a regrupa şirul de biţi T’ divizându-l în părţi de câte opt biţi.
T’’ = < 11011111 00100011 10111101 11110011 10010001 11011000 >
Fişierul comprimat este rezultatul acestei transformări. Decomprimarea revine la prelucrarea informaţiei de la începutul fişierului comprimat. Se reconstruieşte stiva simbolurilor diferite şi se realizează corespondenta între codurile comprimate şi codurile ASCII.
Acest algoritm îşi dovedeşte eficienţa în cazul apariţiei cu o frecvenţă uniformă a simbolurilor într-un text. De asemenea, dacă prin traversarea unei clase de texte cu contorizarea frecvenţelor de apariţie a caracterelor ASCII, se observă că multe dintre simboluri( peste 128) au frecvenţă nulă. În acest caz programele de comprimare şi de decomprimare conţin perechile (ai;bi) şi operează direct fără a mai fi nevoie de două traversări şi de înscrierea perechilor la începutul fişierului comprimat.
Algoritmul LZW
( Lempel – Ziv - Welch)
LZW este un algoritm de comprimare ce înlocuieşte un text cu altul. Mai este cunoscut şi sub numele de ‚On line textual Substitution’. Algoritmul LZW constă în înlocuirea prin câţiva biţi a unui cuvânt, a unei fraze sau chiar a unui paragraf întreg. Biţii sunt constituiţi într-o manieră unică cu ajutorul unui dicţionar dinamic, creat după cerinţele textului. Avantajul faţă de alţi algoritmi îl constituie faptul că dicţionarul nu trebuie transmis sau stocat a dată cu datele, el putându-se reconstitui pe parcurs.
Presupunem că dispunem de un dicţionar de 256 caractere( codul ASCII), cu ranguri cuprinse între 0 şi 255. Ataşăm la acest dicţionar două coduri de control cu valorile 256 şi 257. Codul 256 este folosit ca sfârşit de fişier, iar 257 ca sfârşit de dicţionar, folosit în momentul în care dicţionarul a fost umplut şi se trece la un nou dicţionar.
Pentru a înţelege mai bine paşii acestui algoritm vom trata un exemplu. Fie textul:
T = < compresia şi decompresia datelor >
Este citit primul caracter ‚c’; nu se face cu el nici o operaţie şi se salvează sub numele de caracter latent. Se citeşte al doilea caracter ‚o’ în variabila cod citit. Se caută în dicţionar şirul format din cod citit şi cod latent. Cum suntem la primul pas acest şir nu există. Se trece în dicţionar şirul nou format cu valoarea 258( poziţia curentă liberă din dicţionar). Se transmite codul latent ‚c’ adică 99( codul ASCII), iar codul citit curent devine cod latent.
Se parcurge în continuare textul după acelaşi algoritm, până când ajungem la formarea şirului ‚si’( a doua apariţie) care este deja cunoscut în dicţionar. În acest caz nu se scrie nimic în fişierul comprimat şi şirul ‚si’ devine noul cod latent( el este considerat ca fiind un singur simbol, cu codul 264). Se citeşte următorul caracter ‚ ’( spaţiu). Se formează şirul ‚si’ care va fi trecut în dicţionar cu codul 268( vezi tabelul). Se transmite în fişierul comprimat codul latent 264 şi ‚ ’ devine cod latent. Pentru a observa comprimarea textului T, urmăriţi tabelul 1. Programul care implementează acest algoritm este prezentat în cadrul listingului 1. În ceea ce priveşte procesul de decomprimare, a aceluiaşi text T, urmăriţi tabelul 2.
Coduri de lungime variabilă
Se constată că frecvenţa de apariţie a simbolurilor în text este foarte diferită şi constituirea de subşiruri de simboluri urmează nişte reguli stricte. De aceea se proiectează algoritmi de comprimare care construiesc codurile alfabetului B de lungime variabilă. Astfel simbolurile cu frecvenţele de apariţie cele mai mari au coduri de lungime redusă, în timp ce simbolurile cu frecvenţe mici au coduri de lungime din ce în ce mai mare.
Algoritmul Huffman
Pasul 1 Se traversează fişierul;
Pasul 2 Se construieşte stiva simbolurilor distincte şi a frecvenţei de apariţie a acestora;
Pasul 3 Se construieşte arborele binar, ale cărui frunze sunt simboluri din stivă;
Pasul 4 La a doua traversare se folosesc codurile de lungime variabilă generate şi asociate simbolurilor din stivă şi se obţine fişierul comprimat.
Mecanismul de construire a arborelui binar se exemplifică pe stiva dată în figura 1:
Descrierea algoritmului de realizare a arborelui:
Pasul 1 Se aranjează simbolurile în stivă în odinea descrescătoare a frecvenţelor şi se consideră nodurile frunză ale arborelui;
Pasul 2 Atâta timp cât există mai mult de un nod, se asamblează nodurile cu cele mai mici frecvenţe, pentru a forma un nou nod a cărui frecvenţă este egală cu suma nodurilor asamblate;
Pasul 3 Se asignează arbitrar valorile 1 şi 0 fiecărei ramuri ale arborelui. De exemplu, stânga 1 şi dreapta 0;
Pasul 4 Se citeşte secvenţial, începând de la nodul rădăcină către frunze, atribuindu-se fiecărui simbol codul corespunzător.
Pentru stiva cu simboluri şi frecvenţe din figura 1 vom avea arborele Huffman din figura 2.
Se vor obţine următoarele codificări pentru simbolurile din stivă:
a:0
b:100
c:101
d:110
e:1110
f:1111
Textul sursă al programului care implementează algoritmul Huffman este prezentat în listingul 2. Biblioteca ‚lib.h’ conţine funcţii de calcul şi afişare a rezultatelor. Textul sursă al acestei biblioteci este prezentat în continuare.
Algoritmul DCT
Acest algoritm mai este cunoscut şi sub numele de comprimare JPEG. Cheia algoritmului este Transformarea Cosinus Discretă, funcţie de la care îşi ia numele. Transformarea DCT se realizează pe o matrice de puncte( pixeli), având ca rezultat o matrice de NxN coeficienţi de frecvenţă. Coeficienţii de frecvenţă DCT se calculează după formula:
unde, (i,j) – poziţia din matricea DCT
(x,y) – poziţia pixelului în matricea NxN
Este folosit în special pentru comprimarea de imagini, cu rezultate foarte bune, deşi are pierderi de informaţii nesemnificative în raport cu performanţa realizată. Cu toate că există o pierdere de informaţie, cu o rată de comprimare de 70-90%, comprimarea DCT dă rezultate destul de bune în cazul fişierelor ce conţin imagini. Algoritmii de comprimare imagine fac obiectul unui alt articol, special destinat acestui subiect.
Revenind la algoritmii din clasa Huffman putem spune că există mai multe modalităţi de a constitui un arbore ale cărui frunze sunt simbolurile din stivă. Astfel algoritmul FS( Fano - Shannon) construieşte arborele astfel:
Pasul 1 Se introduc informaţiile în stivă, în ordinea descrescătoare a frecvenţelor;
Pasul 2 Se calculează suma totală a frecvenţelor L;
Pasul 3 Împărţirea ansamblului de date în două jumătăţi având frecvenţe cât mai egale posibil( limitările sunt impuse de frecvenţele simbolurilor care nu pot fi împărţite);
Pasul 4 Se reâmpart ansamblurile rezultate până când rămân ansambluri formate doar dintr-un element;
Pasul 5 Atribuirea succesivă de valori 1şi 0 pentru fiecare ramură( vezi arborele Huffman);
Rezultate experimentale
Algoritmii prezentaţi sunt implementaţi în programe cu nivel omogen de performanţă. Deci programul în sine nu influenţează radical durata comprimării sau gradul de comprimare. Se consideră programele de comprimare prezentate în figurile 1,3,7. Pentru efectuarea comprimării au fost folosite fişiere de intrare ce conţin texte sursă C( cary.c, texthufc.c, textlzwc.c), programe executabile( hufc.exe, lzwc.exe, rlec.exe) şi fişiere cu date extrase din Anuarul Statistic( test1.out, test2.out, solvsamp.xlp, solverex.xlp). Se înregistrează: G – gradul de comprimare. Rezultatele experimentale obţinute sunt date în tabelul 3.
Din tabelele 3 şi 4, rezultă că fiecare algoritm are rezultate bune pentru anumite tipuri de fişiere. Totuşi algoritmul LZW are o rată de compresie mai bună în multe din cazurile considerate. Însă dezavantajul îl constituie, la LZW, viteza de comprimare, care este de 2-3 ori mai mare decât la RLE. Algoritmul RLE are rezultate bune doar pentru fişiere cu un număr mare de caractere identice( fişierele statice conţin în general doar cifre). În ceea ce priveşte algoritmul Huffman, acesta este bine să fie folosit pentru fişiere text sau fişiere în care apar cât mai puţine simboluri diferite. Algoritmul Huffman este cel mai stabil din punctul de vedere al ratei de comprimare, având un grad de comprimare mediu de 75,05%.
Concluzii
Programele care implementează algoritmi de comprimare sunt performante prin flexibilitatea de a utiliza diferenţiat algoritmii. Mai există şi alţi algoritmi( LZSS, TH, Comprimare Aritmetică) a căror abordare prezintă interes când se fac analize asupra stabilităţii de comportament. Ei vor fi prezentaţi numai în acest context.
Problematica realizării unei colecţii a algoritmilor de comprimare rămâne în actualitate mai ales pentru cazurile particulare. Astfel un text format din numere cuprinse între 109-3*1010, ca în cazul capitalului social al firmelor din Lista de Privatizare, poate fi comprimat cu pierdere de informaţie, conducând la un grad de comprimare foarte bun.
Se poate realiza comprimare şi prin apelarea unor funcţii de conversie. Astfel fişierele ce conţin reprezentări în zecimal despachetat de numere, pe cinci octeţi, cu valori în intervalul( -32767 ; 32767), prin reprezentarea binară determină punerea în corespondenţă cu un câmp de doi octeţi.
Bibliografie
● T. C. Bell, J. G. Cleary şi I. H. Witten, Text Compresion, Prentice Hall, Englewood Cliffs, NJ 1990
● E. N. Gilbert, T. T. Kadota, The Lempel-Ziv algorithm and message complexity, IEEE Trancastions on Information Theory, vol. 38, nr. 6, Noiembrie 1992, p. 1839-1842
● I. Ivan şi A. Adam, Compactarea datelor în Structuri de date şi programe Pascal, Editura QED, Bucureşti, 1992
● Mark Nelson, LZW data compresion, Dr. Dobb’s Journal, vol. 14, nr. 10, Octombrie 1989, p. 29-37
● Pascal Plume, Compression de donnees, Editura Eyrolles, Paris 1993
● K. Rose, A. Heiman şi I. Dinstein, DCT/DST alternate-transform image coding, IEEE Transactions on Communications, vol. 38, nr. 1, Ianuarie 1990, p. 94-101