hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
mgr-szz:in-pos:3-pos [2019/06/08 11:48] lachmanfrantisek kódování |
mgr-szz:in-pos:3-pos [2020/04/12 16:56] |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== IN-POS 3. Databáze ====== | ||
| - | ===== Zadání ===== | ||
| - | |||
| - | * Kódování dat, kompresní kódování dat, organizace souborů dat. | ||
| - | * Indexování a hašování, bitmapové indexy, dynamické hašování. | ||
| - | * Vyhodnocení dotazů, transformační pravidla, statistiky a odhady. | ||
| - | * Optimalizace dotazů a schématu. | ||
| - | * Zabezpečení báze dat, přístupová práva. | ||
| - | * Transakce, řízení souběžných transakcí, systémy obnovy transakcí po výpadku. | ||
| - | |||
| - | |||
| - | * PV062, PA152, PA150 | ||
| - | |||
| - | ===== Vypracování ===== | ||
| - | |||
| - | |||
| - | ==== Kódování dat ==== | ||
| - | |||
| - | **Kódování** = Proces nahrazování symbolů (resp. jejich posloupností) zprávy symboly (resp. jejich posloupností) nabývajících znaků cílové (kódovací) abecedy. | ||
| - | |||
| - | <box 90% red|Množství informace> | ||
| - | Množství získané informace odpovídá velikosti odstraněné neurčitosti získáním informace. | ||
| - | |||
| - | <m>i(A) = - log P(A)</m> | ||
| - | |||
| - | Pro <m>log_2</m> je jednotkou **bit**. | ||
| - | |||
| - | </box> | ||
| - | |||
| - | <box 90% red|Entropie> | ||
| - | |||
| - | Neurčitost zdroje zprávy je rovna množství informace v ní obsažení. (Neurčitost je přijetím zprávy odstraněna.) | ||
| - | |||
| - | <m>H(X) = sum{i=1}{s}{p_i log_2 p_i}</m> | ||
| - | |||
| - | |||
| - | * Každý stav s pravděpodobností svého výskytu přispívá do neurčitosti svojí neurčitostí. | ||
| - | * Vztah nabývá maxima pro <m>p_1 = ... = p_s</m>, kde <m>p_i = 1/s</m>. | ||
| - | |||
| - | </box> | ||
| - | |||
| - | * **Abeceda** = konečná množina znaků (prvků abecedy, písmen,...) | ||
| - | * **Kódové slovo** = slovo (posloupnost znaků) v kódové abecedě | ||
| - | * **Kódování** = funkce <m>K : A -> A^{+}_C</m> | ||
| - | * **Kód** = kódem daného kódování se rozumí obor hodnot zobrazení K | ||
| - | |||
| - | |||
| - | === Klasifikace kódů === | ||
| - | |||
| - | * Kód s kódovými slovy **pevné** délky. | ||
| - | * Kód s kódovými slovy **proměnlivé** délky. | ||
| - | * prefixový, sufixový kód | ||
| - | * **stupeň** (rate) kódu = průměrný počet bitů použitých pro kódování zdrojových znaků v tomto kódu. | ||
| - | * **optimální kód** má stupeň minimálně převyšující množství informace obsažené v symbole zdrojových zpráv. | ||
| - | * **Nesingulární kód** = jeho kódovací funkce je prostá | ||
| - | * **Jednoznačně dekódovatelný kód** = Všechny možné řetězce jsou jednoznačně dekódovatelné | ||
| - | * prefixové, sufixové a blokové kódy jsou jednoznačně dekódovatelné | ||
| - | * **Prefixový kód** = Bezprostředně jednoznačně dekódovatelný kód. | ||
| - | |||
| - | <box 90% blue|Minimální kódování> | ||
| - | |||
| - | * Fanovo kódování | ||
| - | * kódová slova znaků mají délky úměrné množství informace, které znaky nesou. | ||
| - | |||
| - | Př.: | ||
| - | |||
| - | * A = 1 , C = 01 , G = 000 a T =001 | ||
| - | * např. řetětzec 8 symbolů ACATGAAC je kódovaný 14 bity: | ||
| - | |||
| - | 10110010001101 | ||
| - | |||
| - | * tj. v průměru <m>14/8 = 1.75</m> b/symbol | ||
| - | |||
| - | </box> | ||
| - | |||
| - | |||
| - | === Kompresní kódování dat === | ||
| - | |||
| - | Cílem: | ||
| - | |||
| - | * minimalizace stupně kódu | ||
| - | * při schopnosti on-line dekódování slov bez vkládání separátorů | ||
| - | |||
| - | <box 90% red|Kraftova nerovnost> | ||
| - | Prefixový q-ární kód s délkami kódových slov d1,d2,...,dm existuje právě tehdy, když je splněna Kraftova nerovnost: | ||
| - | |||
| - | <m>sum{i=1}{m}{q^{{-d}_{i}}} <= 1</m> | ||
| - | |||
| - | </box> | ||
| - | |||
| - | <box 90% red|McMillanova veta> | ||
| - | Kraftova nerovnost platí pro libovolné jednoznačně dekódovatelné kódování. | ||
| - | </box> | ||
| - | |||
| - | == Eliasovy kódy == | ||
| - | |||
| - | |||
| - | <box 90% blue|Eliasův kód> | ||
| - | |||
| - | Kódování celých čísel u kterých není předem známá horní hranice. | ||
| - | |||
| - | - Zapíšeme číslo dvojkově. | ||
| - | - Odečteme 1 od počtu bitů zapsaných v kroku 1 a na začátek připojíme takový počet nul. | ||
| - | |||
| - | </box> | ||
| - | |||
| - | <box 90% blue|Eliasův kód C1> | ||
| - | |||
| - | Prefix 0 určuje délku binární reprezentace. | ||
| - | |||
| - | Př.: | ||
| - | |||
| - | * n=38, <m>hat{B}(38)= 00110_2</m> <m>|B(38)|=6</m> | ||
| - | * => <m>C_1(38)</m> = <color red>000001</color>00110 | ||
| - | |||
| - | </box> | ||
| - | |||
| - | <box 90% blue|Eliasův kód C2> | ||
| - | |||
| - | Přeuspořádání C1. | ||
| - | |||
| - | * Bity nul se rozptýlý do kódového slova a na konec se přidá 1. | ||
| - | |||
| - | Př.: | ||
| - | |||
| - | * <m>C_2(5)</m> = 0<color red>0</color>0<color red>1</color>1 | ||
| - | |||
| - | </box> | ||
| - | |||
| - | <box 90% blue|Eliasův kód C3> | ||
| - | |||
| - | Vyjádření délky kódového slova pomocí C2. | ||
| - | |||
| - | * Bity nul se rozptýlý do kódového slova a na konec se přidá 1. | ||
| - | |||
| - | Př.: | ||
| - | |||
| - | * <m>C_3(50)</m> (<m>50_{10} = 110010_2</m>) | ||
| - | * <m>|B(50)|</m> = 6 bitů | ||
| - | * <m>C_1(6)</m> = <color red>001</color>10 | ||
| - | * <m>C_2(6)</m> = <color red>0</color>1<color red>0</color>0<color red>1</color> | ||
| - | * <m>C_3(50)</m> = <color red>01001</color>10010 | ||
| - | </box> | ||
| - | |||
| - | == Komprese == | ||
| - | |||
| - | |||
| - | * **Neztrátová komprese (Lossless Compression)** | ||
| - | * dekompresí se získají originální data | ||
| - | * Cílem je zobrazení informace do bitového prostoru co nejméně převyšujícího množství informace obsažené v originálních datech. | ||
| - | * Typicky komprese textů. | ||
| - | |||
| - | |||
| - | * **Ztrátová komprese (Lossy Compression)** | ||
| - | * Zefektivnění procesu a výsledku komprese za cenu snížení požadavků na přesnost rekonstrukce. | ||
| - | * Informace nevýznamná pro následující zpracování se odstraňuje definitivně. | ||
| - | * Typicky komprese obrázků, zvuku,... | ||
| - | |||
| - | |||
| - | * Kompresní a dekompresní (rekonstrukční) algoritmus. | ||
| - | |||
| - | * **Komprese** = Kódování zprávy délky P(X) [b] na zprávu délky L(X) [b] | ||
| - | * cílem je dosažení L(X) << O(X) | ||
| - | * ideálně L(X) -> H(X) (neurčitost zprávy; méně bity nelze zakódovat beztrátově) | ||
| - | * **Kompresní poměr** = L(X)/O(X) | ||
| - | * **Kompresní faktor** = O(X)/L(X) | ||
| - | * **Kompresní zisk** = (O(X)-L(X))/O(X) | ||
| - | * **Redundance zprávy** = R(X) = O(X) - H(X) | ||
| - | * **Redundance komprimované zprávy** = R'(X) = L(X) - H(X) | ||
| - | |||
| - | * **Statická komprese** | ||
| - | * Neměnná procedura, model. | ||
| - | * **Adaptivní komprese** | ||
| - | * Procedura komprese se dynamicky mění. | ||
| - | |||
| - | * **Fyzická komprese** | ||
| - | * Ignoruje se význam komprimovaných dat. | ||
| - | * **Logická komprese** | ||
| - | * Pro dosažení lepších výsledků se zohledňuje/využívá význam komprimovaných dat. | ||
| - | * Převážně ztrátová komprese. | ||
| - | |||
| - | == Kompresní metody == | ||
| - | |||
| - | * **Základní metody** | ||
| - | * Brailovo písmo | ||
| - | * Baudotův kód: 5bit kód, číslicová/písmenová změna | ||
| - | * RLE (Run Length Encoding): náhrada opakujících se sousedních symbolů čítačem opakování a specifikací opakovaného symbolu | ||
| - | * Kódování podle Bentleyho (Move-to-Front Coding): Dynamicky se tvořící abeceda | ||
| - | * lokální adaptivita | ||
| - | |||
| - | * **Statistické metody** | ||
| - | |||
| - | <box 90% blue|Shannon-Fanovo kódování> | ||
| - | * Metoda na vytvoření prefixového kódu proměnné délky pro známou množinu znaků a četností. | ||
| - | * Reprezentace binárním stromem na základě dělení posloupnosti na poloviny dle četností. | ||
| - | </box> | ||
| - | |||
| - | <box 90% blue|Huffmanovo kódování> | ||
| - | * Metoda na vytvoření kódu s minimální redundancí. | ||
| - | * Tvorba stromu opačným směrem než Shannon-Fannova metoda. (Od spoda nahoru.) | ||
| - | </box> | ||
| - | |||
| - | <box 90% blue|Aritmetické kódování> | ||
| - | Nekóduje jednotlivé symboly zprávy, ale používá jedno kódové slovo pro zakódování celé zprávy. | ||
| - | * Kódem celé zprávy je číslo z intervalu <0,1) | ||
| - | </box> | ||
| - | |||
| - | * **Slovníkové metody**: Vytváří se slovník dříve přečtených řetězců výstupem jsou indexy do slovníku. | ||
| - | |||
| - | <box 90% blue|LZ77> | ||
| - | * Jako slovník se používá jistá zpracovaná část zdrojového textu, vybíraná klouzajícím oknem, kódují se v něm obsažené řetězce proměnlivé. | ||
| - | * Výstupem je trojice: | ||
| - | * ukazatel počátku vzoru ve slovníku | ||
| - | * délka vzoru | ||
| - | * kódové slovo příštího symbolu za kódovým textem | ||
| - | </box> | ||
| - | |||
| - | <box 90% blue|LZ78> | ||
| - | * Používá se samostatný dynamicky vytvářený slovník. | ||
| - | * Výstupem je dvojice: | ||
| - | * index vzoru ve slovníku | ||
| - | * kódové slovo příštího symbolu za kódovým textem | ||
| - | </box> | ||
| - | |||
| - | <box 90% blue|LZW> | ||
| - | * Používá se samostatný dynamicky vytvářený slovník. | ||
| - | * Potenciální elementy slovníku jsou v kódové knize přednastaveny. | ||
| - | * Výstupem je jediný údaj -- index vzoru ve slovníku. | ||
| - | </box> | ||
| - | |||
| - | === Organizace souborů dat === | ||
| - | |||
| - | |||
| - | ==== Indexování a hašování ==== | ||
| - | |||
| - | === Bitmapové indexy === | ||
| - | |||
| - | === Dynamické hašování === | ||
| - | |||
| - | ==== Dotazy ==== | ||
| - | |||
| - | === Vyhodnocení dotazů === | ||
| - | |||
| - | === Transformační pravidla === | ||
| - | |||
| - | === Statistiky a odhady === | ||
| - | |||
| - | === Optimalizace dotazů a schématu === | ||
| - | |||
| - | ==== Zabezpečení báze dat ==== | ||
| - | |||
| - | === Přístupová práva === | ||
| - | |||
| - | ==== Transakce ==== | ||
| - | |||
| - | === Řízení souběžných transakcí === | ||
| - | |||
| - | === Systémy obnovy transakcí po výpadku === | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | ==== Zdroje ==== | ||
| - | |||
| - | * slidy PV062 (verze jaro 2015) | ||
| - | * slidy PA150 (podzim 2016) | ||
