Juraj na 20:30, 16. august 2010

2010-08-16T20:30:25Z

Juraj na 19:12, 5. apríl 2010

2010-04-05T19:12:54Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadanie== Vytvorte program n…“

2010-04-05T16:14:31Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadanie== Vytvorte program n…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:jazyk C]]
{{Draft}}
{{Skripta programovanie (zbierka úloh)}}

==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 (,.-/()+-")
<source lang="c" line>
void pravdepodobnost_znakov()
{
ifstream in;
in.open("text.txt");
if(!in) return;

int znaky[64];
for(int i=0;i<64;i++)
znaky[i]=0;
char c;
do
{ c=in.get();
znaky[c-' ']++;
}while(c>=0);
in.close();
}
</source>
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:
<source lang="c" line>
struct Znak{
char znak;
double pp;
};

int porovnajZ(const void *a, const void *b)
{

if( (*(Znak*)a).pp > (*(Znak*)b).pp ) return 1;
if( (*(Znak*)a).pp < (*(Znak*)b).pp ) return -1;
return 0;
}
void pravdepodobnost_znakov()
{
ifstream in;
in.open("text.txt");
int n=64;
if(!in) return;
int znaky[64];
for(int i=0;i<64;i++)
znaky[i]=0;
char c;
do
{ c=in.get();
znaky[c-' ']++;
}while(c>=0);
double suma=0;
for(int i=0;i<n;i++)
{
cout<<(char)(i+32)<<" "<<znaky[i]<<endl;
suma+=znaky[i];
}
in.close();

Znak abc[n];
for(int i=0;i<n;i++)
{
abc[i].znak=(char)(i+32);
abc[i].pp=znaky[i]/suma;
}
qsort(abc,n,sizeof(abc[0]),porovnajZ);
ofstream out;
out.open("znaky.txt");
out<<n<<endl;
for(int i=0;i<n;i++)
{
out<<abc[i].znak<<"\t"<<abc[i].pp<<endl;
}
out.close();
}
</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.

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.

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

← Staršia verzia		Verzia zo dňa a času 20:30, 16. august 2010
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)}}

Binárny strom - Huffmanovo kódovanie (riešené príklady) - História úprav

Juraj na 20:30, 16. august 2010

Juraj na 19:12, 5. apríl 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadanie== Vytvorte program n…“