okruhy 14/15: ''Architektury databázových systému. Modely a vlastnosti transakcí: uzamykací protokoly, casová razítka. Izolace transakcí, alokace prostredku. Distribuované transakce. Zotavení z chyb, žurnály. Indexace relacních dat: B-stromy, hašování, GRACE algoritmus. Prístupové metody k prostorovým objektum: R-stromy a jejich varianty. Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace. Komprese dat: modely textu, kódování, Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy, komprese bitových map, rídkých matic, Burrows-Wheelerova transformace.''
'''Vsechnu latku pokryva text "Zaklady implementace souboru a databazi" od Pokorneho a Zemlicky a slajdy "Dokumentografickych informacnich systemu" od Kopeckeho'''
== Architektury databázových systému. ==
{{TODO|co sem patří?}}
==Transakce==
{{:Implementace_databázových_systémů/Transakce}}
== Indexace relacních dat: B-stromy, hašování, GRACE algoritmus. ==
{{Zkazky|
* '''Indexace relacnich dat''' - B-stromy a hasovani
* '''DS - B-stromy a ich varianty (Kopecky)''' - Napisal som si zakladne definicie B, B+, B* a VB stromov. Pobavili sme sa o redundantych/neredundantych stromoch. Potom o dotazoch na viacero atributov z coho sme sa dostali k hasovaniu a dotazom na ciastocnu zhodu a koncilo to iba otazkou na priestorove data. Tam stacilo povedat, ze je na to dobry R-strom. (Tiez niekde v debate padla otazka na paralelny pristup do B-stromu.) Prijemne aj ked pomerne podrobne sa snazil preverit znalosti.
* '''DS - B-stromy a jejich varianty (?)''' - Popsal jsem definice, co splňují, operace, vyváženosti a jaké jsou varianty ((ne)redundantní, B+, B*). Pak chtěl pan Kopecký vědět, k čemu jsou dobré (zmínil jsem indexování) a dlouho se ptal na různé detaily (např. jak zabránit zamykání celého B-stromu při insertu pokud se ke stromu přistupuje paralelně - lze provádět dopředný split již naplněného uzlu, jaká varianta stromu je nejlepší pro indexování, které atributy v DB jsou vhodné pro indexování - záleží např. na doméně, atd.)
}}
=== Metody indexace relací ===
* relacie mozu byt chapane ako subory, zaznamy suboru ako n-tice relacie, samozrejme su tam rozdiely, napr.:
** schemy vsetkych relacii sa natiahnu naraz s celou DB, subory musime otvarat/zatvarat jednotlivo
*indexsekvenční soubor (indexováno jen podle primárního klíče)
*invertovaný soubor - lze indexovat podle čehokoliv - indexují se přímo záznamy
*bitová mapa
**pro atributy malých domén (pohlaví, typ karoserie vozu...) se pro každou doménu vytvoří bitový vektor a jednička tam kde hodnota pro daný řádek platí, tedy vždy jen jedna jednička na řádku => hodně nul, lze dobře komprimovat
**vyhledávání je rychlé používají se operace AND, OR atd.
**insertem se všechny vektroy prodlouží, přidáním další možnosti (rozšíření domény) se přidá další bitový vektor
**lze využívat i pro GROUP BY, COUNT atd.
=== Hashování ===
* perfektni hasovani Cormacka
* perfektni hasovani Larsona a Kalji
* Deskriptory stranek, Grayovy kody (viz Vícerozměrné dotazy implementované pomocí hashovacích metod)
* hasovani Fagina
* dynamicke hashovani Litwina
* skupinove stepeni stranek
=== B-stromy ===
''viz [[Státnice_-_Stromové_vyhledávací_struktury#B-Stromy|společná část "B-Stromy a jejich varianty"]]''
* redundantni, neredundantni B-strom
* redundantni, neredundantni B*-strom
* redundantni B+-stromy
* prefixove stromy
* (a, b)-stromy
* stromy s promenlivou delkou zaznamu
* vicerozmerne B-stromy
=== Datové struktury na externí paměti ===
*hromada - nehomogenni záznamy (ruzne delky) jsou ukládány za sebou (bez dalších podmínek) - vyhledání čehokoliv = projití celé hromady (v nejhorším případě)
*sekvenční soubor - podobný jako hromada, jen záznamy jsou pevné délky (homogenni)
** uspořádaný sekvenční soubor - záznamy uspořádány podle klíče, nově přidávané se ukládají do "souboru aktualizací" a občas je provedena reorganizace, kdy je "soubor aktualizací" vyprázdněn a data z něj zatříděna do uspořádaného sekvenčního souboru. Nalézt záznam lze pak půlením intervalů v case O(log_2(n)).
** indexsekvenční soubor - obdobně jako předchozí jsou záznamy setříděny podle klíče, navíc existují indexy do jednotlivých bloků (stránek). Indexy jsou tvořeny klíči některých záznamů. Celý index je pak jakýsi B-strom. Při přidávání není index reorganizován, ale je použita oblast přetečení, kam je nový záznam vložen. K záznamu, za který měl být nový záznam vložen se pak uloží číslo bloku i číslo záznamu, kde nový záznam leží. V oblasti přetečení jsou tak vytvářeny lineární seznamy.
**invertovaný (indexovaný) soubor - indexují se přímo záznamy, ne bloky (jak tomu je v indexsekvenčním souboru), data nejsou v souboru nijak uspořádána, jednotlivé bloky nemusí být na disku za sebou. Indexů může být více různých. Při přidávání není použita další struktura, přímo se upravují indexy. Používá se v DIS (invertovany soubor).
*ukládání pomocí hashování
*b-stromy
Jiny (urcite lepsi :) popis:
:[http://siret.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_11.pdf Fyzická implementace relačních databází] (Databázové systémy)
:[http://siret.ms.mff.cuni.cz/sites/default/files/doc/david.hoksza/lectures/ndbi007/2014W/lecture2.pdf File Organizations] (OZD 1)
Definice: '''Klíč''' schématu relace R je nejmensi mnozina atributů ze schématu R, na níz celá R funkčně závisí. Jakmile tedy máme hodnoty pro klíčové atributy, máme jednoznačné určen libovolný řádek tabulky.
;Organizace databázových souborů (podle OZD 1)
:'''Halda''' (hromada / heap file)
::zaznamy maji ruznou delku
::zaznamy jsou vkladany na konec souboru
:'''Sekvenční soubor''' (sequential file)
::''nesetrideny'' - halda s pevnou delkou zaznamu
::''setrideny'' - zaznamy setridene podle klice (narocny INSERT a DELETE)
:'''Index-sekvenční soubor''' (indexed sequential file)
::index nad jednim klicem je vytvoren
::je to vlastne primarni soubor se setridenymi daty podle klice + indexovy soubor, ktery muze mit vice urovni indexu
:'''Indexový soubor''' (index file)
::indexy nad vice klici jsou vytvoreny
::muze obsahovat primarni index (coz je index nad klicem, podle ktereho je setrideny primarni soubor - asi klastrovany index) a obsahuje sekundarni indexy (asi neklastrovane indexy)
:'''Hashovaný / hešovaný soubor''' (hashed file)
::pro jeden atribut (asi i klic) existuje hesovaci funkce
=== Vícerozměrné dotazy implementované pomocí hashovacích metod ===
* viacrozmerne dotazy - obsahuju viac atributov (n>1)
** na uplnu zhodu - hodnoty vsetkych n atributov su pevne dane (n=2: MENO='Jiri' AND MESTO='Praha')
** na ciastocnu zhodu - hodnoty niektorych atributov (<n) su pevne dane
** na uplnu intervalovu zhodu - pre vsetkych n atributov su dane intervaly hodnot (napr. VEK>22)
** na ciastocnu intervalovu zhodu - intervaly hodnot su dane len pre niektore atributy
* implementacia
**'''signatury''' - d bitove binarne retazce
*** signatura zaznamu (dlzky d) je zretazenim signatur jednotlivych atributov, pre kazdy atribut A_i je samostatna hasovacia funkcia h_i, ktora vytvori signaturu dlzky d_i. Plati, ze d_0+d_1+...+d_n=d; n-pocet atributov. Signatura dotazu sa tvori podobne, nezadane atributy su reprezentovane retazcom nul.
*** signatura dotazu Q sa porovnava so signaturami zaznamov S - na pozicii, kde je v Q jednicka, musi byt jednicka aj v S, inak zaznam do odpovede nepatri
**'''deskriptory stranok'''
*** vrstvia sa deskriptory zaznamov v danej stranke pomocou logickeho OR. Deskriptor zaznamu je opat zretazenie deskriptorov atributov A_i, pre kazdy atribut je dana hasovacia funkcia h_i, ktora priradi kazdej hodnote atributu binarny retazec obsahujuci prave 1 jednicku.
*** subor deskriptorov stranok je pripojeny k primarnemu suboru, ak je velky, moze byt dvojurovnovy (prim. subor sa rozdeli do segmentov, kazdy ma svoj subor deskriptorov, tie tvoria 1. uroven; 2. uroven ma deskriptory ukazujuce do 1.)
*** rychlejsie ako signatury, lebo sa musi porovnat menej deskriptorov (ale na ukor pamate); lepsie ako indexovany subor, lebo nerastie cas vyhodnocovania s rastucim poctom atributov v dotaze, pamatove naroky su podobne
**'''grayove kody''' - binarne retazce, hodnoty nasledujuce za sebou sa lisia vzdy len v jednom bite
*** adresa stranky dana signaturou je interpretovana ako grayov kod
*** zaznamy vyhovujuce signature dotazu tvoria zhluky, kde zaznamy su fyzicky za sebou v jednej stranke (alebo viacerych po sebe iducich strankach), nikdy nie je viac pristupov na disku ako u binarneho kodovania
*** dobre pre dotazy na ciastocnu zhodu pri malom pocte zadanych atributov a pre dotazy na intervalovu zhodu
=== Vícerozměrná mřížka ===
[http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/cont.htm Slajdy Pokorný]
=== Vícerozměrné stromy ===
==== Vícerozměrné B-stromy ====
[http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/cont.htm slajdy Pokorný]
*lze pomocí nich indexovat soubor podle několika atributů současně.
*celý strom má tolik hladin, kolik je atributů (hlavní strom není B-Strom!)
*pro každý atribut jsou vytvořeny stromy - pro první jeden, pro druhý tolik, kolik má první atribut různých hodnot atd. U každé hodnoty atributu (uzlu stromu) existuje index na strom s dalším atributem.
*jednotlivé vrstvy celého stromu jsou indexovány polem Level (vrstva = jeden atribut) - slouží pro přeskočení prvních i atributů, které nebyly v dotazu zadány
*stromy v jedné vrstvě jsou propojeny do spojáku pomocí NEXT v kořeni, poddoména jednoho stromu je určena pomocí LEFT a RIGHT (uloženy v kořeni), které ukazují do další hladiny na první a poslední strom, který se týká daného stromu. Tedy každý prvek z vrstvy i-1 má ve vrstvě i určeny všechny prvky ve vrstvě i+1, LEFT a RIGHT dává vše.
*podobná struktura by pravděpodobně šla definovat i pro obecný, nebo jakýkoliv jiný vyhledávací strom.
== Přístupové metody k prostorovým objektům: R-stromy a jejich varianty ==
{{Zkazky|
* '''R-stromy''' - ''Napsal jsem, k čemu jsou dobré, definici a štěpení uzlů dle Guttmana a Greeneové. Dále jsem se zmínil o některých variantách R stromů. Zkoušející se pak jen zeptali na pár otázek.''
* '''R-Stromy (Pokorný)''' - ''Zadefinovať, k čomu slúžia, nákres, štiepenie Gutmann, Green. Rozhovor pokračoval k MOO, MOK - aproximáciám, aké sú výhody jednotlivých prístupov - náročnosť uloženia vs. schopnosť aproximácie. Žiadne detaily, stačilo rozumieť. R+ stromy som len popísal kritériá výberu osi a distribúcie, vravel som, že to kludne na papier dopíšem, ale Pokorný to zjavne nevyžadoval.''
* '''R-stromy (Skopal)''' - tuhle otazku jsem tak nejak cekal :-) Bohuzel pan Skopal zkousi pro me dost neprijemnym stylem .. po prvni vete vas dokaze zaskocit nejakou treba i jednoduchou a ne spatne minenou otazkou, na kterou rychle nevite, co odpovedet a pak se do toho tak zamotate, ze zacnete placat nesmysly..on se vas snazi k necemu dokopat, ale kdyz nevite kam presne miri, da se to jen tezko odhadnout..navic z jeho vyrazu nejde vycist, jestli je to jeste v pohode nebo jste na pokraji vyhozeni :-) Nastesti jsem u pana Skopala delal predtim jednu zkousku, tak uz jsem vedel, ze takhle zkousi, ale zas tak zly to neni, jak to v prubehu zkousky vypada...navic me potesilo, ze me nerozebral hned na zacatek uplne a vcas toho nechal..
}}
:''viz [[wen:R-Tree]]''
{{TODO|R-stromy komplet}}
== Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace. ==
{{TODO|sloučit s otázkou v DMJ}}
{{Zkazky|
* '''DMJ - Booleovský a vektorový model (?)''' - Slovy jsem popsal oba modely. U Booleovského jsem popsal, jak se indexuje, jak se vybírají termy a jak vypadají dotazy. Zmínil jsem se o složitosti počítání relevance. Dále jsem popsal vektorový model, jak vypadají dotazy apod. Zmínil jsem se, jak se počítá TF a ITF. Zkoušející se jen zeptal na pár otázek a byl spokojen.
* '''DMJ - Indexace v DIS (Kopecky)''' - Boolske systemy - reprezentace matici - moc velke, signatury, zbytek ze mne musel pan Kopecky dost pacit (invertovany soubor, jak ho ziskame - setridim dvojice (term, dokument) vnejsim tridenim a pak k nim sestrojim ten invertovany index). Vektorove systemy - formulovat vsechny vzorecky na TF, ITF, NTF, normalizovany vektor pro dokument. Takze tam jsem uz dalsi otazku nedostal..
* '''DMJ - Vekt. a boolsky model (Kopecky)''' - Zrejme oblubena otazka pana Kopeckeho. Uz som bol unaveny ale dal som boolsky model vcelku obstojne a pri vektorovom iba zaklad. Pan Kopecky ale skusa prijemnym sposobom a ak ste to nikedy vedeli tak to z vas dostane seriou lahkych otazok. Nepotrpi si na formalizmoch - staci mu to porozpravat po lopate a vediet princip :)
* '''DMJ - Indexace dokumentů (Skopal)''' - mám invertovaný soubor, index obsahuje jednotlivé termy, které pak mají seznam dokumentů, ve kterých se vyskytují - co ze mě doc. Skopal doloval bylo říct, že tyhle dokumenty jsou v tom seznamu setřízené, aby bylo urychlené vyhodnocování (problém byl v tom, že obrázek, kterej jsem k tomu nakreslil nebyl úplně jednoznačnej a každej jsme ho pochopili jinak, takže jsem za vůbec nechápal, co po mě chce, ale moh jsem si za to sám
* '''DMJ - Booleovský a vektorový model (?)''' - ''Slovy jsem popsal oba modely. U Booleovského jsem popsal, jak se indexuje, jak se vybírají termy a jak vypadají dotazy. Zmínil jsem se o složitosti počítání relevance. Dále jsem popsal vektorový model, jak vypadají dotazy apod. Zmínil jsem se, jak se počítá TF a ITF. Zkoušející se jen zeptal na pár otázek a byl spokojen. ''
* '''DMJ - Vektorový model (Pokorný)''' - chápal som to len intuitívne (vôbec som nevedel žiadne vzorce ITF a podobne), čo mu trochu vadilo, nakoniec to pochopil a netrápil ma
* '''IDS - Vektorovy a boolovsky model (Kopecky)''' - princip, tvar dotazu a odpovede, implementacia
}}
==== Boolský model DIS ====
:Každý dokument je popsán množinou termů, které obsahuje. Termy jsou uloženy v indexovém souboru a odtud potom probíhá vyhledávání.
*určení termů:
**ručně - každý může určit jiné termy, dokonce i jeden člověk se může 2x rozhodnout jinak
**automaticky - jednoznačné, ale bez porozumnění textu
** při určování termů by se měla vynechávat nevýznamová slova (předložky, spojky...), ale také příliš specifická slova
*Indexy lze nad kolekcí dokumentů vytvářet dvojím způsobem. Buď je množina termů pevně daná a pro každý nový dokument se aktualizují jen indexy (řízená indexace), nebo se s každým novým dokumentem přidávají i nové termy (neřízená indexace).
*Vyhledávání:
** probíhá klasicky přes termy pomocí "AND", "OR", "NOT"
** lze také využít faktografické informace o dokumentu (autor, datum vytvoření...)
** lze použít zástupné znaly ?, *
*Proximitní omezení
** při vyhledávání lze také užít proximitních omezení, tedy informaci o tom, v jaké vztahu dva hledané termy jsou (o kolik slov jsou vzdáleny, zda jsou ve stejném odstavci, nebo větě.
** pro práci s omezeními je třeba buď mít přítomny dokomenty a informaci zjišťovat přímo v nich a nebo rozšířit index -> namísto <term_id, doc_id> musí existovat index <term_id, doc_id, par_nr, sent_nr, word_nr>
Nevýhody boolského DIS:
*při zadávání dotazu jsou všechny termy stejně důležité
*ve výsledku disjunktního dotazu jsou promíchány dokumenty které obsahují všechny požadované termy s těmi, které obsahují pouze jeden
*ve výsledku konjunktivního dotazu nejsou dokumenty, které obsahují neobsahují žádný z termů stejně tak jako ty které neobsahují pouze jeden
==== Vektorový model DIS ====
Vektorový model je mladší než boolský (asi o 20 let) a vznikl aby odstranil chyby boolského modelu - především díky možnosti ohodnotit termy jak v dotazu, tak v indexu.
*Každý dokument je v indexu definován váhami pro jednotlivé termy.
*dotaz se zadává vektorem vah pro požadované termy <w1, w2, .. , wn>, w in <0,1>
*protože dlouhé dokumenty by byly zvýhodněny (obsahují jistě více termů), provádí se normalizace vektorů, to lze provádět:
**během indexace, což nezvětšuje odezvu, je však zapotřebí občas vše znovu "přenormalizovat"
**během vyhledávání - zpomaluje odezvu, je v definici podobnostní funkce
*Oproti boolskému modelu lze omezit velikost výstupu - výstup je seřazen dle relevance a tedy lze omezit jak počtem výstupů tak minimální relevancí.
*Podobnost mezi dotazem a dokumentem se určuje pomocí podobnostní funkce. Taková funkce není jednoznačně daná, podobnost může být tedy při různých implementacích různá. Základní podobnostní funkce je skalární součin přes dotaz a dokument (sim(q,d) = q x d), jsou ale i složitější:
Kosinová míra: <math>sim(q,d) = \frac{q \times d}{\sqrt(\sum(q_i^2)) * \sqrt(\sum(d_i^2))}</math>
Jaccardova míra: <math>sim(q,d) = \frac{q \times d}{\sum(q_i) + \sum(d_i) - \sum(q_i * d_i)}</math> a další.
*Pokud je po vektorovém modelu požadován i dotaz s negací, lze váhu w uvažovat z <-1, 1> a stejně tak i zadávat dotaz.
*Indexace:
**frekvence termu v dokumentu TF = #výskytů termu / #všech termů v dokumentu
**je potřeba vyřadit nevýznamová slova (stop list = {the, a, an, on ... })
**ignorovat termy s velmi nízkým výskytem
**normalizovat frekvenci ostatních termů <math>NTF_i = \frac{1}{2} + \frac{1}{2} * \frac{TF_i}{max(TF_j)}</math>, j = index jednotlivých termů
* Inverzní frekvence termu v dokumentech
** Nasel jsem dvě definice. První je od [http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/disslide.ppt Kopeckého] druhá od [http://lisp.vse.cz/znal2001/pokorny.ppt Pokorného]. Definice jsou v podstatě matematicky ekvivalentní.
** ''n'' je počet všech dokumentů.
** ''k'' je počet dokumentů ve kterých se term vyskytuje.
# <math>ITF = -log\left(\frac{k}{n}\right)</math>
# <math>IDF = log\left(\frac{n}{k}\right) + 1</math>
Váha termu i v j-tém dokumentu se urči jako <math>w_{ij} = NTF_{ij} * ITF_j</math>
*Dotazování (dotaz má stejnou reprezentaci jako index):
**Zadáním vektoru dotazu
**odkazem na zaindexovaný dokument (tedy "najdi mi dokumenty podobné tomuto")
**odkazem na jiný dokument (není problém pro něj spočítat vektor termů)
**přímo vložený text (obdoba předchozího)
*Lze uplatnit i zpětnou vazbu, kdy uživatel označuje relevantní dotazy a DIS na to reaguje přehodnocením výpočtu.
=== Vyhledávání v textech ===
=== Signatury, metody implementace signatur (vrstvené kódování) ===
[http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny6 Slajdy pokorny]
*signatura bloku textu je d-bitový řetězec, který v sobě nese informaci o tom, které termy v bloku jsou
*'''vrstvéní signatur'''
**každý term má svou signaturu (vypočtenou pomocí hash funkce) dlouhou d bitů a signatura bloku = OR přes všechny signatury termů v bloku.
*'''řetězení signatur'''
**signatury se spojují do řetězce - vhodné pro strukturovaná data (autor, rok vydání, nakladatelství...)
*'''transponovaný soubor signatur'''
**namísto N řetězců délky d mám d řetězců délky N (pokud signatury bloků naskládám do matice, koukám se pak na ně místo jako na řádky jako na sloupce)
**protože počet 1 v dotazu délky d je o mnoho menší než d a můžu porovnávat jen řetězce kde má dotaz jedničku, porovnávám toho daleko méně
**složitější aktualizace
*'''soubor indexovaných deskriptorů'''
**stejně jako z termů vytvářím vrstvením signaturu bloku, můžu pro více bloků vytvořit společnou signaturu
*'''dvouúrovňové vrstvené kódování'''
**každý blok má dvě signatury - vnětší (délky ds) a vnitřní (délky dn) kde dn << ds, bloky jsou rozděleny do skupin a každá skupina má vrstvenou signaturu ds - podle ní se rozlišují skupiny a ve skupin se bloky rozlišují podle signatury dn (tedy najdu skupinu bloků a pak v ní blok)
*'''rozdělený soubor signatur'''
**signaturu bloku délky d rozdělím na dva kusy (prefix a zbytek) a pak seskupím "zbytky" se stejnými prefixy - pokud testuju, otestuju nejdřív prefix a pokud se neshoduje, do skupiny vůbec nemusím chodit, čímž ušetřím celkem dost času
Metody je možné různě kombinovat tak, aby výsledná struktura byla co nejefektivnější.
=== Uspořádání odpovědi ===
== Komprese dat: modely textu, kódování, Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy, komprese bitových map, rídkých matic, Burrows-Wheelerova transformace. ==
{{Zkazky|
* '''komprese, obecně + komprese čísel (Kopecký)''' - opět jsem neměl moc jasnou představu, kde je to využíváno - nicméně po lehkým naťuknutí jsem rovnou použil předchozí pohovor o indexaci dokumentů a správně řekl, že se to používá v tom invertovaném souboru pro kódování seznam těch dokumentů, kde se term vyskytuje. Pak jsem byl ještě poučen, že jak je ten seznam setřízen, tak se nekódují konkrétní čísla, ale přírustek od předchozího indexu.
}}
=== Komprese dat: modely textu, kódování ===
[[Image:Komprese.png|right|thumb|604px|komprese textu]]
obecné typy redukce dat:
*ztrátová (nazývá se kompakce) - např. obraz, zvuk, video
*bezeztrátová (nazývá se komprese a je reverzibilní přes dekopresi)
Proces komprese má 2 fáze:
* modelování (modely textu) - přiřazení pravděpodobností jednotkám textu (znaky nebo m-tice znaků pevné délky)
* kódování - transformace do nového kódu pomocí modelu
'''prefixový kód''' - jednotliva kodova slova nejsou prefixem zadneho jineho slova
dělení modelů:
*statická - model je statický pro všechny dokumenty (uložen jednou)
*semiadaptivní (polostatické) - každý dokument má vlastní model (pošle se s dokumentem)
*dynamická (adaptivní) - oba algoritmy si model tvoří na základě již zpracovaných dat (musí se dekodovat od zacatku)
=== Huffmanovo kódování (statické, dynamické) ===
{{zarovka
|
* JPEG
* MP3,...
| Huffmanovo k. se pouziva v poslední fázi u
}}
{{Zkazky|
* '''Huffmanovo kódování (?)''' - stručně jsem popsal a nakreslil příklad k statické verzi, popsal jsem jak funguje dynamická, jak se mění strom atd.
* '''Huffmanovo kódovanie (Galamboš)''' - toto som vedel, takže sa v tom moc nevŕtal
* '''Huffmanovo kódování - statické, dynamické (Holubová)''' - Hned na zacatku mi bylo receno, ze se mam zamerit na dynamicke H. kodovani. Mel jsem cokoliv zakodovat a dekodovat.
}}
====Staticke Huffmanovo kodovaní====
{{zarovka
|
# Spočítáme frekvence výskytů symbolů (včetně mezer).
# Seřadíme znaky od nejmenší frekvence.
# Spojováním dvojic zleva vytváříme strom. Nové vrcholy zařazujeme do řady (co nejvíce doprava).
# Levé hrany jsou 0, pravé 1.
| statické kodovani
}}
:'''Vstup:''' seznam <math>n</math> zdrojovych jednotek ke kodovaní, <math>p</math> - usporadana posloupnost <math>n</math> vah (pravdepodobností) <math>p[i]</math> (<math>1 ≤ i ≤ n</math>) jejich vyskytu ve zprave
:'''Vystup:''' kodova slova dana zretezením ohodnocení hran na cestach od korene k jednotlivym listum binarního stromu
* výsledný strom se nazývá Huffmanův, výsledný kód je prefixový
* místo pravděpodobností můžeme použít i četnosti znaku, ohodnocení hran stromu pomocí 0 a 1 je konvencí (je tudíž možno použít i ohodnocení opačné)
* Huffmanuv i Shannon-Fanův kód je možné generovat v čase <math>O(n)</math>
<pre>
BEGIN
∀ jednotku i vytvoř list o(p[i])
(uzel ohodnocený pravděpodobností p[i]);
k := n;
WHILE k ≥ 2 DO
BEGIN
vyber z p dvě nejmenší nenulové p[r] a p[s], kde r ≠ s;
q := p[r]+p[s];
vytvoř uzel ohodnocený q;
hranám < o(q); o(p[r]) > a < o(q); o(p[s]) >
přiřaď ohodnocení 0 a 1;
p[r] := q; p[s] := 0; k := k-1
END
END
</pre>
====Dynamické (Adaptivní) Huffmanovo kódování====
[[Image:ahc.png|right|thumb|394px|Sourozenecká vlastnost stromu: ∀ uzel má sourozence a četnosti v uspořádání podle č.šipky neklesají]]
* strom reorganizován podle toho, jak se mění pravděpodobnosti v průběhu kódování (tj. poruší se sourozenecké pravidlo)
* nepředpokládají se žádné informace o pravděpodobnostech zdrojových jednotek (strom ale můžeme inicializovat vstupní abecedou)
=====FGK (Faller, Galagher, Knuth)=====
:'''Vstup:''' daný Huffmanův strom <math>T_1</math>, uzel <math>o</math>
:'''Výstup:''' modif. Huff. strom <math>T_2</math>
<pre>
BEGIN
current:=o;
WHILE current ≠ root DO
BEGIN
vyměň uzel a jeho příp.podstrom v current s uzlem o', který má nejvyšší pořadí mezi uzly se stejnou frekvencí;
četnost[current]++
current:=predcessor(current)
END
END
</pre>
* <math>AL_{HD} ≤ 2 . AL_{HS}</math>, kde <math>AL_{HD}</math> je průměrná délka kódových slov dynamického Huffmanova kódování a <math>AL_{HS}</math> statického
💡 '''Λ (Vitter)''' - složitější úprava FGK s těmito vlastnostmi:
* počet výměn podstromů je nejvýše <math>1</math>, přidá se escape sekvenci pro první výskyt nového znaku
* minimalizuje nejen <math>\sum^n_{i=1} d[i] . p[i]</math> ale i <math>\sum^n _{i=1} d[i]</math> a <math>max_i d[i]</math>
* <math>AL_{HD} ≤ AL_{HS} + 1</math> (nejlepší hodnota mezi dynamickými Huffmanovými metodami)
{{Zdroje|
* Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf#40 OZD II] (od slajdu 40) (statické, adaptivní kódování)
* Dobře popsáno také na stránkách k [http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/ DIS] 530
* http://www.stringology.org/DataCompression/fgk/index_en.html
* http://www.stringology.org/DataCompression/ahv/index_en.html
}}
=== aritmetické kódování, ===
:''viz [[wen:Arithmetic coding]]''
:Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf#47 OZD II] (od slajdu 47)
:Dokumenty k [http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/11/dis11_v1.html DIS] (myslím, že v posledním kroku příkladu je chyba)
=== LZ algoritmy, ===
Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf#56 OZD II] (od slajdu 56) (LZ77, LZSS, LZ78, LZW a další)
=== komprese bitových map, ===
:Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf#92 OZD II] (od slajdu 92)
* pomocí Huffmanova kódování
** kódováním posloupností pevné délky
** kódování běhů (posloupnost nul ukončených jedničkou apod.)
=== rídkých matic, ===
[http://www.ksi.mff.cuni.cz/~zemlicka/pdf/2011/matcomp.pdf OZD II]
=== Burrows-Wheelerova transformace. ===
=== <strike>Reprezentace celých čísel</strike> (asi už není součástí okruhů) ===
Slajdy k [http://www.ksi.mff.cuni.cz/~zemlicka/pdf/compression.pdf OZD II] (od slajdu 21) (Fibonacciho, Eliasovy kódy, fázování)
{{Statnice_I2}}
