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. ==
== Modely a vlastnosti transakcí: uzamykací protokoly, casová razítka. ==
{{Zkazky|
* '''Uzamykaci protokoly, casova razitka (Riha)''' - Serializovatelnost rozvrhu, legalni rozvrh, dobre formovane transakce. Nevedel jsem si rady s pohledovou x konfliktovou ekvivalenci (nejak tak?). Dale casova razitka, jako priklad stromoveho protokolu jsem dal B-stromy se zamykanim a na zaver byla otazka na optimisticke algoritmy.
}}
===Modely a vlastnosti transakcí===
====Vlastnosti transakcí====
;Databázové transakce musí splňovat tzv. vlastnosti ACID (''viz [[wen:ACID]]''):
:'''A'''tomicity - Transakce proběhne celá, nebo vůbec.
:'''C'''onsistency - Při provádění transakcí se DB převádí z jednoho konzistentního stavu do jiného.
:'''I'''solation - Transakce o sobe navzájem nevědí, jako by běžela jen jedna.
:'''D'''urability - Změny commitnuté transakce jsou trvalé.
*Rozvrhy (neboli historie) maji ruzne vlastnosti. Tedy rozvrh muze byt (formalne viz [[File:Transakce-typy historii.pdf]]):
**'''Zotavitelny''' (RC) - pokud transakce T1 cte nepotvrzena data zapsana transakci T2 (data zapsana jinou transakci T2, ktera jeste neskoncila), pak komit transakce T1 nastane po transakci T2. Pokud ne, transakce T1 by mohla uspesne skoncit (komitovat), ale T2 ma pritom abortovat po komitu T1 -> T1 uspesne skoncila, pritom ale cetla data, ktera se nikdy nepotvrdily (rollback neni mozny a rozvrh neni zotavitelny).
**'''Predchazet kaskadovemu abortu''' (ACA) - pokud transakce cte data, museji byt potvrzena (po COMMITu).
**'''Striktni''' (ST) - pokud transakce T1 zapise data, jina transakce T2 muze pozdeji cist/prepsat tyto data pouze pokud T1 skoncila (ABORTem nebo COMMITem).
**'''Pohledove usporadatelny''' (VSR), pokud je pohledove ekvivalentni se seriovym rozvrhem na stejnych transakcich. Dva rozvrhy S1, S2 jsou '''pohledove ekvivalentni''', pokud splnuji nasledujici:
***Pokud transakce Ti cte pocatecni hodnotu v S1, cte ji i v S2
***Pokud transakce Ti cte hodnotu zapsanou Tj v S1, cte ji i v S2
***Pokud transakce Ti provede posledni zapis hodnoty v S1, provede jej i v S2
**'''Konfliktove usporadatelny''' (CSR) prave tehdy, kdyz precedencni graf neobsahuje cykly.
***''Precedenční graf'' historie H nad množinou transakcí {T1, .., Tn} je orientovaný graf
****Kde uzly jsou transakce z KOMITOVANE projekce historie H
****Hrana mezi uzlem Ti a Tj existuje prave tehdy, kdyz operace z Ti předchází a je v konfliktu s nějakou operací z Tj (v konfliktu jsou operace RW (read-write), WR (write-read) a WW (write-write))
**[[File:Vztahy_mezi_rozvrhy.png]]
**'''Usporadatelny''' (ci '''serializovatelny'''), pokud jeho vykonani vede ke konzistentnimu stavu databaze. Tedy výsledný stav odpovídá nějakému sériovému rozvrhu.
***Pozor, nyní uvažujeme pouze potvrzené (committed) transakce a statickou databázi (neexistuje vkládání a mazání objektů, pouze čtení a aktualizace)
***Zcela obecně (včetně akce abort a dynamické povahy DB) se pak definuje konzistence zachovávající uspořádatelnost jako ''pohledová uspořádatelnost''
*Pokud je historie CSR, tak je i usporadatelna, tedy CSR ⊂ usporadatelna (tvrdil p. Lokoc)
*Testování uspořádatelnosti pro pohledovou ekvivalenci je ''NP-úplný problém'', takže se v praxi nepoužívá - lze nahradit konfliktově uspořádatelnými a zotavitelnými rozvrhy
[[File:models_of_transactions.PNG]]
====flat model====
Omezení transakčního modelu flat transactions, která mohou bránit jeho praktickému využití v některých transakčních systémech:
*Mají příliš velký rozsah. Abortu po stotisící operaci se nedá nijak zabránit. To se dá přičíst tomu, že nemají žádnou vnitřní strukturu.
*Žádný dílčí neúspěch není tolerován. Pokud je špatně jediné číslo konta u deseti tisíc zaměstnanců nějakého podniku, pak transakce odeslání mezd všem zaměstnancům kvůli této chybě abortuje.
*Flat transakce nemohou spolupracovat s jinými transakcemi. Nemohou s nimi sdílet data (pro sdílení dat neexistují žádná primitiva nebo pravidla), nemohou být vzájemně propojeny přes signifikantní události.
*Neřeší přirozený problém vnoření do sebe. Běžné programovací jazyky umožňují vnořovat volání procedur, take se může stát, že zavoláme v transakci proceduru, která zahájí novou vnořenou transakci.
====Savepointy (SP)====
*podporuje MS SQL Server 2008 a Oracle také commitovány.
*rollbacky se neprovadi az na zacatek, ale k jiz ulozenym savepointum (první SP většinou po startu transakce).
*dopředný rollback
**rollback k rollbacknutým stavům
**rollbacky se pak stávají součástí historie
*neřeší tvrdé výpadky systemu -> po opetovnem nabehnuti systemu se musi transakce provest znovu, ne od posledniho savepointu
====Zřetězené transakce====
*Programátor se po části výpočtu vzdá možnosti rollbacku nad touto částí, tj. komituje
*Nechce ale ztratit kontext, kurzory, atp.
*Tj. je potřeba zavést atomickou operaci ''Chain work'' = Commit + Begin
====Hnízděné transakce====
výpočet jako hierarchie transakcí, zobecnění SP
:☀ podporuje MS SQL Server 2008
Pravidla pro podtransakce:
*COMMIT pravidlo - po potvrzení podtransakce jsou výsledky dostupné jen v rodičovské transakci, podtran. skutečně potvrdí až s potvrzením kořenové transakce
*ROLLBACK pravidlo - pokud je podtransakce zrušena, bere sebou všechny své potomky (i když už lokálně potvrdili), když je zrušena kořenová transakce
*pravidlo viditelnosti změn - zmeny v podtransakci jsou po lokálním COMMITu vidět jen v rodiči, objekty držené rodičem jsou přístupné potomkům, potomci jsou izolovaní v případě souběžného spuštění
*rodič rozhoduje o řešení zrušení potomka (restartovat, zvolit alternativní výpočet, abortovat)
ACID vlastnosti podtransakci jsou splnene jen částečně: A - podtr. jsou A jen z rodiče, C - podtr. jsou C vzhledem lok.fci., I - silná, D - neplatí kvuli commit pravidlu
{{TODO|obrázky}}
====Distribuované transakce====
viz nize ve vlastni casti
Plánování, izolace běhu transakcí:
=== Uzamykací protokoly ===
:''viz [[wen:Concurrency control#Concurrency control mechanism]]''
*2PL protokol (dvoufázové zamykání)
**'Klasicky' 2PL protokol
***pokud už transakce o nějaký zámek požádala a uvolnila ho, nesmí o žádný požádat znovu = 2 fáze - zamykání a odemykání (tyto 2 faze se tykaji vzdy kazde transakce zvlast, ne celeho rozvrhu)
***takovýto rozvrh je konfliktově uspořádatelný, ale negarantuje zotavitelnost rozvrhu a tim padem ani ACA a ST (=> striktní 2PL)
**Striktní 2PL protokol (S2PL)
***všechny zámky jsou uvolněny až při ukončení transakce
***generuje striktni rozvrh (tim padem predchazi kaskádovému rušení transakcí a je i zotavitelny)
***rozvrh je konfliktově uspořádatelný (jako klasicky 2PL)
**Konzervativní 2PL protokol
***všechny zámky které bude potřebovat si vyžádá hned na začátku a nebo alespoň požádá o jejich rezervaci
***rozvrhy stejne jako u klasickeho 2PL - jsou CSR, ale ne RC (tudiz ne ACA i ST)
***vyhoda: nenastane deadlock
***není používán, protože se nemusí vědět, které zámky bude potřebovat a navíc je zde vysoká režie uzamykání
{{TODO|tabulka, obrázky}}
=== Časová razítka ===
:''viz [[wen:Timestamp-based concurrency control#Informal]]''
:Nepoužívá zámky, zatím se v komerčních systémech moc neujalo
:Je založeno na časovém uspořádání ('''T'''ime '''O'''rdering)
:Pokud je H historie reprezentující výpočet plánovaná pomocí TO pravidla, pak je H uspořádatelná. H je dokonce CSR (viz [http://www-db.in.tum.de/teaching/ws1213/ts/chapter4.pdf odkaz]), z cehoz plyne usporadatelnost
;Zakladni TO pravidlo
:Každá transakce dostane unikatni časové razítko (TS(T1), TS(T2)) a následně během rozvrhování je kontrolováno pořadí konfliktních operací. Pokud TS(T1) < TS(T2) a A1 (akce T1) je v konfliktu s A2 (akce T2) musí A1 nastat před A2, jinak je T1 restartována.
:Nezajistuje zotavitelnost. Pro dosažení zotavení je potřeba implementovat bufferování všech zápisů dokud transakce nepotvrdí.
;Striktní TO pravidlo
:Kazda transakce pred zapisem danou polozku zamkne (pro zapis i cteni), aby se soucasne nesahalo do DB, a odemkne az skonci (COMMITem/ABORTem). V základním TO pravidle se zamek uvolni hned po potvrzeni zapisu databazi
:Zajistuje zotavitelnost (vysledny rozvrh je striktni z cehoz vyplyva, ze je zotavitelny)
:Nemuze nastat deadlock (cekaji vzdy transakce s vyssim razitkem). Pri zakladnim TO pravidle deadlock take nenastava - neblokuje se nic (jen objekt pro rychle precteni z DB)
;Konzervativní TO pravidlo
:Pozdržet některé operace (čekat na operace starších transakcí), aby nedochazelo k restartovani transakci.
:???Pry muze nastat deadlock (viz [http://www.inf.unibz.it/dis/teaching/DDB/ln/ddb09.pdf zde]) kvuli temto zdrzenim - zvlastni, kdyz cekaji novejsi transakce na ty starsi (starsi by nemela cekat na novejsi)???
== Izolace transakcí, alokace prostředků (zámky, granularita zamykání, dvoufázové uzamykání, deadlock) ==
{{Zkazky|
* '''Izolacie transakcii (Skopal)''' - Ak uz je spominane nizsie, p.Skopal skusa velmi zahadnym sposobom ked polozi otazku a vy netusite co chce pocut. Po 15 minutach ked uz ste spotili aj kravatu zisite ze sa pyta na uplnu trivialitu, ktoru ovladate ale bohuzial za tych 15 minut ste nezistili ze sa pyta prave na to. Toto bolo najtazsia cast mozno aj preto ze pri uceni som to preskakoval s tym ze je to lahke a potom som sa tazko z hlavy vymyslal definicie.
}}
:''viz [[wen:Isolation (database systems)]]'', [[wen:Lock (database)]], [[wen:Two phase locking]], [[wen:Deadlock]]
;Úrovně isolace transakcí
:Obecne jsou 4 druhy (definovane standardem SQL92). Jsou to (viz [http://www.602.cz/datainc/produkty/winbase/napoveda/html/sql27ag9.htm tabulka]):
::''READ UNCOMMITTED'' - zabranuje prepsání nepotvrzených dat
::''READ COMMITTED'' - zabraňuje navíc čtení nepotvrzených dat
::''REPEATABLE READ'' - zabraňuje navíc neopakovatelnému čtení (nestane se tedy, ze dve stejna cteni vrati ruzne hodnoty)
::''SERIALIZABLE'' - zabraňuje navíc fantomům
:Ne vždy je potřeba uroven SERIALIZABLE, např. pro statistické dotazy (pro vypocet průměrneho platu z 1000 zaměstannců mi nevadí neopakovatelné čtení), pro účetnictví už by to byl problém
Existuje více strategií, jak zajistit izolaci transakcí
*'''Zamykání objektů'''
**viz vyse
*'''Časová razítka'''
**viz vyse
*'''Pomocí precedenčního grafu (PG)'''
**nepoužívá zámky, zatím se v komerčních systémech moc neujalo
**je postaveno na udržování lehce modifikovaného precedenčního grafu, ve kterém se hlídá acykličnost
**modifikovaný precedenční graf (MPG)
***neobsahuje všechny komitované transakce (jsou odebrány takové, které byly dávno ukončené)
***uzly všech aktivních transakcí jsou uloženy (až na abortované a komitované)
**existuje ''základní'' a ''konzervativní'' plánování pomocí PG. Vytváří uspořádatelné historie, které ale nejsou RC (tedy ani nejsou ACA a ST)
*'''Certifikace (optimistické řešení)'''
**používá se tam, kde dochází velmi zřídka k jakýmkoliv konfliktům, naopak tam kde je více konfliktů použít nelze. Korektnost se testuje až při komitu
**certifikace může být založena na různých algoritmech – 2PL, TO, PG certifikátory
**skládá se ze tří fází
***Read - transakce čte z databáze, provádí různé operace, ale vše zapisuje do svého prostoru (databázi nemění)
***Validation - transakce předloží co vytvořila a SŘBD zkontroluje, zda to není v konfliktu s jinou transakcí, pokud ano, transakce je zrušena, v opačném případě potvrzena
***Write - vše je zapsáno do db
*'''Integrované plánovače'''
**asi jakesi vylepseni stavajicich planovacu. Je to ukazano na prikladu TO a '''Thomas Write pravidla''':
***to rika, ze kdyz prepisuju neco, co se vubec neprecetlo (jinak by nastal rollback kvuli tomu cteni) a pritom je to v poradi tech razitek, tak ten drivejsi zapis lze ignorovat. Rozdil je nicmene v tom, ze ten naivni pristup zajisti ''konfliktovou usporadatelnost'', kdezto ten Thomas Write Rule nutne nemusi, nicmene zajisti ''pohledovou usporadatelnost'', coz staci.
*'''Multiversion data'''
**existuje vice verzi hodnot nejakeho objektu, takze prepsanim nejake hodnoty se neztrati ta minula, ale jsou znamy obe verze. Přestávají být konfliktní w/w dvojice – nejsou nad stejnou proměnnou
**s tím jsou ale spojené nové problémy - plánovač musí doplnit operaci čtení o informaci, jakou verzi číst (od toho by měl být uživatel odstíněn)
**může být založena na různých algoritmech – 2PL, TO, PG
'''Zámky'''
Transakce, která chce přistoupit k datům musí nejdříve tyto data zamknout
;Typy
:''Sdílený zámek (shared lock)'' - udělován při čtení dat
:''Exkluzivní zámek (exclusive lock)'' - udělován při aktualizaci dat
:Konkrétní implementace DB obsahují mnoho dalších typů zámku, MSSQL např. implementuje tzv. ''range lock'', ''intent lock'', ''schema lock'', …
Platí, že exkluzivní zámek je vzdy konfliktní s jinym (sdilenym/exkluzivnim). Jen dva sdilene zamky jsou v poradku
;Zajištění izolace pomocí zamykání
:READ UNCOMMITTED - '''nepoužívají se''' zámky pro čtení dat ('''shared lock'''), S2PL na zápis
:READ COMMITTED - '''používají se''' zámky na čtení ('''shared lock'''), S2PL na zápis
:REPEATABLE READ - čtení i zápis S2PL
:SERIALIZABLE - čtení i zápis S2PL, navic se používají speciální typy zámků, které umožňují zamknout interval ('''range lock''') a ne pouze konkrétní hodnoty
;Fantom
:Jedna transakce pracuje s množinou zaznamu a druhá ji mění - maze/pridava. Takto necekane pridany zaznam se nazyva '''fantom'''
:Výskyt v dynamických DB (dynamicke DB podporuji vkládání a mazání záznamů)
:Triviálně lze řešit zamknutím celé DB -> SR rozvrh
:V praxi se spíš řeší jemnějším zamykáním (melo by stacit vedet jen, ze existuji)
::''Predikátové zámky'' - napr. se zamknou vsechny zaznamy lidi, kteri jsou starsi nez urcity vek
::''Rozsahové zámky'' - vhodné pro struktury využívající uspořádání záznamů
::''Granulované zámky'' - používají se pro data organizovaná do logických hierarchií, kde zámek na určitém uzlu hierarchie implikuje zámky na všech potomcích
'''Deadlock (uváznutí)'''
transakce na sebe čekají v kruhu (čekají navzájem na nějaký zdroj a nechtějí si dát ten svuj)
'''podmínky pro vznik Deadlock (musí být splněny všechny)'''
*vzájemné vyloučení - prostředek může být přidělen pouze jednomu procesu
*držení prostředků
*neodnímatelnost
*čekání v kruhu
'''Detekce, řešení'''
*detekce: cyklus v grafu waits-for
*abort + restart transakce z cyklu podle nějakého kriteria (např. nejnovější)
'''snížení frekvence uváznutí (ne její řešení)'''
*lock downgrade - pokud už nepotřebuji výhradní zámek, snížím na sdílený
*lock upgrade - pokud potřebuju výhradní a mám sdílený, mám větší právo, než ten co nemá nic a chce výhradní
'''prevence deadlocku'''
*konzervativní 2PL
*časové razítko (klasicke nebo striktni, asi ne konzervativni)
*prioritizování/timestamp (pro 2PL)
**každá transakce dostane nějakou prioritu (např. časové razítko - čím starší, tím vyšší priorita)
**dvě možnosti řešení za použití priorit
***wait-die: pokud chce transakce T1 zámek a už ho má někdo jiný (T2), pokud má T1 vyšší prioritu, čeká, jinak zemře
***wounds-wait: pokud chce transakce T1 zámek a už ho má někdo jiný (T2), pokud má T1 vyšší prioritu, T2 zemře, jinak T1 čeká
**rušeným transakcím je třeba zvyšovat prioritu aby nebyly pořád utiskované
== Distribuované transakce. ==
{{Zkazky|
* '''Distribuované transakce (Richta)''' - Stačilo jen základy. Centralizovaný/decentralizovaný přístup. Dvoufázový potvrzovací protokol.
}}
''viz [[wen:Distributed transaction]]''
''viz [[wen:Two-phase commit protocol]]''
Ve stručnosti:
:říká se jim také globální transakce
:jsou to transakce, které pracují s '''více uzly najednou''' (s '''více databázemi v síti''' apod.). Napr.:
::BEGIN TRANSACTION
::UPDATE amount = amount - 100 IN bankAccounts WHERE accountNr = 1
::UPDATE amount = amount + 100 IN someRemoteDatabaseAtSomeOtherBank.bankAccounts WHERE accountNr = 2
::COMMIT
:musejí splňovat ACID (jako jakékoliv jiné transakce)
:celkem jednoduchý algoritmus, který problém řeší je "Dvoufázový commit"
;Zamykani
:V distribuovanych systemech muze byt sprava zamku bud centralni nebo v kazdem uzlu pro lokalni data.
::'''centralni''' - uviznuti je mozne detekovat pomoci konstrukce grafu vzajemnych zavislosti, nevyhodou jsou vysoke komunikacni naklady a zranitelnost systemu vypadkem uzlu spravujiciho zamky.
::'''lokalni''' - obvykle vsak lze graf vzajemnych zavislosti konstruovat bez prilisnych pridavnych nakladu alespon pro lokalni podtransakce (lokální waits-for graf na každém uzlu ale nezachycuje globální závislosti). Pro globalni transakce se casto urcuje casovy limit, jehoz vyprseni se povazuje za uviznuti.
=== Dvoufázový commit ===
Neboli 2PC (two-phase commit)
;1.fáze (commit-request phase)
:kordinátor (transakční manažer) pošle všem uzlům dotaz, který je zde potřeba vykonat
:uzly vykonají vše až do doby, kdy by měly commitovat/abortovat
:každý uzel pošle svůj výsledek koordinátorovi (YES/NO)
;2.fáze (commit phase)
:pokud koordinátor dostal od všech uzlů odpověď YES (success)
:*koordinátor pošle commit zprávu všem uzlům
:*všechny uzly uvolní své zdroje a zámky
:*všechny uzly pošlou koordinátorovi výsledek dotazu
:*koordinátor vše skompletuje
:pokud koordinátor dostal alespoň jedno NO (failure)
:*koordinátor všem uzlům pošle abort zprávu
:*každý z uzlů udělá vlastní abort a uvolní zámky a zdroje
:*všechny uzly pošlou koordinátorovi výsledek dotazu (??? nechápu ale k čemu to je ???)
:*poté co koordinátor obdrží výsledky abortuje celou transakci
=== Stromový 2-fázový commit (Tree two-phase commit protocol) ===
Obdoba předchozího jen s rozdílem, že koordinátor je kořenem stromu a vše se děje na stromové struktuře - commity jsou sbírány do uzlu stromu a až jsou všechny, jsou propagovány víš až ke kořeni. Oproti tomu abort je propagován hned.
V pripade ''read-only distribuovanych transakci'' nemusi ucastnik cekat na vysledek hlasovani (staci jen 1. faze) a po 1. fazi uz uvolni zamky. Koordinator nemusi ucastnikovi zasilat vysledek hlasovani
Problémem 2PC protokolu je, že každý z uzlů čeká, až dodělá práci poslední z uzlů, čímž dost dlouho blokuje.
== Zotavení z chyb, žurnály. ==
{{Zkazky|
* '''Zotavení a žurnály (?)''' - popsal jsem dva typy způsobů jak to provádět (visí to někde, snad na wiki), proč se to stane a co se musí zajistit. K tomu po mě chtěl zkoušející popsat v základu co je to transakce.
* '''Zotavení po chybě systému (Říha)''' - Zmínil jsem ukládání operací v transakcích do logu (žurnál), dále jak a kdy se ukládá log na disk, jak probíhá samotné zotavení (UNDO, REDO - kdy co) a ještě jsem popsal politiky zápisu nových dat do DB (okamžitý/odkládaný zápis). Zkoušel mě pan Říha, který byl velice příjemný, ale chtěl vědět ještě více informací (jak se udržuje identifikace transakcí v logu, kdy se ukládají savepointy, ...) a já jsem se do toho trochu zamotal a některé věci popletl, ale nakonec taky v pohodě.
}}
[http://siret.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_10.pdf Transakce - uzamykací protokoly, zotavení] (Databázové systémy)
Zotavení po havárii systému provádí recovery manager, zajišťuje:
*atomicitu (odvolání akcí, pokud byla transakce zrušena - undo)
*trvanlivost (zapsání potvrzených akcí i když systém havaroval)
Zotavení je jedna z nejsložitějších součástí SŘBD, používá se algoritmus '''ARIES''' (implementovan napr. IBM DB2, MS SQL, Informix, Sybase, Oracle) - spustí se po restartu havarovaného systému.
*tři fáze ARIES
**Analysis - identifikují se dirty pages (stránky modifikované, ale nezapsané v okamžiku havárie) v bufferu a transakce, které byly aktivní v okamžiku havárie
**Redo - zopakují se všechny akce od příslušného místa (zapsané v logu) tak aby se databáze dostala do stavu před havárií
**Undo - odvolají se všechny akce těch transakcí, které nebyly potvrzeny (commitnuty), tedy databáze obsahuje pouze potvrzené transakce
Log algoritmu ARIES se označuje journal, každá změna databáze je nejdříve uložena zde (právě kvůli možné havárii). Po restartu algoritmus vystopuje všechny akce před havárií a znovu je provede tak, aby se db dostalo do stavu před havárií. Nepotvrzené akce jsou zrušeny. Při rušení je opět vše logováno pro případ opětovné havárie při provádění ABORT.
Take se zalohuji zurnaly. Predpokladame zalohovani v dobe nerozjetych transakci a tudiz kdyz se DB zotavuje ze zalohy zurnalu (neco se s puvodnim zurnalem stalo), nedela se faze Undo.
== 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.
}}
{{TODO|přidat obrázkové příklady- připadně co zakódovat}}
====Staticke Huffanovo 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í 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]
* 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}}
