{{predmet|Organizace a zpracování dat I|Michal Žemlička|DBI007}}
= Přednáška – stručný přehled =
== Schémata organizace souborů ==
* '''hromada''' – nehomogenní soubor (nemá pevný typ záznamu s primitivními typy)
** pravěk
* '''sekvenční soubor''' – homogenní soubor uspořádaný dle nějakého klíče
** + sekvenčí přístup; - ''(minus)'' přístup k záznamům
* '''index-sekvenční soubor''' – sekvenční soubor + (víceúrovňový) index na blocích, příp. oblast přetečení
** + přístup k záznamům i sekvenční přístup
* '''indexovaný soubor''' ''(také invertovaný soubor)'' – primární soubor + více indexů na záznamech (klasický index, bitmapy, ..)
** + přístup k záznamům, k množině záznamů; - sekvenční přístup
* '''soubor s přímým přístupem''' – typicky ''hašování''
** + přístup k záznamům; - přístup k množině i sekvenční přístup
** perfektní (prosté) hašování
*** Cormack – 2-stupňové hašování přes pomocný adresář
*** Larson & Kalja – 2-stupňové hašování + signatury a separátory stránek
** dynamické hašování
*** s pomocným adresářem (Fagin)
*** bez adresáře – skupinové štěpení
** výcerozměrná mřížka (pro OLAP?)
== Popis jednotlivých algoritmov ==
=== Perfektní hešovaní (Cormack) ===
Cormakovo hašování je založeno na existenci primární hašovací funkce <math>h(k)</math>, a celé třídy sekundárních hašovacích funkcí <math>h_{i}(k,r)</math>. funkce <math>h(k)</math> musí mít [[obor hodnot]] roven velikosti adresáře.
Položky jsou ukládány do primárního souboru (pevné velikosti), způsobem, který bude popsán za pomoci adresáře (pevné velikosti). Protože je i primární soubor i adresář pevné velikosti, řadí se Cormacovo hašování do tzv [[statické metody hasšování|statických metod hašování]].
Primární soubor si jde představit jako pole pevné velikosti. Adresář vypadá následujícím způsobem:
{| border="1" cellpadding="2" cellspacing="2"
|+Adresár
! pozice !! p !! i !! r
|-
! 1
| || ||
|-
! 2
| || ||
|-
! ...
| || ||
|-
! j
| || ||
|-
! ...
| || ||
|}
'''Význam položek''' <br>
'''p''' je odkaz do primárního souboru <br>
'''i''' značí kolikátá hašovací funkce byla použita a <br>
'''r''' označje počet položek v primárním souboru, na které se odkazuje '''p''' <br>
'''pozice''' je index položky v adresáři.
===Příklad 1.===
<table border="0" cellpadding="20">
<tr><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Adresár
! pozice !! p !! i !! r
|-
! 1
| 1||2 ||3
|-
! 2
| || ||
|-
! ...
| || ||
|-
! j
| || ||
|-
! ...
| || ||
|}
</td><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Primární soubor
! pozice !! hodnota
|-
! 0
| 4
|-
! 1
| 5
|-
! 2
| 6
|-
! 3
|
|-
! 4
|
|-
! 5
|
|}
</tr>
</table>
Tato situace nám popisuje, že v primárním souboru jsou uloženy 3 položky, všechny v jednom bloku(vede na ně jen jeden pointer '''p'''), které jdou od sebe rozlišit hašovací funkcí číslo 2 ('''i''' == 2) a první z těchto položek je v primárním souboru na pozici 1 ('''p''' == 1).
=== Jak funguje vkládání ===
Pokud přidáváme položku s klíčem '''k''', nejprve spočteme <math>h(k)</math>. Pokud je Adresář[<math>h(k)</math>].r == 0, provedeme následující akce
* Adresář[<math>h(k)</math>].r = 1
* Adresář[<math>h(k)</math>].i = <math>\heartsuit</math> (Pozor, ne 0)!
* V primárním souboru na první volnou pozici s adresou p<sub>new</sub> umístíme ukládanou položku
* Adresář[<math>h(k)</math>].p = p<sub>new</sub>
Pokud je Adresář[<math>h(k)</math>].r != 0, provedeme následující akce
* Adresář[<math>h(k)</math>].r = Adresář[<math>h(k)</math>].r +1
* Najdeme nejmenší i takové, že <math>h_{i}(k,r)</math> je růzdné pro nově vkládanou položku a pro všechny položky v datovém bloku příslušném pointeru Adresář[<math>h(k)</math>].p
* Adresář[<math>h(k)</math>].i = i
* V primárním souboru na první volnou a dostatečně velkou pozici s adresou p<sub>new</sub> umístíme ukládanou položku a všechny položky z bloku Adresář[<math>h(k)</math>].p v pořadí, které určí klíč sekundární hašovací funce
<math>h_{i}(k, r)</math>
* Adresář[<math>h(k)</math>].p = p<sub>new</sub>
===Příklad 2.===
Zvolne velikost adresáře M=7.
Potom <math>h(k)</math> navrhneme ve tvaru <br>
<math>h(k)</math> <math>h(k)= k \quad mod \quad M</math>;<br>
<math>h_{i}(k, r) = (k << i) \quad mod \quad r </math>, pro r případ '''r''' jemocninou 2; <br>
<math>h_{i}(k, r) = (k \quad xor i) \quad mod \quad r </math>, jinak.<br>
(<math> << i</math> značí [[bitový posun]] vlevo o i bitů)
Postupně budeme přidávat do prázného souboru položky 6, 3, 13.
<math>h(6) = 6, h(3) = 3</math>, přidání je tedy triviální a struktury mají po přidání prvních dvou tento tvar.
<table border="0" cellpadding="20">
<tr><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Adresár
! pozice !! p !! i !! r
|-
! 0
| || ||
|-
! 1
| || ||
|-
! 2
| || ||
|-
! 3
| 1 ||<math>\heartsuit</math> || 1
|-
! 4
| || ||
|-
! 5
| || ||
|-
! 6
| 0 ||<math>\heartsuit</math> || 1
|}
</td><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Primární soubor
! pozice !! hodnota
|-
! 0
| 6
|-
! 1
| 3
|-
! 2
|
|-
! 3
|
|-
! 4
|
|-
! 5
|
|}
</tr>
</table>
Potom se pokusíme přidat 13. <math>h(13) = 6</math>, což už je obsazeno.
Updatneme Adresář[6].r na 2, a najdeme čím je to obsazeno (položkou s klíčem 6), a hledáme první sekundární funkci, která tyto klíče rozliší. To je <math>h_{0}</math>, protože <math>h_{0}(6,2) = 0</math>, a <math>h_{0}(13,2) = 1</math>.
Takže po vložení 13 budou struktuy vypadat následujícím způsobem
<table border="0" cellpadding="20">
<tr><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Adresár
! pozice !! p !! i !! r
|-
! 0
| || ||
|-
! 1
| || ||
|-
! 2
| || ||
|-
! 3
| 1 ||<math>\heartsuit</math> || 1
|-
! 4
| || ||
|-
! 5
| || ||
|-
! 6
| 2 ||0 || 2
|}
</td><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Primární soubor
! pozice !! hodnota
|-
! 0
|
|-
! 1
| 3
|-
! 2
| 6
|-
! 3
| 13
|-
! 4
|
|-
! 5
|
|}
</tr>
</table>
=== Jak funguje vyhledávání ===
* spočteme <math>h(k)</math>.
* podle Adresář[<math>h(k)</math>].r se buď podíváme na přímo příslušné místo do primárního souboru, nebo spočteme příslušnou (Adresář[<math>h(k)</math>].i) sekundární hašovací funkci, najdeme příslušný blok a v něm příslušnou položku.
Další často používanou sekundární funkcí je funkce
<math>h_{i}(k,r)=(k \quad mod \quad (2i + 100r +1))\quad mod \quad r</math>
Predpokladá se, že <math> k << 2i + 100r +1</math>.
=== Pseudokód ===
Zadefinujeme si ješte nějaké datové položky:
<code>
typedef head_1 {int p; int i; int r;}
typedef body_1 {int k; int v;}
head_1 *head=new head_1[s];
body_1 *body=new body_1[];
</code>
==== Vyhledávání ====
<code>
int h(int k, int s) {}
int hi(int i, int k, int r) {}
bool find(int k, int *v) {
j=h(k, s);
if (head[j].r==0) return false;
else {
body *p=body[head[j].p+hi(head[j].i, k, head[j].r)];
if (p->k!=k) return false;
else {*v=p->v; return true;}
}
}
</code>
==== Vkládání ====
...je trošku zložitejšie, c-like algoritmus není kompletní, ale je názorný...
<code>
int free(int size) {/*nájde voľné miesto v primárnom súbore s veľkosťou size*/}
bool insert(body_1 d) {
j=h(d.k, s);
if (head[j].r==0) { //pre daný kľúč ešte nemáme alokovaný blok
int p=free(1);
body[p].k=d;
head[j].p=&body[p]; head[j].i=0; head[j].r=1;
} else {
Ak už je hodnota d.k v množine head[j].p - head[j].p+head[j].r, vráť false
Nájdi voľné miesto pre (head[j].r+1) prvkov
Nájdi i také, aby hashovacia funkcia hi vrátila pre každý z prvkov (pôvodný blok+d) rôznu adresu
Premiestni prvky zo starého umiestnenia na nové, zapíš nový prvok
Oprav adresár
}
}
</code>
=== Perfektné hashovanie - Larson & Kalja (beta) ===
* otvorené adresovanie s dvojitým hašhovaním a jedným prístupom
* používa tabuľku pomocných informácií, nazvime ju sep (povolenie), ktorá je podstatne menšia ako u Cormacka. Vyžaduje M*d bitov, kde M je počet stránok adresového priestoru, a d je veľkost pomocnej dátovej štruktúry (reťazec 0 a 1) - separátor/povolenie. Ďalej sa používa M hashovacích funkcií h<sub>i</sub>, ktoré pre každý kľúč vracajú postupne postupnosť adries tých stránok, kde je možné hľadať (vložiť) daný záznam; dalších M hashovacích funkcií s<sub>i</sub> generuje signatúry kľúča k .
Predstava:
Stránka:
+------+
| sep |
+------+-----+
| data sig | (PS: sig-signatúry záznamov si ukladať nemusíme, pomocou s<sub>i</sub> si ich dopočítame...)
| ... |
+------------+
Na začiatku sú všetky stránky prázdne...
1 2 3 M
+------+ +------+ +------+ +------+
| 1111 | | 1111 | | 1111 | | 1111 |
+------+-----+ +------+-----+ +------+-----+ +------+-----+
| | | | | | ... | |
| | | | | | | |
+------------+ +------------+ +------------+ +------------+
==== Vkladanie ====
# i=1
# Keď chceme pridať záznam (k), pomocou h<sub>i</sub>(k) zistíme umiestnenie stránky. Potom záznam zahashujeme pomocou s<sub>i</sub>, čím získame jeho signatúru.
# Porovnáme povolenie/separátor stránky so signatúrou záznamu - ak je sep<=sig, i=i+1 a opakujeme od predchadzajuceho bodu.
# Inak sme našli správnu stránku - pokúsime sa pridať do nej náš záznam. Záznamy v stránke usporiadame podľa signatúry (od zostupne - od najvačšej).
# V prípade, že je záznamov v stránke priveľa (viac ako je veľkosť stránky): vyberieme (vymažeme zo stránky) záznamy s najvačšou signatúrou (teda všetky s rovnakou signatúrou z "vrchu" stránky), túto signatúru nastavíme ako separátor stránky, a vybrané záznamy znovu zahashujeme...
Pridanie jedného prvku (33, h<sub>1</sub>=4, s<sub>1</sub>=(001)b)...
4
+------+
| 111 |
+------+-----+
| data sig |
| 33 001 |
| |
+------------+
Pridanie ďalších dvoch (11, h<sub>1</sub>=4, s<sub>1</sub>=(101)b; 15, h<sub>1</sub>=4, s<sub>1</sub>=(001)b)...
4
+------+
| 111 |
+------+-----+
| data sig |
| 11 101 | <= stránka je plná, toto budeme musieť "vyhodiť"
| 33 001 |
| 15 001 |
+------------+
|
V
4
+------+
| 101 |
+------+-----+
| data sig |
| 33 001 |
| 15 001 |
+------------+
Hodnotu 11 budeme musieť zahashovat znovu, ale tentokrát už nie "pomocou" h<sub>1</sub>/s<sub>1</sub>, ale niektorých ďalších funkcií...
==== Vyhľadávanie ====
Viď bod 0-2 z pridávania :-)
== Stromy ==
* [[wikipedia:B-Tree|B-stromy]]
= Cvičení =
Triedenie veľkých objemov dát - [http://en.wikipedia.org/wiki/Heapsort heapsort] (vytváranie v lineárnom čase), ďalej optimalizácia jeho práce s pamäťou, a nakoniec [http://en.wikipedia.org/wiki/Mergesort zlievanie] (=mergesort)
= Odkazy =
* [http://kocour.ms.mff.cuni.cz/~zemlicka/vyuka/DBI007/ Žemličkove stránky k predmetu]
* [http://kocour.ms.mff.cuni.cz/~zemlicka/cz.html Žemličkove stránky]
