Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Matematica


Index » educatie » Matematica
» Arbori binari optimi


Arbori binari optimi


Lucrarea

Arbori binari optimi

1.Definitia arborilor binari optimi

In lucrarile precedente, organizarea structurii de arbore binar ordonat nu a luat in considerare probabilitat ile de acces (frecventele de aparitie) ale cheilor nodurilor.

Uneori se cunosc probabilitatile de acces la cheile dintr-un arbore, astfel incat organizarea arborelui binar le poate lua in calcul, plasand cheile mai frecvent cautate in noduri mai aproape de radacina.

Se pune problema ca numarul total al pasilor de cautare contorizat pentru un numar suficient de incercari, sa fie minim.



Se defineste drumul ponderat ca fiind suma tuturor drumurilor de la radacina la fiecare nod, ponderate cu probabilitatile de acces la noduri:

unde pi - ponderea nodului i, iar hi - nivelul nodului i.

Se urmareste minimizarea lungimii drumului ponderat, pentru o distributie data.

Exemplu: Se considera secventa de chei: 1,2,3 si probabilitatile de acces p[1]=1/7, p[2]=2/7 s i p[3]=4/7. Exista 5 arbori binari ordonat i care pot fi construit i din aceste chei, reprezentat i mpreuna cu drumurile ponderate corespunzatoare in figura 1.

De exemplu, pentru primul arbore, drumul ponderat PI se calculeaza: PI= (1/7)*3+(2/7)*2+(4/7)*1=11/7

Daca organizarea arborelui binar ia n considerare si probabilitatile (ponderile) cautarilor nereusite, deci notand cu qi probabilitatea cautarii unei chei x cu valoarea ntre cheile ki si ki+1, lungimea drumului ponderat va fi:

unde

Se considera ca fiecarei cautari nereusite i este asociat un acces ipotetic la un nod 'special', situat ntre cheile imediat mai mica , respectiv imediat mai mare. Unui astfel de nod special i se asociaza o lungime, numita a drumului extern. In formula anterioara , hj reprezinta nivelul nodului 'special'.;

Se considera toate structurile de arbori binari care pot fi alcatuiti pornind de la setul de chei ki, avand probabilitatile asociate pi si qj. Se numeste arbore binar optim, arborele a carui structura conduce la un cost minim.

In practica se pot nlocui probabilitatile cu contoare de frecventa, care memoreaza numarul de accese la un nod, si atunci:

unde numerele ai, bj precizeaza :

ai - numarul care precizeaza de cate ori x = ki;

bj - numarul care precizeaza de cate ori kj<x<kj+1;

b0- numarul care precizeaza de ca te ori x<k1;

bn- numarul care precizeaza de cate ori x>kn.

2. Constructia arborilor binari optimi

Arborii optimi au proprietatea ca toti subarborii lor sunt optimi, sugerand algoritmul care construieste sistematic arbori din ce n ce mai mari, pornind de la nodurile individuale (subarbori de naltime 1), arborii crescand de la frunze spre radacina, conform metodei "bottom-up".

Notand cu P lungimea drumului ponderat al arborelui, cu PS ?i PD lungimile drumurilor ponderate ale subarborilor stang si drept ai radacinii si cu W ponderea arborelui, deci numarul de treceri prin radacina (tocmai numarul total de cautari n arbore):

Media lungimii drumului ponderat e P/W.

Pentru subarborele optim ti,j format din nodurile ki+1, ki+2, , kj, bi, , bj se noteaza cu wi,j ponderea si cu pi,j lungimea drumului total (0<=i<=j<=n).

Sunt adevarate relatiile:

wi,i=bi, 0<=i<=n

wi,j=wi,j-1 + aj + bj , 0<=i<j<=n (1) ;

pi,i=wi,i ;

pi,j=wi,j + min(i<k<=j)(pi,k-1 + pk,j) (2) ;

Pentru ca exista aproximativ n^2/2 valori ale lui pij pentru cele 0<j-1<=n cazuri, operatia de minimizare va necesita aproximativ n^3/6 operat ii, deci determinarea unui arbore optim se va face n O(n^3) unitati de timp, folosind O(n^2) locatii de memorie.

Knuth propune reducerea timpului de executie cu un factor proportional cu n, prin aplicarea urmatoarei metode de constructie.

Se noteaza cu ri,j (i<j) multimea tuturor valorilor k pentru care relatia (2) e minima, ea reprezentand radacinile posibile ale arborilor optimi.

Daca s-a gasit o radacina ri,j a unui subarbore optimal Ai,j, atunci nici extinderea arborelui prin adaugarea unui nod la dreapta, nici suprimarea celui mai din stanga nod al sau, nu poate cauza deplasarea spre stanga a radacinii.

ri,j-1<=ri,j<=ri+1,j

Atunci solutiile pentru ri,j sunt n domeniul ri,j-1 ,, ri+1,j, rezultand un numar de O(n^2) pasi elementari. Se considera urmatoarele structuri de date: type index=0..n;

var a:array[1..n] of integer;



b:array[index] of integer;

p,w:array[index,index] of integer;

r:array[index,index] of index;

Ponderile wi,j (valorile din w) se calculeaza folosind relatia (1), w se considera argument al procedurii de constructie, vectorul r, ce descrie constructia completa va fi rezultatul sau, iar p un rezultat intermediar.

Se noteaza cu h latimea j-i a subarborelui Ai,j.

Pentru h=0, pii se determina direct din relatia (2).

for i:=0 to n do p[i,i]=w[i,i];

Pentru h=1, arborii au un singur nod, radacina:

for i:=0 to n-1 do
begin
j:=i+1;
p[i,j]:=p[i,i]+p[j,j];
r[i,j]:=j
end

Pentru h>1 se foloseste o secventa repetitiva, cazul h=n presupunand traversarea ntregului arbore A0,n:

for h:=2 to n do
for i:=0 to n-h do
begin
j:=i+h;
* gaseste pe m din intervalul r[i,j-1]<=m<=r[i+1,j],
pentru care p[i,m-1]+p[m,,j] are valoarea minima min;
p[i,j]:=min+w[i,j];
r[i,j]:=m
end;

Algoritmul de determinare al arborilor optimi necesita O(n^2) unitati de timp si un volum de memorie de acelasi ordin.

3. Coduri Huffmann

Codurile Huffmann constituie un exemplu de utilizare a arborilor binari ca structuri de date si reprezinta o varianta de codificare a unor caractere ce apar ntr-un limbaj, fiind determinata de probabilitat ile de apari?ie ale caracterelor, ale caror valori se cunosc.

Codul oricarui caracter e o secventa de 0 sau 1, astfel incat sa nu fie prefix pentru codul niciunui alt caracter. Se impune cerinta ca lungimea medie a codurilor sa fie minima, deci si lungimea mesajului codificat sa fie minima.

Algoritmul Huffmann selecteaza doua caractere a si b care au probabilitatile cele mai scazute de aparitie si le nlocuieste cu un caracter imaginar x cu probabilitatea egala cu suma probabilitatilor lui a si b. Aplicand recursiv aceasta procedura, se reduce n final setul de caractere la doua , codificate prin 0 si 1. Codul pentru setul original de caractere se obtine adaugand la codul lui x un 0 la ntalnirea caracterului a si un 1 pentru b.

Un cod prefix se poate asimila cu un drum ntr-un arbore binar, considerand ca trecerea la fiul stang al unui nod adauga un 0 codului, la cel drept, 1.

In implementarea algoritmului lui Huffmann se foloseste o colectie de arbori binari, ale caror noduri terminale sunt caractere si ale caror radacini au asociata suma probabilitatilor de aparitie a caracterelor corespunzatoare tuturor nodurilor terminale, numita greutatea (ponderea) arborelui.

In continuare se descrie o varianta de structuri de date necesare implementarii algoritmului.

Pentru reprezentarea arborelui binar se foloseste un tablou ARBORE, fiecarui nod rezervandu-i-se cate o intrare cu cursorii la fiul stang, la cel drept si la parinte.

Variabila de tip indice (cursor) ULTIM_NOD indica ultimul element ocupat al tabloului. Tabloul ALFABET inregistreaza pentru fiecare simbol probabilitatea sa de aparitie si cursorul la nodul terminal asociat.

Tabloul ZONA nregistreaza colectia de arbori binari, fiecare nregistrare referindu-se la un arbore si cuprinzand greutatea arborelui si un cursor la radacina sa din ARBORE; ULTIM_NOD indica ultima intrare ocupata din ZONA.

var ARBORE:array[1..max1] of
record
fiu_stang, fiu_drept, parinte : integer

end

ULTIM_NOD:integer;
ALFABET:array[1..max2] of
record
simbol:char;
probabilit:real;
terminal:integer

end

ZONA:array[1..max3] of record;
greutate:real;
radacina:integer

end

ULTIM_ARB:integer;

Exemplu: Se considera urmatorul alfabet, format din simbolurile a,b,c,d, avand probabilitatile: P(a)=15% P(b)=52% P(c)=10% P(d)=23%. Constructia arborelui de codificare Huffman cuprinde etapele ilustrate in figura 2.



Pentru codificarea obisnuita a unui alfabet compus din 4 simboluri sunt necesari cate 2 biti pentru fiecare simbol.

Se observa ca, aplicand algoritmul lui Hufman, simbolurilor care au frecventa de aparitie maxima li se atribuie coduri scurte, iar celor rar folosite coduri lungi. Astfel, simbolului 'b', care este cel mai des utilizat, i se atribuie un cod format dintr-un bit, iar simbolurilor 'a' si 'c' coduri pe trei biti.

La decodificarea unui mesaj, pe ma sura ce bitii sunt cititi, se parcurge arborele de coduri de la radacina pana la intalnirea unei frunze, calea urmand fiul stang daca bitul citit este 0 si fiul drept daca bitul citit este 1. De exemplu, daca se citeste mesajul codificat 010110011, se poate reconstitui mesajul initial abbdbb. Proprietatea de prefix a codului Hufmann este deosebit de importanta , permitand decodificarea neambigua a mesajului.

4. Exercitii

4.1. Se considera cheile a,b,c,d cu probabilitatile de acces 3/15, 1/15, 7/15, respectiv 4/15.

a) Sa se construiasca toti ABO ce cont in cheile date;

b) Sa se calculeze drumurile ponderate pentru toti arborii; care este arborele optim ?

4.2. Fie secventele de codificat:

i) 'MARE E MAREA MARMARA',

ii) 'CAPRA CALCA PIATRA, PIATRA CRAPA-N PATRU, ASA SA CRAPE CAPUL CAPREI, PRECUM A CRAPAT PIATRA-N PATRU'

Pentru fiecare secventa in parte, se cere:

a) Sa se construiasca arborele de codificare Huffman si sa se scrie codurile obtinute;

b) Care este codificarea secventei initiale si ce lungime exprimata in octeti are ?

5. Aplicatii

5.1. Pentru o sursa C oarecare, sa se construiasca doi arbori optimi continand cuvintele cheie, primul pe baza contoarelor de aparitie a cuvintelor cheie, iar al doilea luand in considerare si contoarele de cautare corespunzatoare celorlalti identificatori din text.

Pentru fiecare arbore, sa se afiseze contoarele ce au stat la baza constructiei, arborii obtinuti si timpii necesari cautarii tuturor identificatorilor din fisierul initial si din alte fisiere sursa.

5.2. Sa se gaseasca codurile Huffmann corespunzatoare caracterelor dintr-un text oarecare. Sa se afis eze codurile obtinute si raportul intre lungimea textului initial si a celui codificat (comprimat).

5.3. Sa se implementeze un program utilitar de compresie-decompresie a datelor, pe baza algoritmului lui Huffmann.







Politica de confidentialitate





Copyright © 2024 - Toate drepturile rezervate