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.
|
