Arbori digitali
SD 2019/2020
Cont, inut
Arbori digitali
Compactarea lant,urilor
Structuri Patricia
Arbori de sufixe
FII, UAIC Curs 12 SD 2019/2020 2 / 29
Arbori digitali (Tries)
I Information retrieval
I O structura de date pentru a lucra cu s, iruri de caractere carebeneficiaza de proprietat, ile structurale ale acestora
I Spat, iul de memorie necesar reprezentarii unui dict, ionar este redus:radacina comuna este reprezentata o singura data
I Economie de memorie cand exista multe prefixe comune
FII, UAIC Curs 12 SD 2019/2020 3 / 29
Arbori digitali
I Structura de date care se bazeaza pe reprezentarea digitala aelementelor
I Un arbore cu radacina ordonat k-ar, unde k este numarul de cifre(litere din alfabet)
I Se presupune ca elementele sunt reprezentate prin secvent,e de cifre(litere) de aceeas, i lungime m (|U| = mk)
FII, UAIC Curs 12 SD 2019/2020 4 / 29
Arbori digitali - Structura de date
I O colect, ie de noduri, fiecare nod avand k fii
I Presupunem alfabetul {0, . . . , k − 1}; elementele din S sunt chei, iarnodurile de pe frontiera memoreaza informat, iile asociate acestor chei
FII, UAIC Curs 12 SD 2019/2020 5 / 29
Arbori digitali
Un arbore digital care memoreaza o colect, ie de cuvinte S , |S | = n dintr-unalfabet de marime k , are urmatoarele proprietat, i:
I orice nod intern are cel mult k fii
I arborele are n noduri externe
I ınalt, imea arborelui este egala cu lungimea celui mai mare cuvant din S
FII, UAIC Curs 12 SD 2019/2020 6 / 29
Arbori digitali - Cautarea
I Cauta un element a ın structura t: parcurge drumul descris desecvent,a a[0], . . . a[m − 1]
Function cauta(a,m, t)begin
i ← 0p ← twhile (p 6= NULL AND i < m) do
p ← p → succ[a[i ]]i ← i + 1
return pend
I Complexitatea timp pentru cazul cel mai nefavorabil: O(m)
FII, UAIC Curs 12 SD 2019/2020 7 / 29
Arbori digitali - Inserarea
I Inserarea unui cuvant x ın structura t: simuleaza parcurgereadrumului descris de secvent,a x [0], . . . x [m − 1]; pentru componentelepentru care nu exista noduri ın t, adauga un nod nou
Figura: Inserarea cheii 110
FII, UAIC Curs 12 SD 2019/2020 8 / 29
Arbori digitali - S, tergerea
I Un element x care trebuie eliminat este ımpart, it ın:I un prefix comunI un sufix care nu mai apart, ine niciunui element
I Se parcurge drumul descris de x s, i se memoreaza ıntr-o stivaI Se parcurge acest drum ınapoi s, i daca pentru un nod tot, i succesorii
sunt nil , atunci se elimina nodul
Figura: Eliminarea cheii 102
FII, UAIC Curs 12 SD 2019/2020 9 / 29
Cont, inut
Arbori digitali
Compactarea lant,urilor
Structuri Patricia
Arbori de sufixe
FII, UAIC Curs 12 SD 2019/2020 10 / 29
Compactarea lant,urilor
I O structura rara memoreaza put, ine chei; exista multe lant,uri dinnoduri intermediare cu un succesor
I Eliminarea acestor lant,uri ar duce la ımbunatat, irea complexitat, iispat, iu s, i timp; pastram doar nodurile intermediare cu cel put, in 2succesori
FII, UAIC Curs 12 SD 2019/2020 11 / 29
Compactarea lant,urilor
I In structura compactata se memoreaza:I ın nodurile interne pozit, ia de la care difera cheile cu un prefix comunI ın nodurile de pe frontiera cheia.
FII, UAIC Curs 12 SD 2019/2020 12 / 29
Compactarea lant,urilor
Un arbore digital compactat care memoreaza o colect, ie de cuvinte S ,|S | = n dintr-un alfabet de marime k are urmatoarele proprietat, i:
I fiecare nod intern are cel put, in 2 fii s, i cel mult k fii
I arborele are n noduri externe
I numarul de noduri al arborelui este O(n)
FII, UAIC Curs 12 SD 2019/2020 13 / 29
Compactarea lant,urilor - Operat, ii
I Cautarea: similara cazului necompactat, cu deosebirea ca ın fiecarenod este testata valoarea de pe pozit, ia memorata de nod, iar cand seajunge pe un nod de pe frontiera se testeaza cheia
I Inserarea presupune o operat, ie de cautare a cheii urmata de inserareaunui nou nod care sa distinga dupa pozit, ia pe care difera ultimul,respectiv noul nod
Figura: Inserarea cheii 0111
FII, UAIC Curs 12 SD 2019/2020 14 / 29
Compactarea lant,urilor - Operat, ii
I Stergerea: ıntr-o maniera asemanatoare cazului necompactat;I se cauta nodul care memoreaza cheia s, i se memoreaza drumul ıntr-o
stiva;I se s, terge nodul cu cheia respectivaI se parcurge drumul ınapoi, eliminandu-se nodurile cu un singur succesor
Figura: S, tergerea cheii 1011
FII, UAIC Curs 12 SD 2019/2020 15 / 29
Cont, inut
Arbori digitali
Compactarea lant,urilor
Structuri Patricia
Arbori de sufixe
FII, UAIC Curs 12 SD 2019/2020 16 / 29
Structuri Patricia
I Practical Algorithm to Retrieve Information Coded in Alphanumeric
I Un arbore digital binar este un arbore digital peste alfabetul {0, 1}.
I Numarul nodurilor de pe frontiera este cu 1 mai mare decat numarulnodurilor interne.
I Daca mai adaugam un nod intern, putem memora cheile ın nodurileinterne. Nodul adaugat va fi radacina s, i va avea un singur fiu(stanga). Pozit, ia din radacina va fi -1.
FII, UAIC Curs 12 SD 2019/2020 17 / 29
Structuri Patricia - Exemplu
FII, UAIC Curs 12 SD 2019/2020 18 / 29
Structuri Patricia - Operat, ii
I Cautarea - se poate termina cand pozit, ia curenta este mai micadecat ultima pozit, ie testata
I Inserarea: se cauta cheia ın structura, se identifica prima pozit, ie j pecare x s, i cheia difera;
Figura: Inserarea cheii 1100
FII, UAIC Curs 12 SD 2019/2020 19 / 29
Structuri Patricia - Operat, ii
I S, tergerea - exemplu
Figura: S, tergerea cheii 0111
Teorema:Presupunem ca se creeaza o structura Patricia pornind de la o structuravida prin n inserari de chei generate aleator. Atunci operat, ia de cautarenecesita O(log n) comparat, ii ın medie.
FII, UAIC Curs 12 SD 2019/2020 20 / 29
Arbori digitali - Aplicat, ii
I Determina toate cheile care ıncep cu un prefix dat (funct, iaautocomplete)
I Determina cea mai lunga cheie dintr-o tabela de simboluri care esteprefix al unui s, ir de caractere (exemplu: pentru a trimite pachete,alege adresa IP care este cel mai lung prefix)
I Determina toate cuvintele care corespund unei secvent,e de numere
I Cautarea ın baze de date, ın ret,ele P2P, ın fisiere XML
I Biologie computat, ionala
FII, UAIC Curs 12 SD 2019/2020 21 / 29
Burst Tries
Burstsort
I complexitatea timp pentru inserare
I DFS (inordine)
FII, UAIC Curs 12 SD 2019/2020 22 / 29
Cont, inut
Arbori digitali
Compactarea lant,urilor
Structuri Patricia
Arbori de sufixe
FII, UAIC Curs 12 SD 2019/2020 23 / 29
Arbori de sufixe
Un arbore de sufixe pentru un sir de caractere s este un arbore digitalcompactat al sufixelor lui s.
Exemplu: s = abab; multimea de sufixe: {$, b$, ab$, bab$, abab$}.
FII, UAIC Curs 12 SD 2019/2020 24 / 29
Constructia unui arbore de sufixe
Adauga cel mai mare sufix:
Adauga sufixul bab$:
Adauga sufixul ab$:
Adauga sufixul b$:
FII, UAIC Curs 12 SD 2019/2020 25 / 29
Constructia unui arbore de sufixe
Adauga sufixul $:
Eticheteaza nodurile frunza (cu indexul sufixului corespunzator):
Complexitate timp: O(n2). Algoritmul lui Ukkonen: O(n).FII, UAIC Curs 12 SD 2019/2020 26 / 29
Utilizare: string matching
Verifica daca un subsir de caractere (pattern) P(|P| = m) apare intr-un sirT (|T | = n).
I construieste un arbore de sufixe pentru T (O(n))
I traverseaza arborele conform subsirului P
I fiecare frunza din subarborele identificat corespunde unei aparitii (kaparitii)
Complexitate: O(n + k).
FII, UAIC Curs 12 SD 2019/2020 27 / 29
Utilizare: cel mai lung subsir comun
Un arbore generalizat de sufixe pentru o multime de siruri S este unarbore digital compactat al sufixelor s ∈ S .
Exemplu: s1 = abab, s2 = aab; {$, b$, ab$, bab$, abab$},{#, b#, ab#, aab#}.
FII, UAIC Curs 12 SD 2019/2020 28 / 29
Utilizare: cel mai lung subsir comun
Exemplu: s1 = abab, s2 = aab; {$, b$, ab$, bab$, abab$},{#, b#, ab#, aab#}.
Orice nod care are $ si # in subarborele sau corespunde unui subsir comunpentru s1 si s2. Cel mai lung subsir comun: nodul care satisfaceproprietatea si care are cel mai lung subsir.
FII, UAIC Curs 12 SD 2019/2020 29 / 29