Binárny strom - Huffmanovo kódovanie (riešené príklady)
Obsah
Zadanie
Vytvorte program na zakódovanie správy pomocou Huffmanovho kódovania. Text načítajte z textového súboru.
Analýza
Huffmanovo kódovanie je metóda bezstratového kódovania dát založená na entropii kódovaného textu. Pri tvorbe samotného Huffmanovho kódu využijeme dátovú štruktúru binárny strom. Pri vytváraní Huffmanovho kódu potrebujeme poznať celú abecedu, ktorá bola použitá v správe a ďalej je potrebné vedieť pravdepodobnosti výskytov znakov abecedy v texte. Pre získanie týchto pravdepodobností môžeme postupovať dvoma spôsobmi:
- Pravdepodobnosti výskytu znakov v texte si vypočítať z:
- textu, ktorý budeme kódovať,
- veľkej vzorky textu v danom (prirodzenom) jazyku. Prirodzený jazyk sa myslí slovenčina, čeština, angličtina.
- Pravdepodobnosti výskytu znakov v texte použiť známe pravdepodobnosti pre daný prirodzený jazyk.
Výsledkom tejto analýzy bude súbor "znaky.txt" v ktorom bude zoznam všetkých znakov abecedy spolu s ich pravdepodobnosťou výskytu v texte. Formát súboru je nasledovný:prvý údaj je počet znakov abecedy (n). V ďalších n riadkoch je znak abecedy a jeho pravdepodobnosť výskytu.
8 E 0.05 G 0.05 A 0.1 C 0.1 F 0.1 H 0.1 B 0.2 D 0.3
Výpočet pravdepodobnosti výskytu znakov v texte
Uvažujme vstupný textový súbor ("text.txt") v ktorom je text v prirodzenom jazyku. Ú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. Kvôli zjednodušeniu bude súbor text.txt obsahovať len veľké písmená abecedy a nebude obsahovať slovenské písmená(v súbore nie sú písmená ľ,š,č,ť,ž,ý,á,í,é,ä,ú,ň,ĺ,ď).
Získanie pravdepodobnosti výskytu je jednoduché. Stačí spočítať početnosť všetkých znakov. Využijeme fakt, že vstupnú abecedu tvoria len veľké písmená abecedy bez znakov s mäkčeňmi a dĺžňami, ďalej číslice a interpunkčné znamienka (,.-/()+-")
1 void pravdepodobnost_znakov()
2 {
3 ifstream in;
4 in.open("text.txt");
5 if(!in) return;
6
7 int znaky[64];
8 for(int i=0;i<64;i++)
9 znaky[i]=0;
10 char c;
11 do
12 { c=in.get();
13 znaky[c-' ']++;
14 }while(c>=0);
15 in.close();
16 }
V tabuľke ASCII má znak medzery hodnotu 32. Tento znak je zároveň prvým nie kontrolným znakom. Posledný znak, ktorého pravdepodobnosť budeme počítať je znak apostrov, ktorý má hodnotu 96. Preto nám stačí vytvoriť pole 64 znakov (riadok č.7). Na riadkoch 11 až 14 je načítavanie jedného znaku zo súboru, až pokým nenarazíme na koniec súboru. Pri načítaní znaku zvýšime počet jeho výskytov o 1 (riadok 13).
Ú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. Upravíme teda prechádzajúci kus kódu nasledovne:
1 struct Znak{
2 char znak;
3 double pp;
4 };
5
6 int porovnajZ(const void *a, const void *b)
7 {
8
9 if( (*(Znak*)a).pp > (*(Znak*)b).pp ) return 1;
10 if( (*(Znak*)a).pp < (*(Znak*)b).pp ) return -1;
11 return 0;
12 }
13 void pravdepodobnost_znakov()
14 {
15 ifstream in;
16 in.open("text.txt");
17 int n=64;
18 if(!in) return;
19 int znaky[64];
20 for(int i=0;i<64;i++)
21 znaky[i]=0;
22 char c;
23 do
24 { c=in.get();
25 znaky[c-' ']++;
26 }while(c>=0);
27 double suma=0;
28 for(int i=0;i<n;i++)
29 {
30 cout<<(char)(i+32)<<" "<<znaky[i]<<endl;
31 suma+=znaky[i];
32 }
33 in.close();
34
35 Znak abc[n];
36 for(int i=0;i<n;i++)
37 {
38 abc[i].znak=(char)(i+32);
39 abc[i].pp=znaky[i]/suma;
40 }
41 qsort(abc,n,sizeof(abc[0]),porovnajZ);
42 ofstream out;
43 out.open("znaky.txt");
44 out<<n<<endl;
45 for(int i=0;i<n;i++)
46 {
47 out<<abc[i].znak<<"\t"<<abc[i].pp<<endl;
48 }
49 out.close();
50 }
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. Takáto štruktúra je na riadku 1. Štruktúra Znak obsahuje premennú znak typu char a premennú pp typu double, čo je vlastne pravdepodobnosť znaku.
Na riadku 35 si vytvoríme pole štruktúr Znak o veľkosti 64. Toto pole naplníme hodnotami (riadky 35 až 40) údajmi získanými analýzou textu. Prvý prvok poľa abc reprezentuje znak medzera ' '. Na zotriedenie tohoto poľa využijeme funkciu qsort. Na riadkoch 45 až 48 je zápis údajov do súboru vo formáte aký bol dohodnutý na začiatku.
Známe pravdepodobnosti výskytu znakov v texte v prirodzenom jazyku
Pravdepodobnosti pre anglickú abecedu
a .082 b .015 c .028 d .043 e .127 f .022 g .02 h .061 i .07 j .002 k .008 l .04 m .024 n .067 o .075 p .019 q .001 r .06 s .063 t .091 u .028 v .01 w .023 x .001 y .02 z .001
