Strom rodičovský uzol: Efektívne kódovanie dát pomocou Huffmanovho kódovania

Moderný digitálny svet vyžaduje efektívne metódy spracovania, ukladania a prístupu k informáciám. Jednou z kľúčových techník je kompresia dát, ktorá znižuje objem dát bez straty informácií. V tomto článku sa zameriame na Huffmanovo kódovanie, metódu bezstratovej kompresie, ktorá využíva stromovú štruktúru - strom rodičovský uzol - 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) tohoto 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é. Stačí spočítať početnosť všetkých znakov.

Prečítajte si tiež: Starostlivosť o drevo a povrchy: Kompletný sprievodca

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. Zmeny v kóde sú až na riadku 35. 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.

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>using 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);}int main() { // 1. Výpočet pravdepodobnosti znakov vector<Znak> znaky = pravdepodobnost_znakov("text.txt"); // 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 vypis_kodove_slova(koren); return 0;}

Tento kód demonštruje základné kroky Huffmanovho kódovania:

  1. Výpočet pravdepodobnosti znakov: Funkcia pravdepodobnost_znakov číta vstupný súbor, spočíta výskyty jednotlivých znakov a vypočíta ich pravdepodobnosti. Výsledkom je vektor štruktúr Znak, ktorý obsahuje znak a jeho pravdepodobnosť.

  2. Vytvorenie Huffmanovho stromu: Funkcia vytvor_huffmanov_strom vytvára binárny strom na základe pravdepodobností znakov. Využíva prioritnú frontu (min-heap) na efektívne spájanie uzlov s najmenšími pravdepodobnosťami.

    Prečítajte si tiež: Naučte sa rozoznávať vtáčie melódie

  3. Priradenie kódových slov: Rekurzívna funkcia zapis_kodove_slova prechádza stromom a priraďuje každému znaku kódové slovo. Ľavému potomkovi priradí bit "0" a pravému potomkovi bit "1".

  4. Výpis kódových slov: Funkcia vypis_kodove_slova vypíše kódové slová pre jednotlivé znaky.

Princíp fungovania

Pri tvorbe Huffmanovho kódu budeme vytvárať binárny strom, čo bude vlastne kódovací strom Huffmanovho kódu. Vstupný údaj pre tento príklad je tabuľka pravdepodobností výskytu znakov abecedy v texte.

Implementácia algoritmu prebieha v dvoch fázach:

  1. Fáza 1: Vytvorenie stromu.

    Prečítajte si tiež: Ako pestovať červienku

    • Na začiatku máme pre každý znak abecedy jeden uzol stromu (list).
    • Opakovane vyberáme dva uzly s najmenšou pravdepodobnosťou výskytu.
    • 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.
    • Tento nový uzol vložíme späť do množiny uzlov.
    • Tento proces opakujeme, kým nám nezostane len jeden uzol - koreň stromu.

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

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

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, 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.

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 (riadok 5 a 6). Po tomto posunutí sa počet zástupných znakov v abecede zmmenší o 1 (riadok 7). Riadok 8 - na pozícii n už nebude žiaden uzol.

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.

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. Typický príklad je stromová štruktúra.

tags: #strom #rodičovský #uzol

Ďalšie články