Binárny strom - Huffmanovo kódovanie (riešené príklady): Rozdiel medzi revíziami

Z Kiwiki
Skočit na navigaci Skočit na vyhledávání
(Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadanie== Vytvorte program n…“)
 
 
(Jedna medziľahlá úprava od rovnakého používateľa nie je zobrazená.)
Riadok 1: Riadok 1:
−
[[Kategória:Študijné materiály]]
 
−
[[Kategória:Programovanie]]
 
−
[[Kategória:jazyk C]]
 
 
{{Draft}}
 
{{Draft}}
 
{{Skripta programovanie (zbierka úloh)}}
 
{{Skripta programovanie (zbierka úloh)}}
Riadok 14: Riadok 11:
 
##veľkej vzorky textu v danom (prirodzenom) jazyku. Prirodzený jazyk sa myslí slovenčina, čeština, angličtina.
 
##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.
 
#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.
+
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.  
−
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===
 
===Výpočet pravdepodobnosti výskytu znakov v texte===
Riadok 75: Riadok 63:
 
     do
 
     do
 
     {  c=in.get();         
 
     {  c=in.get();         
 +
        if(c==' ')
 +
          c='_';
 
         znaky[c-' ']++;             
 
         znaky[c-' ']++;             
 
     }while(c>=0);
 
     }while(c>=0);
 
     double suma=0;
 
     double suma=0;
 
     for(int i=0;i<n;i++)
 
     for(int i=0;i<n;i++)
−
     {
+
     { // len kontrolny vypis v pripade ladenia programu
−
        cout<<(char)(i+32)<<" "<<znaky[i]<<endl;
+
    //  cout<<(char)(i+32)<<" "<<znaky[i]<<endl;
 
         suma+=znaky[i];
 
         suma+=znaky[i];
 
     }
 
     }
Riadok 94: Riadok 84:
 
     ofstream out;
 
     ofstream out;
 
     out.open("znaky.txt");
 
     out.open("znaky.txt");
−
     out<<n<<endl;
+
    int index=0;
−
     for(int i=0;i<n;i++)
+
    for(index=0;abc[index].pp==0;index++);   
 +
     out<<64-index<<endl;
 +
     for(int i=index;i<n;i++)
 
     {
 
     {
 
         out<<abc[i].znak<<"\t"<<abc[i].pp<<endl;
 
         out<<abc[i].znak<<"\t"<<abc[i].pp<<endl;
 
     }     
 
     }     
−
     out.close();    
+
     out.close();  
 
}
 
}
 
</source>
 
</source>
 
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.  
 
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 (jazyk C)|qsort]]. Na riadkoch 45 až 48 je zápis údajov do súboru vo formáte aký bol dohodnutý na začiatku.
+
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 (jazyk C)|qsort]]. Na riadkoch 45 až 48 je zápis údajov do súboru vo formáte aký bol dohodnutý na začiatku. Znaky, ktoré mali v skúmanom texte nolový výskyt do súboru znaky.txt nezapisujeme. Na toto nám poslúži cyklus na riadku 45, ktorý premennú index nastaví na index prvého znaku v poli abc, ktorý sa vo vstupnom texte vyskytuje.
  
 
===Známe pravdepodobnosti výskytu znakov v texte v prirodzenom jazyku===
 
===Známe pravdepodobnosti výskytu znakov v texte v prirodzenom jazyku===
Riadok 134: Riadok 126:
 
  y  .02  
 
  y  .02  
 
  z  .001
 
  z  .001
 +
===Návrh vhodnej dátovej štruktúry===
 +
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. Do štruktúry opisujúcej znak abecedy ešte pridáme časť "kódové slovo", v ktorom bude uložený samotný Huffmanov kód pre daný znak abecedy.
 +
<source lang="c">
 +
struct THuff
 +
{  char znak;
 +
    float pp;
 +
    char *kodove_slovo;
 +
};
 +
 +
struct TUzol
 +
{    THuff *data;
 +
      TUzol *lavy,*pravy;
 +
};
 +
</source>
 +
*THuff - dátová štruktúra opisujúca znak vstupnej abecedy:
 +
**znak - samotný znak abecedy
 +
**pp - pravdepodobnosť výskytu znaku
 +
**kodove_slovo - Huffmanov kód pre daný znak. Doplní sa až po vytvorení kódovacieho stromu.
 +
*TUzol - uzol binárneho, resp. kódovacieho stromu.
 +
**data - smetník na dátovú časť uzla stromu - THuff
 +
**lavy, pravy - smerníky na ľavý a pravý podstrom.
 +
==Vzorový príklad==
 +
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.
 +
===Vzorový vstup===
 +
Formát súboru ''znaky.txt'' 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
 +
===Vzorový výstup===
 +
Huffmanov kód pre abecedu definovanú v súbore znaky.txt.
 +
{| class=prettytable
 +
|-
 +
!Znak
 +
!Kód
 +
|-
 +
|E
 +
| 0000
 +
|-
 +
|G
 +
| 0001
 +
|-
 +
|H
 +
| 001
 +
|-
 +
|A
 +
| 010
 +
|-
 +
|F
 +
| 011
 +
|-
 +
|C
 +
| 100
 +
|-
 +
|B
 +
| 101
 +
|-
 +
|D
 +
| 11
 +
|}
 +
==Postup pri riešení==
 +
Riešenie si rozdelíme na 2 hlavné časti a niekoľko podúloh:
 +
 +
'''1. Fáza: Fáza redukcie (smer hore)'''
 +
:1. Znaky kódovanej usporiadame podľa pravdepodobnosti výskytu
 +
 +
:2. Postupne redukujeme abecedu spojením dvoch znakov s najmenšou pravdepodobnosťou do jedného zástupného znaku s pravdepodobnosťou rovnou súčtu týchto dvoch pp.
 +
 +
:3. Ak obsahuje redukovaná abeceda 2 zástupné znaky – krok 4, inak krok 2
 +
 +
[[Súbor:huff_kod1.png|framed|center|Znaky kódovanej sú usporiadané podľa pravdepodobnosti výskytu ]]
 +
[[Súbor:huff_kod2.png|framed|center|Postupná redukcia vstupnej abecedy]]
 +
[[Súbor:huff_kod3.png|framed|center|Postupná redukcia vstupnej abecedy]]
 +
[[Súbor:huff_kod4.png|framed|center|Koniec redukcie - vstupná abeceda obsahuje už len 2 zástupné znaky]]
 +
 +
'''2. Fáza: Fáza zostavenia kódu (smer dole)'''
 +
 +
:4. Dvom zástupným znakom redukovanej abecedy priradíme kódové slová 0 a 1. Kódové slová priraďujeme od vrcholu kódovacieho stromu.
 +
 +
[[Súbor:huff_kod5.png|framed|center|Postupné priraďovanie kódových znakov]]
 +
 +
:5. Potupne, keď prechádzame smerom dole, pridávame kódovým znakom, ktoré sú potomkami zástupného znakom slová 0 a 1
 +
 +
:6. Pokiaľ sa nedostaneme k pôvodnej abecede, tak krok 5.
 +
 +
[[Súbor:huff_kod6.png|framed|center|Vizualizácia kódového stromu]]
 +
 +
==Riešenie v jazyku C==
 +
<source lang="c" line>
 +
int main(int argc, char *argv[])
 +
{
 +
pravdepodobnost_znakov();
 +
ifstream in;
 +
char subor[]="znaky.txt";
 +
in.open(subor);
 +
int n;                        // pocet znakov abecedy
 +
TUzol **abc;                  // pole ukazatelov na TUzol
 +
if(in)
 +
{  in>>n;
 +
    abc=new TUzol*[n];
 +
    for(int i=0;i<n;i++)
 +
    {  abc[i]=new TUzol; 
 +
      abc[i]->data=new THuff;
 +
      abc[i]->lavy=abc[i]->pravy=NULL;
 +
      in>>abc[i]->data->znak;
 +
      in>>abc[i]-> data-> pp; 
 +
    }
 +
}
 +
else
 +
  return 1;                            // nepodarilo sa otvorit vstupny subor
 +
 
 +
int min1,min2;
 +
min1=min2=0;
 +
TUzol *strom=new TUzol;  // binarny strom, ktory budeme vytvarat
 +
strom->data = new THuff;
 +
while(n>1)             // vytvaranie noveho binarneho stromu z pola TUzlov
 +
{  Hladaj2Min(abc,n,min1,min2);
 +
    strom=VlozDoStromu(abc[min1],abc[min2]);
 +
    UsporiadajKodoveSlova(abc,strom,min1,min2,n);
 +
}
 +
 +
char *slovo=new char[32];
 +
slovo[0]=0;
 +
ZapisKodoveSlova(strom,slovo); // priradenie kodov jednotlivym znakom
 +
vypis(strom); // vypis zakodovanych znakov
 +
 +
zmazStrom(strom);
 +
 +
//zmazanie pola smernikov na uzly
 +
for(int i=0;i<n;i++)
 +
{   
 +
  delete abc[i]->data;
 +
  delete abc[i]; 
 +
}
 +
delete []abc;
 +
}
 +
</source>
 +
===Vysvetlenie kódu===
 +
;riadok 3: výpočet pravdepodobnosti výskytu znakov vo vstupnej abecede. V prípade, ak máme pripravený súbor znaky.txt s pravdepodobnosťami, tak tento riadok treba zakomentovať alebo odstrániť.
 +
;riadok 8-11: Na uloženie vstupných údajov si vytvoríme pole smerníkov na štruktúru TUzol. Pole smerníkov na TUzol je výhodnejšie použiť vzhľadom na neskoršie operácie kopírovania uzlov. ''abc'' je dvojitý smerník na dátovú štruktúru TUzol. Na riadku 11 pre abc alokujeme n smerníkov na štruktúru TUzol
 +
;riadok 12-19: Načítanie vstupných údajov do dátovej štruktúry abc - pole smerníkov na TUzol. Pre dátovú časť štruktúry TUzol si treba alokovať miesto (riadok 14), pretože v definícii je premenná data definovanná ako smerník na štruktúry THuff. Na riadku 16 je načítanie znaku a na riadku 17 je načítanie jeho pravdepodobnosti.
 +
;riadok 25: ''strom'' - koreň binárneho stromu, ktorý bude tvoriť kódovací strom.
 +
;riadok 27-30: 1. Fáza riešenia. Premenná n má význam počet znakov v postupne redukovanej abecede. Abecedu redukujeme, pokiaľ je n väčšie ako 1.
 +
;riadok 35: 2. Fáza riešenia. Funkcia ''ZapisKodoveSlova'' pridelí znakom abecedy (listy stromu) do časti ''kodove_slovo'' kódové slová.
 +
;riadok 38-46: zmazanie binárneho stromu a zmazanie poľa smerníkov na šštruktúru TUzol, ktorá bola využitá pre uloženie vstupných znakov abecedy.
 +
 +
===Ďalšie funkcie===
 +
====void Hladaj2Min(TUzol **abc,int n,int &min1,int &min2)====
 +
<source lang="c" line>
 +
void Hladaj2Min(TUzol **abc,int n,int &min1,int &min2)
 +
{   
 +
  int i,index_i=0;
 +
  float mmin1,mmin2;        // hodnoty pp dvoch min prvkov
 +
  min1=min2=0;              // indexy, ktore hladame
 +
  mmin1=mmin2=1;
 +
  for(i=0;i<n;i++)
 +
      if(abc[i]->data->pp < mmin1 )  // hladanie prveho minima
 +
      { min1=i;
 +
        mmin1=abc[i]->data-> pp;
 +
      }
 +
  for(i=0;i<n;i++)  // hladanie 2 minima, neberieme v uvahu prvok s indexom min1
 +
      if((abc[i]->data-> pp <= mmin2) && (i!=min1) )
 +
      { min2=i;       
 +
        mmin2=abc[i]->data-> pp;
 +
      }   
 +
}
 +
</source>
 +
'''Opis funkcie:'''
 +
 +
Funkcia hľadá 2 prvky v poli vstupných znakov (pole smerníkov na TUzol) 2 prvky s najmenšou pravdepodobnosťou výskytu.
 +
 +
'''Parametre:'''
 +
 +
''TUzol **abc'' - pole smerníkov na TUzol. každý prvok poľa obsahuje v dátovej časti znak vstupnej abecedy a pravdepodobnosť výskytu
 +
 +
''int n'' - veľkosť poľa abc
 +
 +
''int &min1'' - výstupný parameter. Index prvého prvku poľa abc s najmenšou pravdepodobnosťou výskytu znaku v texte
 +
 +
''int &min2'' - výstupný parameter. Index druhého prvku poľa abc s najmenšou pravdepodobnosťou výskytu znaku v texte
 +
 +
'''Návratová hodnota:'''
 +
 +
žiadna
 +
====TUzol* VlozDoStromu(TUzol *a,TUzol *b)====
 +
<source lang="c" line>
 +
TUzol* VlozDoStromu(TUzol *a,TUzol *b)
 +
{  //vytvaram kodovaci strom zospodu hore
 +
  TUzol *otec=new TUzol;
 +
  otec->data = new THuff;
 +
  otec->lavy=a;
 +
  otec->pravy=b;
 +
  otec->data->pp= a->data->pp + b->data->pp;
 +
  otec->data->znak=0;
 +
  return otec;   
 +
}
 +
</source>
 +
'''Opis funkcie:'''
 +
 +
Funkcia vytvorí rodičovský uzol uzlov ''a'' a ''b''. Dátová časť rodičovského uzla neobsahuje žiaden znak (riadok 8) a pravdepodobnosť výskytu tohoto 'zástupného' znaku je vypočítaná ako súčet pravdepodobností výskytov jeho dvoch potomkov (riadok 7).
 +
 +
'''Parametre:'''
 +
 +
''TUzol *a,TUzol *b'' - vstupné parametre funkcie. Uzly ''a'' a ''b'' sú existujúce uzly (TUzol)
 +
 +
'''Návratová hodnota:'''
 +
 +
Smerník na novo vytvorený uzol kódovacieho stromu.
 +
====void UsporiadajKodoveSlova(TUzol **abc,TUzol *novy,int min1,int min2,int &n)====
 +
Pri tvorbe stromu vznikajú v poli prvkov prázdne miesta, ktoré treba zrušiť. Namiesto dvoch uzlov, z ktorých sme vytvorili nový uzol, ktorého pravdepodobnosť výskytu znaku v texte je rovná súčtu pravdepodobností výskytov týchto znakov, vložíme na správne miesto nový uzol.
 +
 +
Nový uzol
 +
<source lang="c" line>
 +
void UsporiadajKodoveSlova(TUzol **abc,TUzol *novy,int min1,int min2,int &n)
 +
{
 +
  int i;
 +
  abc[min1]=novy;          // na index min1 vlozim novy uzol
 +
  for(i=min2;i<n-1;i++)    // ostatne uzly posuniem o 1 dolava
 +
    abc[i]=abc[i+1];
 +
  n--;              // tym padom sa mi zmensi pocet uzlov v poli 
 +
  abc[n]=NULL;
 +
}
 +
</source>
 +
'''Opis funkcie:'''
 +
 +
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. Preto treba preusporiadať pole abc ako ukazujú nasledujúce obrázky:
 +
 +
[[Súbor:huff_kod7.png|framed|center|hodnoty min1 min2 určujú indexy prvkov v poli abc s najmenšími pravdepodobnosťami výskytu znaku v texte. Premenná novy je nový uzol, ktorý sme vytvorili v predchádzajúcom kroku a teraz ho treba zaradiť do poľa abc ]]
 +
[[Súbor:huff_kod8.png|framed|center|Riadok č. 4 v prechádzajúcom zdrojovom kóde. Na pozíciu min1 sa vloží nový uzol (TUzol). Jeho vzťah s uzlami na indexe min1 a min2 je naznačený šípkami.]]
 +
[[Súbor:huff_kod9.png|framed|center|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. POZOR!! tento uzol nemôžeme zmazať pomocou delete, pretože by sme zmazali uzol, ktorý sme posunuli o jedno miesto naľavo.]]
 +
 +
'''Parametre:'''
 +
 +
''TUzol **abc'' - pole smerníkov na TUzol v ktorom sú uložené znaky vstupnej abecedy a v priebehu programu sa tu ukladajú zástupné znaky.
 +
 +
''TUzol *novy'' - smerník na nový uzol, ktorého potomkovia sú uzly poľa ''abc'' na indexoch ''min1'' a ''min2''
 +
 +
''int min1,int min2'' - indexy svoch prvkov s najmenšou pravdepodobnosťou výskytu znaku v texte
 +
 +
''int &n'' - výstupný parameter : veľkosť poľa ''abc''.
 +
 +
'''Návratová hodnota:'''
 +
 +
žiadna
 +
====void ZapisKodoveSlova(TUzol *ks,char *hodnota)====
 +
 +
<source lang="c" line>
 +
// funkcia zmaze posledny znak v retazci 'hodnota'
 +
void substring(char *hodnota)
 +
{ 
 +
    hodnota[strlen(hodnota)-1]=0;
 +
}
 +
 +
void ZapisKodoveSlova(TUzol *ks,char *hodnota)
 +
{ 
 +
    if(!ks) return;
 +
    else
 +
    { // kodove slovo zapisujeme len pre listy stromu
 +
      if(ks->lavy==NULL && ks->pravy==NULL) 
 +
      {      ks->data->kodove_slovo=new char[strlen(hodnota)];
 +
              strcpy(ks->data->kodove_slovo,hodnota);     
 +
      }
 +
      ZapisKodoveSlova(ks->lavy,strcat(hodnota,"0"));
 +
  substring(hodnota);
 +
      ZapisKodoveSlova(ks->pravy,strcat(hodnota,"1"));
 +
        substring(hodnota);
 +
  }                   
 +
}
 +
</source>
 +
'''Opis funkcie:'''
 +
 +
Listom kódovacieho stromu priradí kódové slová Huffmanovho kódu.
 +
 +
''ZapisKodoveSlova'' je rekurzívna funkcia, ktorá ľavému potomkovi priradí znak 0 a pravému potomkovi znak 1. Ak sa pri rekurzívnom volaní narazí na list stromu (riadok 12), tak sa do dátovej časti daného uzla zapíše kódové slovo, ktoré je v parametri funkcie ''hodnota''. Na riadku 13 je alokázia potrebného miesta pre toto kódové slovo a na riadku 14 je skopírovanie tohto reťazca do časti ''kodove_slovo''. Rekurzívne volanie sa ukončí ak narazíme na neexistujúci uzol (riadok 9).  Pomocná funkcia ''substring'' zmaže z reťazca ''hodnota'' posledný znak. Je to potrebné kvôli spätnému rekurzívnemu volaniu, keďže pri rekurzívnom volaní k tomuto parametru pridávame ďalšie znaky.
 +
 +
 +
'''Parametre:'''
 +
 +
''TUzol *ks'' - koreň kódovacieho stromu
 +
 +
''char *hodnota'' - kódové slovo pre daný uzol. Na začiatku je je premenná ''hodnota'' prázdny reťazec.
 +
 +
'''Návratová hodnota:'''
 +
 +
Žiadna. Po skončení funkcie všetky listy stromu ''ks'' obsahujú reťazec s hodnotou kódového slova pre daný znak.
 +
 +
====void zmazStrom(TUzol *uzol)====
 +
<source lang="c" line>
 +
void zmazStrom(TUzol *uzol)
 +
{
 +
  if (!uzol) return;
 +
  if (uzol->lavy)  // ak existuje lavy uzol 
 +
      zmazStrom(uzol->lavy);
 +
  if (uzol->pravy) // ak existuje pravy uzol
 +
      zmazStrom(uzol->pravy);
 +
  delete uzol;
 +
}
 +
</source>
 +
'''Opis funkcie:'''
 +
 +
Zmaže binárny strom. Je použitý algoritmus [[Binárny_strom#Preh.C4.BEad.C3.A1vanie_postorder:|postorder]]
 +
 +
'''Parametre:'''
 +
 +
''TUzol *uzol'' . binárny strom, ktorý sa má zmazať.
 +
 +
'''Návratová hodnota:'''
 +
 +
Žiadna
 +
====void vypis(TUzol *s)====
 +
<source lang="c" line>
 +
void vypis(TUzol *s)
 +
{    if(!s)
 +
        return;
 +
      else   
 +
      { 
 +
        vypis(s->lavy);
 +
if(s->data->znak)
 +
{
 +
    cout<<s->data->znak<<" | ";
 +
            cout<<s->data->kodove_slovo;
 +
            cout<<endl;
 +
        }
 +
        vypis(s->pravy);
 +
}
 +
}
 +
</source>
 +
'''Opis funkcie:'''
 +
 +
Vypíše binárny, resp. kódovací strom. Je použitý algoritmus [[Binárny_strom#Preh.C4.BEad.C3.A1vanie_inorder:|inorder]]
 +
 +
 +
'''Parametre:'''
 +
 +
''TUzol *s'' . binárny strom, ktorý sa má vypísať
 +
 +
'''Návratová hodnota:'''
 +
 +
Žiadna
 +
 +
==Prílohy==
 +
Vstupný súbor je upravený text z http://sk.wikipedia.org/wiki/Dejiny_Ko%C5%A1%C3%ADc.
 +
 +
[http://kiwiki.fmtnuni.sk/~itpk/wiki_upload/programovanie/text.txt vstupný súbor text.txt]

Aktuálna revízia z 22:30, 16. august 2010

Imbox draft.png
 Toto je projekt, na ktorom sa ešte stále pracuje!!

Aj keď sú v tomto dokumente použiteľné informácie, ešte nie je dokončený. Svoje návrhy môžete vyjadriť v diskusii o tejto stránke.

Algoritmy a programovanie - zbierka úloh

Štruktúry

Rekurzia

Dynamická alokácia pamäti

Vyhľadávanie

Triedenie

Lineárny zoznam

Binárny strom

>Binárny strom - Morseova abeceda
>Binárny strom - Huffmanovo kódovanie

Numerické algoritmy

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:

  1. Pravdepodobnosti výskytu znakov v texte si vypočítať z:
    1. textu, ktorý budeme kódovať,
    2. veľkej vzorky textu v danom (prirodzenom) jazyku. Prirodzený jazyk sa myslí slovenčina, čeština, angličtina.
  2. 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.

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          if(c==' ')
26            c='_';
27          znaky[c-' ']++;            
28      }while(c>=0);
29      double suma=0;
30      for(int i=0;i<n;i++)
31      {  // len kontrolny vypis v pripade ladenia programu
32      //   cout<<(char)(i+32)<<" "<<znaky[i]<<endl;
33         suma+=znaky[i];
34      }
35      in.close();
36      
37      Znak abc[n];
38      for(int i=0;i<n;i++)
39      {
40         abc[i].znak=(char)(i+32);
41         abc[i].pp=znaky[i]/suma;
42      }       
43      qsort(abc,n,sizeof(abc[0]),porovnajZ);
44      ofstream out;
45      out.open("znaky.txt");
46      int index=0;
47      for(index=0;abc[index].pp==0;index++);     
48      out<<64-index<<endl;
49      for(int i=index;i<n;i++)
50      {
51         out<<abc[i].znak<<"\t"<<abc[i].pp<<endl;
52      }     
53      out.close();   
54 }

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. Znaky, ktoré mali v skúmanom texte nolový výskyt do súboru znaky.txt nezapisujeme. Na toto nám poslúži cyklus na riadku 45, ktorý premennú index nastaví na index prvého znaku v poli abc, ktorý sa vo vstupnom texte vyskytuje.

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

Návrh vhodnej dátovej štruktúry

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. Do štruktúry opisujúcej znak abecedy ešte pridáme časť "kódové slovo", v ktorom bude uložený samotný Huffmanov kód pre daný znak abecedy. 

struct THuff
{   char znak;
    float pp;
    char *kodove_slovo;
};

struct TUzol
{     THuff *data;
       TUzol *lavy,*pravy;
};
  • THuff - dátová štruktúra opisujúca znak vstupnej abecedy:
    • znak - samotný znak abecedy
    • pp - pravdepodobnosť výskytu znaku
    • kodove_slovo - Huffmanov kód pre daný znak. Doplní sa až po vytvorení kódovacieho stromu.
  • TUzol - uzol binárneho, resp. kódovacieho stromu.
    • data - smetník na dátovú časť uzla stromu - THuff
    • lavy, pravy - smerníky na ľavý a pravý podstrom.

Vzorový príklad

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.

Vzorový vstup

Formát súboru znaky.txt 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

Vzorový výstup

Huffmanov kód pre abecedu definovanú v súbore znaky.txt.

Znak Kód
E 0000
G 0001
H 001
A 010
F 011
C 100
B 101
D 11

Postup pri riešení

Riešenie si rozdelíme na 2 hlavné časti a niekoľko podúloh:

1. Fáza: Fáza redukcie (smer hore)

1. Znaky kódovanej usporiadame podľa pravdepodobnosti výskytu
2. Postupne redukujeme abecedu spojením dvoch znakov s najmenšou pravdepodobnosťou do jedného zástupného znaku s pravdepodobnosťou rovnou súčtu týchto dvoch pp.
3. Ak obsahuje redukovaná abeceda 2 zástupné znaky – krok 4, inak krok 2
Znaky kódovanej sú usporiadané podľa pravdepodobnosti výskytu
Postupná redukcia vstupnej abecedy
Postupná redukcia vstupnej abecedy
Koniec redukcie - vstupná abeceda obsahuje už len 2 zástupné znaky

2. Fáza: Fáza zostavenia kódu (smer dole)

4. Dvom zástupným znakom redukovanej abecedy priradíme kódové slová 0 a 1. Kódové slová priraďujeme od vrcholu kódovacieho stromu.
Postupné priraďovanie kódových znakov
5. Potupne, keď prechádzame smerom dole, pridávame kódovým znakom, ktoré sú potomkami zástupného znakom slová 0 a 1
6. Pokiaľ sa nedostaneme k pôvodnej abecede, tak krok 5.
Vizualizácia kódového stromu

Riešenie v jazyku C

 1 int main(int argc, char *argv[])
 2 {
 3  pravdepodobnost_znakov();
 4  ifstream in;
 5  char subor[]="znaky.txt";
 6  in.open(subor);
 7  int n;                         // pocet znakov abecedy
 8  TUzol **abc;                   // pole ukazatelov na TUzol
 9  if(in)
10  {  in>>n;
11     abc=new TUzol*[n]; 
12     for(int i=0;i<n;i++)
13     {  abc[i]=new TUzol;  
14        abc[i]->data=new THuff;
15        abc[i]->lavy=abc[i]->pravy=NULL;
16        in>>abc[i]->data->znak;
17        in>>abc[i]-> data-> pp;  
18     }
19  }
20  else 
21    return 1;                            // nepodarilo sa otvorit vstupny subor
22    
23  int min1,min2;
24  min1=min2=0;
25  TUzol *strom=new TUzol;  // binarny strom, ktory budeme vytvarat
26  strom->data = new THuff;
27  while(n>1)	            	// vytvaranie noveho binarneho stromu z pola TUzlov
28  {   Hladaj2Min(abc,n,min1,min2);
29      strom=VlozDoStromu(abc[min1],abc[min2]);
30      UsporiadajKodoveSlova(abc,strom,min1,min2,n);
31  } 
32 
33  char *slovo=new char[32];
34  slovo[0]=0;
35  ZapisKodoveSlova(strom,slovo);	// priradenie kodov jednotlivym znakom
36  vypis(strom);		// vypis zakodovanych znakov
37 
38  zmazStrom(strom);
39  
40  //zmazanie pola smernikov na uzly
41  for(int i=0;i<n;i++)
42  {    
43    delete abc[i]->data;
44    delete abc[i];   
45  }
46  delete []abc;
47 }

Vysvetlenie kódu

riadok 3
výpočet pravdepodobnosti výskytu znakov vo vstupnej abecede. V prípade, ak máme pripravený súbor znaky.txt s pravdepodobnosťami, tak tento riadok treba zakomentovať alebo odstrániť.
riadok 8-11
Na uloženie vstupných údajov si vytvoríme pole smerníkov na štruktúru TUzol. Pole smerníkov na TUzol je výhodnejšie použiť vzhľadom na neskoršie operácie kopírovania uzlov. abc je dvojitý smerník na dátovú štruktúru TUzol. Na riadku 11 pre abc alokujeme n smerníkov na štruktúru TUzol
riadok 12-19
Načítanie vstupných údajov do dátovej štruktúry abc - pole smerníkov na TUzol. Pre dátovú časť štruktúry TUzol si treba alokovať miesto (riadok 14), pretože v definícii je premenná data definovanná ako smerník na štruktúry THuff. Na riadku 16 je načítanie znaku a na riadku 17 je načítanie jeho pravdepodobnosti.
riadok 25
strom - koreň binárneho stromu, ktorý bude tvoriť kódovací strom.
riadok 27-30
1. Fáza riešenia. Premenná n má význam počet znakov v postupne redukovanej abecede. Abecedu redukujeme, pokiaľ je n väčšie ako 1.
riadok 35
2. Fáza riešenia. Funkcia ZapisKodoveSlova pridelí znakom abecedy (listy stromu) do časti kodove_slovo kódové slová.
riadok 38-46
zmazanie binárneho stromu a zmazanie poľa smerníkov na šštruktúru TUzol, ktorá bola využitá pre uloženie vstupných znakov abecedy.

Ďalšie funkcie

void Hladaj2Min(TUzol **abc,int n,int &min1,int &min2)

 1 void Hladaj2Min(TUzol **abc,int n,int &min1,int &min2)
 2 {     	
 3    int i,index_i=0;
 4    float mmin1,mmin2;        // hodnoty pp dvoch min prvkov
 5    min1=min2=0;              // indexy, ktore hladame
 6    mmin1=mmin2=1;
 7    for(i=0;i<n;i++)
 8       if(abc[i]->data->pp < mmin1 )  // hladanie prveho minima
 9       { min1=i;
10         mmin1=abc[i]->data-> pp; 
11       }
12    for(i=0;i<n;i++)  // hladanie 2 minima, neberieme v uvahu prvok s indexom min1
13       if((abc[i]->data-> pp <= mmin2) && (i!=min1) )
14       { min2=i;        
15         mmin2=abc[i]->data-> pp; 
16       }    
17 }

Opis funkcie:

Funkcia hľadá 2 prvky v poli vstupných znakov (pole smerníkov na TUzol) 2 prvky s najmenšou pravdepodobnosťou výskytu.

Parametre:

TUzol **abc - pole smerníkov na TUzol. každý prvok poľa obsahuje v dátovej časti znak vstupnej abecedy a pravdepodobnosť výskytu

int n - veľkosť poľa abc

int &min1 - výstupný parameter. Index prvého prvku poľa abc s najmenšou pravdepodobnosťou výskytu znaku v texte

int &min2 - výstupný parameter. Index druhého prvku poľa abc s najmenšou pravdepodobnosťou výskytu znaku v texte

Návratová hodnota:

žiadna

TUzol* VlozDoStromu(TUzol *a,TUzol *b)

 1 TUzol* VlozDoStromu(TUzol *a,TUzol *b) 
 2 {  //vytvaram kodovaci strom zospodu hore
 3   TUzol *otec=new TUzol;
 4   otec->data = new THuff;
 5   otec->lavy=a;
 6   otec->pravy=b;
 7   otec->data->pp= a->data->pp + b->data->pp;
 8   otec->data->znak=0;
 9   return otec;    
10 }

Opis funkcie:

Funkcia vytvorí rodičovský uzol uzlov a a b. Dátová časť rodičovského uzla neobsahuje žiaden znak (riadok 8) a pravdepodobnosť výskytu tohoto 'zástupného' znaku je vypočítaná ako súčet pravdepodobností výskytov jeho dvoch potomkov (riadok 7).

Parametre:

TUzol *a,TUzol *b - vstupné parametre funkcie. Uzly a a b sú existujúce uzly (TUzol)

Návratová hodnota:

Smerník na novo vytvorený uzol kódovacieho stromu.

void UsporiadajKodoveSlova(TUzol **abc,TUzol *novy,int min1,int min2,int &n)

Pri tvorbe stromu vznikajú v poli prvkov prázdne miesta, ktoré treba zrušiť. Namiesto dvoch uzlov, z ktorých sme vytvorili nový uzol, ktorého pravdepodobnosť výskytu znaku v texte je rovná súčtu pravdepodobností výskytov týchto znakov, vložíme na správne miesto nový uzol.

Nový uzol 

1 void UsporiadajKodoveSlova(TUzol **abc,TUzol *novy,int min1,int min2,int &n)
2 { 
3    int i; 
4    abc[min1]=novy;          // na index min1 vlozim novy uzol
5    for(i=min2;i<n-1;i++)    // ostatne uzly posuniem o 1 dolava
6      abc[i]=abc[i+1];
7    n--;              // tym padom sa mi zmensi pocet uzlov v poli   
8   abc[n]=NULL;
9 }

Opis funkcie:

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. Preto treba preusporiadať pole abc ako ukazujú nasledujúce obrázky:

hodnoty min1 min2 určujú indexy prvkov v poli abc s najmenšími pravdepodobnosťami výskytu znaku v texte. Premenná novy je nový uzol, ktorý sme vytvorili v predchádzajúcom kroku a teraz ho treba zaradiť do poľa abc
Riadok č. 4 v prechádzajúcom zdrojovom kóde. Na pozíciu min1 sa vloží nový uzol (TUzol). Jeho vzťah s uzlami na indexe min1 a min2 je naznačený šípkami.
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. POZOR!! tento uzol nemôžeme zmazať pomocou delete, pretože by sme zmazali uzol, ktorý sme posunuli o jedno miesto naľavo.

Parametre:

TUzol **abc - pole smerníkov na TUzol v ktorom sú uložené znaky vstupnej abecedy a v priebehu programu sa tu ukladajú zástupné znaky.

TUzol *novy - smerník na nový uzol, ktorého potomkovia sú uzly poľa abc na indexoch min1 a min2

int min1,int min2 - indexy svoch prvkov s najmenšou pravdepodobnosťou výskytu znaku v texte

int &n - výstupný parameter : veľkosť poľa abc.

Návratová hodnota:

žiadna

void ZapisKodoveSlova(TUzol *ks,char *hodnota)

 1 // funkcia zmaze posledny znak v retazci 'hodnota'
 2 void substring(char *hodnota)
 3 {  
 4     hodnota[strlen(hodnota)-1]=0;
 5 }
 6 
 7 void ZapisKodoveSlova(TUzol *ks,char *hodnota)
 8 {   
 9     if(!ks) return;
10     else
11     { // kodove slovo zapisujeme len pre listy stromu
12       if(ks->lavy==NULL && ks->pravy==NULL)  
13       {       ks->data->kodove_slovo=new char[strlen(hodnota)];
14               strcpy(ks->data->kodove_slovo,hodnota);       
15       }
16        ZapisKodoveSlova(ks->lavy,strcat(hodnota,"0"));
17   	substring(hodnota);
18        ZapisKodoveSlova(ks->pravy,strcat(hodnota,"1"));
19         substring(hodnota);
20    }                     
21 }

Opis funkcie:

Listom kódovacieho stromu priradí kódové slová Huffmanovho kódu.

ZapisKodoveSlova je rekurzívna funkcia, ktorá ľavému potomkovi priradí znak 0 a pravému potomkovi znak 1. Ak sa pri rekurzívnom volaní narazí na list stromu (riadok 12), tak sa do dátovej časti daného uzla zapíše kódové slovo, ktoré je v parametri funkcie hodnota. Na riadku 13 je alokázia potrebného miesta pre toto kódové slovo a na riadku 14 je skopírovanie tohto reťazca do časti kodove_slovo. Rekurzívne volanie sa ukončí ak narazíme na neexistujúci uzol (riadok 9). Pomocná funkcia substring zmaže z reťazca hodnota posledný znak. Je to potrebné kvôli spätnému rekurzívnemu volaniu, keďže pri rekurzívnom volaní k tomuto parametru pridávame ďalšie znaky.


Parametre:

TUzol *ks - koreň kódovacieho stromu

char *hodnota - kódové slovo pre daný uzol. Na začiatku je je premenná hodnota prázdny reťazec.

Návratová hodnota:

Žiadna. Po skončení funkcie všetky listy stromu ks obsahujú reťazec s hodnotou kódového slova pre daný znak.

void zmazStrom(TUzol *uzol)

1 void zmazStrom(TUzol *uzol)
2 {
3   if (!uzol) return;
4   if (uzol->lavy)  // ak existuje lavy uzol   
5       zmazStrom(uzol->lavy);
6   if (uzol->pravy) // ak existuje pravy uzol
7        zmazStrom(uzol->pravy);
8   delete uzol;
9 }

Opis funkcie:

Zmaže binárny strom. Je použitý algoritmus postorder

Parametre:

TUzol *uzol . binárny strom, ktorý sa má zmazať.

Návratová hodnota:

Žiadna

void vypis(TUzol *s)

 1 void vypis(TUzol *s)
 2 {     if(!s)
 3          return;
 4       else    
 5       {  	
 6          vypis(s->lavy);
 7 	 if(s->data->znak)
 8 	 {
 9 	    cout<<s->data->znak<<" | ";
10             cout<<s->data->kodove_slovo;
11             cout<<endl;
12          } 
13          vypis(s->pravy);
14 	}
15 }

Opis funkcie:

Vypíše binárny, resp. kódovací strom. Je použitý algoritmus inorder


Parametre:

TUzol *s . binárny strom, ktorý sa má vypísať

Návratová hodnota:

Žiadna

Prílohy

Vstupný súbor je upravený text z http://sk.wikipedia.org/wiki/Dejiny_Ko%C5%A1%C3%ADc.

vstupný súbor text.txt

Zdroj: „http://www.kiwiki.info/index.php?title=Binárny_strom_-_Huffmanovo_kódovanie_(riešené_príklady)&oldid=6682“