Diversitatea Textelor Utilizând Structuri de Tip Arbori Binari

1. Introducere

Obiectivul prezentului proiect este prezentarea unui algoritm de calcul al gradului de diversitate a textelor utilizând structuri de date de tip arbore binar, mai exact utilizând structuri de cautăre rapidă de tip arbore binar de căutare.

În realizarea obiectivului sunt utilizate o serie de funcţii de calcul a unor indicatori în urma parcurgerii arborilor binari de căutare, aceşti indicatori folosind la calculul ortogonalităţii textelor, care reprezintă gradul de diversitate ce se doreşte a fi calculat.

Algoritmii prezentaţi sunt implementaţi cu ajutorul limbajului de programare C++, sursa programului fiind inclusă în secţiunea Anexe a prezentului proiect.

2. Structura programului

Pentru a calcula gradul de diversitate, programul realizează mai întâi citirea a două texte din două fişiere text. Pentru fiecare din aceste fişiere programul citeşte linie cu linie, fiecare linie fiind împărţită ulterior în cuvinte, care la rândul lor vor fi încărcate în structurile de tip arbore binar de căutare.

Pentru a evidenţia ortogonalitatea textelor programul calculează două tipuri de indicatori, fiecare indicator luând valori în intervalul [0,1] unde extremele 1 şi 0 reprezintă:

- 1 dacă textele sunt complet diferite conform criteriului utilizat;

- 0 dacă textele sunt perfect identice conform criteriului utilizat.

Primul indicator defineşte ortogonalitatea textelor utilizând lungimele în cuvinte ale acestora. Dacă L1 este lungimea în cuvinte a primului text si L2 lungimea în cuvinte a celui de-al doilea text, indicatorul are următoarea formulă de calcul: I=1-min(L1,L2)/max(L1,L2) ([IVAN 09]).

Cel de-al doilea indicator calculează ortogonalitatea textelor pornind de la elementele structurale ale acestora. Considerând nrcv numărul de cuvinte al mulţimii reuniunii vocabularelor celor două texte şi nrcf numărul de cuvinte comune celor două texte care au aceeaşi frecvenţă de apariţie, indicatorul va avea urmatoarea formulă de calcul: I=1-nrcf/nrcv ([IVAN 09]).

Odată calculaţi, indicatorii de ortogonalitate sunt afişaţi pe ecran cu explicaţiile de rigoare, ei fiind salvaţi şi într-un fişier extern pentru o eventuală folosire de către alte programe e rezultatelor obţinute. Fişierul de ieşire a datelor conţine pe o linie cei doi indicatori desparţiţi printr-un spaţiu.

3. Structurile de date utilizate intern

Programul prezentat utilizează o structură de tip articol denumită „cuvant” cu următoarele două câmpuri:

- c: de tip şir de caractere în care se va memora un cuvânt al textului;

- nr: de tip întreg care va reţine frecvenţa de apariţie în text a cuvântului.

struct cuvant{

char *c;

int nr;

};

În programul de faţă s-au folosit şi structuri de date de tip masiv unidimensional de caractere. În strucura „cuvant” prezentată anterior, câmpul „c” este de tipul masiv unidimensional de caractere şi va fi alocat dinamic. Algoritmul utilizează de asemenea un masiv unidimensional de caractere alocat static în memorie pentru a citi o linie a unui fişier text, fiind evidenţiat modul de extragere a cuvintelor din şir utilizând funcţia „strtok” din biblioteca „string.h”. Cuvintele astfel obşinute sunt încărcate apoi în structura de tip arbore binar de cătare:

char lin[250];

fis.getline(lin,250);

char *cuv;

cuv=strtok(lin," ,.-");

while (cuv != NULL)

{

creare(rad1,cuv);

cuv=strtok(NULL, " ,.-");

}

Principala structură de date folosită este cea de tip arbore binar de căutare denumită generic arbB şi care prezintă următoarele câmpuri:

- cuv: de tipul cuvânt definit anterior. Reprezintă informaţia utilă cu care va lucra arborele;

- st,dr: de tipul pointer către arbore binar, reprezentând subarborii stâng şi drept ai unui nod din arbore.

struct arbB{

cuvant info;

arbB *st, *dr;

};

Operaţiile elementare asupra arborilor binari utilizate în program sunt:

- crearea unui nou nod de tip arbore binar

- inserarea unei noi informaţii utile în arbore, respectând structura de tip arbore binar de căutare

- căutarea unei informaţii utile în arborele binar

- calculul numărului de noduri al unui arbore binar.

4. Descrierea implementării operaţiilor de bază

Pentru crearea unui nou nod de tip arbore binar este utilizată o funcţie care primeşte ca parametrii cuvântul ce urmează a fi inserat în arbore şi subarborii stâng, respectiv drept ai nodului de inserat. Funcţia crează un nou nod de tip arbore binar, copiază cuvântul de inserat în câmpul „c” al informaţiei utile „info”, iniţializează frecvenţa acestuia(câmpul „nr” al informaţiei utile „info”) cu 1, precum şi câmpurile „st” şi „dr” cu valorile primite ca parametrii. Funcţia va returna pointer către noul nod alocat.

arbB* c_nod(char *cuv, arbB* stang, arbB* drept){

arbB* temp = (arbB*)malloc(sizeof(arbB));

temp->info.c=new char[strlen(cuv)+1];