Kódování a redundance
- Proč obvykle data obsahují méně informace, než by se do nich mohlo vejít, a že to není nutně na škodu
- Že přirozené jazyky jsou příkladem kódování a čím to, že jsou různě úsporné
- Co je a k čemu slouží redundance
- Na čem záleží kvalita kódování informací
V této hodině se studenti blíže seznámí s problematikou kvalitního kódování v reálnější situaci než „Myslím si číslo.“ Hodina stojí na příkladech, z nichž většinu studenti znají (především přirozený jazyk). Otázky, které jim klademe, ale většině z nich dosud nikdy nepřišly na mysl. Otvírá se jim tak poněkud jiný pohled na jazyky a gramatiku, ale i další kódování.
Příklady jsme se snažili vybrat tak, aby oslovili i neinformaticky založené studenty (třeba právě ty, kteří jsou „zaměření spíš na ty jazyky“). Samozřejmě se lze zaměřit na příklady v informatice tradičnější, jako jsou kódování znaků a čísel (např. se znaménkem, s plovoucí řádovou čárkou...). Přirozeně se nabízí také přesah do otázek komprese, k tomu je ale vhodné vědět něco z následujících dvou kapitol.
Kromě bližšího seznámení s jednotlivými příklady by studenti měli pochopit, že vhodné kódování znamená rovnováhu mezi úsporností, robustností a snadností použití.
B. Pascal na konci dopisu: „Omlouvám se, že je můj dopis tak dlouhý, neměl jsem čas napsat kratší."
Umíme spočítat maximální množství informace ve zprávě. Toho ovšem v praxi nebývá dosaženo. Běžně dochází k tomu, že je ve zprávě informace méně, než kolik by se do ní vešlo. Napadnou tě nějaké důvody, proč by to tak mohlo být? Některé z nich zde prozkoumáme.
Vím něco předem
První důvod je nejjednodušší, už jsme se s ním setkali. Když už obsah zprávy nebo jeho část znáš, její informační přínos pro tebe klesá.
Příklad: Nápověda 50:50 v soutěži Chcete být milionářem?
Co kdybych veděl jenom to, že správně není Kodaň? Nápověda může vyloučit Kodaň a Karáčí, Kodaň a Karakas, nebo Karáčí a Karakas. Kolik dostanu ve kterém případě informace?
Řešení
První dvě varianty mi ze 3 uvažovaných možností ponechají 2, výsledek je log(3/2) ≈ 0,585. Třetí varianta mi ze tří ponechá možnost jedinou, dodá tedy log(3/1) ≈ 1,585Zdá se to, nebo se výsledky skutečně liší přesně o jeden bit? Proč? bitů informace.
V soutěži Chcete být milionářem vím, že hlavní město Egypta je Karakas nebo Káhira, a nikoliv Karáčí nebo Kodaň. Risknu nápovědu 50:50, která vyloučí dvě možnosti ze čtyř.
Kdyby byla nápověda zakódována co nejúsporněji (nikoliv např. přímo názvy měst), kolik potřebuje bitů dat?
Nápověda musí jednoznačně určit některé dvě možnosti ze čtyř. Ze čtyř možností lze ale vybrat dvojici několika (více než dvěma) různými způsoby, jeden bit (hodnota nula nebo jedna
dvě města vyloučená nápovědou totiž nelze zakódovat jedinou binární číslicí).
To je záludná otázka, datová zpráva totiž vypadá poněkud neobvykle: dvě možnosti ze čtyř prostě zhasnou. Žádné odesílané symboly se nikde zřetelně nevyskytují. Jak si poradíme? Najdeme nějakou rovnocennou situaci. Buď zkusíme zjistit, kolik může nápověda nanejvýš předat informace, což odpovídá minimálnímu množství dat. Nebo se zkusíme zamyslet, jak informaci co nejúsporněji zakódovat, např. pro poslání pokynu z režie do studia.
Nenech se zmást tím, že nápověda vyloučí polovinu možností. Nápověda sama totiž musí obsahovat jejich identifikaci, tedy určit, která polovina ze všech možných polovin to je.
Přímočarý postup by byl zakódovat nápovědu prostě pomocí vyloučených možností, např. "AD" vyloučí možnosti A a D. Každou možnost lze přitom jednoznačně určit dvěma bityRozmysli si proč!, celkem by nápověda spotřebovala čtyři bity.
Lze ovšem postupovat i o něco úsporněji. Uvedené kódování například rozlišujePřiřazuje různé kódy. nápovědu "AD" a "DA", i když obě takové nápovědy mají přesně stejný význam. První krok ke zlepšení je tedy zjistit počet možností, jak lze vybrat dvě možnosti ze čtyř. Když tě nenapadne nic lepšího, prostě je všechny vypiš. Potom už stačí každé možné dvojici jednoznačně přiřadit posloupnost nul a jedniček. Ti, kdo dávali pozor v předchozích kapitolách, mohou postupovat rychleji a počet dvojit opakovaně dělit dvěma, nebo použít logaritmus.
Řešení
Počet různých nápověd 50:50(neboli způsobů, jak vybrat dvě možnosti ze čtyř), je šest:
AB, AC, AD
BC, BD
CD
Pro předání jedné z šesti možností potřebujeme tři bity, např. takto:
| AB | AC | AD | BC | BD | CD |
|---|---|---|---|---|---|
| 000 | 001 | 010 | 011 | 100 | 101 |
Nebo rychleji:
- Počet dvojic je šest: Ke každé ze 4 možností lze do dvojice přiřadit jednu ze 3 zbývajících. To dá celkem 4⋅3=12 dvojic. Každá nápověda je ale započtena jednou navíc „pozpátku“, polovinu dvojic tedy odstraníme, 12/2=6.
- K zakódování 6 dvojic potřebujeme přinejmenším log(6) ≈ 2,585 bitů. Výsledek zaokrouhlíme nahoru na celé bity, potřebujeme tedy 3 bity.
Kolik informace mi dá nápověda 50:50, pokud vyloučí Karáčí a Kodaň? (rozhoduji se mezi městy Karakas a Káhira)
Porovnej počet uvažovaných možností před nápovědou a po ní. Přesný postup výpočtu jsme odvodili v předchozí kapitole.
Řešení
Vím-li předem, že hlavní město Egypta je Karakas či Káhira, vyloučení možností Karáčí a Kodaň mi nijak nepomůže. Před nápovědou i po ní uvažuji dvě možnosti, nápověda mi tedy žádné informace neposkytla.
Kolik informace mi dá nápověda 50:50, pokud vyloučí Karakas a Kodaň? (rozhoduji se mezi městy Karakas a Káhira)
Porovnej počet uvažovaných možností před nápovědou a po ní. Přesný postup výpočtu jsme odvodili v předchozí kapitole.
Řešení
Nápověda sníží počet mnou uvažovaných možností (Káhira a Karakas) přesně na polovinu (zbyde Káhira). Získám tedy přesně 1 bit informace.
Kolik informace mi dá nápověda 50:50, pokud vyloučí Karakas a Karáčí? (rozhoduji se mezi městy Karakas a Káhira)
Jak se tento případ liší od předchozího z hlediska toho, co nás zajímá, tedy z hlediska počtu vyloučených možností?
Řešení
Získám přesně 1 bit informace.
Všimni si, že v každém případě dostanu méně informace než dat. Dovedeš říct, proč tomu tak je?
Jako soutěžící nás zajímá jen to, která odpověď ze čtyř nabízených je správná. Nápověda ale dvojici nesprávných odpovědí různě vybírá, čímž si vlastně přidělává práci a poskytuje víc dat, než by bylo třeba. Kdyby pokaždé vyloučila první dvě nebo druhé dvě, stačil by pro ni jeden bit dat. Tím, že vybírá dvojice různě, ovšem činí hru zajímavější.
Uvedený příklad ukázal, že množství informace ve zprávě může klesnout prostě tím, že už něco vím předem, nebo tím, že je zpráva vlastně o něčem jiném, než nás zajímá (které dvě konkrétní odpovědi jsou špatně, a nikoliv která jedna je správně bez ohledu na ostatní).
Všechna kódování nejsou stejná
Informace mohou být do dat zakódovány více či méně úsporně. Potom je množství dat větší, než množství obsažené informace. Týdenní televizní program pro každý den opakuje, kdy začínají večerní zprávy a další pravidelné pořady. To zvětšuje množství použitých dat. Z informačního hlediska by přitom stačilo jednou prostě napsat, v kolik hodin každý den začínají zprávy. Cenou za tuto úsporu místa by bylo obtížnější použití programu. Jistá neúspornost ale může být i přímo vlastností toho kterého kódování.
Aktivitu lze zrealizovat také tak, že každý žák dostane ke změření jiný jazyk, ve výsledku tak lze získat mnohem širší porovnání. Urychlit ji lze rychlým nasměrováním ke konkrétnímu, předem vyzkoušenému zdroji textů, např. tento rozsudek.
Když máš za úkol napsat esej na 1000 znaků, víš, že se obvykle těžko vměstnáš do limitu, a máš na výběr mezi češtinou, angličtinou a němčinou, který jazyk si pro psaní vybereš? Kolik prostoru navíc můžeš získat vhodnou volbou jazyka eseje? (zvol případně jiné tři jazyky, ve kterých dovedeš napsat tisíciznakovou esej)
Obsahově bude esej pokaždé stejná. Je ale možné, že by některý jazyk byl úspornější, neboli dokázal by stejný význam zakódovat s menším počtem znaků? Nejjistější by bylo napsat esej ve všech třech jazycích. Ale to se asi nikomu nechce. Jak určit nejúspornější jazyk předtím, než se pustíš do psaní?
Pomůže nalezení shodných textů v různých jazycích. Různé jazykové verze má např. Wikipedie - jenže obsah článků se v různých jazycích liší (i proto se vyplatí nahlížet třeba aspoň na anglickou verzi, leckdy uvádí další zdroje a informace). Zamysli se: jaké texty existují v různých jazycích, jsou snadno dostupné a nedá příliš práce spočítat jejich délku?
Nabízí se např. základní náboženské texty, klasická beletrie (nepodléhající autorskému právu), ale také evropská legislativa, překládaná do jazyků členských zemí.
Zbývá tedy jen najít vhodné texty a zjistit jejich délku. To lze uskutečnit v lepším textovém editoru, nebo s jistou opatrností porovnáním velikosti souborů s textem (je třeba zajistit, aby soubory obsahovaly opravdu jen daný text). Výsledek bude tím relevantnější, čím bude obsah blíž typické školní eseji. Obsahuje-li text příliš mnoho odrážek, číslování a dalších znaků, které nenesou obsah, je třeba je odstranit. Pro další zvýšení přesnosti si rozmysli, jestli správně pracuješ s mezerami.
Našel se mezi jazyky nějaký rozdíl? Odpovídá tvému odhadu?
Nasnadě je otázka: čím to je, že se délka textu v různých jazycích mezi sebou tolik liší?
Využij toho, že už víš, které jazyky se jak liší, a zároveň ty jazyky znáš. Otázka tedy ve skutečnosti zní např. „proč je německy psaný text delší, než český?“ Podívej se podrobněji na kratší odpovídající úseky textů.
Možné odpovědi
- Některé jazyky mohou mít v průměru delší slova. Takovou hypotézu je samozřejmě třeba ověřit. A i potom se musíme ptát: proč?
- Jazyky mohou používat více či méně slov ve větě, zatímco počet vět bude asi přibližně stejný.
- Některé jazyky používají členy, některé se obejdou bez nich.
- Různé jazyky slova do různé míry ohýbají. To může znamenat použití koncovek, tedy znaků navíc. (Ovšem otázka je: Jak to, že jsou jiné jazyky srozumitelné i bez odlišných tvarů slov pro sedm pádů? Jakým způsobem je v nich sděleno to, co my vyjádříme pádem? Nejsou jejich texty nakonec delší, protože musí chybějící význam nějak opsat?
- Existují slova a znaky, které přinášejí jen velmi málo významu (málokdy rozliší nějaké možnosti). Např. v angličtině najdeme téměř za každým q jedno u. Takže by vlastně stačilo si ho tam domyslet, a texty by se opět o něco zkrátily. Najdeš další podobné příklady?
- Některé jazyky používají např. diakritiku k měkčení (ď, ť, ň...). Jiné jazyky používají ke změkčení zvláštní znak (gy, ty, ny...). Ty druhé jsou patrně o něco delší. Ovšem abychom byli fér, je potřeba si uvědomit, že ď, ť, ň a další jsou nové znaky abecedy. Dá se očekávat, že v jazycích s menší abecedou budou texty delší, kdežto v jazycích s rozsáhlejší abecedou mohou být texty kratší. Podobně, jako jsou desítkově zapsaná čísla kratší, než jejich dvojkové zápisy. Pro korektní srovnání je tedy třeba převod na jednotnou velikost abecedy.
Jaké je dobré kódování?
Dobré kódování znamená také snadnou srozumitelnost příjemcem. Pro lidské příjemce (na rozdíl od strojových) je často vhodná vizuální reprezentace sdělení, jak ukazuje Tomáš Marek na následujícím videu: https://www.youtube.com/watch?v=2VJDnuoLwV8
Proč jsou přirozené jazyky tak neúsporné? Zčásti je to dáno historickým vývojem. Hlavně je ale třeba si uvědomit, že úspornost sdělení není jediným kritériem kvality. Čím je kódování úspornější, tím je zpravidla složitější. Unární soustava je krásně jednoduchá na pochopení, zápis i počítání. Jenže prostě zabere hodně místa. Dvojková soustava je mnohem úspornější, ale také o dost obtížnější na pochopení. Ještě úspornější je soustava desítková. Ovšem ve srovnání s dvojkovou je mnohem složitější jak počtem použitých znaků, tak algoritmy pro počítání. Kdybychom se vyjadřovali jen stručně namísto stručně, jasně a výstižně, nemuselo by nám být pro samou stručnost rozumět.
Redundance
Typickým zdrojem chyb při přenosu signálů je šum. Komunikační kanál nemíváme celý pro sebe. Rozhovor vedle sportovního přenosu je obtížný, protože si televize bere kus komunikačního kanálu pro sebe a zaplňuje ho zvuky, které nás nezajímají - tedy šumem. Šum se mísí se signály, které nás zajímají (mluvené slovo partnera), a my je při poslechu musíme opět oddělit, abychom se dostali k významu sdělovaných slov.
Šum uslyšíš, když zapneš rádio a nenaladíš žádnou stanici. Když totéž uděláš s televizí, tak šum uvidíš. Jde o elektromagnetický šum na vysílacích frekvencích. Šum můžeš i vyfotit. Zamiř aparátem do tmy, nastav dlouhý čas a vysokou citlivost a pořiď snímek. Vidíš elektromagnetický šum na frekvenci viditelného světla. Šum je nežádoucí jev, a proto informatici hledají způsoby, jak jeho vliv omezit. Zcela odstranit jej totiž nejde, je prostě součástí prostředí a kazí tak všechny komunikační přenosy.
Kódování (nejen přirozené jazyky) také často pracují s redundancí, neboli nadbytečností. Na jedné straně je redundance plýtváním, na druhé straně přináší některé výhody. V první řadě je to robustnost. Když se část zprávy poškodí či ztratí, máme šanci informaci zrekonstruovat z toho, co zbylo.
Příklad:
Ve spojení „červená pilulka“ se rody adjektiva a substantiva shodují. My ale víme, že pilulka je rodu ženského, takže ženský rod adjektiva červený žádnou informaci neposkytne. Srovnej s anglickým “red pill”, “Red Bull”, “Red Sonja”.
Na redundanci lze nahlížet i z jiné strany. Obrovské množství různých posloupností písmen nemá v češtině žádný význam. Plýtváme tedy potenciálními slovy a větami. Příznivým důsledkem ovšem je, že snáze poznáme chybu — chybný text často prostě nedává smysl. Kdyby každý text nějaký smysl dával, mohli bychom komunikovat pomocí kratších zpráv, ale jen obtížně bychom odhalovali chybně přenesené zprávy.
Díky tomu, že tolik posloupností nedává smysl, nejsou všechny možné zprávy stejně pravděpodobné. Lze proto např. z části zprávy odhadnout její zbytek. Neúplné využití možných zpráv je tedy jen jiným popisem téhož jevu, totiž redundance.
Redundance je ovšem mnohem obecnější princip. Silniční síť je dostatečně „hustá“, aby při opravách umožnila objížďky. Telefonní pevná linka funguje i při výpadku proudu - telefonní kabely totiž mají vlastní napájení. Výtah visí na víc než jednom laně.
Vzpomeň si na další příklady redundance, ať už umělé či přirozené. Jaké redundance v daných případech přináší výhody a nevýhody?
Řešení
- Motor velkého dopravního letadla, rezerva v autě, třetina plynu v lahvi jeskynních potápěčů;
- zálohovaná data, tři procesoryaritmeticko-logické jednotky v historických počítačíchv samočinném počítači pro zvýšení spolehlivosti výsledků;
- druhé zadání nového hesla, zkouška v matematice, většina osobních údajů na formulářích, údaje při citaci zdrojů;
- polovina molekuly DNA, jedna ledvina, mláďata r-stratéga, spermie;
- prezentační zásada „řeknu, co řeknu, pak to řeknu, nakonec řeknu, co jsem řekl“;
- Senát Parlamentu České republiky
- Vyjádření kompaktní CD disk, paměť RAM, virus HIV, RAS syndrom, dárek zdarma, nejoptimálnější přetransformace, we don’t need no education
- Opakování školní látky není redundance, lidský mozek potřebuje opakování a procvičování, aby si látku dlouhodobě zapamatoval.
Další příklady najdeš v úlohách.
Kontrolní součet je jednoduchá metoda, jak za cenu jisté redundance zjistit většinu chyb při přenosu zprávy. Spočívá v připojení součtu zprávyPřipomeňme si, že jakákoliv zpráva lze reprezentovat čísly. na její konec. Po přijetí příjemce zhotoví součet svůj a srovná ho se součtem přijatým. Pokud se liší, je jasné, že se zpráva po cestě nějak změnila. Tento princip, ovšem v mnohem pokročilejší formě, se využívá v podstatě při všech síťových přenosech. Když se redundance ještě trochu přidá, je dokonce někdy možné případné chyby opravit, aniž by bylo nutno cokoliv znovu posílat. To má značný význam pro rychlost komunikace. Spojení s vesmírnými sondami je bez podobných mechanismů téměř nemyslitelné.
Přitom „součet“ není zcela přesné vyjádření. Cílem je najít hodnotu, která zprávu dobře reprezentuje. To znamená, že když se zpráva při přenosu byť jen mírně poškodí, změní se i „součet“. Nejjednodušším příkladem takového součtu je paritní bit. Vyjadřuje, jestli je ve zprávě (ve dvojkové soustavě) sudý nebo lichý počet jedniček. Ke zprávě se tedy připojí jediný bit. Např. ke zprávě 1011011 se připojí 1, kdežto ke zprávě 0110110 se připojí 0. Pokud se při přenosu změní hodnota i jen jediného bitu, kontrolou paritního bitu to bude odhaleno. Je to ovšem nástroj poměrně základní, jak je vidno i z toho, jak si poradí s poškozením dvou bitů.
Kontrolní součet můžeme použít i pro kontrolu výsledků v matematice. Ciferace je výsledek opakovaného počítání ciferného součtu čísla, dokud nezůstane jediná cifra. Ciferace tzv. zachovává běžné operace. To znamená, že např. ciferace rozdílu dvou čísel je rovna rozdílu ciferací těch čísel, neboli C(a-b) = C(a)-C(b). Využití je nasnadě. Pro kontrolu spočteme a porovnáme příslušné ciferace a se značnou pravděpodobnostíZkus najít příklad chyby, kterou kontrola pomocí ciferace neodhalí. odhalíme numerickou chybu. Např. spočteme, že 92-48=54. Následně spočteme ciferace, C(92)=C(11)=2, C(48)=C(12)=3, C(54)=9. Ovšem 2-3 není 9, takže je někde chyba. Detaily procesu si ještě promysli. Především otázky:
- V jakém vztahu jsou ciferace 0 a 9?
- Jak zacházet se zápornými ciferacemi?
- Jak si počítání ciferace vícemístných čísel ještě víc zjednodušit, co to celé má společného s dělením devíti?
- Jak pohodlně kontrolovat správnost dělení, které je opakem násobení?
Redundance je někdy chápána ne jako samotný jev nadbytečnosti, ale jako jeho míra. V teorii informace je tak redundance rovna rozdílu mezi délkou zprávy a množstvím informace, kterou nese. Redundance tedy udává, kolik bitů je ve zprávě „navíc“.
Kvalita kódování nutně vychází z účelu kódování. Pro různé druhy informací, různé požadavky na rychlost a spolehlivost, různá prostředí atd. se tedy používají různá kódování. Cílem je najít rovnováhu mezi často protichůdnými vlastnostmi kódování, jako jsou úspornost, spolehlivost, snadnost použití. Řečeno jinými slovy, rozhodujícím kritériem kvality kódování zpravidla nebude efektivita ve smyslu délky výsledných zpráv, nýbrž efektivita ve smyslu celkových nákladů. V těch se projeví náklady na přenos, dané délkou zpráv, ale také náklady na opakování přenosu nebo dokonce napravování důsledků chybně přenesených zpráv, a v neposlední řadě také náklady na samotné kódování a dekódování, které by tedy nemělo být přehnaně složité. Jak spočítat skutečné množství informace ve zprávě zjistíme v kapitole o entropii.
Shrnutí
Datová zpráva obvykle nenese tolik informace, kolik by se do ní teoreticky vešlo. Kromě předchozích znalostí příjemce to ovlivňuje především (ne)úspornost kódování a záměrná redundance (nadbytečnost).
Redundance zvyšuje množství potřebných dat, ale na druhé straně umožňuje zjistit a opravit chyby v přenesených zprávách. Méně úsporné kódy mohou být také snazší na zpracování.
