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