davidbalan05/Suffix-tree
Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|
Repository files navigation
Algoritmul incepe prin initializarea arborelui, folosind functia aferenta,
arbore ce este definit prin strutctura de date "Trie" si are drept campuri
radacina(root) si numarul de frunze, ce se calculeaza pe masura ce sunt adauga-
te noduri noi in arbore. Radacina este de tip "TrieNode", o strutctura ce are
drept campuri descendentii sai directi, numarul lor, nivelul pe care se afla
in arbore si data-ul, respectiv stringul pe care il retine.
Se citesc apoi din linia de comanda argumentele aferente, printre care
fisierele de input si output, si se rezolva cerinta ceruta:
- In cazul cerintei 1, se citeste numarul de cuvinte si stringurile din
fisierul de input, se creaza sufixele ce trebuie adaugate in arbore si se
insereaza pe rand. In final se afiseaza data-urile salvate in fiecare nod
printr-o parcurgere in latime a arborelui, folosind o functie ce implementeaza
BFS.
- In cazul cerintei 2, se mai citeste din linia de comanda argumentul K,
argument ce indica dimensiunea sufixelor pe care algoritmul trebuie sa le
numere. Se insereaza in arbore exact ca la prima cerinta, iar apoi se apeleaza
o functie ce calculeaza numarul maxim de copii ai unui nod din arbore si
numarul de K-sufixe, folosindu-se, de asemenea, o parcurgere in latime pentru
a interoga fiecare nod.
- In cazul cerintei 3, se procedeaza ca la prima cerinta, insa mai sunt
citite din fisierul de output numarul si sufixele pe care algoritmul trebuie
sa le caute. Se foloseste in aceasta privinta functia "search_suffix", care
intoarce valoarea 0 daca sufixul nu exista in arbore, si 1 daca acesta exista.
- In cazul cerintei 4, se procedeaza, si aici, exact ca la prima cerinta,
doar ca se realizeaza in plus compresarea arborelui folosindu-se functia
"compress_trie". Aceasta functie, atunci cand gaseste un nod care are un
singur copil, ii sterge copilul din arbore, isi actualizeaza stringul, face
legaturile intre nodul curent si copii nodului sters si actualizeaza nivelele
noilor sai descendenti. Acest proces este executat cat timp este realizabil si
apar schimbari in arbore.