DBI007 probraná látka

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Přehled látky probrané na přednášce Organizace a zpracování dat I.

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 $ 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:

Adresár
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.

Adresár
pozice p i r
0
1 1 2 3
2
...
j
...
Primární soubor
pozice hodnota
0
1 4
2 5
3 6
4
5
6

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 $ 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.

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.

Adresár
pozice p i r
0
1
2
3 1 $ \heartsuit $ 1
4
5
6 0 $ \heartsuit $ 1
Primární soubor
pozice hodnota
0 6
1 3
2
3
4
5

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

Adresár
pozice p i r
0
1
2
3 1 $ \heartsuit $ 1
4
5
6 2 0 2
Primární soubor
pozice hodnota
0
1 3
2 6
3 13
4
5

Jak funguje vyhledávání

  • 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

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í

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í

...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)

  • 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

  1. i=1
  2. 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.
  3. 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.
  4. 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ší).
  5. 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

Viď bod 0-2 z pridávania :-)


Stromy

Citováno z „http://wiki.matfyz.cz/index.php?title=DBI007_probraná_látka&oldid=18964“