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

Prostorové databáze

r^d-stromy

Quad-tree

R-stromy

o textu

Následující text si klade za cíl ilustrovat principy struktury R stromů a algoritmy, které používá, tak aby čtenáři umožnil snadný start do problematiky a umožnil mu vytvořit si první představu. Neměl by být vaší jedinou informací, ideální je doplnit ho nějakou odbornější literaturou (skripta), která obsahuje rigorózní definice a přesný popis algoritmů - je potřeba abstraktní "představu" doplnit přesnými informacemi - a navíc poskytne mnohé ilustrace v podobě obrázků a příkladů.

intro

R používají princip hierarchického pokrývání prostoru obdélníky (kostkami, n-rozměrnými..).: při popisu struktury se hodí zadefinovat dva pojmy:

<ul> <li>minimální ohraničující obdélník - pro objekt či množinu objektů je to nejmenší obdélníkový (kvádrový) objekt, který ho/je zcela obsahuje

<li>mrtvá plocha - uvnitř obdélníku popsaného výše je část plochy (objemu) zaplněna objekty a část prázdná. obsah prázdné části se nazývá mrtvá plocha. je snadné si uvědomit, že mrtvá plocha vystihuje kvalitu aproximace objektu (množiny objektů) ohraničujícím obdélníkem. U R stromů se setkáme s tím, že v některých fázích budeme usilovat o minimalizaci této plochy. </ul>

struktura stromu

přibližme si strukturu stromu: <ul>

<li>kořen stromu odpovídá obdélníku (kostce), obsahujícímu všechny objekty, pro které jsme strukturu vytvořili (je to minimální ohraničující kostka množiny všech objektů..) <li>synové kořene jsou menší obdélníky uvnitř prostoru vymezeného kořenem, které přesněji ohraničují nějaké (disjunktní) podmnožiny objektů - opět jsou to MOO těchto podmnožin objektů. dohromady obsahují zas všechny objekty. kořen obsahuje ukazatele na své syny..

<li>potomci synů zas zjemňují strukturu atd. -> obecněji řečeno, vnitřní uzly stromu odpovídají odbdélníku v prostoru a obsahují ukazatele na menší obdélníky, které leží uvnitř něj a zjemňují dělení prostoru. <li>listy stromů pak obsahují ukazatele na původní objekty, nebo na nějaké pomocné struktury jim odpovídající (třeba na minimální obal. obd. jednotlivých objektů)

<li>pro strukturu stromu je určující minimální a maximální počet potomků uzlu </ul>

abychom pochopili, k čemu se tohle může hodit, uvažme jednoduchý příklad: objekty v R-stromu jsou vesmírné lodě, a my chceme efektivně řešit dotaz, zda nějaký laserový paprsek některou z nich zasáhne:

<ul> <li>sestrojíme si MOO (mimim. obal. obd.) pro každou loď

<li>sestavíme nad těmito kostičkami R-strom (kořen obsahuje kostku obsahující všechny lodě, ta ukazuje na několik (dle mezí) kostek, z nichž každá obaluje nějaou menší podmnožinu lodí (podmnožiny vždy disjunktní, kostky se mohou "nedopatřením" přkrývat. listy budou malé kostky, které budou obalovat malé množiny kostiček, odpovídajících jednotlivým lodím, na které budou ukazovat <li>pokud teď dostaneme paprsek, zkusíme, zda protíná kostku odpovídající kořenu - pokud ano, zjemníme kritérium a podíváme se na potomky kořene

<li>pro každého z nich se opět podíváme, zda-li paprsek protíná jemu odpovídající kostku - pokud ne, tuto větev výpočtu ukončíme, pokud ano, rekurzivně postoupíme na jeho syny... <li>takto nám buď všechny cesty skončí, a my víme, že paprsek se k žádné lodi nepřiblíží, nebo se nakonec propracujeme k listové úrovni a k nějakým konkrétním obalovým kostkám reprezenrujícím lodě. jen pro ty má pak cenu počítat konkrétní průnik jejich povrchu (složitého) s paprskem..

<li>jak je vidět, struktura v této aplikaci nám pomůže ušetřit mnoho výpočtů průniků s obaly jednotlivých lodí (něco okolo <i>log_n(n)</i> ku <i>n</i>), trochu jsme ušetřili i tím, že jsme všechny lodě už na nejmenší úrovni zabalili do minimální obalující kostky.. <li>zkuste se zamyslet, kterou veličinu je dobré minimalizovat, aby úspora plynoucí z použití R stromu byla co největší. Je zřejmé, že doba běhu algoritmu přímo souvisí s tím, do kolika větví a jak hluboko v každé z nich sestoupíme, než danou větev vyloučíme. Z tohoto pohledu je vidět, že je rozumným požadavkem usilovat o to, aby obdélníky jednotlivých uzlů byly co nejmenší a aby se co nejméně překrývaly. první kritérium bude z hlediska našeho příkladu znamenat, že na při postupném testování průniku paprsku s kostkami se nám pro menší ohraničující obdélník spíše stane, že zjistíme, žz náš paprsek jím neprochází a tak pro danou větev výpočtu můžeme skončit. to ušetří čas.. podobně minimalizace překryvu způsobí, že se z menší pravděpodobností dostaneme do situace, kdy pro jediný paprsek budeme muset zkoumat více větví stromu.

<li>tedy zrekapitulujme: větší (zbytečně) pokrytá plocha = falešný poplach v některých oblastech = delší běh algoritmu v neperspektivních větvích, větší překryv = větší pravděpodobnost paralelního běhu ve více větvích = delší běh algoritmu. </ul>

z uvedeného příkladu je vidět, že kritérií, podle kterých by se strom dal efektivně stavět je víc. minimalizace <i>překryvu</i>, minimalizace <i>pokryté plochy</i> jsou ale jen některá. v rodině R-stromů (R*) se v některých fázích příslušných algoritmů můžeme setkat i s jinými metrikami (povrch objektů..) a jistě by se daly vymyslet další..

u klasických R-stromů stojí v popředí veličiny volně odpovídající pokryté ploše (takovou veličinou je třeba i <i>mrtvá plocha</i>, se kterou se právě u R stromů potkáme (algoritmus <i>split-node</i>)..)

algoritmus přidávání prvku

při přidávání objektu je potřeba napřed určit list, do kterého daný prvek "padne" - tomu odpovídá algoritmus <i>choose leaf</i> - tam prvek přidáme. může se ale stát, že přidáním objektu počet objektů v daném listu stoupne nad pro daný strom specifickou mezní hranici. V takovém případě je nutné uzel rozštěpit - algoritmus <i>split node</i>. tím ovšem vzroste počet potomků jeho rodiče, který tím může také "přetéct", také se štěpí.. v nejhorším případě "probubláme" až ke kořenu a zvýší se výška stromu.

algoritmus choose leaf

algoritmus

<ul>

<li>na vstupu máme objekt, který chceme zařadit do struktury stromu, a strom, kterému odpovídá jakási "hierarchie obdélníků" <li>začneme s kořenem:

<ul> <li>najdeme alespoň jednoho syna (obdélníky), který obsahuje přidávaný objekt - může jich být víc, protože jim odpovídající obdélníky se mohou překrývat (ačkoliv neobsahují stejné objekty) - vybereme ten nejmenší..

<li>pro něj zopakujeme rekurzivně právě popsaný krok - tedy mezi syny najdeme ty, které obsahují daný objekt <li>může se stát, že náš objekt nepadne do žádného ze synů - potom vybereme syna, jemuž odpovídající obdélník, pokud by se rozšířil tak, aby pokryl přidávaný objekt, by <b>nejméně zvětšil svůj obsah</b> (objem..). Případnou rovnost řešíme tak, že vybereme syna s celkově menším obsahem.

</ul> <li>ve finále máme jeden list, do kterého přidáme náš objek. pokud přidávaný objekt přesahuje přes hranici nalezeného listu (viz předchuzí odstavec), musíme list rozšířit a tuto změnu propagovat stromem nahoru. pokud bude po přidání objektu list přeplněný, dostane se ke slovu algoritmus "split node" a list rozdělíme na dva. změna se pochopitelně promítne do rodičocvského uzlu (počet potomků o 1 stoupne) - tím může dojít k jeho přeplnění a tedy k nutnosti znova použí "split node". při přidávání tudíž hrozí rekurzivní rozdělování listů až ke kořeni (!)..

</ul>

poznámky

<ul> <li>všimněte si, že kritérium pro výběr listu de facto odpovídá minimálnímu zvětšení pokryté plochy, které jsme jako klíčové pro strategii R-stromů předeslali už v minulém odstavci..

<li>je vidět, že nelze udělat nějaký jednoduchý závěr o složitosti algoritmu. pokud se budou objekty v prostoru hodně často měnit, může být režie dost velká <li>studenta potší, že v typickém písemkovém příkladu existuje list, do kterého objekt přímo padne, takže průběh algoritmu je jednoduchý a přímočarý..

<li>další věcí, které si můžeme všimnout, je, jak negativně ovlivňuje jakýkoliv vyhledávací proces ve stromě, pokud se uzly překrývají - algoritmy pak pokračují ve více větvích a složitost roste. </ul>

algoritmus split node

oproti předchozímu algoritmu zde nebudeme usilovat o minimalizaci pokryté plochy, ale o <b>minimalizaci mrtvé plochy</b>, tak jak jsme ji zadefinovali výše. Pochopitelně bychom mohli použít "brutal-force" a zkrátka vyzkoušet všechna možná dělení oběktů v přeplněném uzlu do dvou zkupin a vybrat z nich to s nejmenší mrtvou plochou. Pro potřeby rychlejších aplikací existují ale i lineární a kvadratický algoritmus. My si ukážeme ten kvadratický

algoritmus

vstup: přeplněný uzel v R-stromu (max. objektů + 1)

<ul> <li>najdeme dva objekty, které, pokud bychom je obalili do jednoho obdélníka, by měly největší mrtvou plochu (tedy pro každou dvojici z objektů spočteme obsah (objem) minimálního obdélníka, který je obaluje a od něj odečteme velikost samotných objektů. tak abychom zachytili "nepoužitou" - mrtvou - plochu").

<ul> <li>zkuste si rozmyslet, že tyto dva objekty by představovaly obzvláštní problém, pokud by byly v jedné skupině - skupina, která by obsahovala tyto dva objekty by měla pravděpodobně velkou mrtvou plochu..

<li>tyto dva objkty budou představovat zrnka v nově vznikajícím rozdělení do dvou skupin - ostatní objekty buď "padnou" k jednomu, či k druhému. označme je A a B </ul>

<li>máme tedy iniciální stav každé ze skupin - jedna obsahuje A, druhá B. <li>pro všechny zbylé objekty nyní spočteme přírůstek mrtvé plochy, který by způsobilo jejich přidání do skupiny s A, a přírůstek, který by způsobilo přidání do skupiny s B a jejich rozdil.

<li>vybereme objekt, který má <b>největší přírůstkový rozdíl</b> přidáme ho do skupiny, kde je jeho přírůstek menší. <li>nyní máme jednoprvkovou a dvouprvkovou skupinu. pro zbylé nezařazené objekty budeme postupovat zcela stejně

<ul> <li>pro všechny spočteme přírůstek mrtvé plochy po přiřazení k jedné i druhé skupině

<li>opět vyberem celkové minimum a opět odpovídající objekt přidáme do dopovídající skupiny </ul>

<li>tuto "smyčku" opakujeme do té doby, dokud zbývají nezařazené objekty, nebo pokud některá ze skupin má maximální velikost, definovanou pro konkrétní strom. </ul>

výstup, rozdělení těchto objetů do dvou skupin...

poznámky

<ul>

<li>kvadratická složitost je jasně vidět... <li>algoritmus nemusí vypočíst optimální výsledek, dle statistiky jsou ale výledky algoritmu dobré

<li>doporučuji umět, skoro určitě bude v písemce </ul>

R*-stromy

o textu

Následující text si klade za cíl ilustrovat principy struktury R* stromů a algoritmy, které používá, tak aby čtenáři umožnil snadný start do problematiky a umožnil mu vytvořit si první představu o tom, co vlastně látka, kterou se chystá naučit obnáší.. Neměl by být vaší jedinou informací, ideální je doplnit ho nějakou odbornější literaturou (skripta), která obsahuje rigorózní definice a přesný popis algoritmů - je potřeba abstraktní "představu" doplnit přesnými informacemi - a navíc poskytne mnohé ilustrace v podobě obrázků a příkladů. Čtenáři, který tak ještě neučinil, doporučujeme si nejdříve přečíst a pochopit text o R stromech.

intro

R* stromy, stejně jako R-stromy, používají princip hierarchického pokrývání prostoru obdélníky (kostkami). Pro připomenutí: <ul>

<li>kořen stromu odpovídá obdélníku (kostce), ubsahujícímu všechny objekty, pro které jsme strukturu vytvořili. <li>synové kořene jsou menší obdélníky uvnitř prostoru vymezeného kořenem, které přesněji ohraničují nějaké (disjunktní) podmnožiny objektů - dohromady obsahují zas všechny objekty.

<li>potomci synů zas zjemňují strukturu atd. -> obecněji řečeno, vnitřní uzly stromu odpovídají odbdélníku v prostoru a obsahují ukazatele na menší obdélníky, které leží uvnitř něj a zjemňují dělení prostoru. <li>listy stromů pak obsahují ukazatele na původní objekty, nebo na nějaké pomocné struktury jim odpovídající (minim. obalující obdélníky ...)

<li>pro strukturu stromu je určující minimální a maximální počet potomků uzlu </ul>

Princip struktury stromu je stejný jako u R-stromu, stejně jako navigace v něm.

Bez dalších podrobností můžeme říct, že R* se od R-stromů liší tím, jakou strategii používají při přidávání objektů: u R stromů jde od začátku (výběr cílového listu - <i>choose leaf</i>) do konce (eventuální štěpení přeplněného listu - <i>split node</i>) o minimalizaci plochy, která je obdélníky pokrytá (pozor, kritérium není stejné pro první a druhý algoritmus, v prvním jde o celkovou plochu, ve druhém je v popředí tzv. <i>mrtvá plocha</i>!). Zcela stranou naopak u R-stromů zůstává <i>překryv</i> jednotlivých obdélníků. U R*-stromů je situace o kousek složitější, bez podrobností můžeme říci, že zohledňuje do jisté míry oba aspekty..

Připomeňme jen, že přidání do stromu obnáší za prvé nalezení listu, do kterého se má daný objekt přidat, (algoritmus choose leaf) a za druhé - v případě, že po přidání bude list přeplněný - rozdělení listu podle příslušného algoritmu na dva listy a přípagné propagování změn dále do stromu. (algoritmus split node)

Zpřesněme nyní úvodní pseudodefinici: konkrétně R*-stromy možné chápat jako <b>R-stromy s pozměněným algoritmem štěpení uzlu na poslední úrovni</b> (algoritmus vyhledání listu pro přidávaný prvek (choose Leaf) je stejný, jako u R stromu!!). Zároveň je tento algoritmus tím nejtěžším, co na R*-stromech je a je možné, že se objeví v testu.. pozor, neopomiňte konec věty - opravdu se liší jen a pouze tím, jak probíhá štěpení listu!!

V této chvíli je dobré si uvědomit, že algoritmus přidávání objektů je integrální součást definice R*-stromů. R*-stromy nelze definovat jinak, než právě popisem těchto algoritmů, jakkoliv je lze obecně charakterizovat tak, jak jsme se o to pokusili výše.

algoritmy přidání prvku

při přidávání objektu je potřeba napřed určit list, do kterého daný prvek "padne" - tomu odpovídá algoritmus <i>choose leaf</i> - tam prvek přidáme. může se ale stát, že přidáním objektu počet objektů v daném listu stoupne nad pro daný strom specifickou mezní hranici. V takovém případě je nutné uzel rozštěpit - algoritmus <i>split node</i>. tím ovšem vzroste počet potomků jeho rodiče, který tím může také "přetéct", také se štěpí.. v nejhorším případě "probubláme" až ke kořenu a zvýší se výška stromu.

algoritmus choose leaf

algoritmus

<ul>

<li>na vstupu máme objekt, který chceme zařadit do struktury stromu, a strom, kterému odpovídá jakási "hierarchie obdélníků" <li>začneme s kořenem:

<ul> <li>najdeme všechny syny (obdélníky), které obsahují přidávaný objekt - může jich být víc, protože jim odpovídající obdélníky se mohou překrývat (ačkoliv neobsahují stejné objekty).

<li>pro ně zopakujeme rekurzivně právě popsaný krok - tedy mezi syny najdeme ty, které obsahují daný objekt <li>když se dostanem "na konec" - tedy jde o list, či o uzel, který ale už nemá potomka přímo obsahujícího přidávaný objekt, zapamatujem si ho

</ul> <li>takto dostaneme seznam podezřelých uzlů, do kterých by náš objekt mohl být přidán

<li>pokud jsou mezi nimi nějaké listy, můžeme objekt přidat do některého z nich (nejlépe do nějakého málo zaplněného), pokud takový neexistuje, přidáme ho do nějakého plného (který se tím přeplní) a rozštěpíme ho algoritmem "split node". <li>pokud tam listy nejsou - ve všech prohledávaných cestách došlo k tomu, že na nějaké úrovni žádný ze synovských obdélníků nepřekrýval přidávaný objekt - vezmeme ty nejdelší z cest a zkusíme najít synovský obdélník, který, pokud by se rozšířil tak, aby pokryl přidávaný objekt, by <b>nejméně zvětšil svůj obsah</b> (objem..).

<li>vezmeme ho za kořen a budeme pokračovat s algoritmem z tohoto místa. <li>ve finále budeme každopádně mít alespoň jeden list, do kterého přidáme náš objekt. pokud bude po přidání objektu list přeplněný, dostane se ke slovu algoritmus "split node" a list rozdělíme na dva. změna se pochopitelně promítne do rodičocvského uzlu (počet potomků o 1 stoupne) - tím může dojít k jeho přeplnění a tedy k nutnosti znova použí "split node". při přidávání tudíž hrozí rekurzivní rozdělování listů až ke kořeni (!)..

</ul>

poznámky

<ul> <li>všimněte si, že kritérium pro výběr listu de facto odpovídá minimálnímu zvětšení pokryté plochy, které jsme jako klíčové pro strategii R-stromů předeslali už v minulém odstavci..

<li>je vidět, že nelze udělat nějaký jednoduchý závěr o složitosti algoritmu. pokud se budou objekty v prostoru hodně často měnit, může být režie dost velká <li>studenta potší, že v typickém písemkovém příkladu existuje list, do kterého objekt přímo padne, takže průběh algoritmu je jednoduchý a přímočarý..

<li>další věcí, které si můžeme všimnout, je, jak negativně ovlivňuje jakýkoliv vyhledávací proces ve stromě, pokud se uzly překrývají - algoritmy pak pokračují ve více větvích a složitost roste. </ul>

algoritmus split node

algoritmus

první a velice důležitá poznámka: tento algoritmus se uplatní pouze při štěpení listu. Při propagování změn nahoru stromem a případném štěpení nelistového uzlu, použijeme stejný štěpící algoritmus, jako u R stromů

jak už jsme předeslali, algoritmus víceméně usiluje o to, minimalizovat překryv obdélníků. šlo by použít brutal-force, a najít skutečně nejvýhodnější dělení uzlu, nicméně v definici R*-stromu figuruje jiný, výpočetně jednodušší algoritmus (jinak podstatně složitější :-) ). pozor, veškeré zmínky o minimalizaci překryvu jsou zde proto, aby pro vás bylo snažší udržet nějakou centrální myšlenku. R*-stromy jsou definovány s tím algoritmem, který uvedeme a jedině tímto (narozdíl od R-stromů, kde v definici je na prvním místě kritérium a algoritmy jen umožňují snadnější aprofimativní výpočet). tento algoritmus nemusí vrátit nejmenší překryv, pouze překryv používá jako jedno z významných rozhodovacích kritérií.. pokud tedy v písemce použijete jiný postup, ač by třeba dával nulový překryv, nemusí to být správný výsledek..

algoritmus lze rozdělit do dvou navazujících částí: <i>výběr osy</i>, <i>výběr dělení</i>, z nichž každá stojí na formuli typu min(suma..) - to jen pro ilustraci toho, že celý postup je poměrně jednoduchý, leč pracný..

vstup: uzel, min. a max. počet prvků v uzlu, prvky v uzlu, které chceme rozdělit do dvou skupin

<b>výběr osy</b>:

<ul> <li>postup budeme velmi zhruba ilustrovat: nechť jsou meze např. 3-7 (objektů) potomků na uzel, a nechť máme např. objekty A,B,C,D,E,F,G,H

<li>seřadíme prvky podle jejich menší hraniční x-ové souřadnice (pokud shodná, rozhodnem dle větší x-ové..) <ul><li>seřazení dle x: BCADFEHG</ul>

<li>pro každé přípustné rozdělení této posloupnosti (respektující min a max) spočteme součet velikostí obvodů (okrajů, povrchů) obdélníků ohraničujících každou ze skupin. pro celou osu x pak tyto částečné součty sečteme a dostaneme jedno číslo, které nám pomůže s výběrem osy.. <ul><li>přípustná dělení: (1)BCA|DFEHG, (2)BCAD|FEHG, (3)BCADF|EHG

<li>obvody (v nějakých imagiárních jednotkách..): (1) o(BCA) + o(DFEHG) = 50, (2) o(BCAD) + o(FEHG) = 52, (3) o(BCADF) + o(EHG) = 57) <li>takže součet obvodů pro celou osy x = 50+52+57 = 159

</ul> <li>stejný postup opakujeme pro osu x, ale pro seřazení podle větší x-ové souřadnice, oba výpočty pak i pro osu y -> ve finále získáme 4 čísla (např. 159 (x menší), 162 (x větší), 170 (y menší), 165 (y větší)

<li>vybereme tu osu (a seřazení), které odpovídá nejmenší ze spočtených čísel!! (tedy zde osu x dle menší souřadnice) </ul>

<b>výběr dělení</b>:

vstup: osa a seřazení z minulého kroku <ul>

<li>opět vyjdeme ze všech možných dělení v rámci daného seřazení prvků dle osy (na vstupu), ovšem zaměříme se na jinou veličinu <li>mezi děleními vybereme to, které má <b>nejmenší překryv</b> - tzn. plochu (objem), který obdélník, ohraničující jednu skupinu objektů sdílí s obdélníkem ohraničujícím druhou skupinu..

<li>pokud nastane rovnost, přijde ke slovu druhé pravidlo, které dobře známe z R-stromů - totiž <b>minimální mrtvá plocha</b> <li>takto konečně dostaneme dělení (2 skupiny objektů), dle kterého daný uzel rozdělíme na dva nové uzly. změny je samozřejmě třeba propagovat nahoru stromem, pozor, znovu připomeňme, že v nelistových uzlech používáme jiný algoritmus než tento - a to algoritmus shodný s R-stromy..

</ul>

poznámky

<ul>

<li>rovnost mže nastat i při výběru osy: zde se s ní vypořádáme tak, že porovnáme stejná dělení i podle druhé souřadnice (ve smyslu větší/menší souřadnice..). pokud ani potom nemáme "vítěze", tak si prostě nějakého vyberem. <li>v písemce doporučuji buď precizně dokumentovat postup, nebo si dát záležet na numerických výpočtech - vyučujícímu nestačí myšlenka a nejlépe je mít správně výsledek..

<li>jak vidno, je těžké popsat R*-stromy nějak jednoduše - grafická představa funguje dobře pro jednotlivé kroky algoritmu, ale ne pro algoritmus celý - dokonce ani poučka "minimalizuje překryv při dělení" není zcela pravdivá - může se stát, že se vybere jiná osa, než ta, na které leží ten úplně nejnižší překryv.. takže <b>nejlepší je R* brát jako R s jiným štěpením a nesnažit se je zabalit do nějaké vševystihující fráze..</b> </ul>

K-D-stromy

Jedná se o datovou strukturu zachycující B-dělení datového prostoru. Každý vnitřní uzel reprezentuje B-kostku, obsahuje záznam o jedné z os (v případě roviny vybíráme z osy x a 'y) a jeho potomci jsou podstromy reprezentující B-kostky, které vznikly z rodičovského uzlu dělením podle osy specifikované v rodičovském uzlu.

K-D-stromy jsou pouhou reprezentací B-kostek, nejsou tedy plnohodnotnou stukturou pro ukládání prostorových objektů.

Buddy-stromy

O textu

Tento text je pouze shrnutí s pár postřehy, na které jsem při učení přišel, možná jsou i chybné, ale myslím si, že se to bude hodit, neboť je toho na Internetu o buddy-stromech velice málo a řekl bych, že na slidech od Žemličky je to dost podivně popsané. Hlavně je tu milion side-efektů a ten kód se nedá moc číst.

Úvod

Základ Buddy-stromů je podobný jako u K-D-stromů, také se zde využívá rozdělení datového prostoru na B-kostky.

Hlavní rozdíl je v tom, že Buddy-strom je plnohodnotná struktura, která se hodí například pro uložení bodů v prostoru. Další podstatný rozdíl je ten, že potomky nějakého (vnitřního) uzlu nemusí být pouze B-kostky vzniklé dělením podle jedné osy, ale i B-kostky, které vznikly více děleními, klidně na více úrovních. Vše záleží na blokovacím faktoru vnitřního uzlu, který uchovává adresář.

Tedy pokud je například blokovací faktor vnitřního uzlu 4, je uzel schopen uložit až 4 B-kostky. Ty mohly vniknou například následujícím dělením:

• celá B-kostka se rozdělila na dvě půlky

• jedna její půlka se rozdělila, máme tedy jednu polovinu a dvě čtvrtiny původní kostky.

• jedna ze čtvrtin se rozdělila, máme tedy jednu polovinu, jednu čtvrtinu a dvě osminy původní kostky.

Pokud by mělo dojít k dalšímu dělení v této kostce, nebyl by schopen uzel udržet 5 záznamů o potomcích a musel by se tedy sám rozdělit. O tom ale později.

Struktura

Struktura vnitřního uzlu:

• pos: integer - nevím přesně, ale řekl bych že to bude nějakým způsobem popsaná pozice reprezentované B-kostky.

• dir: bool - zda jedná se o adresář/vnitřní uzel, zde je True.

• dirnode: array of direntries - pole obsažených potomků, kde direntry je dvojice (interval, pointer). Interval je kostka reprezentující potomka a pointer je ukazatel na uzel tohoto potomka.

Struktura listu:

• pos: integer - nevím přesně, ale řekl bych že to bude nějakým způsobem popsaná pozice reprezentované B-kostky.

• dir: bool - zda jedná se o adresář/vnitřní uzel, zde je False.

• datanode: array of datarecs - pole obsažených datových položek (například bodů, kde datarec je dvojice (klíč, info). Klíč je v podstatě pozice v datovém prostoru. Je-li tedy klíč K v intervalu I, pak I.low <= K <= I.high.

Možná je to špatným pochopením struktury, ale řekl bych, že v téhle struktuře není nikde popsán interval reprezentující celý datový prostor (B-kostka kořene).

Algoritmy

Nebudu je zde opisovat, jen vysvětlení. Kdyžtak koukejte do slidů.

Dotaz na úplnou shodu

• Vstup

  • T - kořen prohledávného stromu

  • K - hledaný klíč

• Výstup

  • T - nalezený uzel (T je vstupně-výstupní parametr, předaný referencí)

  • pos - pozice klíče

• Metoda

  • (Funkce GetPosition) Pokusí se najít klíč v kořeni, resp. najde potomka, do kterého by měl klíč spadnout.

  • Pokud funkce GetPosition vrátí pos == 0, pak klíč nepadne ani do jednoho potomka a dotaz končí chybou.

  • V opačném případě:

    • Pokud T je už list, pak je T náš výsledek.

    • Pokud T je vnitřní uzel, pak zarekurzíme do nalezeného potomka.

Intervalový dotaz

Algoritmus je dost podobný dotazu na úplnou shodu, rozdíl je v tom, že místo jednoho if probíráme podmínku na nenulovost pos ve while cyklu. To je z důvodu, abychom odchytili všechny B-kostky, které se prekrýají v hledaným intervalem (v případě dotazu na úplnou shodu se mohl klíč vyskytnout jen jednou, proto jsme hledali cestu).

• Vstup

  • T - kořen prohledávného stromu

  • S - Interval, podle kterého se vyhledává

• Výstup

  • Seznam datových záznamů, které spadají do zadaného intervalu (výstup tady není explicitně popsán, ale dělá ho volání funkce GetRecord).

• Metoda

  • Stejně jako předtím najdeme potomka, který se překrývá s intevalem S.

  • Pro všechny potomky, kteří se překrývají s intevalem S (while cyklus řízený voláním funkce GetPosition):

    • Když je to vnitřní uzel, zarekurzí se do něj.

    • Když je to list, najde odpovídající datové záznamy.

Insert

Samotna myšlenka insertu je snadná a stejná jako u jiných struktur. Nejdřív najde místo, kam má položku vložit, následně jí vloží a pokud přetekla, pak uzel rozdělí (rozdělování je pochopitelně propadováno od listu až do kořene).

Jediná obtížná situace nastane ve chvíli, kde se pokoušíme vložit záznam do kostky, která ještě nemá ve stromě žádnou reprezentaci. Patrně se může stát (budu rád, když někdo doplní za jakých okolností), že Buddy-strom nebude reprezentovat celý datový prostor, ale některý B-kostka bude vynechána (nealokována). V tom případě vrátí dotaz na úplnou shodu vnitřní uzel, do kterého by se měla nově reprezentovaná B-kostka připojit. Toto situaci ošetřuje ten divný while cyklus uprostřed metody.

• Vstup

  • T kořen stromu, do kterého se vlkádá

  • drec - datový záznam, který chceme vložit, jedná se o dvojici (klíč, info)

• Výstup

  • Modifikovaný strom

• Metoda

  • Najde uzel, do kterého má záznam vložit. Pozor, T je i výstupní parametr, T od této chvíle není kořen stromu, ale uzel, do kterého máme přidat datový záznam.

  • Pokud dotaz na úplnou shodu vrátil vnitřní uzel (T.dir == true), provedeme následující (jen letmo, kdyby měl nekdo podrobnější popis, ať ho doplní):

    • Vytvoříme reprezentaci dané B-kostky

    • Když najdeme okolo nějakou kostku (parťáka), je kterou ji můžeme slít, pak je slijeme (Mergable, Merge)

    • Když neslíváme, musíme otestovat, zda nám nepřetekl rodičovský uzel a případně ho rozdělit.

  • Nyní bychom měli mít v T listový uzel.

  • Pokud nám dotaz na úplnou shodu na začátku metody vrátil nějakou platnou pozici, znamená to, že záznam s daným klíčem už ve stromě existuje. V takovém případě končíme chybou

  • Nyní máme list a můžeme přidat datový záznam. Přidáme a v případě přetečení rozdělíme.

Split

• Vstup

  • U - Uzel pro rozdělení

• Výstup

  • Mofifikovaný strom

• Metoda

  • (Funkce Předek) Najdi otce přeplněného uzlu. Zde je opět takový skrytý fígl a to ten, že pokud toto zavoláme na kořen, který je zároveň list, vytvoří to jeden vnitřní uzel jako kořen s jedním potomkem (původním listovým kořenem).

  • (GetSplitAxis) Najdeme osu, podle které se bude dělit uzel.

  • (RozdělZáznamy) Podle nalezená osy rozdělí uzel a to tak, že něco nechá v U a zbytek dá do uzlu novy.

  • (ObnovZáznam) Modifikuje direntry uzlu U v otci.

  • (VložZáznam) Vloží direntry uzlu novy do otce.

  • Pokud otec přetekl, rekurzí nahoru ke kořeni.

  • Pokud nepřetekl, zavolá Minimize, což je funkce, která opět rekurivně od listu ke kořeni upraví hodnoty interval v direntries jednotlivých uzlů. V podstatě zařídí, aby byly informace i intervalech v celém stromu nadále konzistentní.

Komprese

Číselné

Kódy pevné délky

Eliasovy kódy

*α(n)

:Unární kódování :α(7)=000 000 1

*β(n) :Binární kódování

:β(1)=1 :β(2n)= β(n)0

:β(2n+1)= β(n)1 :β(6)=110

**β'(n) ::Úvodní 1 lze vynechat. Je v čísle vždy

::β'(6)=10 *γ(n)

:β'(n)=xxxx :α(|β(n)|)=α(5)=00001

:γ(n)=0x0x0x0x1 ... zip β'(n) a α(|β(n)|) **γ'(n)

::γ'(n)=α(|β(n)|)β'(n) *δ(n)

:δ(n)=γ(|β(n)|)β'(n) *ω(n)

:zakoduj(N) ::K=0

::while (int )log₂N>0 do :::K=concat(β(n),K)

:::N=(int )log₂N ::endo

::return K :pro mene zdatne:

::- postupujem zprava doleva - myslim tim, ze postupne pridavame k uz existujicimu neuplnemu kodu nova binarni cisla zleva (ilustrujem na cisle 17) :::- napis 0 (0)

:::- napis cislo samotne binarne ( 10001 0 ) :::- az do chvile, kdy bude na zacatku pouze dvoumistne cislo pis vzdy delku predchoziho napsaneho retezce minus 1, binarne:

- delka posledniho retezce = 5 (=|10001|) , bez 1 = 4 -> (100 10001 0)

- delka posledniho retezce = 3 (=|101|), bez 1 = 2 -> (10 100 10001 0) coz je vysledny kod

*τ(n) :τ(n)=β(n)#

**τ'(n) ::τ'(n)=β'(n)#

wiki: Elias gamma coding,

Elias delta coding, Elias omega coding

Golombo

:vzdy pro nejaky parametr - oznacime b :kodujeme cislo n

::spocteme si x = (n-1) div b, y = (n-1) mod b (zbytek po predchozim deleni) ::pak x+1 ulozime unarne - to je prvni cast kodu

::se zbytkem je to trosku tezsi - je treba si predem zkostruovat kody zbytku (nejsou to totiz jen ciste bin. zapis) :::princip funguje tak, ze zbytky, ktere lze ulozit v spodni_cela(log2(b)) bitech s nulou na zacatku, tak ukladame

:::ostatni (vetsi) cisla ukladame do o jedna delsiho retezce s jednockou na zacatku a poradim cisla binarne zapsaym na konci (presneji radeji prikladem: 011111 je posledni s nulou na zacatku (delka 6), tak dalsi je 1000000 (delka sedm, prvni v poradi), dalsi 1000001, dalsi 1000010, dalsi 1000011, 1000100 atd) :::pro b = 10 tedy zkonstruujeme 9 kodu pro zbytky po div 10 (spodni_cela(log2(10)) = 3):

::::0 ~ 000 ::::1 ~ 001

::::2 ~ 010 ::::3 ~ 011

::::4 -> pozor, uz by neslo napsat ve trech bitech s 0 na zacatku, prepiname do ctyr bitu, jednicky na zacatku a binarniho "odpocitavani") ~ 1000 ::::5 ~ 1001

::::6 ~ 1010 ::::7 ~ 1011

::::8 ~ 1100 ::::9 ~ 1101

*Pokud se nepletu, mělo by jít definovat Golombovy kódy G_b(i)=α(i div b + 1)β_b(i mod b), i od 0 výš (α .. unární, β_b .. min. binární aka fázování).

Fázování

V přednášce Algoritmy komprese dat značen β_n a nazýván Minimální binární kód. Variace na téma β, když rozsah k zakódování přesně 2^k (např. n=|{0,..,8}|=9 ale k=4 a 2⁴=16).

Pro i<2^k-n se volí kódování β délky k-1 pro i.

Pro ostatní i se volí kódování β délky k pro i+(2^k-n).

*Příklad n=|{0,..,8}|=9, k=4.

:2^k-n=16-9=7 :Kódují se {0,..,6} jako 000 až 110 (binárně 0 až 6) a dále {7,8} jako 1110 a 1111 (binárně 7+7=14 a 8+7=15).

Znakové

Shannon-Fano kódování

EMA MELE MASO A MELE U TOHO A MELE A MELE A MELE

Celkem znaků (pravděpodobost získáme podělením četnosti): 12+6+11+1+4+7+3+1+1=30+16=46

Součástí zakódování je i tabulka kódů.

Huffmanovo kódování

• wen:Huffman coding

<graphviz>

digraph G { LME_TUHOA;

LME; _TUHOA;

LME_TUHOA -> LME [label="1"]; LME_TUHOA -> _TUHOA [label="0"];

LM; E;

LME -> LM [label="1"]; LME -> E [label="0"];

L; M;

LM -> L [label="1"]; LM -> M [label="0"];

_; TUHOA;

_TUHOA -> _ [label="1"]; _TUHOA -> TUHOA [label="0"];

TUHO; A;

TUHOA -> TUHO [label="1"]; TUHOA -> A [label="0"];

TUH; O;

TUHO -> TUH [label="1"]; TUHO -> O [label="0"];

TU; H;

TUH -> TU [label="1"]; TUH -> H [label="0"];

T; U;

TU -> T [label="1"]; TU -> U [label="0"];

} </graphviz>

Součástí zakódování je i tabulka kódů.

Aritmetické kódování

HALOOOO!

Kód tvoří kódové slovo,délka slova po dekódování a tabulka znaků s četnostmi.

pro zacatecnika je dobre dodat, ze: <ul>

<li>vychazime z intervalu 0-1 <li>ten delime na intervaly delkou odpovidajici jednotlivym relativnim cetnostem, prave hranice intervalu zapisujeme ve dvojkove soustave!! (zde je videt, ze je potreba, aby vstup byly mocniny 1/2

<li>pak zpravu kodujem po znacich a to tak, ze se vzdy "smrskneme" do intervalu odpovidajicimu prave kodovanemu znaku - vezmem ho jako vychozi "0-1" interval a rozdelime zas podle cetnosti. <li>takhle rekurzivne porad zmensujem interval - ve vysledku mame jeden malinky interval charakterizujici celou zpravu

<li>jak se pracuje s binární desetinnou soustavou http://en.wikipedia.org/wiki/Binary_numeral_system </ul>

Slovníkové

Slova jazyka

BSTW

Intervalové kódování

Řetězcové

LZ77

LZSS

poznámky

LZ78

LZW

Burrows-Wheelerova transformace

Komprese bitovych map

Hledani v textech

Invertovany soubor

Signatury

Grayovy kódy