PV062.md

PV062 Organizace souborů

1,5 hodiny, písemná zkouška, bez pomůcek, 6 příkladů (z toho 3 početní, 3 koncepčního typu), max. 12 bodů, na E alespoň 6 bodů

Informační teorie

informace -- získaná fakta o něčem nebo o někom, snižuje míru entropie

zpráva -- sdělení o nějakém objektu, události, jevu..., obsahuje informace

nosič -- médium, které slouží k přenosu a uchovávání informace, informace je na něm nějak zakódovaná

signál -- fyzikální veličina uchovávající informaci ve svých proměnnách v čase

informační teorie -- Claude E. Shannon

Kvalita a kvantita informace

syntax -- skladba, forma, uspořádání, kvantitativní (informační teorie)

sémantika -- obsah, význam, kvalitativní chápání (SW inženýrství)

Míra množství informace ve zprávě

• množství informace souvisí s pravděpodobnosti jejího výskytu (Shannonova formule)
• míra množství informace -- nejvhodnější řešení f{x} = −log(x), musí mít aditivní charakter (pravděpodobnosti sčítáme)
• ASCII je velmi redundantní kódování, ale zato se s ním snadno manipuluje
• množství informace je vždy kladné
• méně pravděpodobná zpráva nese větší množství informace
• informace ze skupiny různých zpráv = součet informací z jednotlivých zpráv
• míra je spojitá a symetrická
• entropie má maximum, když jsou všechny výstupy stejně pravděpodobné
• množství entropie odpovídá množství informace
• entropie roste s počtem možností
• minimální kódování: Fanovo kódování -- kódy znaky mají délky úměrné množství informace, které nesou (častější znak je zakódován krátce), oddělovače nejsou potřeba

Diskrétní zpráva, analogová zpráva

• zpracování -- srozumitelné pro funkce a procedury

• sdělování -- srozumitelnost

• skladování -- minimalizace redundance

• přenos -- minimalizace redundance & samoopravitelnost

• statické (př. text) × dynamické (př. zvuk) informace

Kódování

• zpráva je tvořena symboly zdrojové abecedy
• kódování je proces přiřazování symbolům (nebo skupinám symbolů) zprávy symboly z cílové (kódovací) abecedy
• zpráva musí jít zase rozkódovat a výše zmíněná přiřazení musí být unikátní
• cílem je kódovat s co nejnižším nárokem na paměť

Kód

• trojce: kódovací abeceda, vstupní abeceda, výstupní abeceda
• kód s kódovými slovy pevné nebo proměnné délky
• kód by měl být jednoznačně dekódovatelný
• stupeň -- průměrný počet bitů kódových znaků
• třídy nesingulárních kódů: prefixové, sufixové a blokové (ty mají pevnou délku)
• prefixový ⊂ jednoznačně dekódovatelný ⊂ nesingulární

Kraftova nerovnost -- abeceda q-árního kódu obsahuje q znaků, Suma všech záporně vzatých mocnin q je menší rovno 1.

McMillanova věta -- Kraftova věta platí pro libovolné jednoznačně dekódovatelné kódování.

Unární kód

• C(1) = 1
• C(2) = 01
• C(3) = 001
• ...

Binární kód

• musíme použít oddělovače nebo určit pevnou délku slova

Eliasovy kódy

• univerzální kód pro kladná celá čísla
• C1: N nul + první binární jednička + zbytek binárního čísla, která má délku N
• C2: z binární reprezentace čísla odstraním nejvyšší jedničkový bit, následně před každý bit umístím 0 a za celé číslo přidám 1.
• C3: délka (počet nul, N + 1) zakódovaná pomocí C2 + druhá půlka slova

Komprimace

= proces identifikace a odstraňování redundance

• ztrátová × bezztrátová komprimace

• kompresní a dekompresní algoritmus

• kompresní poměr (zakódovaná/původní)

• kompresní faktor (původní/zakódovaná)

• kompresní zisk, redundance zprávy, redundance komprimované zprávy

• hodnotící metody kompresních algoritmů: algoritmická složitost, paměťová složitost, kompresní poměr, míra ztrátovosti

• metodika kompresních technik:

  1. modelování (hledání redundance)
  2. kódování

• fyzická (logika na úrovni bitů) vs. logická (logika na úrovni typu dat) komprese

• statická komprese -- neadaptivní, vždy použije stejný postup, nehledě na význam dat

• adaptivní komprese -- využívá význam komprimovaných dat

prefixový kód -- žádný kód slova nemá prefix takový, že by to byl kód jiného slova

model -- vyjádření zprávy pro její rozpoznávání a generování

Modelovací techniky

• **statistické (nahrazení za kratší)
• slovníkové metody (seznam často se opakujícího)
• predikativní kódování

Ztrátová komprese

• GSM (kódování řeči), MP3 (kódování zvuku), JPEG (kódování obrazu), DVD (kódování videa)

Statistické modely konečného kontextu

• statistický model nultého stupně -- pravděpodobnosti výskytu znaků jsou stejné
• statistický model prvního stupně -- pravděpodobnosti výskytu znaků jsou různé
• statistický model druhého stupně -- pravděpodobnosti výskytu dvojic znaků

Základní techniky komprimace

• Braillovo písmo
• Baudotův kód -- dvě kódová slova slouží k rozlišení, zda se jedná o písmeno nebo číslo
• Ad-hoc textové komprese -- vynechání mezer, ASCII
• Slovníková přední komprese -- opakování prefixů (víno bílé, víno červené, víno růžové)
• MacWrite -- symbol = slabika, některé paragrafy kódovány nebo ne (podle toho, jestli je komprimovaná verze kratší)
• RLE (Run Length Encodings) -- opakující se znak -> znak + počet opakování (MNP)
  • MNP class 5 -- inflight coding - statistika výskytu znaků, častá slova probublávají nahoru na kratší kódy
• BinHex 4.0 Format -- RLE + kódování do textové formy
• Move to Front Coding (Bentey kódování) -- upravuji tabulku, lokální adaptivita

Statistické metody komprimace

Morseova abeceda

Shannon-Finnovo kódování

• bázový princip - shora dolů
• rozdělím na poloviny se zhruba stejnou pravděpodobností, jedna bude mít 1 druhá 0, atd.

Huffmanovo kódování a adaptivní podobě

• bázový princip zhora zdola nahoru
• není jednoznačné
• algoritmus FGK
• Huffmanův (binární) strom - postupné budování
• sourozenecká vlastnost: každý uzel kromě kořene stromu má sourozence, lze to uspořádat podle vah, aby byli vedle sebe
• vždy spojím dvě slova s nejmenší pravděpodobností a ty budou mít zbytek cifer už společný

Aritmetické kódování

• kódový slova na intervalu <0,1)

Slovníkové metody komprimace

• kódujeme řetězce
• LZ77 -- používá WinZip, Leupel-Ziv, okno
• LZ78 -- kódovací (vyhledávací) strom
• VZW -- GIF, TIFF, PDF
• VZSS - Leupel-Ziv-Storer-Szymanski

Vnější paměti

Sekundární paměti

Magnetický disk

• stopy > sektory
• doba vystavení
• rotační zpoždění
• řadič disku, řídící jednotka disku
• postupy vystavení: FIFO, Shortest Seek Time First, výtah (SCAN), jednosměrný výtah (C-SCAN)

RAID

= organizace diskového pole tak, aby působila jako jeden disk

• RAID 0 -- žádná redundance
• RAID 1 -- zrcadlení
• RAID 2 -- sebeopravující kódy
• RAID 3 -- parita
• RAID 4 -- disk na víc, který kontroluje paritu napříč ostatními disky ("po řádcích")
• RAID 5 -- jako předchozí, ale každý disk má kontrolu parity pro jeden řádek ("diagonála")

SSD

• tiché, rychlejší, bytelnější, omezená životnost

Terciální paměti

Magnetooptický disk

• magnet + laser

Optický disk

• bez magnetismu
• využívá se u přepisovatelných CD a DVD

CD/DVD

• -ROM: Read Only Memory
• -R: Recordable
• -RW: ReWritable

Pásky

• levnější, pomalejší, větší kapacita
• vhodné pro archivaci

bandwidt -- šířka pásma (kolik můžeme přenést naráz)

latence -- zpoždění při přístupu

Hierarchical Storage Management (HSM) -- zahrnuje i terciální paměti, v superpočítačových centrech

Soubor, souborové organizace

Soubor

• soubor může obsahovat jak data, tak programy
• data lze do vnější paměti zapsat pomocí souboru
• pole (elementární jednotka), záznam (strukturovaná jednotka, kolekce polí), soubor (kolekce záznamů, databáze
• logický (z fyzického pomocí open()) × fyzický

databáze -- kolekce souvisejících dat

soubor -- logicky související kolekce údajů, se kterou se dá manipulovat (soubor > záznam > atribut)

• statické soubory -- vnitřní struktura se nemění
• dynamické soubory -- vnitřní struktura se mění

záznam -- jeho obsah je specifikován atributy, podle atributů fixní × proměnná délka

• logický záznam -- kolekce hodnot atributů tvořící záznam
• fyzická záznam -- logický záznam + oddělovače, definice délek,...

atribut -- proměnná × fixní délka (oddělovač), pojemnovaný × nepojmenovaný

homogenní soubory -- jednotná deklarovaná struktura, liší se hodnotami atributů

blok -- manipulační jednotka dat

primární klíč, sekundární klíč

logická stránka, fyzická stránka -- alokační blok

implementační schéma -- optimální využití diskového prostoru (související data by měla být umístěna na stejném válci apod.)

Operace se souborem

konstruktor/destruktor: create, build, remove

modifikátory: insert, delete, update

inspektory: read, query, list

údržba souboru: open, close, reorganize

Schémata organizace souborů

logické schéma -- logická paměť (soubor + pomocné soubory)

fyzické schéma -- zobrazení logických stránek do konkrétního typu fyzické paměti

implementační schéma -- umístění fyzických stránek v zařízení

• prostorová a časová složitost
• zpřístupňování souborů: sekvenční, stromy, hašování

Druhy organizace souborů

• strukturované × nestrukturované soubory
• ovlivňuje přístup, údržbu, spolehlivost...

Sekvenční soubor

• vkládání O(1)
• vyhledávání O(n), uspořádaný O(log n)
• homogenní soubor
• klíč
• keysort -- netříděný primární soubor + tříděný index, který ukazuje na původní místa v paměti hodnot (nemusíme je přesouvat)

Hromada (heap)

• nehomogenní soubor
• obsahuje záznamy proměnné struktury
• nutnost použít oddělovače

Indexovaný sekvenční soubor

• záznamy uspořádány posle klíče
• přetoková oblast

Indexovaný soubor

• záznamy jsou neuspořádané, vyhledávají se podle (více) klíčů
• B-strom (hierarchická struktura)
• lineární (tabulková) struktura

Hašovaný soubor

• soubor s přímým přístupem
• klíčová je doba přístupu

Koncepty a rozhraní souborových systémů

Souborový systém

• soubor služeb sloužících k přístupu k vnější paměti
• sjednocuje pohled na paměť
• zajišťuje soukromí, autorizaci a bezpečnost
• soubory + adresářová struktura
• požadavky: vytvářet, mazat, upravovat a číst soubory, měnit oprávnění, restrukturalizovat, zálohovat, optimalizovat, umožnit paralelismus

Atributy souborů

• jméno (vnitřní × vnější - číselné, v tabulce otevřených souborů)
• typ
• organizace
• umístění
• rozměr
• oprávnění
• čas, datum, historie

File control block

• obsahuje charakteristiku souboru (metadata)
• na vnější paměti

logický soubor, fyzický soubor

Správa otevřených souborů

• ukazatel na právě zpřístupňovaný záznam
• čítač otevření
• přístupová práva

Adresář

• typ souboru
• snazší vyhledávání, kolekce podobných souborů, možnost existence souborů se stejným jménem
• implementace: acyklické grafy, stromy, B-stromy

pracovní adresář -- aktuální adresář

absolutní vs. relativní cesta

linky na soubory

File System Mounting -- připojení souborového systému z externího zařízení

DAC (Direct Access Control) -- kdo soubor vytvořil, tak má práva, určuje OS

MAC (Mandatory Access Control) -- určují aplikace

ACL (Access Control List)

• standardní stup a výstup a chybový výstup, roury (pipe), přesměrování

inode

NTFS

Implementace souborových systémů

Struktura systému souborů

• existuje na vnější paměti
• hierarchické uspořádání
• součást OS
• Logical File System -- stará se o správu metadat (organizace, adresáře, oprávnění)
• File Organization Module -- spravuje volnou paměť
• Basic File System -- manipulace s fyzickými stránkami
• I/O Control -- správa přerušení, drivery
• pro manipulaci se souborem jej musíme otevřít

Implementace systému souborů

otevírání souboru -- mapování jména souboru na index (vnitřní jméno)

čtení souboru -- identifikace pomocí indexu

• raw disk -- s prostorem na disku nakládá sama aplikace
• dělení disku na oddíly
• virtualizace -- jednotné API pro různé souborové systémy

Implementace adresářů

• lineární struktura jmen (bez uspořádání lineární složitost)
• B-strom (logaritmická složitost)
• Hašování (konstantní složitost)

Metody alokace prostoru souborům

• přidělování souvislých diskových prostorů
• vázané přidělování (mapa disku - FAT) -- soubor je rozptýlen do bloků
• indexované přidělování (mapa souboru) -- seskupení ukazatelů na boky pro jeden soubor
• kombinace přístupů
• problém s vnitřní fragmentací

Správa volné paměti

• bitová mapa disku
• řetězení volných stránek
• ukazatelé na volný prostor

NTFS

• NTFS svazek (volume)
• metadata ukládána jako soubory
• struktura svazku: ID, tabulka MFT, blok dat
• svazky jsou lineární posloupnosti alokačních bloků
• soubory jsou strukturované, mají atributy pojmenované (metadata) a nepojmenované (data)
• index jmen v adresáři je organizován do B+ stromu
• Recovery funkce
• security token (vlastník + ACL práva)

MFT (Master File Table)

• definuje obsah svazku
• lineární posloupnost 1 KB záznamů pevné délky
• jméno, čas, čítač násobných vazeb, bezpečnostní deskriptor, data...

Srovnání FAT a NTFS

• NTFS
  • pro disky nad 500 MB
  • lepší řízení přístupu
  • podpora obnovy
  • adresáře log(n)
  • RAID 1 (zrcadlení) & RAID 5 (diagonální parita)
• FAT
  • nižší paměťová náročnost
  • jednodušší efektivnější
  • rychlejší vytvoření
  • adresáře n/2

Indexy, index-sekvenční a indexové organizace souboru

• {klíč, ukazatel na záznam}
• primární soubor - data, sekundární soubor - indexy + ukazatele
• metriky indexů:
  • typ přístupu
  • doba přístupu
  • doba vložení
  • doba rušení
  • režie paměti
• lineární indexy, indexové bitové mapy, hašované indexy, stromové indexy
• primární, sekundární index (musí být hustý)
• víceúrovňové indexy
• přímé × nepřímé indexování
• rozsáhlý index se těžko umisťuje do RAM, není vhodný pro dynamické struktury

hustý index -- každý záznam má svůj index

řídký index -- jen vybrané záznamy mají index (vymezují jednu skupinu), soubor je tříděný

index sekvenční organizace souboru -- problém při vkládání je řeší přetekovou oblastí, jednou za čas je nutno soubor reorganizovat

Hašování

• konstantní složitost pro nalezení prvku O(1)
• hashovací funkce m = h(k)
  • m ... cílová adresa
  • h ... hashovací funkce
  • k ... klíč záznamu
• na cílové adrese jsou ukazatele na data nebo se jedná pří o umístění souboru

perfektní hašování -- funkce h je prostá

perfektní minimální hašování -- prostoru je tolik, kolik položek

Hašovací funkce

• deterministická
• rychlá (konstantní)
• vypočítává se z celého klíče
• umisťuje souboru rovnoměrně

Příklady hašovacích funkcí

• přímé zobrazení
• modulo
• modulo +× konstanty
• mid-square
• změna číselné soustavy

uniformní hašovací funkce -- každá kapsa obsahuje stejný počet položek

Otevřené hašování - řešení kolizí

• lineární adresování -- při mazání si musím poznačit, že na onom místě něco bylo
• kvadratické adresování -- nezpůsobuje shluky
• násobné adresování -- dvojité adresování, znovu se použije nová funkce modulo +1
• kapsy - logické paměťové jednotky, na výsledné adrese je místo pro více položek, kapsa je procházena lineárně

Uzavřené hašování

• adresace s kapsami

Dynamické hašování

• rozšiřitelné hašování
• kapsy indexovány adresářem kapes
• tries

Lineární hašování

• štěpení kapes - rozšiřování adresového prostoru při každém přetoku

Hierarchické indexy, B/B+stromy, tries

Grafy

• dvojce vrcholů a hran G = (V, E)

orientovaný graf × neorientovaný graf

stupeň vrcholu

arita vrcholu -- počet výstupních hran z vrcholu (binární graf, n-ární graf...)

délka cesty -- počet hran mezi vrcholy

cyklus

smyčka

jednoduchá cesta -- žádný z vrcholů se neopakuje

ohodnocený, souvislý, acyklický graf

jednoduchý graf -- orientovaný, acyklický, bez cyklů, smyček a násobných hran

strom -- neorientovaný souvislý acyklický graf

kořenový strom -- vstupní stupeň roven jedné (kromě kořenového uzlu)

list, podgraf, kostra grafu, podstrom

hloubka uzlu -- hloubka kořene = 0

úroveň ve stromu, hloubka stromu, šířka stromu (na určité úrovni)

výška stromu hloubka - 1

vyvážený, uspořádaný, neuspořádaný strom

(neúplný, úplný, kompletní, degenerovaný) binární strom -- Huffmanovo kódování, indexování

B stromy

• vyvážené (Balanced), neredundantní
• vyšší prostorová režie + časová režie
• štěpení a slévání
• uzel v B stromě řádu 3 má 3 syny
• hodnoty jsou i ve vnitřních uzlech stromu

B+ stromy

• jsou redundantní
• hodnoty jsou jen v listech

trie

• m-ární strom
• uzly reprezentují slova nebo prefixy slov
• není vyhledávací
• využití: rychlé prohledávání textů
• (funguje to jako pomůcka na morseovku)
• výška je dána délkou nejdelšího klíče

CHYBY V SLAJDECH: 04 - str. 3: aplykačnímy systémy -> aplikačními systémy 04 - str. 6: redord -> record