Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17

Táto stránka sa týka školského roku 2016/17. Od školského roku 2017/18 predmet vyučuje Jakub Kováč, stránku predmetu je https://kubokovac.eu/ds/

Poradie tém, poznámky, prezentácie:

Obsah

Úvodné informácie

Základné údaje

Rozvrh

Vyučujúca

Ciele predmetu

Literatúra

Prezentácia

Cieľom prezentácie je precvičiť si prácu s odbornou literatúrou a oboznámiť sa s ďalšími výsledkami v oblasti dátových štruktúr. Každý študent si zvolí a podrobne naštuduje jeden odborný článok (z odbornej konferencie alebo časopisu) z tejto oblasti a ten odprezentuje spolužiakom na prednáške koncom semestra. Každý študent si musí zvoliť iný článok.

Termíny

Rozvrh prezentácií

Rady k prezentácii

Typická osnova prezentácie (podľa potreby ju však možete meniť):

Typy vhodných článkov

Príklady článkov

Zopár ukážok článkov, nemusíte si však vybrať z tohto zoznamu.

Kirsch A, Mitzenmacher M. Less hashing, same performance: building a better bloom filter. ESA 2006 (pp. 456-467). Springer [11]

[25] Tento článok je už obsadený.


Články navrhnuté študentami

Rady k hľadaniu článkov

Väčšina databáz má linky na elektronické verzie článkov u vydavateľa. Tam väčšinou uvidíte aspoň voľne prístupný abstrakt, ktorý vám pomôže rozhodnúť, či Vás článok zaujíma. Pre niektoré zdroje (napr. ACM, IEEE a ďalšie) je plný text článku prístupný z fakultnej siete. Z domu sa môžete prihlásiť cez univerzitný proxy (v prehliadači nastavte automatický konfiguračný skript http://www.uniba.sk/proxy.pac ). Celý text článku (pdf) sa v mnohých prípadoch dá nájsť na webe (napr. na webstránke autora). V najhoršom prípade, ak neviete zohnať článok, ktorý k projektu alebo prezentácii veľmi potrebujete, kontaktujte ma e-mailom a môžem sa pokúsiť ho zohnať.

Poznámky

Táto stránka obsahuje pokyny k písaniu poznámok na wiki.

Kontá

Ak chcete poznámkovať, vypýtajte si e-mailom konto od vyučujúcej. Vaše užívateľské meno bude užívateľské meno z AIS (napr. mrkvicka37). Ako email budete mať nastavenú univerzitnú adresu (napr. mrkvicka37@uniba.sk). Heslo si môžete dať poslať na túto adresu a potom si ho zmeniť podľa vlastného výberu.

Bodovanie

Štýl poznámok

Autorské práva

Ako editovať

Pravidlá

Stupnica

A: 90 a viac, B:80...89, C: 70...79, D: 60...69, E: 50...59, FX: menej ako 50%

Známkovanie

Sú tri alternatívy známkovacej stupnice:

Alternatíva A Alternatíva B Alternatíva C
  • Aktivita počas semestra: 10%
  • Domáca úloha: 15%
  • Prezentácia článku: 15%
  • Skúška: 60%
  • Aktivita počas semestra: 10%
  • Domáca úloha: 15%
  • Prezentácia článku: 15%
  • Projekt: 60%
  • Aktivita počas semestra: 10%
  • Prezentácia článku: 15%
  • Projekt: 75%

Základná možnosť A je ukončená skúškou. Namiesto skúšky, alebo prípadne aj domácej úlohy môžete v alternatívach B a C robiť projekt, ale iba ak do 31.3. oznámite e-mailom vyučujúcej, o ktorú alternatívu máte záujem a dohodnete sa na predbežnej téme projektu. Projekty sú väčšinou časovo náročnejšie ako príprava na skúšku, takže ich odporúčam len študentom, ktorý majú o nejakú tému súvisiacu s predmetom veľký záujem. Projekty sa budú odovzdávať cez skúškové obdobie (termín bude určený neskôr). Po oznámkovaní projektu sa bude konať ešte krátka ústna skúška týkajúca sa projektu, ktorá môže ovplyvniť vašu výslednú známku.

Body zo semestra môžete priebežne sledovať v systéme Moodle, cez ktorý budete aj odovzdávať domácu úlohu.

Skúška

Na termín sa hláste/odhlasujte v AISe najneskôr 14:00 deň pred skúškou. Na skúške dostanete zadania niekoľkých príkladov, ktoré môžete priebežne odovzdávať, v prípade väčšej chyby môžete ešte svoje riešenie prerobiť, ale za chybné odovzdanie stratíte zopár bodov. Skúška bude obsahovať nasledujúce typy príkladov:

Na skúške je povolený ťahák v rozsahu 2 listov formátu A4 s ľubovoľným obsahom.

Aktivita

Počas semestra študent môže získať body za aktivitu nasledovnými spôsobmi:

Celkovo je možné za aktivitu získať najviac 20%, t.j. najviac 10% bonus ku známke.

Body za aktivitu môžete získavať aj počas skúškového opravovaním a dopĺňaním poznámok, avšak najneskôr 12 hodín pred začiatkom vášho termínu skúšky. Ak vám po skončení ústnej skúšky bude chýbať najviac 5 bodov do lepšej známky, môžete sa pred zápisom známky dohodnúť s vyučujúcou, že v priebehu nasledujúcich 7 dní sa pokúsite chýbajúce body týmto spôsobom získať.

Prezentácia

Cieľom prezentácie je precvičiť si prácu s odbornou literatúrou a oboznámiť sa s ďalšími výsledkami v oblasti vyhľadávania v texte. Každý študent si zvolí a podrobne naštuduje jeden odborný článok (z odbornej konferencie alebo časopisu) z tejto oblasti a ten odprezentuje spolužiakom na prednáške koncom semestra. Každý študent si musí zvoliť iný článok.

Viac informácií na zvláštnej stránke.

Opisovanie

Sylabus na skúšku

Na tejto stránke je sylabus na skúšku v školskom roku 2016/17 (neobsahuje úplný obsah všetkých prednášok)

Úsporné dátové štruktúry

Amortizovaná zložitosť

Prioritné rady

RMQ a LCA

Scapegoat stromy, splay stromy a link-cut stromy

Vyhľadávanie kľúčových slov

Sufixové stromy a polia

Burrowsova–Wheelerova transformácia

Vyhľadávanie vzorky v texte

Hešovanie

Štruktúry pre externú pamäť

Štruktúry pre celočíselné kľúče

Streaming model

Perzistentné dátové štruktúry

Geometrické dátové štruktúry

Nepovinná DÚ

Nepovinné domáce úlohy môžete použiť na získanie bodov za aktivitu aj mimo prednášky. V rámci semestra bude ešte aspoň jedna ďalšia séria úloh, ale nespoliehajte sa na to, že ich ešte bude veľa. Celkovo máte v hodnotení za body za aktivitu 10 bodov a môžete získať ďalších 10 ako bonus.

Maximálny počet bodov je orientačný, ak sa úloha ukáže náročnejšia, než sa očakávalo, môže byť zvýšený. O úlohách sa môžete rozprávať, ale nepíšte si z takýchto rozhovorov poznámky a napíšte text vlastnými slovami. Pri väčšine úloh preferujem vaše vlastné riešenie, ale ak riešenie nájdete v literatúre, uveďte zdroj a napíšte riešenie vlastnými slovami. Všetky odpovede zdôvodnite.


Séria 2, odovzdať najneskôr deň pred skúškou do 10:00

Nepovinnú domácu úlohu môžete odovzdať písomne v M163 (ak tam nie som, strčte papier pod dvere) alebo emailom v pdf formáte a môžete za ňu dostať body za aktivitu. Všetky odpovede stručne zdôvodnite.

Úloha 1 (2 body)

Uvažujme Morissov-Prattov algoritmus pre vzorku P dĺžky m, ktorý bežíme na veľmi dlhom texte T. Koľko najviac bude trvať spracovanie úseku dĺžky k niekde uprostred textu T ako funkcia parametrov m a k? Hodnota k môže byť menšia alebo väčšia ako m. Uveďte asymptotický horný aj dolný odhad, t.j. aj príklad, kde to bude trvať čo najdlhšie (príklad by mal fungovať pre všeobecné m a k, ale môžete si zvoliť T a P a aj ktorý úsek T dĺžky k uvažujete).

Úloha 2 (2 body)

Máme dané Bloom filtre pre množiny A a B, vytvorené s tou istou sadou hešovacích funkcií (a teda aj s tou istou veľkosťou tabuľky).

Úloha 3 (3 body)

Máme reťazce X a Y rovnakej dĺžky n, ktorých Hammingova vzdialenosť je 1.

Úloha 4 (? bodov, podľa náročnosti)

Máme reťazce X a Y rovnakej dĺžky n, ktorých Hammingova vzdialenosť je 1.

Séria 1, odovzdať do 14.3.

Úloha 1 (max 2 body)

V štruktúre RRR sme rozdelili reťazec na bloky dĺžky t2 a každému sme v komprimovanom poli B priradili kód, pričom bloky s veľmi málo alebo veľmi veľa jednotkami mali kratšie kódy ako bloky, v ktorých bol počet jednotiek a núl probližne rovnaký. Namiesto tohto spôsobu môžeme použiť nasledovný spôsob kompresie bitového reťazca. Pre každý z 2^{{t_{2}}} typov bloku spočítame počet výskytov, t.j. koľko blokov nášho reťazca má tento typ. Potom typy blokov zoradíme podľa počtu výskytov a pripradíme im kódy tak, že najčastejšie sa vyskytujúci typ bloku dostane ako kód prázdny reťazec, druhé dva najčastejšie sa vyskytujúce typy blokov dostanú kódy 0 a 1, ďalšie štyri typy dostanú kódy 00, 01, 10 a 11, ďalších 8 typov dostane kódy dĺžky 3 atď.

Popíšte ako k takto komprimovanému reťazcu zostavíme všetky ďalšie potrebné polia na to, aby sme mohli počítať rank v čase O(1). Veľkosť vašej štruktúry by mala byť m+o(n), kde n je dĺžka pôvodného binárneho reťazca a m dĺžka jeho komprimovanej verzie. Vaša štruktúra sa asi bude podobať na štruktúru RRR z prednášky, ale popíšte ju tak, aby text bol zrozumiteľný pre čitateľa, ktorý RRR štruktúru nepozná, pozná však štruktúru pre nekomprimovaný rank.

Úloha 2 (max 2 body)

Označme B1 komprimovaný reťazec z úlohy 1, t.j zreťazenie kódov pre jednotlivé bloky. Označme B2 komprimovaný reťazec z prednášky o dátovej štruktúre RRR, t.j. zreťazenie odtlačkov (signature) pre jednotlivé bloky. Nájdite príklad, kedy je B2 kratší ako B1 a naopak príklad, pre ktorý je B1 oveľa kratší ako B2.

Poznámka: B1 ani B2 neobsahujú dosť informácie, aby sa z nich samotných dal spätne rekonštruovať pôvodný binárny reťazec, lebo nepoužíme bezprefixový kód. Huffmanovo kódovanie je bezprefixový kód, lebo kód žiadneho znaku nie je prefixom kódu iného znaku.

Ak bonus za ďalšie body sa pokúste navrhnúť schému, v ktorej bude komprimovaný reťazec najviac taký dlhý ako B2, ale ktorá búde spĺňať to, žo okrem nej potrebujeme len \lg t_{2}+O(1) prídavnej informácie pre každý blok na to, aby sme vedeli spätne určiť pôvodný reťazec.

Úloha 3 (max 4 body)

V prednáške je uvedené bez dôkazu, že ak chceme počítať rank nad väčšou abecedou, môžeme namiesto wavelet tree použiť RRR štruktúru pre indikátorové bitové vektory jednotlivých znakov abecedy a že výsledná štruktúra bude mať veľkosť nH(T)+O(n)+o(\sigma n). Dokážte toto tvrdenie. V tejto úlohe ocením aj vami spísaný dôkaz naštudovaný z literatúry s uvedením zdroja. Ako počiatočný zdroj môžete použiť prehľadový článok Navarro, Mäkinen (2007) Compressed full-text indexes [29] (strana 30).

Úloha 4 (max 3 body)

Uvažujme verziu štruktúry vector, ktorá používa ako parametre tri reálne konštanty A,B,C>1. Ak pridávame prvok a v poli už nie je miesto, zväčšíme veľkosť poľa z s na A*s. Naopak, ak zmažeme prvok a počet prvkov klesne pod s/B, zmenšíme pole na s/C. V knihe Cormen, Leiserson, Rivest and Stein Introduction to Algorithms (kap. 17 v druhom vydaní) nájdete analýzu pre A=2, B=4 a C=2. Nájdite množinu hodnôt parametrov A,B,C, pre ktoré pridávanie aj uberanie prvkov funguje amortizovane v čase O(1).

Nemusíte charakterizovať všetky trojice parametrov, pre ktoré je amortizovaný čas konštantný, ale nájdite nejakú množinu trojíc, pre ktoré je to pravda. Ideálne každému parametru povolíte hodnoty z nejakého intervalu, ktorý môže byť ohraničený konštantami alebo funkciou iných parametrov. Zjavne napríklad musí platiť, že B>C.

Úsporné dátové štruktúry

Rank and select

Introduction to rank/select

Our goal is to represent a static set A\subseteq \{0\dots n-1\}, let m = |A|

Two natural representations: 

                                Array        Bit vector             
Memory in bits                  m log n         n       
Is x in A?                      O(log m)       O(1)         rank(x)>rank(x-1)                 
max. y in A s.t. y<=x           O(log m)       O(n)         select(rank(x))
i-th smallest element of A      O(1)           O(n)         select(i)
how many elements of A are <=x  O(log m)       O(n)         rank(x)

If m relatively large, e.g. m=\Omega (n/\log n), bit array uses less memory

To get rank in O(1)

To get select in O(1)

Rank

data structures:

rank(i):

Select

Wavelet tree: Rank over larger alphabets

Rank in compressed string: RRR

class of a block: number of 1s

rank(i):

Analysis of RRR:


Use in wavelet tree (see Navarro survey of wavelet trees):

Instead of wavelet tree, store indicator vector for each character from alphabet in RRR string

Binarny strom

  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
  1  1  1  1  1  0  1  0  0  1  1  0  0  0  0  0  0
  A  B  C  D  E  .  F  .  .  G  H  .  .  .  .  .  .

Lemma: Pre i-ty vnutorny vrchol (i-ta jednotka vo vektore, na pozicii select(i)) su jeho deti na poziciach 2i a 2i+1

Dosledok:

Ak chceme pouzit ako lexikograficky strom nad binarnou abecedou: potrebujeme zistit, ci vnut. vrchol zodpoveda slovu v mnozine

Catalanove cisla

Ekvivalentne problemy:

Chceme dokazat, ze odpoved je Catalanovo cislo <tex>C_n = {2n\choose n}/(n+1)</tex> (C_0 = 1, C_1=1, C_2 = 2, C_3 = 5,...)

Connection to FM index (to be covered later in the course)

Back to FM index

Opakovanie, amortizovaná zložitosť

tieto poznamky este neexistuju, mozne je ich vytvorit preklopenim informacie z prezentacie

Prioritné rady

Nizsie su pracovne poznamky, ktore doplnuju informaciu z prezentacie, je mozne ich rozsirit, doplnit samotnou prezentaciou

Introduction to priority queues

Review

Operations        Bin. heap    Fib. heap 
                  worst case    amortized
MakeHeap()            O(1)       O(1)   
Insert(H, x)       O(log n)      O(1)   
Minimum(H)            O(1)       O(1)   
ExtractMin(H)      O(log n)    O(log n)   
Union(H1, H2)         O(n)       O(1)   
DecreaseKey(H, x, k)
                    O(log n)     O(1)   
Delete(H, x)        O(log n)   O(log n)

Applications of priority queues



Soft heap

Fibonacci heaps

Motivation

Structure of a Fibonacci heap

Example of Fibonacci heap

Operations analysis

Lazy operations with O(1) amortized time:

MakeHeap()

Insert(H,x)

Minimum(H)

Union(H1, H2)

Other operations

ExtractMin(H)

Analysis: 

1 ExtractMin (H) {
2   z = H.min
3   Add each child of z to root list of H ( update its parent )
4   Remove z from root list of H
5   Consolidate (H)
6   return z
7 }

1 Consolidate (H) {
2   create array A [ 0..Deg(H.n ) ], initialize with null
3   for (each node x in the root listt of H) {
4     while (A[x.degree] != null ) {
5       y = A[x.degree] ;
6       A[x.degree] = null ;
7       x = HeapLink (H, x, y)
8     }
9   A[x.degree] = x
10  }
11  traverse A, create root list of H, find H.min
12 }

1 HeapLink (H, x, y) {
2   if (x.key > y.key) exchange x and y
3   remove y from root list of H
4   make y a child of x, update x.degree
5   y.mark = false ;
6   return x
7 }

DecreaseKey(H,x,k)

Analysis: 

DecreaseKey (H, x, k) {
2   x.key = k
3   y = x.parent
4   if (y != NULL && x.key < y.key) {
5     Cut(H, x, y)
6     CascadingCut (H, y)
7   }
8   update H.min
9 }

1 CascadingCut (H, y) {
2   z = y.parent
3   if (z != null) {
4     if (y.mark==false) y.mark = true
5     else {
6       Cut(H, y, z) ;
7       CascadingCut(H, z)
8     }
9   }
10 }

Delete(H,x)

Maximum degree Deg(n)

Proof of Lemma 3:

Proof of Lemma 4:

Proof of Corollary:

Exercise

Sources

Pairing heaps

ExtractMin

O(log n) amortized time can be proved by a similar analysis as in splay trees (not covered in the course)


Meldable heaps (not covered in the course)

Random meldable heap

Union(H1, H2) {
    if (H1 == null) return H2;
    if (H2 == null) return H1;
    if (H1.key > H2.key) { exchange H1 and H2 }
    // now we know H1.key <= H2.key
    if (rand() % 2==1) {
       H1.left = merge(H1.left, H2);
    } else {
       H1.right = merge(H1.right, H2);
    }
    return H1;
}

Analysis:

Lemma: The expected length of a random walk in a any binary tree with n nodes is at most lg(n+1).

Corollary: The expected time of Union is O(log n)

A different proof of the Lemma via entropy

Leftist heaps

Union(H1, H2) {
    if (H1 == null) return H2;
    if (H2 == null) return H1;
    if (H1.key > H2.key) { exchange H1 and H2 }
    // now we know H1.key <= H2.key
    HN = Union(H1.right, H2);
    if(H1.left != null && HN.left.s <= H1.s) {
       return new node(H1.data, H1.left, HN) 
    } else {
       return new node(H1.data, HN, H1.left) 
    }
}

Lemma: (a) subtree with root x has at least 2^{s(x)}-1 nodes (b) if a subtree with root x has n nodes, s(x)<=lg(n+1) (c) the length of the path from node x using only edges to right child is s(x)

Corollary: Union takes O(log n) time

Skew Heaps

Union(H1, H2) {
    if (H1 == null) return H2;
    if (H2 == null) return H1;
    if (H1.key > H2.key) { exchange H1 and H2 }
    // now we know H1.root.key <= H2.root.key
    HN = Union(H1.right, H2);
    return new node(H1.data, HN, H1.left) 
}

Recall: Heavy-light decomposition from Link/cut trees

Observations:

Potential function: the number of heavy right edges (right edge is an edge to a right child)

Amortized analysis of union:

All light edges we encounter in the algorithm are on the rightmost path in one of the two heaps, which means there are at most 2 lg n of them (lg n in each heap). This gives us amortized cost at most 4 lg n.

Amortizované vyhľadávacie stromy a link-cut stromy

Predbežná verzia poznámok, nebojte sa upravovať: pripojiť informácie z prezentácie, pridať viac vysvetľujúceho textu a pod.

Scapegoat trees

Introduction

Insert

Lemma 1: If a node x in a tree with n nodes is in depth greater than \log _{{3/2}}n, then on the path from x to the root there is a node u and it parent p such that D(u)/D(p) > 2/3

Proof:

Amortized analysis of insert

Delete

Uses of scapegoat trees

Scapegoat trees are useful if nodes of tree hold auxiliary information which is hard to rebuild after rotation

Sources

Splay trees

Splay1.png Splay2.png Splay3.png

Intuition and examples

Amortized analysis of splaying

Lemma1 (proof later): consider one step of splaying x (1 or 2 rotations)

Lemma2: Amortized cost of splaying x to the root in a tree with n nodes is O(log n)

Theorem: Amortized cost of insert, search and delete in splay tree is O(log n)

Proof of Lemma 1:

Adaptability of splay trees

If some element is accessed frequently, it tends to be located near the root, making access time shorter

Weighted potential function

Weighted version of Lemma 2:

Static optimality theorem:

O\left(m+\sum _{{x}}q(x)\log {\frac {m}{q(x)}}\right)=O(m+mH),

Proof:

Note:

Sequential access theorem:

Collection of splay trees

Image now a collection of splay trees. The following operations can be done in O(log n) amortized time (each operation gets pointer to a node)

Sources

Link-cut trees

Union/find

Maintains a collection of disjoint sets, supports operations

Can be used to maintain connected components if we add edges to the graph, also useful in Kruskal's algorithm for minimum spanning tree

Implementation

Exercise: implement as a collection of splay trees

Link/cut trees

Maintains a collection of disjoint rooted trees on n nodes

O(log n) amortized per operation. We will show O(log^2) amortized time. Can be also modified to support these operations in worst-case O(log n) time, add more operations e.g. with weights in nodes.

Similar as union-find, but adds cut plus we cannot rearrange trees as needed as in union-find

Simpler version for paths

Simpler version for paths (imagine them as going upwards):

Can be done by splay trees

Back to link/cut trees

Link1.png

expose(v) 

 
y = cutPathBellow(v);
if(y!=NULL) findPathHead(y).dashed = v;
while(true) {
  x = findPathHead(v);
  w = x.dashed;
  if(w == NULL) break;
  x.dashed = NULL;
  q = splitPathBelow(w);
  if(q != NULL) {
    findPathHead(q).dashed = w;
  }
  linkPaths(w, x); v = x;
}

Heavy-light decomposition

edge from v to its parent p is called heavy if D(v)> D(p)/2, otherwise it is light. Observations:

Proof that there are O(log n) splices amortized per expose

consider a single splice, there are two cases:

Amortized cost of the whole expose is therefore 2L+1, where L is the number of new light solid edges created in expose

some operations change the tree and create new heavy dashed edges from light dashed edges

Fully dynamic connectivity

Applications

Sources

RMQ a LCA

Predbežná verzia poznámok, nebojte sa upravovať: pripojiť informácie z prezentácie, pridať viac vysvetľujúceho textu a pod.

Introduction to LCA, RMQ

Lca1.png


Task: preprocess tree T in O(n), answer lca(u,v) in O(1)

History: Harel and Tarjan 1984, Schieber a Vishkin 1988 (Gusfield book), Bender and Farach-Colton 2000 (this lecture)

LCA via RMQ

Range minimum query RMQ

i    0  1  2  3  4  5  6  7  8  9 10 11 12
A[i] 0  1  2  1  2  3  2  1  0  1  0  1  0
--------------------------------------------
k=1  0  1  3  3  4  6  7  8  0 10 10 12  -
k=2  0  1  3  3  7  8  8  8  8 10  -  -  -
k=3  0  8  8  8  8  8  -  -  -  -  -  -  -

+-1RMQ

+-1RMQ predpracovanie:

spolu O(n)

RMQ(i,j):

spolu O(1)

LCA predspracovanie:

LCA(u,v) 2 pristupy do pola R, +-1RMQ na poli D, pristup do pola V O(1)

RMQ via LCA

Lca2.png

Segment trees

Decompose query interval [x,y) to a set of disjoint tree intervals (canonical decomposition):

Tree of recursive calls:

Segment trees can also support dynamic case where we add operation set(i,x) which sets A[i] = x

Print small

void small(i,j,x) {
  if(j<i) return;
  k = rmq(i,j);
  if(a[k]<=x) { 
    print k;
    small(i,k-1);
    small(k+1,j);
  }
}

Vyhľadávanie kľúčových slov

Predbežná verzia poznámok, nebojte sa upravovať: pripojiť informácie z prezentácie, pridať viac vysvetľujúceho textu a pod.

Keyword search, inverted index, tries, set intersection

Full-text keyword search (Plnotextove vyhladavanie klucovych slov)

Ema: 0,2
Emu: 1
ma: 0,1,2
Mama: 1,2
mamu: 0
sa: 2

Trie-bintree.png

Štruktúra query preprocessing
Utriedené pole O(m\log n+p) O(mN\log N)
Vyhľ. strom O(m\log n+p) O(mN\log n)
Hašovanie - najh. prípad O(mn+p) O(mNn)
Hašovanie - priem. prípad O(m+p) O(mN)
Lex. strom O(m\log \sigma +p) O(mN\log \sigma ) (neskor)

Tries (lexikograficke stromy)


Trie1.png Trie2.png 

node = root;
for(i=0; i<m; i++) {
   node = node->child[w[i]];
   if(! node) return empty_list;
}
return node->list;

Time: O(m) 

node = root;
for(i=0; i<m; i++) {
   if(! node->child[w[i]]) {
     node->child[w[i]] = new node;
   }
   node = node->child[w[i]];
}
node->list.add(d)

Time: O(m) (assuming list addition in O(1))

Deletion of a word: what needs to be done (when do we delete a vertex), possibly a problem with deletion from list of occurrences

Summary and implementations

Multiple keywords

i=0; j=0;
while(i<m && j<n) {
  if(a[i]==b[j]) { print a[i]; i++; j++; }
  else if(a[i]<b[j]) { i++; } 
  else { j++; }
}

What if m<<n? 

for(i=0; i<m; i++) {
   k = binary_search(b, a[i])
   if(a[i]==b[k]) print k;
}

j = 0; // current position in b
for(i=0; i<m; i++) {
    find smallest k>=j s.t. b[k]>=a[i]; (*)
    if(k==n) { break; }
    j=k;
    if(a[i]==b[j]) {
      print a[i]; 
      j++;
    }
}

How to do (*): 

step = 1; k = j; k'=k;
while(k<n && b[k]<a[i]) {
   k'=k; k=j+step; step*=2; 
}
binary search in b[k'..min(n,k)];

Sufixové stromy a polia

Predbežná verzia poznámok, nebojte sa upravovať: pripojiť informácie z prezentácie, pridať viac vysvetľujúceho textu a pod. Cast prednasok tu nie je zastupena, ale najdete ich v poznamkach z predmetu Vyhľadávanie v texte - vid linka na spodku stranky.

Intro to suffix trees

Suffix-trie.png Suffix-comp.png Suffix-suffix.png Suffix-gentrie.png Suffix-gensuffix.png


Maximal pairs

Summary

Further extensions: find only repeats which are not parts of other repeats, finding all maximal pairs,...

LCA v sufixovych stromoch

Aproximate string matching

Counting documents

Suffix-count.png

Proof:

Printing documents

Muthukrishnan, S. "Efficient algorithms for document retrieval problems." SODA 2002. Strany 657-666.

Searching in suffix arrays

Algorithm 1

//find max i such that T[SA[i]..n] < X 
L = 0; R = n;
while(L < R){
  k = (L + R + 1) / 2;
  h = 0;
  while(T[SA[k] + h] == X[h]) h++;
  if(T[SA[k]+h] < X[h]) L = k;
  else R = k - 1;
}
return L;

Algorithm 2

Keep invariant:

S array-alg2.png 

//find max i such that T[SA[i]..n-1]< X 
L = 0; R = n;
XL = lcp(X, T[SA[L]..n]); XR = lcp(X, T[SA[R]..n]);
while(R - L > 1){
  k = (L + R + 1) / 2;
  h = min(XL, XR);
  while(T[SA[k]+h]==X[h]) { h++; }
  if(T[SA[k]+h]<X[h]){ L = k; XL = h; }
  else {  R = k; XR = h; }
}
sequential search in SA[L..R];

Faster on some inputs, but still O(m log n) - see exercise

Algorithm 3

Assume XL>=XR in a given iteration (XL<XR is solved similarly. Consider three cases:

S array-alg3-a.png S array-alg3-b.png S array-alg3-c.png

Running time

Which LCP values are needed?

S array1.png

Literatúra

Burrowsova–Wheelerova transformácia

Trochu ina reverzna transformacia:

FM index

Priklad 

hladam .ama
l(epsilon) = 0
r(epsilon) = 23
l(a) = C(a) + rank[a,L(epsilon)-1] = 6 + rank[a,-1] = 6
r(a) = C(a) + rank[a,R(epsilon)]-1 = 6 + rank[a,23]-1 = 11
l(ma) = C(m) + rank[m,L(a)-1] = 14 + rank[m,5] = 14  
r(ma) = C(m) + rank[m,R(a)]-1 = 14 + rank[m,11] - 1 = 19  
l(ama) = C(a) + ra(L(ma)-1) = 6 + ra(13) = 10
r(ama) = C(a) + ra(R(ma))-1 = 6 + ra(19) - 1 = 10
l(.ama) = C(.) + r.(L(ama)-1) = 1 + r.(9) =  1
r(.ama) = C(.) + r.(R(ama))-1 = 1 + r.(10)-1 =  0

Analyza

Vyhľadávanie vzorky v texte

Literatúra

Theoretical results for edit distance computation

Exact algorithm O(mn) or improved by logarithimc factor.

Approximation algorithm: For strings of length n and every fixed ε > 0 compute (\log n)^{{O(1/\epsilon )}} approximation in n^{{1+\epsilon }} time

Source: Andoni A, Krauthgamer R, Onak K. Polylogarithmic approximation for edit distance and the asymmetric query complexity. FOCS2010, pp. 377-386 [41]

Conditional lower bound: If the edit distance can be computed in O(n^{{2-\delta }}) for some constant δ > 0, then the satisfiability of conjunctive normal form (CNF) formulas with N variables and M clauses can be solved in time M^{{O(1)}}2^{{(1-\epsilon )N}} for a constant \epsilon >0, which would violate Strong Exponential Time Hypothesis (SETH).

Source: Backurs A, Indyk P. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). STOC2015, pp. 51-58 [42]

Hešovanie

Introduction to hashing

Totally random hash function

Universal family of hash functions

Note

Example of a universal family:

Proof of universality

Hashing with chaining, using universal family of h.f.

References

Perfect hashing

Static case

Dynamic perfect hashing

References

Bloom Filter (Bloom 1970)

Algorithm

Bounding the error If hash functions are totally random and independent, the probability of error is approximately (1-exp(-nk/m))^k

Use of Bloom filters

Proof of the bound

However, Pr(B[i]=1) are not independent

Exercise Let us assume that we have separate Bloom filters for sets A and B with the same set k hash functions. How can we create Bloom filters for union and intersection? Will the result be different from filter created directly for the union or for the intersection?

Theory

Counting Bloom filters

References

Locality Sensitive Hashing

Approximate near neighbour (r,c)-NN

Example for Hamming distance in binary strings of length d


Minimum hashing

Notes

Sources

Dátové štruktúry pre externú pamäť

External memory model, I/O model

Introduction

Example: scanning through n elements (e.g. to compute their sum): Theta(ceiling of n/B) memory transfers

B-trees

Search:

Insert:

Sorting

external mergesort

Summary

Cache oblivious model

Introduction

Paging

Back to cache-oblivious model

Static cache-oblivious search trees

van Emde Boas order

          1
     2           3
  4     7    10    13
5  6  8  9 11 12 14 15

Analysis

Dynamic cache oblivious trees

uses "ordered file maintenance"

simpler version of data structure

search

update

analysis of update

improvement of update

Sources

Streaming model

Definition

Majority element

Boyer–Moore majority vote algorithm 1981

This algorithm can be generalized to find all elements with frequency greater than M/k by keeping k-1 counters (Misra and Gries 1982)

Count-Min sketch

Heavy hitters

Sources

Dátové štruktúry pre celočíselné kľúče

Introduction

Models of computations

Word RAM model

Other models

Predecessor problem

van Emde Boas data structure

Integer-clusters.png


Hierarchical coordinates

Integer-hierarchy.png

VEB recursive structure

Integer-veb.png

Operations

Successor

Successor(V, x = <c,i>) {
    if (x < V.min) return V.min;
    if (i < V.cluster[c].max) {
        return <c, Successor(V.cluster[c], i)>;
    } else {
        c' = Successor(V.summary, c);
        return <c', V.cluster[c'].min>;
    }
}

Insert

Insert(V, x = <c,i>) {
    if (V.min == None) {
        V.min = V.max = x;
        return;
    }
    if (x < V.min) swap(x, V.min);
    if (x > V.max) V.max = x;
    if (V.cluster[c].min == None) {
        Insert(V.summary, c);
    }
    Insert(V.cluster[c], i);
}

Delete

Delete(V, x = <c,i>) {
    if (x == V.min) {
        c = V.summary.min
        if (c == None) {
            V.min = None;
            return;
        }
        V.min = <c, i = V.cluster[c].min>;
    }
    Delete(V.cluster[c], i);
    if (V.cluster[c].min == None) {
        Delete(V.summary, c);
    }
    if (V.summary.min == None) {
        V.max = V.min;
    } else {
        c' = V.summary.max;
        V.max = <c', V.cluster[c'].max>;
    }
}

Simple tree view

Integer-treeview.png

Predecessor, successor

Updates


Sources

Perzistentné dátové štruktúry

Sources

Persistent data structures

Pointer machine

General transformation with node copying

First, let us prove that the algorithm for the update will terminate

Notes for the amortized analysis: