Huffmanovo kódovanie a strom rodičovský uzol

V súčasnom digitálnom svete sú dáta jednou z najcennejších komodít. Dáta sú všadeprítomné a stávajú sa hybnou silou inovácií vo všetkých oblastiach ľudskej činnosti. Ich efektívne využitie však vyžaduje porozumenie ich štruktúre a spracovaniu - čo nás privádza k dátovým štruktúram. Predstavme si knižnicu bez akéhokoľvek systému usporiadania kníh - chaos, v ktorom je takmer nemožné nájsť, čo hľadáme. Tieto štruktúry, ktoré sú pre nás používateľov neviditeľnou architektúrou, sú zodpovedné za správnu kategorizáciu dát, uloženie a spracovanie takým spôsobom, aby napríklad bolo možné efektívne vyhľadávať informácie.

V tomto článku sa ponoríme do fascinujúceho sveta dátových štruktúr, konkrétne sa zameriame na Huffmanovo kódovanie a kľúčovú úlohu stromu rodičovský uzol. Huffmanovo kódovanie je metóda bezstratovej kompresie dát, ktorá znižuje objem dát bez straty informácií. Využíva stromovú štruktúru na dosiahnutie optimálnej reprezentácie dát.

Úvod do Huffmanovho kódovania

Huffmanovo kódovanie je metóda bezstratového kódovania dát založená na entropii kódovaného textu. Využíva premenlivú dĺžku kódov pre jednotlivé znaky, pričom častejšie sa vyskytujúce znaky majú kratšie kódy a menej časté znaky dlhšie kódy. Týmto spôsobom sa dosiahne celkové zníženie objemu dát.

Pri tvorbe samotného Huffmanovho kódu využijeme dátovú štruktúru binárny strom. Listy (koncové uzly) tohto binárneho stromu budú reprezentovať abecedu kódovania. V uzle budú teda informácie o konkrétnom znaku a jeho pravdepodobnosti výskytu. Po vytvorení takéhoto kódovacieho stromu musíme znakom vstupnej abecedy prideliť kódové slová. Kódové slovo pozostáva iba z jednotiek a núl.

Analýza textu a získanie pravdepodobností

Pre vytvorenie Huffmanovho kódu je potrebné poznať celú abecedu, ktorá bola použitá v správe, a ďalej je potrebné vedieť pravdepodobnosti výskytov znakov abecedy v texte. Vstupný údaj pre tento príklad je tabuľka pravdepodobností výskytu znakov abecedy v texte. Túto tabuľku si môžeme vypočítať (zo súboru text.txt) pomocou funkcie pravdepodobnost_znakov, alebo použiť už pripravenú tabuľku.

Úlohou je zistiť pravdepodobnosť výskytu všetkých znakov v danom texte. Inak povedané, je treba zistiť pravdepodobnosť výskytu všetkých znakov abecedy. Získanie pravdepodobnosti výskytu je jednoduché. Uvažujme vstupný textový súbor ("text.txt") v ktorom je text v prirodzenom jazyku. Úlohou je ale vygenerovať súbor, v ktorom budú znaky abecedy usporiadané podľa ich pravdepodobnosti výskytu v texte od najmenšieho po najväčšie. Pre potreby zotriedenia znakov podľa ich pravdepodobností musíme tieto znaky uložiť do vhodnej štruktúry, kde by bola informácia o znaku a jeho pravdepodobnosti výskytu.

Princíp fungovania Huffmanovho kódovania

Pri tvorbe Huffmanovho kódu budeme vytvárať binárny strom, čo bude vlastne kódovací strom Huffmanovho kódu. Na začiatku máme pre každý znak abecedy jeden uzol stromu (list).

1. Opakovane vyberáme dva uzly s najmenšou pravdepodobnosťou výskytu.
2. Vytvoríme nový uzol (rodičovský uzol), ktorý bude mať tieto dva uzly ako svojich potomkov. Pravdepodobnosť tohto nového uzla bude súčtom pravdepodobností jeho potomkov.
3. Tento nový uzol vložíme späť do množiny uzlov.
4. Tento proces opakujeme, kým nám nezostane len jeden uzol - koreň stromu.

Fáza 2: Priradenie kódových slov

1. Prechádzame strom od koreňa k listom.
2. Každej hrane vedúcej k ľavému potomkovi priradíme bit "0".
3. Každej hrane vedúcej k pravému potomkovi priradíme bit "1".
4. Kódové slovo pre daný znak získame spojením bitov na ceste od koreňa k listu reprezentujúcemu daný znak.

Strom rodičovský uzol a jeho význam

V kontexte Huffmanovho kódovania, rodičovský uzol zohráva kľúčovú rolu pri vytváraní optimálneho kódovacieho stromu. Každý rodičovský uzol reprezentuje spojenie dvoch uzlov s najnižšou pravdepodobnosťou výskytu, čím sa zabezpečuje, že najčastejšie znaky budú mať kratšie kódové slová.

Funkcia vytvorí rodičovský uzol uzlov a a b. Po vytvorení nového uzla v kódovacom strome treba tento nový uzol vložiť na správne miesto do poľa uzlov. Tento nový uzol sa vloží do poľa abc na miesto s indexom min1. Prvok na indexe min2 už nepatrí do tohoto poľa, lebo je potomkom novo vytvoreného uzla. hodnoty min1 min2 určujú indexy prvkov v poli abc s najmenšími pravdepodobnosťami výskytu znaku v texte. Na pozíciu min1 sa vloží nový uzol (TUzol). Uzol reprezentujúci znak 'B' už do poľa abc nepatrí, pretože sa stal listom v kódovacom strome. Treba pole abc preusporiadať tak ako je naznačené: všetky uzly posunieme o jeden index vľavo. Po tomto posunutí sa počet zástupných znakov v abecede zmenší o 1.

Implementácia v C++

Pre ilustráciu si ukážeme príklad kódu v C++, ktorý demonštruje základné kroky Huffmanovho kódovania.

#include <iostream>#include <fstream>#include <vector>#include <queue>#include <map>#include <algorithm> // Pre sortusing namespace std;// Štruktúra pre uloženie znaku a jeho pravdepodobnostistruct Znak { char znak; double pp;};// Štruktúra pre uzol Huffmanovho stromustruct TUzol { char znak; double pravdepodobnost; TUzol *lavy; TUzol *pravy; string kodove_slovo;};// Funkcia pre výpočet pravdepodobnosti výskytu znakovvector<Znak> pravdepodobnost_znakov(const string& nazov_suboru) { ifstream subor(nazov_suboru); if (!subor.is_open()) { cerr << "Nepodarilo sa otvorit subor: " << nazov_suboru << endl; return {}; } vector<int> pocty_znakov(97 - 32, 0); // Pole pre početnosti znakov (medzera po apostrof) char znak; while (subor.get(znak)) { if (znak >= 32 && znak <= 96) { pocty_znakov[znak - 32]++; } } subor.close(); int celkovy_pocet_znakov = 0; for (int pocet : pocty_znakov) { celkovy_pocet_znakov += pocet; } vector<Znak> znaky; for (int i = 0; i < pocty_znakov.size(); ++i) { if (pocty_znakov[i] > 0) { Znak z; z.znak = static_cast<char>(i + 32); z.pp = static_cast<double>(pocty_znakov[i]) / celkovy_pocet_znakov; znaky.push_back(z); } } // Usporiadanie znakov podľa pravdepodobnosti (od najmenšej po najväčšiu) sort(znaky.begin(), znaky.end(), [](const Znak& a, const Znak& b) { return a.pp < b.pp; }); return znaky;}// Funkcia pre vytvorenie Huffmanovho stromuTUzol* vytvor_huffmanov_strom(const vector<Znak>& znaky) { // Prioritná fronta pre uzly stromu (min-heap) auto comp = [](TUzol* a, TUzol* b) { return a->pravdepodobnost > b->pravdepodobnost; }; priority_queue<TUzol*, vector<TUzol*>, decltype(comp)> fronta(comp); // Vytvorenie listov pre každý znak for (const auto& z : znaky) { TUzol* uzol = new TUzol; uzol->znak = z.znak; uzol->pravdepodobnost = z.pp; uzol->lavy = uzol->pravy = nullptr; fronta.push(uzol); } // Spájanie uzlov, kým nezostane len koreň while (fronta.size() > 1) { TUzol* lavy = fronta.top(); fronta.pop(); TUzol* pravy = fronta.top(); fronta.pop(); TUzol* rodic = new TUzol; rodic->znak = 0; // Zástupný znak pre rodičovský uzol rodic->pravdepodobnost = lavy->pravdepodobnost + pravy->pravdepodobnost; rodic->lavy = lavy; rodic->pravy = pravy; fronta.push(rodic); } return fronta.top(); // Koreň stromu}// Rekurzívna funkcia na priradenie kódových slovvoid zapis_kodove_slova(TUzol* uzol, string kod) { if (!uzol) return; if (!uzol->lavy && !uzol->pravy) { uzol->kodove_slovo = kod; return; } zapis_kodove_slova(uzol->lavy, kod + "0"); zapis_kodove_slova(uzol->pravy, kod + "1");}// Funkcia na vypísanie kódových slov pre jednotlivé znakyvoid vypis_kodove_slova(TUzol* koren) { if (!koren) return; if (!koren->lavy && !koren->pravy) { cout << "Znak: '" << koren->znak << "', Kod: " << koren->kodove_slovo << endl; return; } vypis_kodove_slova(koren->lavy); vypis_kodove_slova(koren->pravy);}// Funkcia na uvoľnenie pamäte stromuvoid zrus_strom(TUzol* uzol) { if (!uzol) return; zrus_strom(uzol->lavy); zrus_strom(uzol->pravy); delete uzol;}int main() { // 1. Výpočet pravdepodobnosti znakov zo súboru "text.txt" vector<Znak> znaky = pravdepodobnost_znakov("text.txt"); if (znaky.empty()) { cerr << "Neboli najdene ziadne znaky na spracovanie." << endl; return 1; } // 2. Vytvorenie Huffmanovho stromu TUzol* koren = vytvor_huffmanov_strom(znaky); // 3. Priradenie kódových slov zapis_kodove_slova(koren, ""); // 4. Výpis kódových slov cout << "Huffmanove kodove slova:" << endl; vypis_kodove_slova(koren); // Uvoľnenie alokovanej pamäte zrus_strom(koren); return 0;}

Dôležité aspekty implementácie

• Prioritná fronta: Použitie prioritnej fronty (min-heap) je kľúčové pre efektívne vyhľadávanie dvoch uzlov s najmenšou pravdepodobnosťou.
• Dynamická alokácia pamäte: Pri vytváraní uzlov stromu je potrebné dynamicky alokovať pamäť pomocou new. Nezabudnite na uvoľnenie pamäte po skončení programu pomocou funkcie zrus_strom, aby nedošlo k memory leakom.
• Rekurzia: Rekurzívna funkcia zapis_kodove_slova elegantne prechádza stromom a priraďuje kódové slová.
• Štruktúra TUzol: Dátová časť štruktúry TUzol by mala byť alokovaná dynamicky, pretože premenná data je definovaná ako smerník na štruktúru THuff.

Optimalizácia a rozšírenia

• Adaptívne Huffmanovo kódovanie: Táto technika dynamicky upravuje Huffmanov strom na základe aktuálnych výskytov znakov v texte. To umožňuje lepšiu kompresiu pre texty s meniacou sa frekvenciou znakov.
• Kanonické Huffmanovo kódovanie: Táto technika zaručuje, že kódové slová sú usporiadané podľa dĺžky a lexikograficky. To zjednodušuje dekódovanie a umožňuje efektívnejšiu implementáciu.

Aplikácie Huffmanovho kódovania

Huffmanovo kódovanie sa používa v mnohých aplikáciách, kde je dôležitá kompresia dát:

• Kompresné formáty: JPEG, PNG, GZIP, ZIP
• Prenos dát: Fax, modem
• Archivácia dát: Ukladanie dát s obmedzeným priestorom

Jednomnohoznačná usporiadanosť a stromové štruktúry

Koncept jednomnohoznačnej usporiadanosti je úzko spojený so stromovými štruktúrami. Jednoduchá charakteristika: Každý prvok má najviac jedného rodiča, ale jeden prvok môže mať viacero detí/potomkov.

V lineárnej dátovej štruktúre sú všetky prvky usporiadané v lineárnom alebo sekvenčnom poradí. V nelineárnej dátovej štruktúre sú elementy usporiadané hierarchicky alebo do viacúrovňovej komplexnej dátovej štruktúry.

Abstraktný dátový typ (ADT) hovorí, čo sa má urobiť, a dátová štruktúra hovorí, ako sa to má urobiť. Inými slovami, môžeme povedať, že ADT nám poskytuje návrh, zatiaľ čo dátová štruktúra poskytuje implementačnú časť. V konkrétnom ADT môžu byť implementované rôzne dátové štruktúry. Napr. ADT zásobník môže na dátovej úrovni využívať dátovú štruktúru pole, alebo pospájaný zoznam (linked list).

Alternatívne dátové štruktúry pre Huffmanovo kódovanie

Aj keď sa binárny strom bežne používa pre Huffmanovo kódovanie, existujú aj alternatívne dátové štruktúry, ktoré sa dajú použiť:

• Pole smerníkov na TUzol: TUzol **abc - pole smerníkov na TUzol. Toto pole je výhodné pre operácie kopírovania uzlov.
• Halda: Halda (heap) je stromová dátová štruktúra, ktorá spĺňa podmienku, že hodnota každého uzla je menšia alebo rovná hodnote jeho potomkov (min-heap) alebo väčšia alebo rovná (max-heap). Halda sa dá použiť na efektívne vyhľadávanie dvoch uzlov s najmenšou pravdepodobnosťou.

tags: #strom #rodicovsky #uzol