Organizace a zpracování dat I

Letos mě stihla povinnost absolvovat předmět Organizace a zpracování dat I. Pro nás, co nemůžeme nebo nechceme chodit na přednášky, jsou k dispozici skripta, ta mají ovšem několik nevýhod. Nevýhodou zdaleka nejvážnější je, že srozumitelnost textu pro běžného matfyzáka se blíží oné větě z práce jakéhosi filozofa "Individuální participanti sociální komunity přijímají informace prostřednictvím symbolických vizuálních kanálů.", kterou proslavil Feynman ve své knize To snad nemyslíte vážně a po vynaložení netriviálního úsilí ji nakonec dešifroval coby sdělení "Lidé čtou."

Abych se tedy vůbec mohla něco naučit, musela jsem skripta nejprve rozluštit a přepsat to potřebné do pohádkové podoby, které jsem schopná rozumět. Pokud "vznešené řeči" rozumíte stejně jako já a čeká vás totéž, třeba bude můj textík k užitku i vám. Vypadá to takhle docela jednoduše... tak mi prosím držte palce, ať to tak vypadá i u zkoušky.

Co zde chybí: počítání doby přístupu na disk (z důvodů, které raději nebudu upřesňovat, dodělávat nebudu), indexové, indexsekvenční a podobné soubory (to je jednoduché, když si člověk pamatuje, co přesně je co - to jde snadno vyluštit ze skript), spirálová paměť (ještě to nechápu, možná časem dodělám), deskriptory stránek a Grayovy kódy (celkem jednoduché, časem možná dodělám).

Cormackovo hashování

Mějme adresář délky d, soubor s daty, hashovací funkci H(k, d) (rozhazuje do d přihrádek, k je klíč záznamu) a sadu hashovacích funkcí Hi(k, r) (rozhazuje do r přihrádek, k je klíč záznamu).

Každý řádek adresáře obsahuje položku p - ukazatel někam do souboru s daty, i - pořadové číslo hashovací funkce Hi a r - počet záznamů uložených v datovém souboru, náležících tomuto řádku adresáře.

Datový soubor obsahuje prostor pro záznamy, každý záznam je identifikován jednoznačným klíčem k. Máme funkci f(x), která nám umí vrátit pointer do datového souboru ukazující na souvislé volné místo o délce x záznamů.

Insert probíhá následovně: Spočítáme hodnotu funkce H pro klíč nového záznamu, dostaneme výsledek j. Pokud na řádku j v adresáři není dosud žádný odkaz do datového souboru, nastavíme mu p na ukazatel vrácený funkcí f(1), i na 0 a r na 1.

V opačném případě se podíváme na hodnotu r z našeho řádku v adresáři. Projdeme všech r záznamů od ukazatele p a zkontrolujeme, že už tam přidávaný záznam není. Pokud ne, pořídíme ukazatel pf do datového souboru pomocí f(r+1) a hledáme m takové, že Hi vrátí různé hodnoty pro čísla 1..r+1 (Tux nám pomáhej.) Potom přehashujeme všech r položek (na první ukazuje p) pomocí Hi(k, r+1) na nové místo, původní místo označíme jako prázdné, v adresáři nastavíme p=pf, i=m, r++.

Find je triviální - spočítáme H hledaného klíče, v adresáři najdeme i, spočítáme Hi, podíváme se na p+Hi.

O tom, jak moc to nechodí pro malé klíče a libovolnou funkci, kterou jsem schopná po zkušenostech ze skript a přednášky vymyslet, si můžete zapřemýšlet nad mým prográmkem. Nebo nějakou máte?

Lajka (Larson a Kajla)

Máme dvě řady funkcí - hashovací funkce Hi (rozhazuje do d přihrádek) a funkce generující signatury záznamů Si. Dále máme d stránek, ke každé stránce si pamatujeme její pořadové číslo a signaturu. Počáteční signaturou každé stránky je maximální možná signatura, nějaké číslo tvaru 2^k - 1 pro k kladné.

V každé stránce si pamatujeme hodnotu klíče a jeho signaturu. Insert provádíme následovně: Počítáme hodnotu funkce Hi tak dlouho, dokud nám nevrátí stránku, jejíž signatura je menší než signatura našeho klíče spočítaná funkcí Si. Pokud je v této stránce volné místo, vyhráli jsme.

Pokud místo došlo, nebohou stránku rozdělíme - snížíme její signaturu na hodnotu právě neúspěšně vkládané stránky a pokračuji ve vkládání. Zároveň zcela znovu vložím všechny stránky, které měly stejnou signaturu jako neúspěšně vložený záznam - intuice praví (skripta zřejmě ne) že kdybychom si mimo signatury a klíče pamatovali ještě generaci hashovací funkce i, mohli bychom vkládat rovnou od i+1. hashovací funkce a ušetřit si práci.

Fagin (rozšiřitelné hashování)

Máme klíč k a hashovací funkci H, o které věříme, že nám bude data rozdělovat rovnoměrně. Dále máme adresář o hloubce d (d je nejvýše rovno logaritmu z maxima H). Adresář obsahuje na jednom řádku položku d bitů a položku s ukazatelem na stránku s daty. Hledáme-li nějaká data, spočítáme H z klíče, podíváme se na posledních d bitů výsledku, najdeme odpovídající řádek v adresáři, pokud data někde jsou, ukazuje na patřičnou stránku ukazatel na tomto řádku adresáře.

Přidáváme-li data, může se nám stát, že na některé stránce dojde místo. V takovém případě zdvojnásobíme délku adresáře (hloubka je d+1) přidáním dalšího bitu. Stránku, kde došlo k přetečení, rozdělíme do dvou novách stránek a aktualizujeme ukazatele v adresáři. Ostatní ukazatele při zvětšování adresáře jen zkopírujeme a necháme je ukazovat po dvou (čtyřech...) na stejnou stránku, dokud nepřeteče, dělíme až potom: podíváme se, v kolika kopiích je stránka v adresáři a podle toho určíme, podle kterého bitu budeme stránku štěpit.

Litwin (lineární hashování)

Máme hashovací funkci H vracející hodnoty o d bitech, nějaké stránky a oblast přetečení. Na začátku ukládáme všechna data do jedné stránky. Když provedeme L operací vkládání, rozdělíme tuto stránku na dvě a hodnoty v ní rozházíme podle posledního bitu hashovací funkce. Po dalších L operacích znovu dělíme stránku 0 a hodnoty nyní rozhazujeme podle posledních dvou bitů... po každých L krocích analogicky dělíme určenou stránku, určena je tímto způsobem: 0, 0,1, 0, 1, 2... (čímž nám, to je náhodička, stránky přibývají v pořadí dělení ?00,?1, ?10...).

Při vkládání máme stránku jednoznačně určenou, pokud se do ní záznam nevejde, použijeme oblast přetečení. Při každém dělení stránek oblast přetečení projdeme a přepočítáme. Pokud se nám nevejde do paměti, buď nám Tux milostiv...

Skupinové štěpení stránek

Na začátku máme n stránek rozdělených do skupin o g stránkách, oblast přetečení, hashovací funkci H (hashuje do n přihrádek) a sadu hashovacích funkcí Hi (ty nám hashují postupně do g+1, g+2... přihrádek). Po L vkládáních přidáme jednu stránku do první skupiny o g stránkách a obsah přerozdělíme do g+1 stránek funkcí H0. Po dalších L vkládáních uděláme totéž s druhou skupinou.

Když jsme rozšířili všechny skupiny, zpermutujeme čísla stránek tak, aby byly zase rozděleny do skupin g prvcích (je-li toho třeba, přidáme nějaké prázdné stránky).

Hledání (vkládání) simuluje kompletní postup štěpení: Nejprve spočítá x = H, pak zjistí, kolikrát se skupina, do které patří x. stránka, rozšiřovala - nechť je to k. Pak pro 1..k vždy spočítáme y = Hi, pokud je i < k, spočítáme nové číslo y. stránky po permutaci, z něj Hi+1... až do alelujá.

B strom

• kořen má nejméně dva potomky, není-li listem
• každý další uzel (mimo listu) má aspoň m/2 (zaokrouhleno nahoru) a nejvýš m potomků a o 1 méně datových záznamů
• všechny větve jsou stejně dlouhé
• vkládá se vždy do listu

Neredundantní verze: data jsou i ve vnitřních uzlech.

Redundantní verze: ve vnitřních uzlech dělí podstromy maximální hodnota v levém (minimální v pravém) podstromu.

B* strom

Obě verze, pokud vkládáme do plného listu, než začneme dělit, podíváme se ještě na levého a pravého souseda. Pokud má některý z nich volno, uložíme data tam (a samozřejmě změníme dělící hodnotu).

O co jde: chceme zachovávat invariant, že každá stránka je zaplněna aspoň ze dvou třetin. (Případně tří čtvrtin.)

Odkládané štěpení

Pokud chceme zlepšit zaplnění stránek, můžeme si pro skupinu stránek pořídit společnou oblast přetečení a štěpit, až když i oblast přetečení přeteče.

Prefixové stromy

Mofifikace redundantních B stromů, jako oddělovač používáme jen nejkratší možný prefix.

B+ stromy

Abychom usnadnili procházení redundantních B stromů, máme mezi listy zleva doprava linked list. Přidávání nové hodnoty, jakož i mazání je levné, protože při dělení použijeme původní stránku, pro pointer tedy nemusíme do jiného podstromu.

Proměnná délka záznamu

Namísto počtu záznamů operujeme v jednom uzlu s počtem znaků, které můžeme uložit. Řadíme lexikograficky, pokud při vkládání přetečeme, štěpíme podle záznamu obsahující prostřední znak. (Tím budeme mít pravděpodobně delší slova výš. Pokud vkládáme slovo delší než polovina kapacity stránky, možná budeme dělit i na tři stránky. Po vkládání se nám kupodivu může strom i snížit: Stačí, když se separátorem stane kratší slovo než před vkládáním a je potřeba slévat záznamy.)