Pochopenie Stromu Rodičovského Uzla v Dátových Štruktúrach

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.

Čo je to dátová štruktúra a prečo sú dôležité stromy?

Dátové štruktúry predstavujú spôsob organizácie, uchovávania a spracovania dát tak, aby sa dali efektívne používať v počítačových programoch. Poskytujú dátam určitú formu a určujú, ako budú dáta usporiadané, ale aj ako s nimi bude možné manipulovať. Vždy sa pri návrhu dátovej štruktúry, alebo pri výbere nejakej existujúcej snažíme optimalizovať rýchlosť operácií ako vyhľadávanie dát, ich načítanie a zápis. Sekundárne treba pamätať na to, že efektívne dátové štruktúry by mali minimalizovať pamäťovú náročnosť.

Strom je základná nelineárna dátová štruktúra, ktorá organizuje dáta hierarchicky. Skladá sa z uzlov, kde každý uzol má jeden nadradený uzol - rodiča (okrem koreňového uzla) a môže mať nula alebo viacero podriadených uzlov - potomkov. Stromy sú jednou z najdôležitejších dátových štruktúr v informatike.

Binárny strom a rodičovský uzol

Binárny strom spĺňa podmienku, že každý rodičovský uzol je väčší alebo menší ako jeho potomkovia. 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 a 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).

Huffmanovo kódovanie: Aplikácia stromu rodičovského uzla

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.

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.

Ú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. Takáto štruktúra obsahuje premennú znak typu char a premennú pp typu double, čo je vlastne pravdepodobnosť znaku.

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

1. Fáza 1: Vytvorenie kódovacieho stromu
   • 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.

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 funkciu 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; TUzol(char z = 0, double p = 0.0, TUzol* l = nullptr, TUzol* r = nullptr) : znak(z), pravdepodobnost(p), lavy(l), pravy(r), 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) { fronta.push(new TUzol(z.znak, z.pp)); } // 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(0, lavy->pravdepodobnost + pravy->pravdepodobnost, lavy, 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) { // Ak je to list 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 zmazanie binárneho stromuvoid zmaz_strom(TUzol* uzol) { if (!uzol) return; zmaz_strom(uzol->lavy); zmaz_strom(uzol->pravy); delete uzol;}int main() { // 1. Vytvorte súbor 'text.txt' s testovacím textom ofstream test_subor("text.txt"); test_subor << "Toto je testovaci text pre Huffmanovo kodovanie."; test_subor.close(); // 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 cout << "Huffmanove kody:" << endl; vypis_kodove_slova(koren); // Uvoľnenie pamäte zmaz_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, aby nedošlo k memory leakom. Funkcia zmaz_strom slúži na rekurzívne uvoľnenie pamäte.
• Rekurzia: Rekurzívna funkcia zapis_kodove_slova elegantne prechádza stromom a priraďuje kódové slová. Rekurzívne volanie sa ukončí ak narazíme na neexistujúci uzol.
• Štruktúra TUzol: Dátová časť štruktúry TUzol by mala byť alokovaná dynamicky.

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

tags: #strom #rodicovsky #uzol