DBI007 probraná látka
Přehled látky probrané na přednášce Organizace a zpracování dat I.
Schémata organizace souborů[editovat | editovat zdroj]
- 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[editovat | editovat zdroj]
Perfektní hešovaní (Cormack)[editovat | editovat zdroj]
Cormakovo hašování je založeno na existenci primární hašovací funkce $ h(k) $, a celé třídy sekundárních hašovacích funkcí $ h_{i}(k,r) $. funkce $ h(k) $ 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ých metod hašování.
Primární soubor si jde představit jako pole pevné velikosti. Adresář vypadá následujícím způsobem:
pozice | p | i | r |
---|---|---|---|
1 | |||
2 | |||
... | |||
j | |||
... |
Význam položek
p je odkaz do primárního souboru
i značí kolikátá hašovací funkce byla použita a
r označje počet položek v primárním souboru, na které se odkazuje p
pozice je index položky v adresáři.
Příklad 1.[editovat | editovat zdroj]
|
|
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í[editovat | editovat zdroj]
Pokud přidáváme položku s klíčem k, nejprve spočteme $ h(k) $. Pokud je Adresář[$ h(k) $].r == 0, provedeme následující akce
- Adresář[$ h(k) $].r = 1
- Adresář[$ h(k) $].i = $ \heartsuit $ (Pozor, ne 0)!
- V primárním souboru na první volnou pozici s adresou pnew umístíme ukládanou položku
- Adresář[$ h(k) $].p = pnew
Pokud je Adresář[$ h(k) $].r != 0, provedeme následující akce
- Adresář[$ h(k) $].r = Adresář[$ h(k) $].r +1
- Najdeme nejmenší i takové, že $ h_{i}(k,r) $ 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ář[$ h(k) $].p
- Adresář[$ h(k) $].i = i
- V primárním souboru na první volnou a dostatečně velkou pozici s adresou pnew umístíme ukládanou položku a všechny položky z bloku Adresář[$ h(k) $].p v pořadí, které určí klíč sekundární hašovací funce
$ h_{i}(k, r) $
- Adresář[$ h(k) $].p = pnew
Příklad 2.[editovat | editovat zdroj]
Zvolne velikost adresáře M=7.
Potom $ h(k) $ navrhneme ve tvaru
$ h(k) $ $ h(k)= k \quad mod \quad M $;
$ h_{i}(k, r) = (k \quad << \quad i) \quad mod \quad r $, pro r případ r jemocninou 2;
$ h_{i}(k, r) = (k \quad xor \quad i) \quad mod \quad r $, jinak.
($ << i $ značí bitový posun vlevo o i bitů)
Postupně budeme přidávat do prázného souboru položky 6, 3, 13. $ h(6) = 6, h(3) = 3 $, přidání je tedy triviální a struktury mají po přidání prvních dvou tento tvar.
|
|
Potom se pokusíme přidat 13. $ h(13) = 6 $, 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 $ h_{0} $, protože $ h_{0}(6,2) = 0 $, a $ h_{0}(13,2) = 1 $. Takže po vložení 13 budou struktuy vypadat následujícím způsobem
|
|
Jak funguje vyhledávání[editovat | editovat zdroj]
- spočteme $ h(k) $.
- podle Adresář[$ h(k) $].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ář[$ h(k) $].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
$ h_{i}(k,r)=(k \quad mod \quad (2i + 100r +1))\quad mod \quad r $
Predpokladá se, že $ k << 2i + 100r +1 $.
Pseudokód[editovat | editovat zdroj]
Zadefinujeme si ješte nějaké datové položky:
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[];
Vyhledávání[editovat | editovat zdroj]
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;} } }
Vkládání[editovat | editovat zdroj]
...je trošku zložitejšie, c-like algoritmus není kompletní, ale je názorný...
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 } }
Perfektné hashovanie - Larson & Kalja (beta)[editovat | editovat zdroj]
- 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í hi, 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í si generuje signatúry kľúča k .
Predstava:
Stránka:
+------+ | sep | +------+-----+ | data sig | (PS: sig-signatúry záznamov si ukladať nemusíme, pomocou si si ich dopočítame...) | ... | +------------+
Na začiatku sú všetky stránky prázdne...
1 2 3 M +------+ +------+ +------+ +------+ | 1111 | | 1111 | | 1111 | | 1111 | +------+-----+ +------+-----+ +------+-----+ +------+-----+ | | | | | | ... | | | | | | | | | | +------------+ +------------+ +------------+ +------------+
Vkladanie[editovat | editovat zdroj]
- i=1
- Keď chceme pridať záznam (k), pomocou hi(k) zistíme umiestnenie stránky. Potom záznam zahashujeme pomocou si, čím získame jeho signatúru.
- Porovnáme povolenie/separátor stránky so signatúrou záznamu - ak je sep<=sig, pak nastavíme 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 nejmenšího po největší).
- 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, h1=4, s1=(001)b)...
4 +------+ | 111 | +------+-----+ | data sig | | 33 001 | | | +------------+
Pridanie ďalších dvoch (11, h1=4, s1=(101)b; 15, h1=4, s1=(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" h1/s1, ale niektorých ďalších funkcií...
Vyhľadávanie[editovat | editovat zdroj]
Viď bod 0-2 z pridávania :-)