Huffmanovy kódy: příklady, aplikace

V tuto chvíli málo lidí uvažuje o tom, jak funguje komprese. Ve srovnání s minulostí je používání osobního počítače mnohem jednodušší. A prakticky každá osoba pracující s souborovým systémem používá archivy. Ale jen málo lidí si myslí, jak fungují a jaký je princip komprese souborů. První verze tohoto procesu byly Huffmanovy kódy a stále se používají v různých populárních archivorech. Mnozí uživatelé si ani nemyslí, jak snadné je komprimovat soubor a podle toho, jak funguje. V tomto článku se podíváme na to, jak se komprese provádí, jaké nuance pomáhají urychlit a zjednodušit proces kódování a zjistíme, jaký je princip konstrukce kódujícího stromu.

Historie algoritmu

Prvním algoritmem pro efektivní kódování elektronických informací byl kód navržený Huffmanem v polovině dvacátého století, jmenovitě v roce 1952. V současné době je hlavním základním prvkem většiny programů vytvořených pro kompresi informací. V současnosti je jedním z nejpopulárnějších zdrojů tohoto kódu ZIP, ARJ, RAR archivy a mnoho dalších. Tento Huffmanův algoritmus se také používá komprese obrázků JPEG a další grafické objekty. Všechny moderní faxové přístroje také používají kódování, vynalezené v roce 1952. Navzdory tomu, že od vzniku tohoto kódu uplynulo tolik času, dodnes se používá v nejnovějších skořápkách a na vybavení starých a moderních typů.

Princip účinného kódování

Huffmanův algoritmus je založen na schématu, který umožňuje nahrazení nejpravděpodobnějších, nejčastěji se vyskytujících symbolů binární kódy systému. A ty, které jsou méně časté, jsou nahrazeny delšími kódy. Přechod na dlouhé kódy Huffmanu nastane až poté, co systém použije všechny minimální hodnoty. Tato technika umožňuje minimalizovat délku kódu pro každý znak původní zprávy jako celku. Důležitým bodem je, že na začátku kódování by měla být pravděpodobnost výskytu písmen známa. Z nich bude sestaven poslední zpráva. Na základě těchto dat je vytvořen kódový strom Huffman, na jehož základě bude probíhat proces kódování písmen v archivu.

Huffmanův kód, příklad

Pro ilustraci algoritmu si vezměme grafickou variantu konstrukce stromu kódů. Chcete-li použít tuto metodu, je užitečné objasnit definici některých hodnot nezbytných pro koncept této metody. Sada oblouků a uzlů, které jsou směrovány z uzlu do uzlu, se obvykle nazývá graf. Samotný strom je graf se souborem určitých vlastností:

• v každém uzlu nelze zadat více než jeden oblouk;
• jeden z uzlů musí být kořen stromu, tj. žádný oblouk by ho vůbec neměl zadat;
• pokud se z kořenu začne pohybovat podél oblouků, měl by tento proces umožnit dostat se úplně do libovolného uzlu.

Tam je také takový koncept, který je obsažen v Huffman kódech, jako list stromu. Je to uzel, ze kterého by neměl unikat žádný oblouk. Pokud jsou dva uzly propojeny obloukem, pak jeden z nich je rodič, druhý dítě, v závislosti na tom, z jakého uzlu vychází oblouk a v které z nich je. Pokud mají dva uzly stejný nadřazený uzel, obvykle se nazývají bratrské uzly. Pokud je kromě listů v uzlech několik oblouků, tento strom se nazývá binární. To je přesně strom Huffmana. Zvláštnost uzlů této konstrukce spočívá v tom, že hmotnost každého rodiče se rovná součtu hmotnosti všech uzlů.

Algoritmus pro stavbu stromu podle Huffmana

Konstrukce Huffmanova kódu je vytvořena z písmen vstupní abecedy. Zobrazí se seznam těchto uzlů, které jsou v budoucím stromu kódu zdarma. Hmotnost každého uzlu v tomto seznamu by měla být stejná jako pravděpodobnost výskytu písmena zprávy odpovídající tomuto uzlu. V tomto případě je mezi několika málo volnými uzly budoucího stromu vybrána ta, která váží nejméně. Současně, pokud jsou pozorovány minimální indikátory v několika uzlech, je možné libovolně vybrat libovolnou dvojici. Poté je vytvořen nadřazený uzel, který by měl vážit tolik, kolik činí součet tohoto páru uzlů. Poté je rodič odeslán do seznamu s volnými uzly a děti jsou smazány. Zároveň oblouky dostávají odpovídající indexy, jedny a nuly. Tento proces se opakuje přesně tak dlouho, dokud je třeba nechat pouze jeden uzel. Poté jsou binární čísla zaznamenána shora dolů.

Zlepšení efektivity komprese

S cílem zvýšit účinnost komprese, je nutné během strom stavebním řádu používat všechny údaje o pravděpodobnosti výskytu písmen v určitém souboru, které jsou připojeny ke stromu, a nedovolí, že jsou rozptýleny přes velký počet textových dokumentů. V případě, že pre-procházka tohoto souboru, můžete okamžitě výpočet statistiky o tom, jak často jsou písmena provozovny podléhající stlačení.

Zrychlení procesu komprese

Zrychlit práci algoritmus, definice dopisy by neměly být prováděny podle indexů pravděpodobnosti výskytu určitého písmena, ale podle četnosti jeho výskytu. Díky tomu se algoritmus stává jednodušším a práce s ním je značně zrychlena. To také zamezuje operacím spojeným s plovoucí čárkami a dělením. Kromě toho v tomto režimu pracuje dynamický Huffmanův kód, nebo spíše samotný algoritmus, žádné změny. To je způsobeno zejména skutečností, že pravděpodobnosti jsou přímo úměrné frekvencím. Stojí za to věnovat zvláštní pozornost skutečnosti, že konečná hmotnost souboru nebo takzvaného kořenového uzlu se bude rovnat součtu počtu písmen v objektu, který má být zpracován.

Závěr

Huffmanovy kódy jsou jednoduchý a dlouho-zavedený algoritmus, který je stále používán mnoha známými programy a společnostmi. Jeho jednoduchost a přehlednost umožňují dosáhnout efektivních výsledků komprese pro soubory libovolné velikosti a významně snížit prostor, který obsazují na úložném disku. Jinými slovy, Huffmanův algoritmus je dlouhý studovaný a dobře navržený schéma, jehož význam se až dodnes nezmenšuje. A díky možnosti snížit velikost souborů, přenášet je přes síť nebo jiným způsobem, je snazší, rychlejší a pohodlnější. Při práci s algoritmem můžete libovolně komprimovat libovolné informace bez poškození struktury a kvality, ale s maximálním účinkem snížení váhy souboru. Jinými slovy, kódování kódu Huffman bylo a zůstává nejpopulárnějším a nejaktuálnějším způsobem komprese velikosti souborů.