Kódováním se řeší otázka, jak převést nějaký text do slov, která používají předem dané symboly. Množině těchto symbolů se říká abeceda, velice často je volena abeceda sestávající ze symbolů 0 a 1, tedy binární abeceda. Důležitým faktorem kódování je otázka, jak tento převod udělat efektivně, protože jedním z hlavních účelů kódování je zbytečně nezatěžovat přenosové kanály (například síť či datové úložiště).
Příkladem kódování je ASCII kód, který písmenům anglické abecedy a dalším běžným znakům přiřazuje sedmibitová slova nad~binární abecedou. Například písmenko „A“ má ASCII kód \(1000001\) (tomu odpovídá číslo \(65\) v desítkové soustavě).
Otázka efektivity kódování je úzce spjata s úlohou komprese a často se s ní překrývá. Úkolem komprese je zmenšení objemu dat s podmínkou, aby data zůstala zachována a bylo možné je zrekonstruovat beze ztrát.
Dalším důležitým prvkem kódování může být odolnost vůči chybám při přenosu. Tzv. samoopravné kódy jsou navrženy tak, že pokud je počet chyb při přenosu menší než daná mez, tak jsme stále schopni ze zakódovaného textu i s chybami způsobenými přenosem zrekonstruovat původní text.
U obou zmíněných faktorů kódování hraje hlavní roli matematika, která nám svými prostředky umožňuje takové kódy navrhnout a dokázat o nich, že mají potřebné vlastnosti. Oblast matematiky, která se zabývá kódováním, se nazývá teorie kódování, částečně se podobnými problémy zabývá u teorie informace. Z rozsáhle literatury, která je této oblasti věnována, jmenujme [1,2], ze kterých bylo čerpáno. Připomeňme ještě rozdíl mezi kódováním a šifrováním, neboť tyto dva termíny jsou někdy používány bez rozdílu. Šifrování převádí text do takové formy, aby jej mohly převést zpět pouze osoby mající oprávnění; kódování tuto otázku neřeší.
Budeme se krátce věnovat jednomu hojně využívanému kódování a to sice Huffmanovu kódu. Stručně řečeno se jedná o kód, který převádí jednotlivé symboly původního textu a dělá to co nejúspornějším způsobem -- výsledná délka zakódovaného textu je v nějakém smyslu nejmenší možná. Huffmanův kód získáme pomocí Huffmanova algoritmu, který David Huffman vymyslel v roce 1951 při zkoušce z teorie informace na univerzitě MIT.
Na Fakultě informačních technologií ČVUT v Praze se s Huffmanovým kódováním můžete setkat v předmětu Komprese dat.
Huffmanův algoritmus vysvětlíme nejlépe na příkladu. Chceme zakódovat do binární abecedy text, který sestává z 5 symbolů: \(A\), \(B\), \(C\), \(D\) a \(E\). Označme tuto abecedu \(\mathcal{X} = \{A, B, C, D, E\}\). Předpokládejme, že těchto 5 symbolů následující pravděpodobnosti výskytu: $$ p(A) = 0,4 \ \text{, } \ p(B) = p(C) = 0,2 \ \text{ a } \ p(D) = p(E) = 0,1 \ . $$ Tuto pravděpodobnost lze chápat tak, že podíváme-li se na jakoukoliv pozici v kódovaném textu, tak pravděpodobnost, že na této pozici nalezneme symbol \(A\) je 40 % (nezávisle na tom, na jakou pozici se koukáme). Tyto pravděpodobnosti vyjadřují jistou znalost obsahu kódovaného textu; právě tato znalost nám pomůže jej efektivně zakódovat. Pokud je text známý, lze jako tyto pravděpodobnosti použít relativní četnosti symbolů, tedy například pravděpodobnost výskytu symbolu \(A\) v textu \(d\) bychom napočítali ze vzorce $$ p(A) = \dfrac{\text{počet výskytů } A \text{ v } d}{\text{délka } d}. $$ Pokud je text neznámý, používají se odhady těchto pravděpodobností získaných například z trénovacích textů či jiných očekávaných vlastností kódovaného textu.
Algoritmus nejprve sestaví Huffmanův strom, který nám pomůže vytvořit Huffmanův kód. Výsledný strom (pro výše zmíněné pravděpodobnosti) je zobrazen na Obrázku 1, pro názorné pochopení následujícího postupu je třeba jej číst odspoda, řádek po řádku.
Nyní je třeba přiřadit každému symbolu z \(\mathcal{X}\) slovo ze symbolů \(0\) a \(1\). To určíme tak, že začneme od kořene stromu, v našem případě vrcholu \(A+B+C+D+E\), přiřazovat symboly \(0\) nebo \(1\) cestám k listům stromu, tedy samotným symbolům původní abecedy. To uděláme tak, že pokud jdeme z rodiče doleva, zapíšeme symbol \(0\), pokud jdeme doprava, zapíšeme symbol \(1\). K symbolu \(A\) se dostaneme jedním odbočením doleva, zapíšeme tedy slovo \(0\). K symbolu \(B\) jdeme nejprve doprava, pak doleva: jeho kódování bude \(10\). Postup je znázorněn na Obrázku 2. Celkem dostaneme následující kódování, které lze chápat jako zobrazení \(h: \mathcal{X} \mapsto \{0,1\}^*\), kde \(\{0,1\}^*\) je množina konečných slov nad binární abecedou.
| \(x\) | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) |
|---|---|---|---|---|---|
| \(h(x)\) | \(0\) | \(10\) | \(110\) | \(1110\) | \(1111\) |
Přímo z našeho příkladu je vidět, že Huffmanův kód není jednoznačný. Pokud bychom ve třetím kroku volili jinak, dostaneme jiný strom, a tedy i jiný kód. Jeden možný výsledek této jiné volby je na Obrázku 3. Toto však nemá vliv na následující vlastnosti Huffmanova kódu.
Platí, že pro všechna \(x \in \mathcal{X}\), žádné slovo \(h(x)\) není prefixem jiného slova \(h(y)\) pro \(y \in \mathcal{X}\) a \(x \neq y\). Tato vlastnost výrazně zjednodušuje dekódování: zakódovaný text čteme zleva doprava a jakmile přečteme nějaké slovo z množiny \(\{ h(x) \colon x \in \mathcal{X} \}\), množiny kódových slov, můžeme jej hned nahradit symbolem z \(\mathcal{X}\). Toto nám zajistí jednoznačnou dekódovatelnost -- každý text sestávající z kódových slov lze jednoznačně dekódovat.
Druhou, neméně důležitou vlastností Huffmanova kódování, je jeho optimalita v následujícím smyslu. Máme-li zakódovaný text, pak jeho střední délka je číslo $$ L = \sum_{x \in \mathcal{X}} p(x) l(x), $$ kde \(l(x)\) je délka kódového slova \(h(x)\). V našem příkladu vyjde $$ L = 0,4 \cdot 1 + 0,2 \cdot 2 + 0,2 \cdot 3 + 0,1 \cdot 4 + 0,1 \cdot 4 = 2,2. $$ Optimalita je pak vyjádřena tvrzením [2], že jakýkoliv jiný jednoznačně dekódovatelný kód (který je stejného typu -- kóduje jednotlivé symboly \(\mathcal{X}\)) ma střední délku větší nebo rovnu střední délce Huffmanova kódu.
O užitečnosti Huffmanova algoritmu svědčí příklady jeho použití. Kódování je použito ve formátech MPEG Layer 3 (neboli MP3) a i jeho následovníku MPEG Advanced Audio Coding (neboli AAC).
Jako další příklad jmenujme formát Joint Photographic Experts Group neboli JPEG, který taktéž používá Huffmanovo kódování (umožňuje použití i jiného kódování).
Některá další kódování dosahují ze jistých podmínek lepšího kompresního poměru než Huffmanův kód. Jmenujme bez uvádění jejich vlastnosti dva příklady takových kódů a to sice aritmetické a LZW kódování.