| CATEGORII DOCUMENTE |
DOCUMENTE SIMILARE |
|
TERMENI importanti pentru acest document |
|
| : | |
Multimi si Dictionare
1 Tipul abstract 'Multime'
Tipul abstract multime ("Set") poate fi definit ca o colectie de valori distincte (toate de aceasi tip) , cu toate operatiile asociate colectiilor. Fata de alte colectii abstracte, multimea are drept caracteristica definitorie cautarea unui element dupa continut, cautare care este o operatie frecventa si trebuie sa necesite un timp cat mai mic. Principalele operatii cu o multime sunt:
void initS ( Set & s ); // creare multime vida (initializare )
int emptyS ( Set s ) ; // test de multime vida : 1 daca s multime vida
int findS (Set s ,T x); // 1 daca x apartine multimii s , 0 altfel
void addS ( Set & s, T x); // adauga pe x la multimea s
void delS ( Set & s, T x); // elimina valoarea x din multimea s
void printS ( Set s ); // afisarea continutului unei multimi s
int sizeS( Set s); // dimensiune multime
Pentru anumite aplicatii sunt necesare si operatii cu doua multimi:
void addAll (Set & s1, Set s2); // reuniunea a doua multimi
void retainAll (Set & s1, Set s2); // intersectia a doua multimi
void removeAll (Set & s1, Set s2); // diferenta de multimi s1-s2
int containsAll (Set s1, Set s2); // 1 daca s1 contine pe s2
Multimea noua (reuniune, intersectie, diferenta) inlocuieste primul operand (multimea s1). Nu exista operatia de copiere a unei multimi intr-o alta multime, dar ea se poate realiza prin initializare si reuniune multime vida cu multimea sursa :
initS (s1); addAll (s1,s2); // copiere s2 in s1
Nu exista comparatie de multimi la egalitate, dar se poate compara diferenta simetrica a doua multimi cu multimea vida, sau se poate scrie o functie mai performanta pentru aceasta operatie.
Tipul "multime" poate fi implementat prin orice structura de date: vector, lista cu legaturi sau multime de biti daca sunt putine elemente in multime. Daca sunt multe elemente atunci se folosesc acele implementari care realizeaza un timp de cautare minim: tabel de dispersie si arbore de cautare echilibrat.
Pentru cazul particular al unei multimi de numere intregi cu valori intr-un domeniu cunoscut si restrans se foloseste si implementarea printr-un vector de biti, in care fiecare bit memoreaza prezenta sau absenta unui element (potential) in multime. Bitul din pozitia k este 1 daca valoarea k apartine multimii si este 0 daca valoarea k nu apartine multimii. Aceasta reprezentare ocupa putina memorie si permite cel mai bun timp pentru operatii cu multimi (nu se face o cautare pentru verificarea apartenentei unei valori x la o multime, ci doar se testeaza bitul din pozitia x ).
Cea mai simpla implementare a tipului abstract multime este un vector neordonat cu adaugare la sfarsit. Realizarea tipului multime ca o lista inlantuita se recomanda pentru colectii de mai multe multimi, cu continut variabil.
Anumite operatii se pot realiza mai eficient daca multimile sunt ordonate: cautare element in multime, reuniune de multimi, afisare multime in ordinea cheilor s.a.
2 Aplicatie: acoperire optima cu multimi
Problema acoperirii optime cu multimi ("set cover") este o problema de optimizare si se formuleaza astfel: Se da o multime scop S si o colectie C de n multimi candidat, astfel ca orice element din S apartine cel putin unei multimi candidat; se cere sa se determine numarul minim de multimi candidat care acopera complet pe S (deci reuniunea acestor multimi candidat contine toate elementele lui S).
Exemplu de date si rezultate :
S = , n=4
C[1]= , C[2] =, C[3] = , C[4] =
Solutia optima este :
Algoritmul 'greedy' pentru aceasta problema selecteaza, la fiecare pas, acea multime C[k] care acopera cele mai multe elemente neacoperite inca din S (intersectia lui C[k] cu S contine numarul maxim de elemente). Dupa alegerea unei multimi C[k] se modifica multimea scop S, eliminand din S elementele acoperite de multimea C[k] (sau se reunesc candidatii selectati intr-o multime auxiliara A). Ciclul de selectie se opreste atunci cand multimea S devine vida (sau cand A contine pe S).
Exemplu de date pentru care algoritmul 'greedy' nu determina solutia optima :
S = , n=4;
C[1]= , C[2]= , C[3] = , C[4] =
Solutia greedy este , dar solutia optima este
In programul urmator se alege, la fiecare pas, candidatul optim, adica cel pentru care intersectia cu multimea scop are dimensiunea maxima. Dupa afisarea acelei multimi se elimina din multimea scop elementele acoperite de multimea selectata.
Colectia de multimi este la randul ei o multime (sau o lista ) de multimi, dar pentru simplificare vom folosi un vector de multimi. Altfel spus, pentru multimea C am ales direct implementarea printr-un vector. Pentru fiecare din multimile C[i] si pentru multimea scop S putem alege o implementare prin liste inlantuite sau prin vectori, dar aceasta decizie poate fi amanata dupa programarea algoritmului greedy:
Set cand[100], scop, aux; // multimi candidat, scop si o multime de lucru
int n ; // n= nr. de multimi candidat
void setcover ()
}
printf ('%d ', imax); printS (cand[imax]); // afiseaza candidat
removeAll (scop,cand[imax]); // elimina elemente acoperite de candidat
} while ( ! emptyS(scop));
}
Se poate verifica daca problema admite solutie astfel: se reunesc multimile candidat si se verifica daca multimea scop este continuta in reuniunea candidatilor:
void main ()
3 Implementarea unor operatii cu multimi
Pentru multimi realizate ca vectori sau ca liste inlantuite, operatiile cu o singura multime se reduc la operatii cu un vector sau cu o lista: initializare, cautare, adaugare, eliminare, afisare colectie, dimensiune multime si/sau test de multime vida.
In continuare vom ilustra cateva operatii pentru multimi realizate ca vectori de 32 de biti. Vom folosi variabile de tipul 'long' pentru fiecare multime in parte. Operatiile cu multimi de biti se realizeaza simplu si rapid prin operatori bit cu bit.
typedef long Set; // multimi cu max 32 de elemente cu valori intre 0 si 31
void initS ( Set & a)
void addS (Set & a, int x)
void delS ( Set& a, int x)
void retainAll ( Set& a1, Set a2)
void addAll ( Set& a1, Set a2)
void removeAll (Set& a1, Set a2)
int findS (Set a,int x)
int containsAll (Set a1, Set a2)
void printS (Set a) n');
}
int sizeS ( Set a)
int emptyS ( Set a)
4 Tipul 'Colectie de multimi disjuncte'
Unele aplicatii necesita gruparea elementelor unei multimi in mai multe submultimi disjuncte. Continutul si chiar numarul multimilor din colectie se modifica de obicei pe parcursul executiei programului. Astfel de aplicatii sunt determinarea componentelor (subgrafurilor) conexe ale unui graf si determinarea claselor de echivalenta pe baza unor relatii de echivalenta.
O multime din colectie nu este identificata printr-un nume sau un numar, ci printr-un element care apartine multimii. De exemplu, o componenta conexa dintr-un graf este identificata printr-un numar de nod aflat in componenta respectiva.
In
literatura se folosesc mai multe nume diferite pentru acest tip de date:
'Disjoint Sets', '
Operatiile asociate tipului abstract 'colectie de multimi disjuncte' sunt:
- Initializare colectie c de n multimi, fiecare multime k cu o valoare k: init (c,n)
- Gasirea multimii dintr-o colectie c care contine o valoare data x: find (c,x)
- Reuniunea multimilor din colectia c ce contin valorile x si y : union (c,x,y)
In aplicatia de componente conexe se creaza initial in colectie cate o multime pentru fiecare nod din graf, iar apoi se reduce treptat numarul de multimi prin analiza muchiilor existente. Dupa epuizarea listei de muchii fiecare multime din colectie reprezinta un subgraf conex. Daca graful dat este conex, atunci in final colectia va contine o singura multime.
Anterior am aratat ca o solutie buna de implementare pentru colectia de multimi este o padure de arbori, memorata intr-un singur vector de indici (cu rol de legaturi intre elementele dintr-un arbore). Vom mentiona acum cateva posibilitati de reducere a duratei operatiilor "find" si "union" prin reducerea inaltimii (adancimii) arborilor ce reprezinta multimile din colectie.
Prima idee este ca la reunirea a doi arbori in unul singur sa se adauge arborele mai mic (cu mai putine noduri) la arborele mai mare (cu mai multe noduri). O solutie simpla este ca numarul de noduri dintr-un arbore sa se pastreze in nodul radacina, ca numar negativ. Functia de reuniune de multimi va arata astfel:
void unif ( ds & c,int x,int y) else
}
A doua idee este ca in timpul cautarii intr-un arbore sa se modifice legaturile astfel ca toate nodurile din arbore sa fie legate direct la radacina arborelui:
int find ( ds c, int x)
In cazul unui graf cu 8 varfuri si muchiile 3-6, 5-7, 1-3, 2-5, 4-8, 1-6, 3-7 vor fi doi arbori cu 6 si respectiv 2 noduri, iar vectorul p de legaturi la parinti va arata astfel:
i 1 2 3 4 5 6 7 8 3 4
p[i] 3 5 -6 -2 3 3 5 4
1 6 5 8
7
Daca se mai adauga o muchie 2-4 atunci inaltimea arborelui ramas va fi tot 2 iar nodul 4 va avea ca parinte radacina 3.
Reuniunea dupa dimensiunea arborilor are drept efect proprietatea ca nici un arbore cu n noduri nu are inaltime mai mare ca log(n). Prin reunirea a doi arbori numarul de noduri din arborele rezultat creste cel putin de doua ori (se dubleaza), dar inaltimea sa creste numai cu 1. Deci raportul dintre inaltimea unui arbore si numarul sau de noduri va fi mereu de ordinul log2(n). Rezulta ca si timpul mediu de cautare intr-un arbore cu n noduri va creste doar logaritmic in raport cu dimensiunea sa.
Ca solutie alternativa se poate pastra inaltimea fiecarui arbore in locul numarului de noduri, pentru a adauga arborele cu inaltime mai mica la arborele cu inaltime mai mare.
5 Tipul abstract 'Dictionar'
Un dictionar ( "map"), numit si tabel asociativ, este o colectie de perechi cheie - valoare, in care cheile sunt distincte si sunt folosite pentru regasirea rapida a valorilor asociate. Un dictionar este o structura pentru cautare rapida (ca si multimea) avand aceleasi implementari: vector sau lista de inregistrari daca sunt putine chei si tabel de dispersie ("hash") sau arbore binar echilibrat de cautare daca sunt multe chei si timpul de cautare este important. Cheia poate fi de orice tip.
Un dictionar poate fi privit ca o multime de perechi cheie-valoare, iar o multime poate fi privita ca un dictionar in care cheia si valoarea sunt egale. Din acest motiv si implementarile principale ale celor doua tipuri abstracte sunt aceleasi.
Operatiile principale specifice unui dictionar, dupa modelul Java, sunt :
Introducerea unei perechi cheie-valoare intr-un dictionar:
int putD (Map & M, Tk key, Tv val);
Extragerea dintr-un dictionar a valorii asociate unei chei date:
Tv getD ( Map M, Tk key);
Eliminarea unei perechi cu cheie data dintr-un dictionar:
int delD (Map & M, Tk key);
Am notat cu 'Map' tipul abstract dictionar, cu Tk tipul cheii si cu Tv tipul valorii asociate; ele depind de datele folosite in fiecare aplicatie si pot fi diferite sau identice. Putem inlocui tipurile Tk si Tv cu tipul generic 'void*', cu pretul unor complicatii in programul de aplicatie care foloseste functiile 'getD' si 'putD'.
Rezultatul functiilor este 1 (adevarat) daca cheia 'key' este gasita sau 0 (fals) daca cheia 'key' nu este gasita. Functia 'putD' modifica dictionarul, prin adaugarea unei noi perechi la dictionar sau prin modificarea valorii asociate unei chei existente.
Functiile 'getD' si 'putD' compara cheia primita cu cheile din dictionar, iar realizarea operatiei de comparare depinde de tipul cheilor. Adresa functiei de comparare poate fi transmisa direct acestor functii sau la initializarea dictionarului.
La aceste operatii trebuie adaugate si cele de initializare dictionar (initD) si de afisare dictionar (printD).
Este importanta precizarea ca executia functiei 'putD' cu o cheie existenta in dictionar nu adauga un nou element (nu pot exista mai multe perechi cu aceeasi cheie) ci doar modifica valoarea asociata cheii existente. In functie de implementare, operatia se poate realiza prin inlocuirea valorii asociate cheii, sau prin eliminarea elementului cu aceeasi cheie, urmata de adaugarea unui nou element (o pereche).
Operatiile 'getD' si 'putD' necesita o cautare in dictionar a cheii primite ca argument, iar aceasta operatie poate fi realizata ca o functie separata.
Implementarile cele mai bune pentru dictionare sunt:
- Tabel de dispersie ("Hash table")
- Arbori binari echilibrati de diferite tipuri
- Liste "skip"
Ultimele doua solutii permit si mentinerea dictionarului in ordinea cheilor, ceea ce le recomanda pentru dictionare ordonate.
Pentru un dictionar cu numar mic de chei se poate folosi si o implementare simpla prin doi vectori (de chei si de valori) sau printr-un singur vector de structuri, care poate fi eventual si ordonat.
6 Implementare dictionar prin tabel de dispersie
In expresia 'tabel de dispersie', cuvantul 'tabel' este sinonim cu 'vector'.
Un tabel de dispersie ("hash table") este un vector pentru care adresa unde trebuie introdus un nou element se calculeaza din valoarea elementului, iar aceste adrese rezulta in general dispersate, fiind determinate de valorile elementelor si nu de ordinea in care ele au fost adaugate. O valoare noua nu se adauga in prima pozitie libera ci intr-o pozitie care sa permita regasirea rapida a acestei valori (fara cautare).
Ideea este de a calcula pozitia in vector in functie de valoarea care trebuie inserata. Acelasi calcul se face atat la inserare cat si la regasire :
- Se reduce cheia la o valoare numerica (daca nu este deja un numar intreg pozitiv);
- Se transforma numarul obtinut intr-un indice corect pentru vectorul respectiv, de exemplu prin calculul restului impartirii prin lungimea vectorului.
Procedura de calcul a indicelui din cheie se numeste si metoda de dispersie, deoarece trebuie sa asigure dispersia cat mai uniforma a cheilor pe vectorul alocat pentru memorarea lor. O metoda generala de calcul a adresei din cheie foloseste un cod 'hash' (un numar natural obtinut pe baza cheii) si produce ca indice in vector numarul ce reprezinta restul impartirii codului 'hash' prin dimensiunea vectorului.
Codul hash ar putea fi adresa absoluta de memorie a unei variabile alocate dinamic sau poate fi calculat din valoarea cheii. De exemplu, pentru siruri de caractere codul hash se poate calcula pe baza primelor 8-10 caractere, dupa o relatie de forma:
Sum ( s[k] * 26 k-1) % m
unde s[k] este caracterul k din sir, iar m este valoarea maxima pentru tipul intreg folosit la reprezentarea codului (int sau long). In esenta este o suma ponderata cu pozitia in sir a codului caracterelor din sir (sau a primelor 10 caractere din sir).
Orice metoda de dispersie conduce inevitabil la aparitia de 'sinonime', adica chei (obiecte) diferite pentru care rezulta aceeasi pozitie in vector. Sinonimele se numesc si 'coliziuni' pentru ca mai multe obiecte isi disputa o aceeasi adresa in vector.
Pentru a
exemplifica sa consideram un tabel de dispersie de 6 elemente in care se
introduc urmatoarele siruri (sau adresele acestor siruri):
Metodele de redistribuire a sinonimelor care poat fi grupate in:
Metode care calculeaza o noua adresa in acelasi vector pentru sinonimele ce gasesc ocupata pozitia rezultata din calcul : fie se cauta prima pozitie libera ("open-hash"), fie se aplica o a doua metoda de dispersie pentru coliziuni ("rehash"), fie o alta solutie. Aceste metode folosesc mai bine memoria dar pot necesita multe comparatii.
Pentru exemplul anterior, tabelul hash ar putea arata astfel:
poz 0 1 2 3 4 5 6
val DT AL AS PA PC BO -
Pentru regasirea sirului 'PC' se calculeaza adresa 1 si apoi se mai fac 4 comparatii pentru a gasi sirul in una din urmatoarele pozitii. Numarul de comparatii depinde de dimensiunea vectorului si poate fi foarte mare pentru anumite coliziuni.
Metode care plaseaza coliziunile in afara vectorului principal: fie intr-un vector auxiliar, fie in liste inlantuite de sinonime care pleaca din pozitia rezultata din calcul pentru fiecare grup de sinonime. Aceste metode asigura un timp mai bun de regasire, dar folosesc mai multa memorie. Exemplu cu liste inlantuite de coliziuni:
__0___1____2___3___4____5__
|____|____|____|____|____|____|
_|_ _|_ _|_ _|_
|DT| |AL| |AS| |BO|
|__ | |__| |__ | |__ |
_|_ _|_
|PC| |PA|
|__ | |__ |
Avantajele structurii anterioare sunt timpul de cautare foarte bun si posibilitatea de extindere nelimitata (dar cu degradarea performantelor). Timpul de cautare depinde de mai multi factori si este greu de calculat matematic, dar o estimare a timpului mediu este O(1), iar cazul cel mai defavorabil ajunge la O(n).
Un dezavantaj al tabelelor de dispersie este acela ca datele nu sunt ordonate si ca se pierde ordinea de adaugare la tabel. O solutie este adaugarea unei liste cu toate elementele din tabel, in ordinea introducerii lor.
De observat ca in liste sau in vectori de inregistrari se poate face cautare dupa diverse chei dar in tabele de dispersie si in arbori aceasta cautare este posibila numai dupa o singura cheie, stabilita la crearea structurii si care nu se mai poate modifica sau inlocui cu o alta cheie (cu un alt camp).
In literatura se discuta diverse variante ale tabelelor de dispersie care sa reduca timpul de cautare: alocarea suplimentara de memorie pentru tabel fata de cerinte, segmentarea tabelei si calculul unei adrese de segment ('bucket'), cu plasare si cautare secventiala in fiecare segment, s.a.
Pentru exemplul cu 6 siruri, daca se aloca un tabel de 11 pozitii (11 este un numar prim, mai mare ca numarul de obiecte ce trebuie memorate), atunci rezulta mai putine sinonime; adresele vor fi: 2, 9, 6, 3, 6, 8 (resturile impartirilor prin 11).
Ideea inlocuirii unui sir de caractere printr-un numar intreg (operatia de 'hashing') are si alte aplicatii: un algoritm eficient de cautare a unui sir de caractere intr-un alt sir (algoritmul Rabin-Karp), in metode de criptare a mesajelor s.a.
Un tabel de dispersie este un vector in care adresa unei chei se calculeaza din valoarea cheii. Sinonimele sunt chei diferite pentru care rezulta aceeasi adresa. Cea mai folosita metoda de rezolvare a coliziunilor intre chei sinonime este crearea cate unei liste pentru fiecare grup de sinonime. Lista de sinonime porneste de la adresa din vector calculata in functie de valoarea cheii.
Un tabel de dispersie va fi deci un vector de pointeri la liste de sinonime, vector care isi mentine dimensiunea initiala oricate chei s-ar adauga la tabel (desi, dupa un numar mai mare de adaugari, poate deveni necesara reorganizarea structurii).
typedef void* Ptr;
typedef int (*Fun) (void*,void*); // tip functie de comparare
typedef struct nod Nod;
typedef struct Map;
// functie de dispersie
int hashno ( Ptr key, Map dic)
// initializare tabel hash
void initD (Map& dic, int n, Fun kcmp)
// cautare cuvant in dictionar
Nod* locD (Map dic, Ptr key )
// pune pereche cheie-val in dictionar
void putD ( Map & dic, Ptr key, Ptr val)
else // cheia exista
p val=val; // modifica valoarea
}
// scoate valoarea asociata unei chei date
Ptr getD (Map dic, Ptr key)
// afisare dictionar
void printD (Map dic, Fun print )
}
}
7 Aplicatii cu dictionare
Prima aplicatie consta din afisarea unei liste de cuvinte (citite de la consola) impreuna cu numarul de aparitii al fiecarui cuvant. In aceasta problema cuvintele sunt chei iar valorile asociate lor sunt numere intregi.
Programul care urmeaza foloseste operatii cu un tip abstract dictionar in care se memoreaza pointeri la chei si valori. Programul principal nu depinde de implementarea tipului dictionar si se poate alege o alta implementare modificand doar functiile asociate tipului dictionar: initD, getD, putD, printD.
typedef void* Ptr; // tip pointer generic
typedef int (* eqcmp)(Ptr,Ptr) ; // tip functie de comparare la egalitate
// o pereche cheie-valoare
typedef struct Entry;
// aplicatia
void main ()
else
}
printD (dic); // afisare dictionar
}
Functiile utilizate au urmatoarele prototipuri:
void initD (Map& dic, int (*cmp)(Ptr,Ptr) ); // initializare dictionar
Ptr getD ( Map dic, Ptr key); // extrage valoarea asociata unei chei
int putD (Map & dic, Ptr key, Ptr val);// pune pereche cheie-valoare in dict
void printD (Map dic, int (*cmp)(Ptr,Ptr)); // afisare dictionar
Dictionarul folosit va fi implementat printr-un vector de perechi cheie-valoare.
typedef struct Map;
Adresa functiei de comparare a cheilor este data la initializarea dictionarului pentru ca este folosita atat la introducerea in dictionar cat si la cautarea dupa cheie.
// comparatie chei la egalitate
int equ (Ptr a, Ptr b)
// cauta cheie in dictionar cu rezultat indice
int locD (Map map, Ptr k)
// pune pereche cheie-valoare in dictionar
int putD (Map & map, Ptr k, Ptr v)
else
}
// citire valoare asociata unei chei date
Ptr getD (Map map, Ptr k )
Pana acum am considerat ca fiecare cheie are asociata o singura valoare, dar exista si situatii cand o cheie are asociata o lista de valori. Un exemplu este un index de termeni de la finalul unei carti tehnice, in care fiecare cuvant important (termen tehnic) este trecut impreuna cu numerele paginilor unde apare acel cuvant. Un alt exemplu este o lista de referinte incrucisate, cu fiecare identificator dintr-un program sursa insotit de numerele liniilor unde este definit si folosit acel identificator.
Un astfel de dictionar este numit dictionar cu valori multiple sau dictionar cu chei multiple sau multi-dictionar ("Multimap").
Sa consideram ca exemplu crearea unei liste de referinte incrucisate care arata in ce linii dintr-un text sursa este folosit fiecare identificator. Exemplu de date initiale:
unu / doi / unu / doi / doi / trei / doi / trei / unu
Rezultatele programului pot arata astfel (ordinea cuvintelor poate fi alta):
unu 1, 3, 9
doi 2, 4, 5, 7
trei 6, 8
Cuvintele reprezinta cheile iar numerele de linii sunt valorile asociate unei chei.
Putem privi aceasta lista si ca un dictionar cu chei multiple, astfel:
unu 1 / doi 2 / unu 3 / doi 4 / doi 5 / trei 6 / doi 7 / trei 8
Oricare din implementarile unui dictionar simplu poate fi folosita si pentru un multidictionar, daca se inlocuieste valoarea asociata unei chei cu lista valorilor asociate acelei chei (un pointer la o lista inlantuita, in limbajul C).
Vom utiliza tot un vector de structuri, pentru a refolosi o parte din programul anterior. Se modifica definitia tipului "Entry" astfel:
typedef struct nod Nod, *List;
// o pereche cheie-lista de valori
typedef struct Entry;
Se mai modifica functiile getD, putD si printD dar celelalte raman la fel:
// pune pereche cheie-valoare in dictionar
int putD (Map & map, Ptr k, int v)
else
}
Functia addL adauga un numar la o lista inlantuita de intregi si, in functie de cerintele aplicatiei, poate sa nu adauge un numar care exista deja in lista.
// adauga x la sfarsitul listei list
void addL (List & list,int x)
Nod* p=list;
while (p->leg !=NULL)
p=p->leg;
p->leg=nou;
}
// aplicatia lista de referinte incrucisate
void main ()
printD (dic); // afisare dictionar
}
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2179
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
