Hlavne menu We are sorry, but magazine AMMO is suspended. Here is just read-only access to the articles archive. Some features are removed because they were outdated, pointless in read-only (voting and pools), or it was missused by spammers (comments) etc. Now the webpages aren't maintained so when something will get broken most probably it won't be fixed at all. If you liked our magazine then please make donation with paypal so we can pay for traffic on this server.

TOP Výuka
01 Maľované krížovky 103 bodov
02 OpenGL, lákadlo 38 bodov
03 MySQL (+ použitie Visual C++ a PHP) 28 bodov
04 OpenGL, časť 1 21 bodov
05 Pascal, časť 1 18 bodov
06 Ako tlačiť s HP 16 bodov
07 Základy HTML časť 2 16 bodov
08 Základy HTML časť 3 13 bodov
09 Hry pre nenáročných + zdrojáky 10 bodov
10 OpenGL, úvod 8 bodov
11 Faktúrka v4.0 + zdrojáky v MS Visual C++ 6.0 7 bodov
12 OpenGL – Intermezzo 1 7 bodov
13 OpenGL povinná literatúra 6 bodov
14 Základy HTML časť 1 6 bodov
15 WinSocket Communication via VC++ 6 bodov
Najnovsie clanky
Kvalitné služby podľa skúseností iných - TopSlužby.sk
LOTR - Dve veže - Parodia - Scénka 2. časť
Neverwinter nights
Children Of Bodom-Hatebreeder
Kult Duny - 6. časť (Bonus)
Kult Duny - 5. časť (Filmy, Hry)
Dobré ráno. (morc certa, hora incerta...)
Kult Duny - 4. časť (Knihy 2/2)
Stretnutie Spoločenstva Tolkiena
GRAVE DIGGER – Knights Of The Cross
Kult Duny - 3. časť (Knihy 1/2)
Kult Duny - 2. časť (Pojmy)
Kult Duny - 1. časť (Úvod)
LOTR - Dve veže - Parodia - Scénka
Jackass
Vsetky clanky
Airsoft - Specnaz [4 clanky]
Básne [6 clankov]
Fantázia [4 clanky]
Filmy a DVD [51 clankov]
Hardware [10 clankov]
Hry [170 clankov]
Hry, návody [6 clankov]
Hudba [8 clankov]
Internet [7 clankov]
Knihy [6 clankov]
O AMME [4 clanky]
Pandemonium [10 clankov]
Poviedky [14 clankov]
Programy [18 clankov]
Rôzne [8 clankov]
Technické [3 clanky]
Úvahy [8 clankov]
Výuka [50 clankov]
Ako tlačiť s HP
Algoritmy v grafoch
Fake2
Faktúrka
Faktúrka v4.0 + zdrojáky v MS Visual C++ 6.0
Fract
HLSaver
Hry pre nenáročných + zdrojáky
IPicture2 & aggresiveoptimize.h
Maľované krížovky
MySQL (+ použitie Visual C++ a PHP)
OpenGL - GLWnd
OpenGL AMMO Saver
OpenGL povinná literatúra
OpenGL – Intermezzo 1
OpenGL, časť 10
OpenGL, časť 11
OpenGL, časť 12
OpenGL, časť 13
OpenGL, časť 14
OpenGL, časť 15
OpenGL, časť 16
OpenGL, časť 17
OpenGL, časť 18
OpenGL, časť 7
OpenGL, časť 8
OpenGL, časť 9
Opengl – Cloth Simulation
RenameR
SkinMagic
WinSocket Communication via VC++
Údajové štruktúry
viac...
Zábava [5 clankov]
Zdravie [15 clankov]
Celkovy pocet clankov: 407
Huffmanove kódovanie 
Výuka | Dna 19.5.2002 | Johny | 15 znamok, priemer 1.66 | 8593 videni | 993 WAP videni

alebo tiež prefixové kódovanie...

Každého, kto trochu programoval už určite napadla myšlienka urobiť nejaký vlastný pakovač, ktorý by nejakým spôsobom „zbalil“ veľkosť súborov. V tomto článku chcem tým, ktorí o tom ešte nepočuli ukázať, čo to vlastne je a na akom princípe to funguje. Na konci článku bude link na zdroják, je to písané v Borland C++ 3.1, a je to výtvor napísaný za hodinu, možno 2. takže nečakajte, že tam nájdete pakovač lepší ako ARJ, RAR, ZIP alebo ACE. Ono to ani pakovač nie je, lebo kopa funkcií mu chýba. Slúži len na demonštráciu, ako začať, alebo aké metódy sa dajú pri pakovaní použiť.

Huffmanove kódovanie sa využíva aj pri stratovom pakovaní aj pri nestratovom. Príklad stratového pakovanie je napr. MP3, ktorá vám možno teraz hrá na pozadí. Nepotrebné informácie o nejakom šume, ktoré ľudské ucho aj tak nezachytí sú jednoducho „odkrojené“ preč. Nestratové pakovanie je napr. ZIP, kto by chcel stratovo spakovať nejaký dokument, ktorý písal 3 hodiny, aby ho potom rozbalil a chýbala mu tam tretina písmen ? ;o)

Takže otázka, ktorá napadla aj autora tejto myšlienky bola : Ako zapísať viac informácii pomocou menšieho počtu znakov abecedy ?
O tomto existuje kopa teórie, kde je dopodrobna rozpísané o úlohe abecedy zdroja, výstupu a ešte určite kopa ďalších vecí.

Takže, čo prevratného tento „ujo“ vymyslel ? Jeho myšlienka bola priradiť znakom alebo teda vstupným informáciám, ktoré sa opakujú najčastejšie, čo najkratšiu značku. Alebo, čo najkratší kód. A v počítačovom prípade sú to bit a byte. Všetko je to založené na pravdepodobnosti výskytu.

Takže uvediem malý príklad:
Vo vstupnom súbore, ktorý chceme pakovať je napísané toto: AABBBBCC
V bytoch to vyzerá takto: 65 65 66 66 66 66 67 67
V bitoch : 10000001 10000001 1000010 1000010 atď.

A huffmanove kódovanie spraví asi to, že každému znaku priradí nejakú kratšiu postupnosť bitov. Napríklad znaku B priradí 1, znaku A priradí 01 a znaku C priradí 00.
Takže takto zakódovaná postupnosť by vyzerala : 01 01 1 1 1 1 00 00
A toto dáva dokopy 12 bitov, čo sú takmer 2 byte. Teda pôvodne súbor, ktorý mal 8 bytov, sme skompresovali na 2 byty.

Teraz si určite kladiete otázku, ako zistím, aké značky mám priradiť jednotlivým znakom. Ako som už spomínal všetko je založené na pravdepodobnosti, teda znaky, ktoré majú najčastejší výskyt, majú aj najkratšie znaky.
A pri určovaní značiek treba dať pozor.
Čo by sa stalo, ak by sme priradili značky zle ?
Napríklad znaku A by sme dali značku 0 a znaku B značku 01, a znaku C 1
Takže náš program by išiel a našiel by takúto postupnosť bitov : 0001
Ak by náš program išiel zaradom tak, by to preložil ako AAAC, ale my sme tak zakódovali AAB. Dá sa v tomto prípade vôbec zakódovať AAB ?

Huffmanove kódovanie to rieši cez strom. Vytvorí sa strom, ktorého vetvy určujú, či sa treba vybrať doľava alebo doprava. A keď narazí na koniec, tak sa pozrie aký tam je znak. A keďže táto naša mapa znakov je strom, tak platí, že v strome existuje z každého do každého vrcholu práve 1 cesta. Teda nemôže dôjsť k omylu, že by sme nevedeli rozhodnúť, aký znak prislúcha nejakej postupnosti bitov.
Príklad stromu pre náš prípad: AABBBBCC
    Root
     /   \
   /\    B
 A  C

Root nie je v tomto prípade správca siete, ale miesto z ktorého vždy štartujeme. Vetvy (hrany) vedúce naľavo majú hodnotu 0 a vetvy vedúce napravo majú hodnotu 1. Môžete si to aj zameniť, na tom až tak nezáleží, len si potom pamätajte, že ste to zamenili ;o).
Teda ak by bola úloha rozpakovať postupnosť bitov 1101001
Tak by sme na to išli takto: začneme v root, zobereme prvý bit, je to 1, ideme teda doprava, je to koniec tejto vetvy ? Áno je, žiadne ďalšie z nej už nevedú. Teda napíšeme si písmeno B. Znovu začneme v root, zobereme bit, je to 1, teda opäť si zapíšeme B. Znovu ideme do root, zoberem ďalší bit, je to 0, ideme z roota doľava, je tam niečo uložené ? Nie, nie je, ďalej sa to vetví, tak zobereme ďalší bit, aby sme videli, ako sa to vetví. Ďalší bit je 1, teda ideme doprava, tam narazíme na C. A takto postupujeme, kým máme nejaké bity na rozpakovanie.

Teraz si možno hovoríte, že je to krásne, keď sa to rozpakúva, ale spakovať je o niečom inom. Urobiť huffmanov strom nie je až také ťažké.

Napíšem sem algoritmus, ktorý je z Teórie grafov, nakoniec bavíme sa o stromoch, takže to sem určite patrí. Týmto pozdravujem doc. RNDr. Stanislava Palúcha CSc., ktorý mi dúfam dá skúšku za Teóriu grafov ;o).

Algoritmus na zostrojenie Huffmanovho stromu.
Krok 1. Zostroj graf G G =(V,H,p), kde V=A, a kde p(v) je pravdepodobnosť znaku v. Polož H=prázdna množina. Všetky vrcholy prehlás za neoznačené.

Krok 2. Nájdi 2 neoznačené vrcholy s najmenšími pravdepodobnosťami, označ ich, vytvor ďalší vrchol X a pridaj hrany spájajúce tieto vrcholy a vrchol X. Polož p(X)=súčtu pravdepodobností oboch vrcholov. Jednej hrane polož značku 0, druhej značku 1.

Krok 3. Ak je graf súvislý, prehlás posledne pridaný vrchol za koreň (ROOT) a choď na krok 4 inak choď na KROK 2.

Krok 4. Graf G je teraz stromom, ktorý ma všetky vrcholy so stupňom 1 so znakmi abecedy A a cesta z koreňa do nejakého koncového vrchola je vlastne binárnym kódom pre zakódovanie tohto znaku.

Neodpísal som to odslova doslova, lebo som chcel, aby pochopili aj tí, ktorí nemajú šajn z teórie grafov.
Ale skúsim to napísať ešte viacej ľudsky:

Krok 1. Sprav vrcholy, a nastav im jednotlivé písmená abecedy. A každému vrcholu urči pravdepodobnosť výskytu znaku, ktorým je označený.

Krok 2. Nájdi 2 vrcholy z najmenšími pravdepodobnosťami. Vytvor nový vrchol X a spoj ho s týmito vrcholmi. Vrcholy označ ako použité a vrchol X ako nepoužitý. Vrcholu X priraď pravdepodobnosť, ktorá je súčtom pravdepodobností tých dvoch vrcholov.

Krok 3. Ak je už strom vytvorený, tak skonči, ak nie je, tak ešte pridávaj vrcholy do stromu.

Snáď teraz je to trošku ľahšie pochopiteľné aj laikom, ak nie, tak už fakt neviem, ako to povedať ešte jednoduchšie.

Takto si vytvoríme ten náš strom, kde hlavný vrchol bude ROOT a každý vrchol má nanajvýš 2 deti. Skúste si to predstaviť v úrovniach. No a každé dieťa, okrem roota má svojho
otca.

V programe, ktorý si môžete stiahnuť je to vidieť. Na čo je dobré mať informácie aj o rodičovi aj o synoch ? Aby ste mohli po strome cestovať oboma smermi.

A teraz trošku popis použitých štruktúr v programe
class Cgraf
{
public:
typedef struct Svrchol
{
struct Svrchol *m_childl; // left child
struct Svrchol *m_childr; // right child
struct Svrchol *m_parent; // parent
int m_data; // data
float m_p; // pravdepodobnost
int m_znak; // znak ci je uz zaradeny
};

Cgraf();
virtual ~Cgraf();

void init_vrcholy(int num); // inicializuje vrcholy
void connect(int v1, int v2); // spoji vrcholy
int check(); // koncime ?
int get_root(); // zaciatok stromu

protected:
int m_num;
Svrchol *m_pvrcholy;
};

toto je objekt Graf, ten sa skladá z vrcholov. Vrchol si vždy udržuje informáciu o svojich deťoch a o svojom rodičovi, dáta ktoré nesie, pravdepodobnosť výskytu a znak, či už bol zaradený do stromu. Niektorí by mohli namietať, že nie všetky vrcholy musia niesť všetky informácie. A majú aj pravdu, ale zase tých informácií nie je toľko, že by to vážne ohrozilo pamäť.
Ďalej nasleduje konštruktor a deštruktor objektu, procedúra init_vrcholy, ktorá nastaví všetkým vrcholom defaultné hodnoty. Funckia connect spojí dva vrcholy tak, že im vytvorí spoločného otca. A nastaví ich znaky, tak že sú už použité. Funckia check() skontroluje či náš graf je už strom. A funkcia get_root vráti index vrchola, ktorý je ROOT.
m_num je počet vrcholov alebo tiež počet písmen vstupnej abecedy
a m_pvrcholy je pointer na pole vrcholov

class Chuff : public Cgraf
{
private:
unsigned long m_pv[256]; // pocet vyskytov
int m_numclenov; // kolko clenov bude mat huffman
unsigned long m_cpv; // celkovy pocet vyskytov
unsigned long m_celkovo;
public:
Chuff(); // konstruktor
virtual ~Chuff(); // destruktor

int load_file(char *name); // nahraj subor
void build_tree(); // sprav strom
void draw_vrchol(Svrchol *vrchol); // nakresli vrchol
void draw_tree(); // vypis strom
void statistics();
void write_vrchol(Svrchol *vrchol, int poc);

};

Ďalej je definovaný objekt Chuff, ktorý využíva všetko, čo vie robiť objekt Cgraf, ale pridáva mu ešte niektoré ďalšie funkcie. Mohlo by to byť pravdaže v jednom objekte, ale chcel som, aby bolo vidieť, ktoré funkcie prislúchajú grafu, a ktoré huffmanovmu kódovaniu.
Takže m_pv je pole, kde si značíme počet výskytov jednotlivých znakov,
m_numclenov je koľko rôznych typov znakov bude strom mať
m_cpv je celkový počet znakov
m_celkovo je približný odhad úspešnosti pri tomto pakovaní
a ďalšie funckie hovoria asi sami za seba, build_tree spraví strom, a draw_tree vypíše pre každý znak jeho cestu až ku vrcholu. Statistics píše koľko krát bol ktorý znak použitý.

Pri spúštaní odporúčam smerovať výstup do súboru, lebo pri veľkých súboroch je tam veľa scrollovania obrazovky. Príklad: huffman.exe >vystup.txt
A všetko nám zapíše do súboru vystup.txt

Tí, ktorí sa o to zaujímajú viacej si môžu premyslieť ako by spravili, ešte dekódovanie, a treba vyriešiť aj zápis toho stromu do súboru. Tu je viac alternatív, ale najviac asi šetrí miesto metóda zapísať graf pomocou okolí. Kde pre každý vrchol určíte jeho susedov.

Ale ani takýto program sa ešte zďaleka nevyrovná známym komprimačným programom. Prečo ? Lebo oni idú ešte ďalej. Spakovať spakované ? V tomto prípade by to možno aj pomohlo. Ale cieľom všetkých je rozmiestniť dáta tak, aby sa všetky znaky vyskytovali rovnomerne. Skúste si spraviť štatistiku napríklad zip súboru. Zastúpenie všetkých znakov z ASCII tabuľky je dosť rovnomerné. Náhoda ? ;o)
Zdrojáky príkladu nájdete tu: zbalené ;o)
http://www.softsklad.host.sk/c/huffman.zip


Najnovsie clanky od tohto redaktora
Podobne clanky