Bezeztrátová komprese pomocí bitů

Počítače reprezentují všechna data v binární soutavě, takže všechny typy souborů, od textu po obrázky a videa, jsou v konečném důsledku sekvencemi bitů. Bez ohledu na to, zda bity reprezentují dokument nebo GIF, počítače mohou použít kompresní bitovou techniku nazývanou Huffmanovo kódování.

Podívejme se, jak algoritmus funguje na jednoduchém textovém příkladu. Tento jazykový příklad používá pouze 4 různé znaky, a přesto je pro nás nesmírně důležitý: je to jazyk používaný k reprezentaci DNA a skládá se ze sekvencí čtyř znaků A, C, G a T.

Například 4,6 milionů znaků reprezentujících sekvenci DNA E.coli začíná následovně:

Protože potřebujeme reprezentovat čtyři znaky, počítač by obvykle reprezentoval každý znak pomocí 2 bitů, a to následovným způsobem:

Výše uvedených 13 znaků by bylo zapsáno pomocí 26 bitů následovně - všimni si, že nepotřebujeme mezi kódem pro jednotlivé bity žádné mezery.

Můžeme to ale udělat i lépe. Ve výše uvedeném vzorovém textu je písmeno "t" mnohem častější než ostatní písmena ("t" se objevuje sedmkrát, "c" třikrát, "a" dvakrát a "g" jen jednou). Pokud pro písmeno "t" použijeme kratší kód, pak bychom využívali méně místa až 54 % času (7 z 13 znaků). Mohli bychom například použít následující kód:

Našich 13 znaků by pak bylo nakódováno následovně:

Je to pouhých 22 bitů, o čtyři bity méně než naše původní kódování. Možná to tak nevypadá, ale představ si, že bychom využili takovouto optimalizaci na všech 4,6 milionů znaků DNA!

Možná se nad novými binárními kódy s různými délkami podivuješ. Je ještě možné kód spolehlivě dekódovat? Ano, se správnou kombinací kódů.

To je krása Huffmanova kódování: algoritmus nám dává způsob, jak použít množinou binárních kódů pro danou sekvenci, čímž se zajistí, že data mohou být rekonstruována jednoznačně a spolehlivě.

Mnoho formátů souborů používá nějaký druh Huffmanova kódování ke zmenšení velikosti souboru. Faxové stroje používají Huffmanovo kódování po použití RLE při černobílých sekvencích. PNG obrázky se komprimují pomocí LZ77, algoritmus podobný technologii komprese textu, který jsme se naučili, v kombinaci s Huffmanovým kódováním výsledků.