23. COMPACTAREA DATELOR 23.1 Parametrii stocrii datelor Volumul datelor este dat n mai multe feluri. Pentru o colectivitate ale

crei indivizi se descriu cu acelai ablon, volumul informaiilor este prezent prin numrul indivizilor. Avem o imagine suficient de clar, despre un fiier care conine informaii referitoare la 30.000 persoane sau despre o matrice are 50 linii i 80 coloane, din punct de vedere al volumului de date.

Pentru o mai bun precizare, se vor lua n considerare: N - numrul de indivizi ai colectivitii; L - lungimea structurii de date asociate unui individ; B - factorul de blocare; R - lungimea informaiilor reziduale;

Volumul de date V este dat de relaia:

V = f (N * L, B) + g(R) (23.1) unde f i g sunt forme analitice ale dependenei dintre factorii considerai, forme ce se determin pentru tipuri de suport extern de date, n mod corespunztor.

Volumul de date astfel calculat este exprimat n numr de baii. Documentaiile tehnice consemneaz capacitatea de memorare pentru fiecare tip de suport extern, ca numr maxim de baii.

Fie suportul extern i, avnd capacitatea Ci. Raportul:

100CVp

ii

(23.2)

reprezint ponderea pe care o au datele memorate n volumul V, fa de capacitatea suportului.

De exemplu, pentru un suport de 1200 ko capacitate, un fiier care ocup 400 ko, ocup 33% din suport.

Dac un programator trebuie s stocheze informaii pe un suport de capacitate Ci, sub forma unor volume V1, V2, . . . , Vn, el stocheaz numai k volume, ntruct:

k

1jij CV (23.3)

Apare ns problema existenei unei diferene, care descrie funcia

obiectiv:

k

1jji VC[min]

(23.4)

a unui model de optimizare a combinaiei de volume, care s conduc la acest obiectiv.

De exemplu, se consider:

Ci = 1000, V1 = 200, V2 = 500, V3 = 400, V4 = 300 (23.5) Se calculeaz sumele: S1 = V1 + V2 + V3 + V4 = 1400 > Ci (23.6) S2 = 200 + 500 + 400 = 1100 > Ci (23.7) S3 = 200 + 500 + 300 = 1000 = Ci (23.8) S4 = 500 + 400 = 900 < Ci (23.9) S5 = 500 + 400 + 300 = 1200 > Ci (23.10) S6 = 200 + 500 = 700 < Ci (23.11) S7 = 500 + 300 = 800 < Ci (23.12) S8 = 200 + 300 = 500 < Ci (23.13) S9 = 200 + 400 = 600 < Ci (23.14) S10 = 400 + 300 = 700 < Ci (23.15) Din toate combinaiile, S3 reprezint varianta care conduce la o bun

umplere a capacitii cu date. Apar deci ca parametri de descriere ai utilizrii unui suport, urmtorii: - gradul de ocupare; - numrul de fiiere; - volumul de informaii stocat n fiier exprimat prin intermediul

numrului de indivizi pentru care se face stocarea sau numrul de cuvinte, depinznd de unitile de msur, de natura fiierelor.

Problema maximizrii, apare pentru: - creterea gradului de umplere; - creterea numrului de fiiere ce se stocheaz; - creterea volumului de informaii. Exist modaliti specifice, care vin s amelioreze unul sau altul

dintre parametrii considerai, ceea ce influeneaz ns asupra tuturor parametrilor, este compactarea datelor.

Prin compactarea datelor, nelegem totalitatea metodelor care conduc la reducerea lungimii exprimate n baii, a datelor. Fiind dat o mulime de cuvinte:

A = {a1, a2, . . an}, de lungime l1, l2 , . . . ln (23.16)

compactarea datelor revine la a gsi funciile:

f : A K i g : K A (23.17) unde:

k = { k1, k2, . . . , km} (23.18) este mulimea cuvintelor compactate, aa fel nct exist o pereche (i, j), pentru care:

kj = f (ai) (23.19) ai = g (kj) (23.20)

Funcia f( ) se numete funcie de compactare, iar funcia g( ) este funcia de decompactare.

Deci, orice metod de compactare este complet definit, dac s-a identificat i modalitatea de a reduce setul de date n forma iniial, prin decompactare.

Pentru perechea (i , j):

lg( kj) < lg (ai) (23.21) Rezult c efectul compactrii, pentru un text format din cuvintele:

a1 a2 a3 a3 a3 a3 (23.22) de lungime iniial: L1 = 1g(a1 a2 a3 a3 a3 a3 a3) = 1g (a1) + 1g (a2) + 4*1g (a3) (23.23)

prin compactare este transformat n textul:

k1 k2 k3 k3 k3 k3 (23.24) de lungime:

L2 = 1g (k1) + 1g (k2) + 4*1g (k3) (23.25)

cu indicile de eficien a compactrii:

100L

L-L p1

21 (23.26)

23.2 Compactarea la nivel de caracter Sistemele de coduri asociate caracterelor pornesc de la urmtoarele

aspecte: - mulimea caracterelor ce sunt reprezentate este finit; de

exemplu, codul ASCII permite reprezentarea unei mulimi de caractere formate din 256 elemente;

- lungimea exprimat n bii a unui element al mulimii, este constant; codul ASCII asociat unui caracter are 8 bii.

Pentru un ir de n bii, se asociaz o mulime format din 2n elemente distincte, ce sunt puse n coresponden cu simboluri sau cuvinte, ale unei mulimi cunoscute.

Vom considera un roman, n care apar numai litere mici i litere mari, semne de punctuaie, separatorul blanc i liniua corespunztoare semnului de dialog.

Analiza textului ce formeaz romanul, pune n eviden urmtoarele aspecte:

- dintre literele mari sunt utilizate 15; - dintre literele mici sunt utilizate 24; - semnele de punctuaie cu liniua de dialog, sunt n numr de 8.

Alfabetul nou cu care operm, este format din 24+15+8 = 47 simboluri. Fiecare simbol are reprezentare pe 6 bii, ntruct cel mai mic numr natural pentru care 2n > 47 este n = 6.

Se vor pune n coresponden cele 47 de caractere, cu coduri de cte 6 bii i textul romanului care avea o lungime iniial Li:

Li = 8 * m (23.27)

unde m reprezint numrul de caractere al textului.

Dup compactarea la nivel de caracter, textul compactat are o lungime final Lf:

Lf = 6 * m (23.28)

Indicele de eficien al acestei compactri este:

%25100L

L-Lp

f

fi (23.29)

Decompactarea, presupune interpretarea succesiunilor de 6 bii i

nlocuirea lor cu caractere ASCII corespunztoare din stiva caracterelor utilizate n text.

23.3 Compactarea la nivel de cuvnt Prin analiza textului, nelegem construirea unei stive a cuvintelor

diferite din text i nregistrarea frecvenei lor de apariie. Dac meninnd codul ASCII pentru caracterele uzuale ale textului,

punem n coresponden cuvintele avnd frecvenele cele mai mari C1, C2, . . ., Ck, cu coduri asociate unor caractere ce nu apar n text, indicile de eficien al compactrii este:

100*L

f)1g(c*f-Lp

i

k

1j

k

1jjjii

(23.30)

Dac stiva cu cuvintele definite C1, C2, . . ., Ck, avnd frecvene

ridicate f1, f2, . . ., fk, este suficient de mare, i mulimea G a simbolurilor neutilizate n text, este insuficient, este necesar construirea cuvintelor g1, g2, . . ., gk formate din 1, 2, . . ., ng simboluri neutilizate, atunci performana compactrii este:

100*L

)]1g)[1g(C*f-Lp

i

k

1jjjji

(23.31)

Decompactarea revine la a nlocui cuvintele gj din text, cu cuvintele

cj, ntruct att algoritmul de compactare ct i cel de decompactare presupun existena stivei cuvintelor diferite ale textului iniial i cuvintele

din mulimea {g1, g2, . . ., gk}, a cuvintelor formate din simboluri neutilizate n text.

23.4 Compactarea prin analiza caracteristicilor textului Vom exemplifica modul de analiz al unui text, folosind reprezentarea

n memorie a tabelului de mai jos ce trebuie imprimat:

Tabelul nr. 23.1 Situaia materialelor 5

30

15

NR. CRT.

DENUMIRE VALOARE

0 1 2 1 CUIE 100 2 TABLA 200 3 VAR 600

TOTAL 900 Pentru memorarea acestui tabel, se definete un articol de 74 baii i

n fiierul TABEL.DAT, vor fi memorate 20 de rnduri, incluznd i blancurile dintre antet i capul de tabel. n fiierul TABEL.DAT vor fi ocupai 20*74=1480 baii cu acest tabel.

Prin convenie, ntruct asteriscul nu este utilizat, n continuare este folosit ca separator, iar dou asteriscuri consecutive au semnificaia de CR.

27 30b*SITUATIA MATERIALELOR 23 30b*22 - **74b**10b* 27 54 = **10b*!*5b!*30b*!*15b** 60 10b*! NR. ! DENUMIRE ! VALOARE !** 25 10b*! CRT !*30b*!*15b*!** 22 10b*!*5b*!*30b*!*15b** 69 10b*54 = **10b*! 0 ! 1 ! 2 !** 69 10b*54 = **10b*! 1 ! CUIE ! 100 !** 60 10b*! 2 ! TABLA ! 200 !** 60 10b*! 3 ! VAR ! 600 !** 9 10b*54 = ** 65 10b*! TOTAL ! 900 !** 10b*54 = ---- 523 baii

Textul astfel codificat are lungimea de 523 baii. Indicele de performan n acest caz este:

64%100*1480

5231480p

(23.32)

Compactarea merge mai n profunzime, prin identificarea elementelor invariante. Apar n mod repetat:

10b*54 = ** 10b*!*5b*!*30b*!*15b*!**

Dac aceste succesiuni vor fi nlocuite, prima cu caracterul & iar a

doua cu @:

68%100*1480

21)8*4(5231480p'

(23.33)

Dac se pune n coresponden construcia **10b* cu :, care are 10

apariii, nc se obine o ameliorare a indicelui de eficien. 23.5 Compactare prin asocierea unor coduri ce permit

eliminarea separatorilor n textele de orice tip ar fi ele, se utilizeaz diveri separatori, care

ocup un numr de poziii, depinznd de regulile acceptate de utilizare, dintre care se enumer:

- separatorii punct i virgul sunt urmai de un spaiu; - separatorul linie de dialog cnd este urmat de o liter mare sau

precedat de punct sau dou puncte, este precedat de 3-6 spaii pentru a marca un dialog;

- cuvintele sunt separate prin cel puin un spaiu; n procesarea de texte, variabilitatea numrului de spaii depinde de limea textului i de dorina de a realiza o aliniere la extremitile definite pentru un rnd.

Se consider de exemplu, nregistrarea profesiilor persoanelor ce alctuiesc o colectivitate. Din nregistrrile efectuate, rezult mulimea de profesii distincte:

forjor

strungar frezor

economist mecanic

supraveghetor Fiierul ce se creeaz, conine niruirea acestor profesii, urmnd ca

programele pentru consultarea lui, s permit numrarea elementelor ce aparin fiecrei meserii.

nregistrarea brut a informaiilor, conduce la ocuparea unei zone de memorie:

Lb=n1*lg(forjor)+n2*lg(strungar)+n3*lg(frezor)+n4*lg(economist)+

+n5*lg(mecanic)+n6*lg(supraveghetor) (23.34)

Dac fiecare meserie este pus n corespondena cu un mnemonic precum:

fo pentru forjor st pentru strungar fr pentru frezor ec pentru economist me pentru mecanic su pentru supraveghetor

n mod sever, lungimea ocupat se reduce.

)nnnnn(n*2L 654321m (23.35)

Pentru eliminarea ambiguitii generate de reducerea lungimii

mnemonicelor de la 2 caractere la un singur caracter, se efectueaz punerea n coresponden a meseriilor cu caracterele:

f forjor s strungar r frezor e economist m mecanic g supraveghetor

n aceste condiii, lungimea textului este:

654321s nnnnnnL (23.36) Forma brut a caracterelor, conduce la calculul lungimii fiierului n

baii. Lungimea efectiv, exprimat n bii, este n continuare redus dac meseriile sunt puse n coresponden cu iruri de bii, ce se bucur de o serie de proprieti suplimentare:

forjor 1 strungar 101 frezor 1001 economist 10001 mecanic 10101 supraveghetor 100001

Aceste construcii, se bucur de proprietatea ca prin concatenare,

locul unde s-a produs aceast operaie apar dou cifre binare de 1. Astfel:

6*n5*n5*n4*n3*n1*nL 654321B (23.37) Observm c:

Bsb LL*8L*8 (23.38)

n multe cazuri, lungimea cmpului este dimensionat n aa fel nct, s poat cuprinde meserii cu cele mai multe caractere, fiierul avnd articole de lungime fix.

n exemplul dat, lungimea este dat de cuvntul supraveghetor, care are 13 caractere.

)nnnnn(n138L 654321F (23.39)

Toi indicii de performan, se calculeaz n raport cu lungimea LF. Dac de exemplu, ntr-o colectivitate de 1000 persoane:

n1=100, n2=300, n3=100, n4=100, n5=300, n6=100 (23.40)

LF=8*13*1000=104000 bii (23.41)

Lb=100*6+300*8+100*6+100*9+300*7+100*13=7900 baii (23.42)

LB=100+300*3+100*4+100*5+300*5+100*6=4000 bii (23.43) n cazul n care lungimea codurilor asociate, iau n considerare

frecvenele aa fel nct, meseria cu cea mai mare frecven s fie codul de lungime cel mai mic, se obine:

LB'=300*1+300*3+100*4+100*5+100*5+100*6=3000 bii (23.44)

97%100*104000

3000104000p1

(23.45)

95%100*8*790030008*7900p2

(23.46)

25%100*4000

30004000p3

(23.47)

23.6 Compactarea prin identificarea de subiruri

repetitive Pentru cele 27 litere ale alfabetului, se construiete matricea

frecvenelor de apariie a grupurilor de cte dou litere, X. Astfel, xij reprezint numrul de apariii al literei cu poziia i, urmat de liter cu poziia j din alfabet.

Construirea matricei X se realizeaz, prin parcurgerea unei diversiti de texte i frecvenele depind de particularitile fonetice ale fiecrei limbi.

Dintre grupurile de cte dou litere, vor fi extrase acelea cu frecvenele cele mai mari i vor fi dispuse pe linii ntr-un tabel, ale crui coloane conin literele alfabetului.

Se construiete matricea Y, ale crei elemente yij, conin frecvenele de apariie ale grupului de dou litere de pe linia i, urmat de litere de pe coloana j a tabelului.

Se are n vedere c totalitatea grupurilor de litere ce vor fi selectate n ordinea descresctoare a frecvenelor de apariie, s nu depeasc un numr K aa fel nct:

K + L < 256 (23.48)

unde L reprezint numrul de caractere considerat necesar pentru introducerea unui text ntr-un fiier.

n continuare, se vor considera cele 27 litere ale alfabetului, cele 10 simboluri ale cifrelor i caracterele: spaiu, plus, minus, egal, punct, virgul, dou puncte, punct i virgul, semnul mirrii, semnul ntrebrii i asteriscul. n total sunt 48 de caractere.

Din analizele statistice efectuate pe texte, se rein grupurile de litere alctuind o mulime format din 64 de elemente dispuse n tabloul de mai jos, care au n dreptul liniilor i coloanelor combinaii de bii care alctuiesc codul asociat fiecrui ir.

Tabelul nr. 23.2 Combinaii de bii asociate irurilor de caractere

1000 1001 1010 1011 1100 1101 1110 1111 1000 u1 1e pr mb mp ni in lui 1001 lor se ut re tr te ta nu 1010 it la ea ta ti ca oi au 1011 am ar ei ra ne un ns nt 1100 cr sc st os ti at ri oa 1101 sa ma ne tre ist tri urile ind 1110 nstr eau eam esti ndu u-se ati nul 1111 asera res tit ros oasa isem tit art

Aceste grupuri de litere au fost puse n coresponden cu codul unui

caracter, altul dect cele 48 considerate. Astfel, versurile eminesciene:

Dintre sute de catarge Care leag malurile Cte oare le vor sparge Vnturile, valurile A fost odat ca-n poveti A fost ca niciodat Din rude mari mprteti O prea frumoas fat.

care nsumeaz 177 caractere incluznd i spaiile care separ cuvintele, vor fi compacte astfel:

Dx x sux de x x rge 17 64 26 36 27 x x x aga x lux x 26 24 12 62 57 12

Cix x x x vor spx ge 26 58 24 12 42 Vix ux x , valux x 48 57 12 57 12 A fox odat ca-n povex

53 73 A fox x x ciodat 53 26 16 Dx rude x x ix aratx 17 62 57 15 74 o x x fata 13 33 85

ceea ce conduce la un indice de performan:

22%100*177

137177p

(23.49)

Construirea matricei generale a subirurilor, are avantajul c este

unic pentru orice text care se compacteaz, dar exist posibilitatea de apariie a situaiei ca frecvenele grupurilor n textul de compact s nu urmeze nivelurile de frecven a textelor care au stat la baza obinerii ei.

Dac pentru fiecare compactare se construiete o matrice de subiruri proprie, performana este cu totul alta.

Pentru textul analizat, subirurile identificare se organizeaz ntr-un tabel, cruia i se ataeaz o matrice C a codurilor, ce conduce la un text de 116 caractere, avnd un indice de performan:

34%100*177

116177p

(23.50)

Dac pornim de la ideea c acest text este memorat folosind

succesiuni de 6 bii, pentru c el conine 25 de combinaii de bii, corespunztoare grupurilor de litere i cele 27 de litere, comparativ cu memorarea ca text avnd fiecare caractere cte 8 bii, indicele de performan este:

52%100*8*177

6*1168*177p

(23.51)

Se observ c algoritmii de compactare, vizeaz att lungimea

codului sub care se reprezint un caracter din text, ct i modul n care se identific elementele invariante n texte.

Spaiul ocupat de textul compactat, i se adaug o zon cu informaii care permit reconstituirea textului iniial. Aceste informaii conin:

- lungimea codurilor asociate caracterelor;

- mulimea subirurilor i a codurilor cu care acestea se pun n coresponden.

n cazul n care se identific pentru reguli complexe de scriere a textelor proceduri, acestea se pun n coresponden cu coduri i ori de cte ori apar codurile respective n text, vor fi activate procedurile care vor prelucra textul adecvat.

De exemplu, dac un text este centrat pe un rnd, blancurile vor fi eliminate, respectivul text fiind precedat de un cod care odat identificat, preia textul, l centreaz, reconstituind blancurile eliminate la compactare.

n cazul dialogurilor, nceperii unui nou paragraf sau scrierii unei formule, reconstituirea poziiei reale a textului, se efectueaz cu ajutorul procedurilor activate odat cu apariia codurilor care semnalizeaz fiecare dintre situaiile menionate.

23.7 Compactarea programelor date n form executabil Pentru utilizatori, prezint importan programele executabile.

Obiectivele programelor care efectueaz compactarea acestui tip de text, sunt gsirea unor modaliti care s determine stocarea unui numr ct mai mare de programe executabile pe un suport. n acelai timp, se urmrete i gsirea posibilitii de a efectua decompactarea textului transformat.

Programele de compactare a programelor executabile, iau n considerare urmtoarele aspecte:

- limbajul de asamblare are o mulime finit de coduri de instruciuni, dintre care programatorii folosesc sub 40%, ca diversitate n programe;

- programele executabile sunt rezultate ale compilrii i editrii de legturi; n cea mai mare parte, aceste operaii conduc la o pondere ridicat a secvenelor construite mecanic, pe baza unor reguli tip;

- programele executabile, au ca entitate instruciunea i aceasta este plasat ntr-o zon de memorie de lungime i structur fix; toate analizele, vizeaz componentele n numr restrns de pe o zon restrns; frecvenele construite vin s ajute alturi de celelalte consideraii, la dimensionarea codurilor cu care se pun n coresponden, instruciunile programului executabil.

Se consider n continuare programul:

ORG 420 H MOV D , E PUSH B XRA A CICLU: LDAX B ADC M DCR E JZ BETA STAX B INX B INX H JMP CICLU BETA: MOV

LOAX B XRA M MOV A , E STAX B STC JM GAMA MOV A , M XRA E STC JM DELTA GAMA: CMC DELTA: POP B MOV E , D RET END

Acestui program i corespunde codul obiect:

0420 53 0421 C5 0422 AF 0423 OA 0424 8E 0425 1D 0426 CA 2F 04 0429 02 042A 03 042B 23 042C C3 23 04 042F 5F 0430 OA 0431 AE 0432 7B 0433 02 0434 37 0435 FA 3F 04 0438 7E 0439 AB 0440 37 043B FA 3F 04 043F C1 0440 5A 0441 C9 0000

Textul obiect generat are 31 baii. Se vor scrie frecvenele de apariie

a elementelor din acest text.

Tabelul nr. 23.3 Frecvenele de apariie a elementelor textului

Element Frecvena 0 1 2 3 4 5 6 7 8 9 A B C D E F

8 2 4 9 4 4 - 4 1 1 6 1 3 1 4 6

mprtierea cifrelor hexazecimale, reduce masiv posibilitatea

efecturii unor prelucrri directe pe textul obiect. Se procedeaz la efectuarea modificrilor: a) se ncepe contorizarea de la zero i se memoreaz 0420 i textul

devine:

0000 53 0001 C5 0002 AF 0003 OA 0004 8E 0005 1D 0006 CA 00 OF 0009 02 000A 03 000B 23 000C C3 00 03 000F 5F 0010 0A 0011 AE 0012 7B 0013 02 0014 37 0015 FA 00 1F 0018 7E 0019 AB 001A 37 001B FA 00 1F 001F C1

0020 5A 0021 C9

Cea mai mic valoare din prima cifr hexazecimal a prii de

instruciune, este 0 i cea mai mare este F. Tabelul nr. 23.4 Frecvenele de apariie a elementelor textului

Element Frecvena 0 1 2 3 4 5 6 7 8 9 A B C D E F

5 1 - 2 - 2 - 2 1 - 2 - 5 - - 2

Din 15 simboluri lipsesc 7. Construim pe 2 baii masca elementelor

absente: 0 1 2 3 4 5 6 7 8 9 A B C D E F

------------------------------------------------------------------------ 1 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1

Se analizeaz frecvena de apariie a cifrelor hexazecimale pe al II-

lea bait al instruciunii. Tabelul nr. 23.5 Frecvenele de apariie a cifrelor hexazecimale

pe baitul II al instruciunii

Element Frecvena 0 1 2 3 4 5 6 7 8 9

- 1 2 4 - 1 - 2 - 1

A B C D E F

6 2 - 1 3 2

Se construiete pe 2 baii masca elementelor absente: 0 1 2 3 4 5 6 7 8 9 A B C D E F

------------------------------------------------------------------------ 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 Se observ c pentru un text de lungime redus, elementele

repetitive nu se identific i deci compactarea are efecte reduse, uneori nule sau chiar pgubitoare.

Limbajele de asamblare moderne, au n definire operaii de tip RR (registru-registru) i ntruct numrul registrelor este redus, sunt asociate coduri diferite pentru combinaia de cod operaie R1, R2 ceea ce reprezint o compactare la nivel de limbaj. Tot astfel, n cazul instruciunilor memorate pe trei baii, deplasarea operandului este reprezentat pe un singur bai, prin recalcularea ei.

n cazul unor texte mult mai lungi, dac resursele sunt folosite convenabil i programatorii stabilesc reguli precise de realizare a unor anumite prelucrri, compactarea este realizabil.

Astfel, n toate subprogramele, secvena de preluare a parametrilor este standardizat i deci este pus n coresponden cu un cod i nlocuit cu acesta.

Aplicnd principiile de analiz ale textului, compactarea se realizeaz n principal prin tratarea elementelor repetitive i n programele scrise n limbajul de asamblare sau generate de compilatoare, acestea nu au o pondere important.

23.8 Compactarea datelor numerice Reprezentarea matricelor rare, este un exemplu de compactare a

datelor. n cazul seriilor de date, problema compactrii este important dac seriile au variaii mici sau dac seriile au o lungime foarte mare.

Fie seria de date X avnd termenii: 11120 11130 11131 11136 11170 11135 11131 11109 11121 11122 11120 11104 Cei 12 termeni ai seriei de date, dac sunt reprezentai binar, ocup

fiecare cte 2 baii, deci n total 24 baii. Observm c termenul minim al seriei este 11104, iar termenul maxim este 11170.

D = Xmax Xmin = 66 (23.52)

iar:

0,00511108

60Xmin

D

(23.53)

ceea ce arat c datele se afl ntr-un interval foarte ngust n raport cu mrimea lor.

Considerm Xmin = 11104. Se calculeaz o nou serie x':

xi' = xi xmin (23.54) al crei termeni sunt:

16 26 27 32 66 51 27 5 17 18 16 0

Numerele acestea se reprezint pe 7 bii. Deci, pentru cei 12 termeni

sunt necesari 84 de bii, iar pentru 11104 sunt necesari 2 bii.

52%100192100100

8*248*284p

(23.55)

Compactarea la nivel de bii, se dovedete cu efecte mai importante

dac se combin cu alte procedee de compactare.

111 111 111 112 112 112 113 113 111 112 112 112

Elementul minim este 111, iar elementul maxim este 113. n

reprezentare binar a ntregilor, pentru fiecare termen este necesar un bai. Seria aceasta necesit 12 baii.

Observm c exist elementele repetitive 111, 112 i 113, care vor fi puse n coresponden cu caracterele a, b, c, respectiv 00, 01, 10. Pentru cele trei numere sunt necesari 7 bii.

46%1009645100

81221273p

(23.56)

23.9 Programe care efectueaz compactarea Un program P de lungime L, se zice c este compactat de programul

X, dac forma obinut P', are o lungime L' cu peste 20% mai mic dect lungimea L.

Programul X execut complet compactarea, dac ncercnd compactarea programului P', se obine un program P" de lungime L" i dac L' = L" i P" este identic cu P'.

Programul Y realizeaz decompactarea programului P', dac dup executarea sa se obine programul P' ' ' de lungime L' ' ', aa fel nct L' ' ' = L i P' ' ' este identic cu P'.

Programele de compactare sunt specializate s aib ca intrare, fie texte surs, fie texte obiect, fie componente executabile. Exist i programe generale care efectueaz compactarea i decompactarea. Exemple de astfel de programe sunt PKZIP . EXE, PKUNZIP . EXE, ARJ . EXE, PKARC . EXE. Fiecare dintre acestea folosesc algoritmi specifici de compactare, n funcie de tipul fiierelor supuse comprimrii.

Formatul general al unei etichete de fiier arhivat, l descriem prin structura urmtoare n C:

struct fisier_compactat { int metoda_compactare[10]; char nume_fisier[8]; char extensie_fisier[3]; unsigned char atribut_fisier; short int data; short int timp; short int cluster_start; long int lungime_fisier_initial; long int lungime_fis_compactat; int suma_control; };

Se asociaz fiecrei metode de compactare folosit un anumit cod, ca

de exemplu: - 0, dac fiierul a fost memorat n forma sa iniial, compactarea

nefiind eficient; - 1, dac fiierul a fost comprimat printr-un algoritm nerepetitiv; - 2, dac fiierul a fost comprimat n mai multe etape. Aceste probleme sunt nzestrate cu funcii specifice gestionrii de

fiiere arhivate, respectiv adugare, tergere, modificare, protecie. Unul dintre algoritmii utilizai de aceste programe de compactare este

cel al lui Huffman. Acest algoritm are drept scop de a minimiza numrul de bii necesar pentru reprezentarea oricrui simbol dintr-un alfabet. Astfel, se atribuie simbolurilor cu o frecven de utilizare mare, coduri mai scurte, iar simbolurilor mai rar folosite, coduri mai lungi. n acest mod, media lungimii codului, este mai redus.

Aceast tehnic a utilizat-o i Samuel Morse cnd a definit alfabetul Morse.

n codul Huffman, frecvena de apariie a caracterelor din textul surs, trebuie cunoscut sau estimat. Apoi, se asociaz fiecrui simbol o secven de bii unic, care este definit utiliznd un arbore binar.

Un cod Huffman este construit astfel: - se ordoneaz descresctor, dup frecven sau probabilitatea de

apariie, simbolurile din textul surs; - se consider fiecare simbol un nod n arbore, fiecrui nod fiindu-i

asociat o probabilitate (frecvena) de apariie; - se leag dou noduri cu probabilitatea de apariie cea mai mic,

ntr-un nod a crui probabilitate este dat de suma probabilitilor celor dou noduri acest proces se ncheie n momentul n care rmne un nod nelegat.

Rezultatul acestei operaii este un arbore binar, n care ramura stng a unui nod printe are eticheta 0, iar ramura din dreapta, eticheta 1 .

S presupunem c textul nostru iniial este format din 40 de caractere, utiliznd un alfabet din 8 simboluri; frecvenele de apariie ale fiecrui simbol, sunt calculate ca raport ntre numrul de apariii a simbolului respectiv i numrul total de caractere ale textului.

n tabelul de mai jos, presupunem numrul de apariii ale simbolurilor i n funcie de acest numr calculm numrul total de bii pe care l ocup simbolul respectiv, n reprezentarea normal (8 bii/caracter).

Tabelul nr. 23.6 Varianta I de construire a codului Huffman

Simbol Nr. de apariii

simbol Total nr. de bii

pentru un simbol (reprez. normal)

Total nr. de bii pentru un simbol (cod Huffman)

0 1 2 3 4 5 6 7

12 8 6 5 4 3 2 0

96 64 48 40 32 24 16 0

12 16 18 20 20 18 14 0

Total 40 320 118

20%

12%

10%

100 %

70 %

50 % 35 %

23%

13 %

5 %

0

0

0

0

0

0

0

1

1

1

1

1

1

1 1111111

0

10

110

1110

11110

111110

1111110

0

1

2

3

4

5

6

7

30%

15%

8%

5%

0%

Figura 23.1 Structura arborescent a codurilor Huffman Dac ns, cuplm nodurile n felul urmtor:

0

100%

111111

0

110

100

101

1110

11110

0

1

2

30%

20%

15%

12%

10%

8%

5%

0%

3

4

5

6

7

0

0

170%43% 1

0

1

1

0

0

11

23%

13%

5%

111110

0

127%

Figura 23.2 Structura arborescent a codurilor Huffman dup cuplarea nodurilor

vom obine:

Tabelul nr. 23.7 Varianta II de construire a codurilor Huffman

Simbol Nr. de apariii simbol

Total nr. de bii pentru un simbol (reprez. normal)

Total nr. de bii pentru un simbol (cod Huffman)

0 1 2 3 4 5 6 7

12 8 6 5 4 3 2 0

96 64 48 40 32 24 16 0

12 24 18 15 16 15 12 0

Total 40 320 112 i se observ c am obinut un numr total de bii mai mic dect n prima variant, iar diferena este cu att mai mare, cu ct avem texte de lungime mai mari.

Observm, c pe lng faptul c codul Huffman folosete n medie, un numr de bii mai mic dect codul ASCII pentru reprezentarea unui caracter, mai are proprietatea c secvena binar asociat fiecrui simbol, nu este prefixul unui alt simbol i de aceea, secvenele de bii sunt concatenate fr s se foloseasc nici o punctuaie de delimitare a acestora.

Tabelul nr. 23.1 Situaia materialelor