Formáty uložení dat Výpočetní technika I

. .

Formáty uložení dat Výpočetní technika I Ing. Pavel Haluza ústav informatiky PEF MENDELU v Brně [email protected]

Přednáška 4:

Osnova přednášky

Formáty uložení dat

Souborové formáty Komprimace a archivace Úvod do teorie informace

• Souborové formáty — otevřený a uzavřený formát — rozpoznávání formátu — asociace a konverze • Komprimace a archivace — komprimační metody — archivace a zálohování — metody a postupy archivace • Úvod do teorie informace — základní pojmy — měření množství informace ve zprávě

Výpočetní technika I

Přednáška 4: Formáty uložení dat

2 / 45

Přednáška 4:

Souborový formát


Souborové formáty Otevřený a uzavřený formát Rozpoznávání formátu Asociace a konverze

• Pojem odvozený z pojmu „datový formát“ • Specifikace tvaru dat uložených v souboru

Komprimace a archivace

• Místo podrobného popisu dat používáme jména

Úvod do teorie informace

formátů (označení přípon) • Dokument – soubor obsahující — vlastní text — formátovací značky • Dělení souborů podle tvaru značek — textové – HTML, XML, RTF, PostScript, TEX, CSV — binární – DOC, DOCX, SAM, INDD, PDF, Text602 • Datové soubory programů určitého zaměření mohou

být v obojím formátu – mají rozdílné vlastnosti a možnosti použití Výpočetní technika I


3 / 45

Přednáška 4:



Komprimace a archivace Úvod do teorie informace

Otevřený a uzavřený formát • Otevřený formát — specifikace formátu je volně dostupná — prostředek pro výměnu informací, efektivní využití a zpracování uložených dat — příklady: JPG, PNG, PDF, všechny textové • Uzavřený formát — specifikace formátu je utajována — umožňuje získat monopol pro jeho zpracování a zároveň silně omezuje možnosti využití uložených dat — příklad: CDR, dříve MS Office (DOC, XLS, PPT)



4 / 45

Přednáška 4:




Přehled základních souborových formátů • Textové formáty — webové aplikace: HTML, XHTML, XML, MHT, CSS — zdrojové kódy: JS, PAS, JAVA, PL, PHP, ASP — dokumenty: RTF, PS, CSV, TEX, TXT — grafika: SVG • Binární formáty — historie: SAM, INDD, T602 — dokumenty: DOC(X), XLS(X), PPT(X), ODF, PDF — grafika: BMP, JPG, PNG, GIF, TIFF, CDR, EPS



5 / 45

Přednáška 4:

Přenositelnost formátu


Souborové formáty Otevřený a uzavřený formát

• Lze pracovně definovat jako množství programů

Rozpoznávání formátu Asociace a konverze


• •

• •


schopných zpracovat tento formát Důležitým faktorem je podpora zpracování formátu v různých operačních systémech Přenositelnost je také úzce svázána s otevřeností formátu, ale závisí také na majiteli formátu (DOC × PDF) Přenositelnost textových formátů je obecně větší Binární otevřené formáty rovněž přenositelné


6 / 45

Přednáška 4:





Rozpoznávání formátu • První krok — roztřídění na textové a binární formáty — využití běžných programů (type, more) • Druhý krok — rozšířené textové formáty – rozpoznání kódování národních znaků a operační systém, v němž soubor pravděpodobně vznikl — binární formáty – použití rozpoznávacích programů — Unix: file, enca, od — Windows: není nástroj (zkusmo?)


7 / 45

Přednáška 4:

Asociace formátů a aplikací


Souborové formáty Otevřený a uzavřený formát

• Udává, která aplikace bude pracovat se souborem dané

Rozpoznávání formátu Asociace a konverze

Komprimace a archivace

•


• •

• •

přípony Laikům usnadňuje zpracování dat v operačním systému Princip – tabulka s řádky „formát → aplikace“ (Tento počítač; Nástroje/Možnosti složky) Spouštění aplikace v případě aktivace souboru příslušného formátu (stažení přes prohlížeč, dvojklik v manažeru, výběr v dokumentech apod.) Orientace jen podle rozšíření (přípony) jména souboru může vést ke zmatkům Ideální stav: 1 formát → 1 aplikace — platí pro speciální případy, např. CDR → CorelDraw!



8 / 45

Přednáška 4:




Problémové případy • Více formátů → 1 aplikace — časté, ale neproblematické • 1 formát → více aplikací — problém nejednoznačnosti, nepříjemné řešení — aktivuje se buď posledně instalovaná aplikace, nebo podle výběru z nabídky • 1 formát → žádná aplikace — chybové hlášení s nabídkou instalovaných aplikací, z nichž uživatel může vybrat (prakticky nikdy nevede k úspěchu) — Windows XP: rozšíření nabídky programů z Internetu • Žádný formát → 1 aplikace — buď aplikace žádné formáty nepotřebuje, nebo se jedná o aplikaci DOS, nebo o chybnou instalaci



9 / 45

Přednáška 4:

Konverze formátů




• Změna souborového formátu bez změny informačního

obsahu • V praxi vzácné ideální případy • Často vede ke ztrátě, ale i k nabytí informací • Provedení konverze — speciálním konverzním programem — služby Open a Save (As) běžných programů • Příklady — konverze čísel mezi textovou a binární podobou — konverze obrazových formátů (Unix: convert) — konverze kódování národních znaků (cstocs) — konverze dokumentních formátů (DOC → RTF)



10 / 45

Přednáška 4:

Potřebnost komprimace


Souborové formáty Komprimace a archivace Komprimační metody Archivace a zálohování Metody a postupy archivace


• Redundance v datech – nutná pro zpracování dat • Vznik redundance — nedokonalým kódováním dat — nutností rychlého přístupu k datům — přidáním zabezpečovacích zařízení • Odstranění (snížení) redundance – použitím

komprimace



11 / 45

Přednáška 4:

Základní pojmy




• Hrubá data – data před komprimací • Čistá (komprimovaná) data – data po komprimaci • Komprimační poměr – poměr délek hrubých

a komprimovaných dat, vyjadřuje se různým způsobem — h/k – udává násobek hrubých dat — k/h · 100 – udává, na kolik procent se data zmenšují — (1 − k/h) · 100 – udává, o kolik procent se data zmenšují • Záporná komprimace – data se komprimací zvětšují • Ztrátová komprimace – některá data se vynechávají • Adaptivní komprimace – komprimační metoda pracuje

v závislosti na hrubých datech • Symetrická komprimace – čas komprimace a dekomprimace je stejný Výpočetní technika I


12 / 45

Přednáška 4:




Komprimační metody • Logická komprimace — jiný (kratší) způsob vyjádření stejných informací — je nutné znát detailně sémantiku (význam) dat — příklady – zkracování slov (těsnopis), čb fotografie vyjádřená v odstínech šedi • Fyzická komprimace — hledání lepšího (kratšího) kódu — nezávisí na sémantice dat



13 / 45

Přednáška 4:

Metoda RLE




• Běh – posloupnost stejných hodnot • Run Length Encoding – kódování délkou běhu • Základní princip – opakovač, hodnota — hrubá data – 65 65 65 65 78 78 78 32 32 32 32 32 — výsledek – 4 65 3 78 5 32 • Problém – střídavá data; může dojít k záporné

kompresi, řeší se speciálním tvarem opakovače • Bitová / bytová / pixelová úroveň



14 / 45

Přednáška 4:

Metoda LZW




• Lempel, Ziv, Welch (1977, vylepšeno 1984) –

algoritmus a jeho implementace • Princip — hledání optimálního kódu pro zadaná hrubá data — prvkem hrubých dat, který se kóduje, jsou posloupnosti • Postup — data se analyzují, zjišťují se posloupnosti a jejich četnost — na základě analýzy a vzniklého slovníku se hledá optimální kód • LZMA – Lempel, Ziv, Markov-Chain Algorithm,

pomalejší, ale s lepším komprimačním poměrem



15 / 45

Přednáška 4:

Metoda CCITT


Souborové formáty Komprimace a archivace Komprimační metody Archivace a zálohování

• Princip — stejný jako u LZW — používá se však pevný slovník

Metody a postupy archivace



• Implementace — CCITT Group 4 pro monochromatická obrazová data (formáty BMP, TIFF, PCX)


16 / 45

Přednáška 4:




Vlastnosti komprimačních metod • Metoda RLE — jednoduchá — závislá na bězích v hrubých datech — nízký komprimační poměr • Metoda LZW — nejsložitější — adaptivní, nezávislá na datech — vysoký komprimační poměr — univerzální použití, kvalitu lze ovlivnit hloubkou analýzy • Metoda CCITT — jednoduchá — závislá na prvcích odpovídajících slovníku — nízký komprimační poměr



17 / 45

Přednáška 4:

Implementace





• Komprimátory – programy schopné komprimovat, ale

také archivovat, pracovat se soubory a adresáři, šifrovat obsah, vkládat poznámky apod. • Komprimace pod OS třídy Unix – gzip, zip/unzip • Komprimace pod OS Windows – pkzip/pkunzip, WinZIP, WinRAR, arj, 7zip apod. • Různé komprimátory – různé formáty archivů, různé ovládání, ale prakticky vždy metoda LZW (LZMA) s mírnými modifikacemi


18 / 45

Přednáška 4:

Archivy





• Soubor vytvořený komprimátorem, obsahuje čistá data

a režijní informace • Procento režijní informace závisí na velikosti a počtu komprimovaných souborů • Formát archivu je pro každý komprimátor jiný • Moderní komprimátory jsou schopny číst a někdy i vytvářet archivy různých typů


19 / 45

Přednáška 4:





Vnitřní fragmentace • Každý disk je složen z alokačních bloků určité délky • Uložený soubor zabírá vždy určitý celočíselný počet

alokačních bloků • Poslední alokační blok souboru není zcela využit – vnitřní fragmentace • Velikost souboru ≤ velikost na disku • Shrnutí více souborů do jednoho archivu znamená eliminaci vnitřní fragmentace (i bez komprimace jde o zmenšení prostoru na disku)


20 / 45

Přednáška 4:





On-line komprimace • Implementace uvnitř jiného programu – služby Otevřít

(Open) a Uložit (Save, Save As) • Při běžné práci se skrytě komprimuje a dekomprimuje • Používáno u programů pracujících s vnitřně komprimovanými daty, například obrazové editory, zpracování hudebních dat a videodat • Použita symetrická komprimace – čas otevření a uložení je podobný, menší nároky na kvalitu komprimace, často i ztrátová komprimace


21 / 45

Přednáška 4:


Souborové formáty Komprimace a archivace Komprimační metody Archivace a zálohování

Archivace a zálohování • Archivace — uchování dat pro budoucí použití — nutnost uchování dokladů o provedených pracích

Metody a postupy archivace


• Zálohování — ochrana před poškozením nebo ztrátou dat (viry, požár, povodeň, chyby uživatelů) • Vzdálenost archivu — příruční – na stejném disku — odkládací – na stejném počítači, ale jiném disku — bezpečnostní – mimo počítač, archivní média — podle vzdálenosti roste i bezpečnost uchování



22 / 45

Přednáška 4:

Způsoby zálohování


Souborové formáty Komprimace a archivace Komprimační metody

• Záloha dat, záloha programů • Zálohují se soubory, adresářové podstromy, disky,

Archivace a zálohování Metody a postupy archivace


• • • •

• Výpočetní technika I

systémové soubory a oblasti Výchozí záloha – kopie původního systému, provádí se po první instalaci Úplná záloha – všechna data, která byla k dispozici v okamžiku jejího vytvoření Rozdílová (diferenciální) záloha – pouze data, která byla změněna od úplné zálohy Přírůstková (inkrementální) záloha – pouze data, která byla změněna od vytvoření poslední plné nebo přírůstkové zálohy Plán záloh Přednáška 4: Formáty uložení dat

23 / 45

Přednáška 4:




Metody a postupy archivace • Vytváření archivních souborů – většinou vhodným

komprimátorem nebo specializovanými programy • Četnost archivace – podle vzdálenosti archivu, po každé modifikaci dat, jednou denně, jednou týdně, jednou měsíčně, … • Média pro zálohy a archivy — pevné disky – v počítači (oblast téhož disku, jiný disk, mirror) – zálohy — přenosná média (CD, DVD, magnetické pásky, flash disky) – zálohy i archivy — NAS (Network Attached Storage) – síťově dostupné úložiště – zálohování



24 / 45

Přednáška 4:

Archivace v Unixu





• Program tar (tape archive) a jeho kombinace

s bezztrátovou komprimací gzip – soubory .tar, .tgz • Vytvoření skriptu (uživatelské dávky) pro archivaci vybraných souborů a adresářů • Nastavení času a periodicity archivace – cron • Automatizované posílání archivů případně na jiný stroj (připojení disku jiného stroje do souborového systému)


25 / 45

Přednáška 4:





Archivace ve Windows • Program backup – varianta v příkazovém řádku nebo

interaktivní (i s průvodcem) • Možnosti zálohy systémových záznamů a jejich obnova v případě havárie • Zálohování souborů – výběr zdrojů a umístění archivů • Plánovač úloh – možnost volby času zálohování a periodicity


26 / 45

Přednáška 4:

Údaje, data


Souborové formáty Komprimace a archivace Úvod do teorie informace Základní pojmy Měření množství informace ve zprávě


• Údaje — hodnota libovolné reálné veličiny — příklad: „167 cm“ • Data — zprávy nebo výroky, které mohou (ale nemusí) snižovat neznalost daného jevu (neurčitost, entropii) — jakékoli vyjádření (reprezentace) skutečnosti, schopné přenosu, uchování, interpretace či zpracování — sama o sobě jsou nehmotná, i když pro jejich uložení potřebujeme hmotné médium — příklad: „Průměrná výška ženy je 167 cm.“


27 / 45

Přednáška 4:

Interpretace dat


Souborové formáty Komprimace a archivace Úvod do teorie informace Základní pojmy

• Data v počítači – jedničky a nuly • Pro člověka musí být zobrazeny • Zobrazení stejné posloupnosti jedniček a nul může být

Měření množství informace ve zprávě

• • • •


provedeno nekonečně mnoha způsoby Interpretace zobrazení – přisouzení významu zobrazeným údajům Datový typ – definován oborem povolených hodnot a kolekcí povolených operací Implementace – přisouzení datového typu posloupnosti binárních hodnot v paměti počítače Modeluje objektivní realitu – hodnoty jsou zobrazeny pro vstup i výstup


28 / 45

Přednáška 4:

Informace, znalosti



• Informace — snižují neurčitost a vyvolávají změnu stavu či chování příjemce — změna stavu po přijetí zprávy je tím větší, čím větším je informace pro příjemce překvapením — množství informace ve zprávě je relativní vzhledem k určitému příjemci a určité situaci — každou informaci lze považovat za součást dat, ale každá data nemusí obsahovat informaci • Znalosti — ucelený komplex informací o nějaké objektivní realitě — výsledek poznávacího procesu, předpoklad uvědomělé činnosti, umožňují porozumět skutečnosti — příklad: „Průměrná žena je docela malá.“



29 / 45

Přednáška 4:




Jak informaci chápat? • Kvalitativní hledisko — získávání, uchovávání, zpracování a přenos informací — zkoumá informatika • Kvantitativní hledisko — množství informace ve zprávě a jeho měření — kódování a dekódování zpráv — přenos zpráv — zkoumá teorie informace


30 / 45

Přednáška 4:

Pojem informace




• Mnoho různých definic podle toho, co autoři definice

považovali za nejdůležitější • Informace je obsah jakéhokoli oznámení, údaje o čemkoli, s určením pro přenos v prostoru a čase. V nejširším slova smyslu je to obsah vztahů mezi materiálními objekty, projevující se změnami těchto objektů • Informace je obsah zprávy, sdělení, objasnění, vysvětlení, poučení • Informace jsou údaje, čísla, znaky, povely, instrukce, příkazy, zprávy apod. Za informace považujeme také podněty a vjemy přijímané a vysílané živými organismy


31 / 45

Přednáška 4:

Informační systém




• Systém – komplex prvků a vazeb ve vzájemné interakci

(definice v teorii systémů) • Informační systém – dynamický systém, jehož vazby tvoří informace a prvky systému jsou místa transformace informací • Úkol IS – poskytovat potřebné informace v požadovaném rozsahu, lhůtách, podrobnostech i formě • Dílčí úlohy IS – sběr informací, přenos, redukce, archivace, zpracování, distribuce


32 / 45

Přednáška 4:




Měření množství informace ve zprávě • Americký fyzik Claude Shannon (1916–2001) — položení základů teorie informace — stanovení možností měření informačního množství • Informace je míra množství neurčitosti nebo nejistoty

o nějakém náhodném ději odstraněná realizací tohoto děje • Množství informace ve zprávě tedy měříme podle toho, o kolik se sníží neurčitost nebo nejistota, když zprávu přijmeme a pochopíme • Pojem informační entropie – míra neurčitosti, která se po přijetí zprávy odstraňuje a vyjadřuje tak množství informace obsažené ve zprávě


33 / 45

Přednáška 4:



Měření množství informace ve zprávě • Jak kvantifikovat rozšíření okruhu znalostí příjemce? • Pravděpodobnost zprávy — spojeno s individuálními vlastnostmi příjemce (Shannon) • Jev — náhodný proces s n možnými realizacemi — tah sportky, účast na přednášce, semafor na křižovatce • Realizace jevu — jeden projev, získání výsledku — vytažení 6 čísel, konkrétní počet osob na přednášce, svítící zelená na semaforu aj.



34 / 45

Přednáška 4:



Požadované vlastnosti funkce pro výpočet množství informace • Jev X má n realizací, množství informace je funkcí n • Jediná realizace jevu X — pokud n = 1, jedná se o jev jistý — množství informace je rovno nule • Současně probíhající nezávislé jevy X a Y — p(x, y) = p(x) · p(y) — množství informace je dáno součtem množství informace u jednotlivých jevů: f(x, y) = f(x) + f(y) • Porovnání pro dva odlišné jevy X a Y — jev X má n realizací, jev Y má m realizací — je-li m > n, pak chceme i f(m) > f(n)



35 / 45

Přednáška 4:

Výpočet vlastní informace


Souborové formáty Komprimace a archivace

• Jediná funkce, která vyhovuje uvedeným podmínkám,

je logaritmus I(x) = log n

Úvod do teorie informace Základní pojmy Měření množství informace ve zprávě

• Předpokládáme, že pravděpodobnost každé realizace je

stejná, tedy 1 p(x) = , n kde n je počet realizací • Úpravou dostáváme n=


1 p(x)


36 / 45

Přednáška 4:



Výpočet vlastní informace • Vlastní informace výsledku realizace x

I(x) = − log p(x)

Základní pojmy Měření množství informace ve zprávě

• Základ logaritmu – principiálně není podstatný, ale

používají se logaritmy o základu 2 (výsledek v bitech) I(x) = − log2 p(x) • Vlastní informace se nazývá též částečná informace • Počítání s logaritmy

loga x =

logb x = loga b · logb x logb a

log2 x = log2 10 · log x = 3,322 · log x Výpočetní technika I


37 / 45

Přednáška 4:



Aplikace vlastní informace • Výpočet vlastní informace v bitech = výpočet prostoru

pro zadaný počet hodnot — příklad: barevná hloubka rastrového obrazu • Velikost prostoru v počítači pro určitý údaj –

hodnocení úspornosti — příklad: uložení 6 tažených čísel Sportky – znaky, čísla malá, velká, souhrn, kódování • Příklad: věta s nezávislými současně vzniklými

realizacemi (Auto 1B1 8877 černé barvy přijelo na křižovatku Horní–Jasanová v 19:10 hodin.)



38 / 45

Přednáška 4:

Řešený příklad



• Jakou vlastní informaci nese zpráva o výsledku

losování určitých 5 čísel z 20? • Aplikujeme vztah pro výpočet vlastní informace

Základní pojmy Měření množství informace ve zprávě

I(x) = − log2 p(x) • Jaká je pravděpodobnost vytažení konkrétní pětice

čísel? • Dosadíme do vzorce 1 I(x) = − log2 (20) = − log2 5

1 = 13,92 15 504

• V jakých jednotkách je výsledek a co nám výsledná

hodnota říká? Výpočetní technika I


39 / 45

Přednáška 4:

Entropie



• Jak spočítat informační množství celého jevu? • Pomůžeme si shrnutím všech vlastních informací

jednotlivých realizací • Předpokládejme, že jev X má n realizací x1 , x2 , …, xn s pravděpodobnostmi p(x1 ), p(x2 ), …, p(xn ) • Entropie H(X) je dána určitou střední hodnotou vlastních informací všech realizací jevů H(X) = −

n ∑

p(xi ) · log2 p(xi ) =

i=1

n ∑

p(xi ) · I(xi )

i=1

• Entropie zahrnující informační množství celého jevu se

nazývá též úplná informace Výpočetní technika I


40 / 45

Přednáška 4:

Příklad



• Počáteční situace — soutěžící v televizní soutěži má na výběr ze čtyř odpovědí na zadanou otázku — správnou odpověď však nezná a dokonce ani žádnou variantu nepreferuje • Nejistota soutěžícího v této situaci — správná odpověď může být se stejnou pravděpodobností kterákoliv ze čtyř nabídnutých p(xi ) = 0,25 • Hodnota informační entropie soutěžícího

H(X) = −4 · 0,25 · log2 0,25 = − log2 0,25 = 2 Výpočetní technika I


41 / 45

Přednáška 4:

Příklad



• Následující situace — soutěžící požádá o nápovědu „50 na 50“ — na výběr už má jen dvě varianty • Nejistota soutěžícího v této situaci — správná odpověď může být se stejnou pravděpodobností kterákoliv ze dvou nabídnutých p(xi ) = 0,5 • Hodnota informační entropie soutěžícího

H(X) = −2 · 0,5 · log2 0,5 = − log2 0,5 = 1



42 / 45

Přednáška 4:

Příklad



• Následující situace — soutěžící si vybere jednu variantu a odpoví na otázku — vzápětí se dozví správnou odpověď • Nejistota soutěžícího v této situaci — správnou odpověď soutěžící v tuto chvíli již zná p(x) = 1 • Hodnota informační entropie soutěžícího

H(X) = −1 · log2 1 = − log2 1 = 0



43 / 45

Přednáška 4:



Odvození nejmenší míry informace • Entropie nabývá nejvyšší hodnoty při stejné

pravděpodobnosti výskytu realizací xi • Potom platí H(X) = − log2 p(x) • Nejmenší jednotka míry informace (1 bit) je odvozena

od entropie jevu, který má jen dvě stejně pravděpodobné realizace H(X) = −2 · 0,5 · log2 0,5 = − log2 0,5 = 1



44 / 45

Přednáška 4:

Řešený příklad



• Vypočtěte entropii zdroje zpráv: Na železničním

návěstidle je možné nastavit návěstí „Stůj“, které svítí 80 % času, a pak dalších 5 různých návěští s přibližně stejnou pravděpodobností • Možné realizace jevu X — — — — — —

x1 x2 x3 x4 x5 x6

p(x1 ) = 0,8 p(x2 ) = 0,04 p(x3 ) = 0,04 p(x4 ) = 0,04 p(x5 ) = 0,04 p(x6 ) = 0,04

• Dosadíme do vzorce

. H(X) = −(0,8 · log2 0,8 + 5 · 0,04 · log2 0,04) = 1,19 Výpočetní technika I


45 / 45

Formáty uložení dat Výpočetní technika I

Recommend Documents