3.Tabel de dispersie. Tipul abstract dictionar.
Multimi realizate prin tabele de dispersie
Structura de date care permite cel mai bun timp de căutare într-o multime neordonată este un tabel de dispersie ("Hash Table"). In expresia "tabel de dispersie", cuvântul "tabel" este sinonim cu "vector". Principala diferentă fată de un vector obisnuit este modul în care se determină pozitia (adresa) unde se introduce un nou element. O valoare nouă nu se adaugă în prima pozitie liberă ci într-o pozitie care să permită regăsirea rapidă a acestei valori (fără o căutare prin vector).
Ideea este de a calcula pozitia în vector în functie de valoarea care trebuie introdusă. Acelasi calcul se face atât la introducere în vector cât si la regăsire.
Tabelul de dispersie este folosit pentru implementarea a două tipuri abstracte de date: multime de valori si dictionar de perechi cheie-valoare.
In principiu procedura de calcul are două părti:
- Reducerea cheii (elementului) la o valoare numerică (dacă nu este deja un număr întreg pozitiv);
- Transformarea numărului obtinut într-un indice corect pentru vectorul respectiv, de exemplu prin calculul restului împărtirii prin lungimea vectorului.
Procedura de calcul a indicelui din cheie se numeste si metodă de dispersie, deoarece trebuie să asigure dispersia cât mai uniformă a cheilor pe vectorul alocat pentru memorarea lor.
Nu există o metodă generală de dispersie si ea trebuie aleasă de utiliz 20520c26u ator, după o analiză a valorilor cheilor si a rezultatelor aplicării metodelor propuse la cheile din fiecare aplicatie. Orice metode de dispersie conduce inevitabil la aparitia de "sinonime", adică chei diferite pentru care rezultă aceeasi pozitie în vector. Se mai foloseste si cuvântul "coliziune" pentru situatia când mai multe chei ar trebui plasate la aceeasi adresă în vector, ceea ce este imposibil.
Pentru a exemplifica să considerăm că trebuie să memorăm într-un vector de 6 elemente următoarele siruri de câte 2 caractere (sau adresele acestor siruri): AL, AS, BO, DT, PA, PC. Adunând codurile celor 2 litere si retinând ultimii 4 biti obtinem numerele întregi :13, 20, 17, 24, 17, 19. Resturile împărtirii prin 6 ale acestor numere conduc la indicii: 1,2,5,0,5,1. După plasarea primelor 4 chei, în pozitiile 1,2,5,0 rămân libere pozitiile 3,4 si vor apare 2 coliziuni. Se observă că este importantă si ordinea de introducere a cheilor într-un tabel de dispersie.
S-au propus mai multe metode de redistribuire a sinonimelor (de rezolvare a coliziunilor):
- Metode care calculează o nouă adresă în acelasi vector pentru sinonimele ce găsesc ocupată pozitia rezultată din calcul : fie se caută prima pozitie liberă, fie se aplică o a doua metodă de dispersie pentru coliziuni, fie altă solutie.
- Metode care plasează coliziunile în afara vectorului principal: fie într-un vector auxiliar, fie în liste înlăntuite de sinonime care pleacă din pozitia rezultată din calcul pentru fiecare grup de sinonime. Un vector de pointeri la liste de sinonime este o solutie destul de generală si comodă pentru utilizator (care nu trebuie să ia o hotărâre de fiecare dată).
Pentru exemplul anterior structura de tabel hash cu 6 liste de sinonime arată astfel:
0 1 2 3 4 5
DT AL , PC AS - - BO,PA
In general, după introducerea în tabel, se pierde si ordinea de introducere, iar afisarea în ordine a datelor din tabel nu este posibilă decât prin crearea unui alt vector ordonat.
In literatură se discută diverse variante ale tabelelor de dispersie care să reducă timpul de căutare: segmentarea tabelei si calculul unei adrese de segment ('Bucket'), cu plasare si căutare secventială în fiecare segment, plasarea sinonimelor în functie de frecventa de căutare, s.a.
Functiile care urmează arată cum pot fi realizate operatiile elementare cu o multime de cuvinte realizată ca tabel de dispersie , folosind un vector de pointeri la liste înlăntuite de sinonime.
#define H 11 // dimens. tabel hash
typedef struct snod * pnod, *pos;
typedef pnod Set[H];
// functie de dispersie
int hashno ( char * s)
// initializare multime
void initS (Set h)
// afisare dictionar
void printS (Set h)
}
// cautare cuvânt în multime
int containsS (Set h, char * c)
// adauga cuvint la multime
void addS ( Set h, char * c)
Functiile anterioare pot fi generalizate pentru o multime de pointeri la orice tip de date.
Redimensionarea vectorului de pointeri necesită re-crearea tabelului de dispersie, deoarece se modifică numărul si continutul listelor de sinonime. Această decizie poate fi luată atunci când lungimea listelor si timpul de căutare secventială în aceste liste devine mare. Avantajul unui tabel de dispersie cu liste fată de o singură listă înlăntuită este acela că înlocuieste căutarea într-o singură listă mare cu căutarea într-una din listele mai mici, selectată direct pe baza valorii căutate.
Tipul abstract "Dictionar"
Un dictionar sau o asociere ( "Map") este o colectie de perechi cheie - valoare, în care cheile sunt distincte si sunt folosite pentru regăsirea rapidă a valorilor asociate. Un dictionar poate fi realizat ca un singur vector, ca listă înlătuită de perechi sau prin doi vectori, dacă performantele nu sunt importante. Cele mai folosite implementări ale tipului "dictionar" sunt ca tabel de dispersie ("hash") sau ca arbore binar echilibrat de căutare, atunci când performantele la căutare sunt importante (se fac căutări frecvente). Cheia poate fi de orice tip.
De observat că în liste sau în vectori de perechi se poate face căutare după diverse chei dar în tabele de dispersie si în arbori această căutare este posibilă numai după o singură cheie, stabilită la crearea structurii si care nu se mai poate modifica sau înlocui cu o altă cheie (cu un alt câmp).
Operatiile principale specifice unui dictionar sunt :
- Introducerea unei perechi cheie-valoare într-un dictionar: putD
- Extragerea dintr-un dictionar a valorii asociate unei chei date: getD
- Eliminarea unei perechi cu cheie dată dintr-un dictionar: delD
Rezultatul functiilor este 1 (adevarat) dacă cheia căutată este găsită sau 0 (fals) dacă cheia nu este găsită. Functia "putD" modifică oricum dictionarul, fie prin adăugarea unei noi perechi la dictionar, fie prin modificarea valorii asociate unei chei existente.
Alte operatii posibile cu dictionare sunt : afisarea tuturor perechilor din dictionar (printD),
initializare dictionar (initD), căutarea unei chei date (containsKey), căutarea unei valori date (containsValue), creare multime de chei (keySet), creare listă de valori (values) s.a.
Un exemplu de aplicatie a unui dictionar este crearea si afisarea unei liste a cuvintelor distincte extrase dintr-un text, împreună cu numărul de aparitii în text al fiecărui cuvânt. Pentru a face programul mai simplu, se citesc de la consolă cuvinte aflate pe linii separate.
In această problemă cheile sunt cuvintele , iar valorile asociate lor sunt numere întregi.
void main (int argc, char * argv[])
printD(dc); // afisare dictionar
Urmează definitiile si functiile pentru operatii cu un dictionar realizat ca un tabel de dispersie :
#define H 11 // dimens. tabel hash
typedef struct snod * pnod, *pos;
typedef pnod Dic[H]; // tip dictionar
// functie de dispersie
int hashno ( char * s)
// initializare dictionar
void initD (Dic dc)
// afisare dictionar
void printD (Dic dc)
}
// cautare cuvânt în dictionar
pos locD (Dic dc, char * c)
// adauga pereche cheie-val la dictionar
void putD ( Dic dc, char * c, int nr) else
// extrage valoarea asociata unei chei date
int getD (Dic dc, char* c)
Functiile "getD" si "putD" implică o căutare a unei chei în dictionar, deci o comparatie de valori. Functia de comparare depinde de tipul datelor comparate si ar trebui transmisă ca argument fie celor două functii, fie functiei de initializare a dictionarului (care memorează adresa functiei de comparare, pentru a fi folosită de alte functii). Functia de initializare poate primi ca parametru si dimensiunea vectorului de pointeri, dimensiune care nu se mai modifică ulterior.
Dictionar cu valori multiple
Uneori unei chei i se asociază o listă (o multime) de valori si nu o singură valoare. Această variantă de dictionar (numită uneori "Multimap" = dictionar cu valori multiple) este necesară în aplicatia "Tabel de referinte încrucisate". O listă de referinte încrucisate, creată pe baza unui text (care poate fi un program sursă), contine pentru fiecare cuvânt distinct din text numerele liniilor unde apare acel cuvânt. O variantă a acestei probleme este un glosar de termeni (un index) asociat unei cărti, glosar care contine doar anumite cuvinte, considerate esentiale.
In programul următor am folosit un dictionar realizat din doi vectori : un vector de cuvinte (de pointeri la cuvinte) si un vector de pointeri la liste înlăntuite cu numere de linii:
// dictionar cu valori multiple (vector de liste)
#define M 1000 // nr maxim de cuvinte
// tip nod de lista inlantuita
typedef struct sn Nod;
// tip dictionar
typedef struct dic, *Dic ;
// operatii cu structura dictionar
Dic initD ()
// cauta cuvant in dictionar
Nod * get (Dic d, char *w)
// adauga pereche la dictionar
void addD (Dic d, char * w, int nl)
else
// afisare dictionar
void printD (Dic d)
printf("\n");
}
// creare si afisare lista de referinte încrucisate
void main (int argc, char* argv[])
}
printD (crf); // afisare multime
Dictionarul cu liste de valori asociate unei chei poate fi definit pentru a lucra cu chei si valori de orice tip, dar codul sursă devine greu de urmărit. De asemenea, putem modifica implementarea tipului dictionar.
Tipul "Colectie de multimi disjuncte"
Unele aplicatii cu grafuri necesită gruparea elementelor unei multimi în mai multe submultimi disjuncte. Continutul si chiar numărul multimilor din colectie se modifică de obicei pe parcursul executiei programului. O astfel de aplicatie este determinarea componentelor (subgrafurilor) conexe ale unui graf (un graf este conex dacă există o cale între orice pereche de noduri din graf).
O altă aplicatie asemănătoare este determinarea claselor de echivalentă ce se pot forma cu o serie de numere (sau alte valori), cunoscând perechi de elemente (numere) echivalente.
Ceea ce este specific acestor aplicatii este faptul că o multime din colectie nu este identificată printr-un nume sau un număr, ci printr-un element care apartine multimii. De exemplu, pentru a găsi o componentă conexă din graf se dă un număr de nod.
Operatiile asociate tipului abstract "Colectie de multimi disjuncte" ("Disjoint Sets") sunt:
- Crearea unei multimi având ca unic membru o valoare dată x , în colectia 'c': initDS (c, x)
- Găsirea multimii dintr-o colectie 'c' care contine o valoare dată x: findDS (c,x)
- Reuniunea multimilor din colectia 'c'ce contin valorile x si y : unionDS (c,x,y)
Functia "findDS" are ca rezultat o multime, deci tipul ei depinde de implementarea colectiei.
Algoritmul pentru determinarea componentelor conexe dintr-un graf poate fi exprimat astfel:
repetă ptr. fiecare nod v din graful g
initDS (g,v)
repetă pentru fiecare arc (x,y) din graf
dacă findDS(g,x) != findDS(g,y) atunci
unionDS (g,x,y)
Initial se crează în colectie câte o multime pentru fiecare nod din graf, iar apoi se reduce treptat numărul de multimi prin analiza arcelor existente. După epuizarea listei de arce fiecare multime din colectie reprezintă un subgraf conex. Dacă graful dat este conex, atunci în final colectia va contine o singură multime. Exemplu: Graful neorientat cu 5 noduri si cu arcele (1,3), (3,5), (1,5), (2,4) are două componente conexe: si .
Programul următor foloseste tipul abstract "DS" si nu depinde de implementarea acestui tip.
void main ()
Cea mai simplă implementare a unei colectii de multimi disjuncte foloseste un singur vector de întregi "m", unde m[x] reprezintă numărul multimii care contine valoarea "x". Evolutia acestui vector în cazul unei colectii de 6 multimi (un graf cu 6 noduri), după operatiile determinate de citirea arcelor 1-3, 4-6, 2-5, 3-6, 2-3 , este ilustrată în secventa următoare:
initial 1 2 3 4 5 6
dupa 1-3 1 2 1 4 5 6
după 4-6 1 2 1 4 5 4
după 2-5 1 2 1 4 2 4
după 3-6 1 2 1 1 2 1
după 2-3 2 2 2 2 2 2
O altă implementare a unei colectii de multimi poate folosi un vector de pointeri la liste înlăntuite; fiecare listă este o multime si este identificată printr-un pointer.
|
