DBI003 probraná látka

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

Prostorové databáze

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:

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

struktura stromu

přibližme si strukturu stromu:

• 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ů..)
• 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..
• 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.
• 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ů)
• pro strukturu stromu je určující minimální a maximální počet potomků uzlu

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:

• sestrojíme si MOO (mimim. obal. obd.) pro každou loď
• 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
• 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
• 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...
• 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..
• 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 log_n(n) ku n), trochu jsme ušetřili i tím, že jsme všechny lodě už na nejmenší úrovni zabalili do minimální obalující kostky..
• 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.
• 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.

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 překryvu, minimalizace pokryté plochy 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 mrtvá plocha, se kterou se právě u R stromů potkáme (algoritmus split-node)..)

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 choose leaf - 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 split node. 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

• na vstupu máme objekt, který chceme zařadit do struktury stromu, a strom, kterému odpovídá jakási "hierarchie obdélníků"
• začneme s kořenem:
  • 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ší..
  • pro něj zopakujeme rekurzivně právě popsaný krok - tedy mezi syny najdeme ty, které obsahují daný objekt
  • 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 nejméně zvětšil svůj obsah (objem..). Případnou rovnost řešíme tak, že vybereme syna s celkově menším obsahem.
• 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 (!)..

poznámky

• 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..
• 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á
• 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ý..
• 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.

algoritmus split node

oproti předchozímu algoritmu zde nebudeme usilovat o minimalizaci pokryté plochy, ale o minimalizaci mrtvé plochy, 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)

• 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").
  • 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..
  • 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
• máme tedy iniciální stav každé ze skupin - jedna obsahuje A, druhá B.
• 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.
• vybereme objekt, který má největší přírůstkový rozdíl přidáme ho do skupiny, kde je jeho přírůstek menší.
• nyní máme jednoprvkovou a dvouprvkovou skupinu. pro zbylé nezařazené objekty budeme postupovat zcela stejně
  • pro všechny spočteme přírůstek mrtvé plochy po přiřazení k jedné i druhé skupině
  • opět vyberem celkové minimum a opět odpovídající objekt přidáme do dopovídající skupiny
• 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.

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

poznámky

• kvadratická složitost je jasně vidět...
• algoritmus nemusí vypočíst optimální výsledek, dle statistiky jsou ale výledky algoritmu dobré
• doporučuji umět, skoro určitě bude v písemce

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

• kořen stromu odpovídá obdélníku (kostce), ubsahujícímu všechny objekty, pro které jsme strukturu vytvořili.
• 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.
• 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.
• 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 ...)
• pro strukturu stromu je určující minimální a maximální počet potomků uzlu

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 - choose leaf) do konce (eventuální štěpení přeplněného listu - split node) 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. mrtvá plocha!). Zcela stranou naopak u R-stromů zůstává překryv 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 R-stromy s pozměněným algoritmem štěpení uzlu na poslední úrovni (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 choose leaf - 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 split node. 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

• na vstupu máme objekt, který chceme zařadit do struktury stromu, a strom, kterému odpovídá jakási "hierarchie obdélníků"
• začneme s kořenem:
  • 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).
  • pro ně zopakujeme rekurzivně právě popsaný krok - tedy mezi syny najdeme ty, které obsahují daný objekt
  • 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
• takto dostaneme seznam podezřelých uzlů, do kterých by náš objekt mohl být přidán
• 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".
• 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 nejméně zvětšil svůj obsah (objem..).
• vezmeme ho za kořen a budeme pokračovat s algoritmem z tohoto místa.
• 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 (!)..

poznámky

• 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..
• 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á
• 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ý..
• 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.

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í: výběr osy, výběr dělení, 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

výběr osy:

• 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
• seřadíme prvky podle jejich menší hraniční x-ové souřadnice (pokud shodná, rozhodnem dle větší x-ové..)
  • seřazení dle x: BCADFEHG
• 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..
  • přípustná dělení: (1)BCA|DFEHG, (2)BCAD|FEHG, (3)BCADF|EHG
  • 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)
  • takže součet obvodů pro celou osy x = 50+52+57 = 159
• 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ší)
• vybereme tu osu (a seřazení), které odpovídá nejmenší ze spočtených čísel!! (tedy zde osu x dle menší souřadnice)

výběr dělení: vstup: osa a seřazení z minulého kroku

• 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
• mezi děleními vybereme to, které má nejmenší překryv - 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..
• pokud nastane rovnost, přijde ke slovu druhé pravidlo, které dobře známe z R-stromů - totiž minimální mrtvá plocha
• 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..

poznámky

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

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é

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

Četnosti
" "	A	E	H	L	M	O	T	U
12	6	11	1	4	7	3	1	1

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

Kódová slova (stavba) (seřadíme podle četnosti a v případe stejné seřazujeme podle abecedy)
1	1	1	3	4	6	7	11	12
H	T	U	O	L	M	A	E	" "
1							0
1					0		1	0
1				0	1	0
1			0
1		0
1	0

Kódová slova
" "	A	E	U	L	M	O	H	T
00	100	01	11110	110	101	1110	111111	111110

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

Huffmanovo kódování

• wen:Huffman coding

Kódová slova (stavba)
1	1	1	3	4	6	7	11	12
T	U	H	O	L	M	A	E	" "
2
3
6
4	6	6				7	11	12
L	M	TUHO				A	E	" "
10		13
10		11	12	13
LM		E	" "	TUHOA
21			25
LME			" "TUHOA
46
LME" "TUHOA

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

Kódová slova
" "	A	E	H	L	M	O	T	U
01	000	10	00110	111	110	0010	001111	001110

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

Aritmetické kódování

HALOOOO!

Četnosti
H	A	L	O	!
1	1	1	4	1

Stavba kódového slova
	!		A		H		L		O
0		0.001		0.01		0.011		0.1		1
				H
	!		A		H		L		O
0.01		0.010001		0.01001		0.010011		0.0101		0.011
		A
	!		A		H		L		O
0.010001		0.010001001		0.01000101		0.010001011		0.0100011		0.01001
						L
	!		A		H		L		O
0.010001011		0.010001011001		0.01000101101		0.010001011011		0.0100010111		0.0100011
								O

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

pro zacatecnika je dobre dodat, ze:

• vychazime z intervalu 0-1
• 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
• 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.
• takhle rekurzivne porad zmensujem interval - ve vysledku mame jeden malinky interval charakterizujici celou zpravu
• jak se pracuje s binární desetinnou soustavou http://en.wikipedia.org/wiki/Binary_numeral_system

Slovníkové

Slova jazyka

BSTW

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

metoda pouziva slovnik, do ktereho se pridavaji slova ze zpravy
na vystup jde bud cislo a slovo, pokud jde o nove slovo, nebo pouze cislo, pokud jde o slovo, ktere uz je ve slovniku
- v prvnim pripade vypiseme: kolikate nove slovo to je (delka slovniku + 1) a slovo samotne & pridame ho na zacatek slovniku
- v druhem pripade vypiseme: index slova ve slovniku & slovo presuneme z pozice kde bylo na zacatek slovniku

-> takze je to zcela intuitivni, az na podivne cachry se slovnikem, ktery se skoro porad meni. dobre je tez dodat, ze slovnik slouzi jen jako pomucka pri kodovani - zpravu muzem tudiz prubezne odesilat na vystup, prijemce si sam rekonstruuje slovnik..

1EMA 2MELE 3MASO 4A 3 5U 6TOHO 4 4 2 2

Slovnik v krocich:
1. EMA
2. MELE EMA
3. MASO MELE EMA
4. A MASO MELE EMA
5. MELE A MASO EMA
6. U MELE A MASO EMA
7. TOHO U MELE A MASO EMA
8. A TOHO U MELE MASO EMA
9. MELE A TOHO U MASO EMA
10. A MELE TOHO U MASO EMA
11. MELE A TOHO U MASO EMA

Dekódování probíhá analogicky. Dvojice kód slovo značí přidání nového slova do slovníku. Samotný kód pak odkaz do slovníku. Nesmí se zapmínat přeskupit slovník.

Intervalové kódování

Za kódové slovo se bere buď samo slovo, pokud ještě nebylo čteno, nebo vzdálenost od jeho poslední pozice.

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

kódování:

EMA MELE MASO A 3 U TOHO 4 4 2 2 2 2

dekódování:

analogicky. slovo znamená jen přepis a kód zas jen odkaz (o kolik slov zpět) do již dekódovaného textu.

Řetězcové

LZ77

Principem je pohyblive okenko:

[jak daleko vidime zpet | jak daleko vidime dopredu]

Typicke nastaveni byva 12+4 bitu

Kodujeme trojicemi <kam zpet, kolik, nasup>

ABLABLABLAM!

(0,0,A);(0,0,B);(0,0,L);(3,4,B);(3,2,M);(0,0,!);
celkem 120 bitu

Analogicky pokud mame nastaveni 3+2 bity ( = 8 hodnot + 4 hodnoty, cili maximalne mohu zakodovat (7dec(=111bin),3dec(=11bin),X(=znak)))

(0,0,A);(0,0,B);(0,0,L);(3,3,A);(3,3,M);(0,0,!)
celkem 78 bitu

za zminku stoji, ze "kolik" muze klidne presahnout hranici mezi "pohledem zpet" a "vyhledem"
kontroluje se vždy od hranice výhledu a pohledu zpět
- takze "aaaaaaaaaaa" v konfiguraci 12,4 (v tuto chvíli není myšlen počet bitů, ale pro názornost počet znaků) bude treba |a|aaaaa|aaaaa (0,0,a)(1,4,a)(1,4,a)(1,4,a)

LZSS

Analogie predchoziho, ale s tim, ze neposilame trojice pokud to neni nezbytne nutne,pokud ano, posleme dvojici.

V kodovem slove posilame znaky (8 bitu) a dvojice podle rozliseni okenka + 1 bit na rozliseni, zda se jedna o dvojici nebo o znak

ABLABLABLAM!

pro velikost okna 12+4 (opět pro názornost myšleno znaky, v reálných případech a v testu definováno počtem bitů):
'A','B','L',(3,4),(3,3),'M','!'
celkem: 5* (8+1) bitu a 2* (5+1) bitu za dve dvojice

poznámky

• http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzss.html

LZ78

Kodovani pomoci slovniku

Pri kodovani si stavime slovnik postupne.

ABLABLABLAM!

(0,A); (0,B); (0,L); (1,B); (3,A); (2,L); (1,M); (0,!);
slovnik:

1 A
2 B
3 L
4 AB
5 LA
6 BL
7 AM
8 !

Slovnik stavime tak, ze pokud frazi nezname, soupneme do slovniku primo znak, pokud zname,
tak na vystup jde adresa zname fraze ve slovniku a vytvori se nova fraze - pouzita se prodlouzi o nasledujici znak.

LZW

Na zacatku mame ve slovniku pouze abecedu.
Ve slovniku vzdy najdeme nejdelsi frazi, ktera odpovida prefixu kodovaneho textu.
Na vystup prijde odkaz do slovniku (cislo fraze).
Na konec slovniku pridame frazi prodlouzenou o jeden znak.

Pr.:
ABRAKADABRAKADABRAKA

Slovnik:
0:A, 1:B, 2:R, 3:K, 4:D

Vystup: 0 1 2 0 3 0 4 5 7 9 11 6 8 0

Fraze:
5:AB, 6:BR, 7:RA, 8:AK, 9:KA, 10:AD, 11:DA, 12:ABR, 13:RAK, 14:KAD, 15:DAB, 16:BRA, 17:AKA
Zakodovanym vystupem bude "vystup" + "slovnik". Stačí ale poslat jen základní slovník se znaky! Delší fráze se tvoří dynamicky.

Burrows-Wheelerova transformace

• wen:Burrows-Wheeler transform

Pozn.: Pitomý příklad. Ale krátký, demonstrující princip.

• Kódování

vstupní slovo

bba

matice permutací (edit by R4D: matice rotací. u slova délky 3 je to totéž, ale pro delší už ne)

b	b	a
b	a	b
a	b	b

setříděná matice permutací

a	b	b
b	a	b
b	b	a

výstup poslední sloupec a číslo řádku se vstupním slovem v setříděné matice permutací

bba,2

• Dekódování

vstupní slovo

bba,2

iterativně stavíme setříděnou matici permutací

první sloupec seřazení znaků vstupního slova

a

b

b

zjistíme mapování permutace

a	1	b
b	2	b
b	0	a

další sloupce zjistíme vždy mapováním posledního přidaného

a	b	1	a
b	a	2	b
b	b	0	b

nakonec

a	b	b	1	b
b	a	b	2	a
b	b	a	0	b

setříděná matice permutací

a	b	b
b	a	b
b	b	a

výstup slovo v daném řádku řádku setříděné matice permutací (zde řádek 2)

bba

Hledani v textech

Invertovany soubor

Idea: ke kazdemu (vyznamovemu) slovu z kolekce dokumentu si zaznamename, v jakem dokumentu se vyskytlo. Pri vyhledavani pak staci tyto seznamy projit.

• soubor - doc1, doc3, doc56...
• index - doc2, doc 10, doc24...
• semestr - doc5, doc6...
• ...

Signatury

Signatura dokumentu napomaha urcit, zda se v nem hledane slovo nachazi. Umi ho vyloucit se 100% pravdepodobnosti, anebo rict, ze slovo tam pravdepodobne je.

Kazde slovo v dokumentu se v signature muze projevit nasledujicim zpusobem:

Nahodi jeden unikatni bit - problem s velikosti signatur
Hash - problem s velkym poctem spatnych hitu
Slovo nahazuje kombinaci nekolika bitu, podle dulezitosti jich muze byt vice - optimalni

Grayovy kódy

No, zde by se asi mělo hovořit spíš v kontextu deskriptorů (stránek, záznamů resp. dotazů). Takže slovo signatura berte s v širším smyslu...

• Výhoda oproti binárním: Grayův kód g_i a g_i+1 se liší pouze v jednom bitu.
• Př.: 3b Grayův kód a signatury při dotazování.

Dek. Gray   Binární
 0   000    000
 1   001    001
 2   011    010
 3   010    011
 4   110    100
 5   111    101
 6   101    110
 7   100    111

Pro signaturu dotazu 0?1 odpovídají sig. odpovědi 001 a 011. Dekadicky binárně 1 a 3, ale v Grayových kódech 1 a 2.

• Převod Bin2Gray.

gi = bi ^ (bi >> 1);

• Převod Gray2Bin.

/* operátor [k] adresuje k-tý bit */
bi[n] = gi[n]
for k = n-1 downto 0
  bi[k] = bi[k+1] ^ gi[k]