» Forum » Programowanie » [C, C++] Szukam pomocy

[C++] Kodowanie Huffmana

Ostatnio zmodyfikowano 2013-05-06 21:09

matid1234

Temat założony przez niniejszego użytkownika

» 2013-05-05 11:19:50

Witam.
Potrzebuję pomocy z napisaniem programu dotyczącego kodowania Huffmana. Nie do końca rozumiem struktury, a tak ma to być własnie napisane i sam sobie z tym nie poradzę. Wiem, że tego jest pełno w internecie, jednak wszędzie gdzie szukałem programy napisane są głównie w klasach. Program ma działać następująco:
Użytkownik wpisuje ilość znaków do kodowania, następnie po kolei litery i po każdej literze ilość jej wystąpień. - To już zrobiłem
Następnie program segreguje je według alfabetu (segregowanie też zrobione)
___________
Każdej literze przypisuje wartości A(000) B(001) C(010) D(011) itd.
Program bierze dwie litery o najmniejszej liczbie wystąpień sumuje ilości wystąpień tych dwóch(tworzy nowy węzeł) i tak dalej do stworzenia jednego wielkiego drzewa i na końcu program ma wywalić że teraz litera 'A' ma kod tam np 101 (droga po drzewie).
Potem trzeba wyliczyć prawdopodobieństwo wystąpienia każdej z liter ale to już sobie zrobię.
Mam jakiś szkielet kodu, który trzeba rozbudować, wygląda to następująco:

#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
// Sortowanie danych
void vSortowanie()
{
ifstream wejscie;
wejscie.open( "Wejscie.txt" );
int iIleWierszy;
wejscie >> iIleWierszy;
string sTab[ 2 ][ iIleWierszy ];
// Wczytuje dane do posortowania
for( int i = 0; i < iIleWierszy; i++ )
for( int j = 0; j < 2; j++ )
wejscie >> sTab[ j ][ i ]; //endfor / endfor

wejscie.close();
// Sortowanie
for( int j = 1; j < iIleWierszy; j++ )
for( int i = 1; i < iIleWierszy; i++ )
if( sTab[ 0 ][ i ] < sTab[ 0 ][ i - 1 ] )
{
swap( sTab[ 0 ][ i ], sTab[ 0 ][ i - 1 ] );
swap( sTab[ 1 ][ i ], sTab[ 1 ][ i - 1 ] );
} //ednif / endfor
// Wypisuje posortowane dane do pliku
ofstream posortowane( "Wejscie_Alfabetycznie.txt" );
for( int i = 0; i < iIleWierszy; i++ )
{
for( int j = 0; j < 2; j++ )
posortowane << sTab[ j ][ i ] << "\t";

posortowane << "\n";
}
posortowane.close();
}
struct drzewo
{
int iWartosc;
drzewo * lewo;
drzewo * prawo;
drzewo * rodzic;
drzewo();
};
struct lista
{
drzewo * head;
lista();
};
int main()
{
vSortowanie();
system( "pause" );
return 0;
}

Pomoże ktoś?

P-82079

Monika90

» 2013-05-05 15:51:29

string sTab[ 2 ][ iIleWierszy ];

To jest źle. W C++ rozmiar tablicy musi być stałą znaną w czasie kompilacji. Dopiero w C++14 będą tablice o rozmiarze znanym w czasie wykonania, ale nawet wtedy będzie to dotyczyć tylko pierwszego wymiaru tablicy.

P-82104

matid1234

Temat założony przez niniejszego użytkownika

Kodowanie Huffmana

» 2013-05-05 18:55:00

Okej, to da się zmienić, ale co do samego kodowania, to jak to zrobić?

P-82122

matid1234

Temat założony przez niniejszego użytkownika

Kodowanie Huffmana

» 2013-05-06 09:15:17

Witam ponownie.
Teraz jestem już na etapie samego kodowania Huffmana i kod wygląda następująco:

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <stdio.h>
using namespace std;
// Sortowanie danych
void vSortowanie()
{
ifstream wejscie;
wejscie.open( "Wejscie.txt" );
int iIleWierszy;
wejscie >> iIleWierszy;
char * cTab = new char[ iIleWierszy ]; // tablica liter
double * dTab = new double[ iIleWierszy ]; //tablica ilosci wystapien liter
// Wczytuje dane do posortowania
for( int i = 0; i < iIleWierszy; i++ )
   wejscie >> cTab[ i ] >> dTab[ i ]; //endfor

wejscie.close();
// Sortowanie
for( int j = 1; j < iIleWierszy; j++ )
for( int i = 1; i < iIleWierszy; i++ )
if( dTab[ i ] < dTab[ i - 1 ] )
{
swap( cTab[ i ], cTab[ i - 1 ] );
swap( dTab[ i ], dTab[ i - 1 ] );
} //ednif / endfor / endfor
// Wypisuje posortowane dane do pliku
ofstream posortowane( "Wejscie_Alfabetycznie.txt" );
posortowane << iIleWierszy << "\n";
for( int i = 0; i < iIleWierszy; i++ )
   posortowane << cTab[ i ] << "\t" << dTab[ i ] << "\n"; //endfor

posortowane.close();
}
struct Drzewo
{
char cZnak;
double dIloscWystapien;
Drzewo * lewo;
Drzewo * prawo;
Drzewo * nastepny;
};
//utworzenie listy z literami
Drzewo * create()
{
ifstream wejscie;
int iIleWierszy;
wejscie.open( "Wejscie_Alfabetycznie.txt" );
wejscie >> iIleWierszy;
Drzewo * t = new Drzewo;
Drzewo * poczatek = t;
char cZnak;
int dIloscWystapien;
//pierwszy wezel
wejscie >> cZnak >> dIloscWystapien;
t->cZnak = cZnak;
t->dIloscWystapien = dIloscWystapien;
t->nastepny = t->lewo = t->prawo = 0;
//reszta wezlow
for( int i = 1; i < iIleWierszy; i++ )
{
wejscie >> cZnak >> dIloscWystapien;
t->nastepny = new Drzewo;
t = t->nastepny;
t->cZnak = cZnak;
t->dIloscWystapien = dIloscWystapien;
t->nastepny = t->prawo = t->lewo = 0;
} //endfor
wejscie.close();
return poczatek;
}
// Oblicza prawdopodobienstwo wystapienia danego znaku
void vPrawdopodobienstwo()
{
ifstream plik;
int iIleWierszy;
plik.open( "Wejscie_Alfabetycznie.txt" );
plik >> iIleWierszy;
char * cTab = new char[ iIleWierszy ]; // tablica liter
double * dTab = new double[ iIleWierszy ]; //tablica ilosci wystapien liter
double dSuma = 0;
// Wczytuje dane do sumowania - Moc Omega
for( int i = 0; i < iIleWierszy; i++ )
{
plik >> cTab[ i ] >> dTab[ i ]; //endfor
dSuma += dTab[ i ];
}
plik.close();
for( int i = 0; i < iIleWierszy; i++ )
   printf( "Prawdopodobienstwo wystapienia znaku '%c' wysnosi %4.2f\n", cTab[ i ],( dTab[ i ] / dSuma ) );

cout << "\n\n";
}
int main()
{
vSortowanie();
vPrawdopodobienstwo();
system( "pause" );
return 0;
}

Wie ktoś jak dokończyć kodowanie? Będę wdzięczny za cokolwiek :)

P-82174

Monika90

» 2013-05-06 14:59:14

Moim zdaniem najlepiej użyć std::priority_queue.

Musisz zdefiniować funkcję porównującą, która porównuje dwa wskaźniki do węzłów drzewa, biorąc pod uwagę częstość występowania znaku.

struct Cmp
{
bool operator ()( const Node * n1, const Node * n2 ) { return n1->frq > n2->frq; };
};

Tylko u ciebie Node nazywa się Drzewo, a frq nazywa się dIloscWystapien.

Deklarujesz kolejkę:

std::priority_queue < Node *, std::vector < Node *>, Cmp > queue;

Tworzysz węzły (jeden dla każdego znaku) i wypełniasz nimi kolejkę. I teraz masz banalny algorytm: dopóki w kolejce jest więcej niż jeden węzeł, to zdejmujesz dwa ze szczytu, tworzysz nowy węzeł, który jest rodzicem dla tych dwóch zdjętych i wstawiasz go do kolejki. W końcu w kolejce zostanie tylko jeden węzeł i to będzie korzeń drzewa Huffmana. Wtedy chodzisz po tym drzewie (rekurencja) generując kody.

std::priority_queue jest opisane tu: http://en.cppreference.com/w/cpp/container/priority_queue

P-82184

matid1234

Temat założony przez niniejszego użytkownika

Kodowanie

» 2013-05-06 18:02:40

Witam ponownie. Udało mi się dojść do tego. To jest nowo utworzona funkcja resztę bez zmian. Dobrze są tworzone te węzły?
Jak teraz mam sprawdzać ten warunek, że dopóki w kolejce jest więcej niż jeden węzeł, to zdejmuje dwa ze szczytu, tworze nowy węzeł, który jest rodzicem dla tych dwóch zdjętych i wstawiam go do kolejki?
Męczę się już z tym dobre 3h.
Dziękuję z góry za pomoc, oto ta funkcja:

void vHuffman()
{
ifstream plik;
int iIleWierszy;
plik.open( "Wejscie_Alfabetycznie.txt", ios::in );
if( plik.good() == true )
{
plik >> iIleWierszy;
char * cTab = new char[ iIleWierszy ]; // tablica liter
double * dTab = new double[ iIleWierszy ]; //tablica ilosci wystapien liter
for( int i = 0; i < iIleWierszy; i++ )
plik >> cTab[ i ] >> dTab[ i ]; //endfor

plik.close();
}
else cout << "NIE UZYSKANO DOSTEPU DO PLIKU 'Wejscie_Alfabetycznie.txt'!\n\n";
// Deklaruje kolejke priorytetowa
priority_queue < Drzewo *, vector < Drzewo *>, Cmp > Kolejka;
plik >> iIleWierszy;
Drzewo * t = new Drzewo;
char cZnak;
int dIloscWystapien;
//pierwszy wezel
plik >> cZnak >> dIloscWystapien;
t->cZnak = cZnak;
t->dIloscWystapien = dIloscWystapien;
t->nastepny = t->lewo = t->prawo = 0;
Kolejka.push( t );
//reszta wezlow
for( int i = 1; i < iIleWierszy; i++ )
{
plik >> cZnak >> dIloscWystapien;
t->nastepny = new Drzewo;
t = t->nastepny;
t->cZnak = cZnak;
t->dIloscWystapien = dIloscWystapien;
t->nastepny = t->prawo = t->lewo = 0;
Kolejka.push( t );
} //endfor
}

P-82204

Monika90

» 2013-05-06 21:09:58

Coś jak to:

while( Kolejka.size() > 1 )
{
Drzewo * n1 = Kolejka.top();
Kolejka.pop();
Drzewo * n2 = Kolejka.top();
Kolejka.pop();
Drzewo * t = /*utworz rodzica, ustaw mu odpowiednio składowe...*/
Kolejka.push( t ); /*... i wstaw*/
}

/*tutaj Kolejka.top() to korzeń drzewa*/

Pamietaj, że ilość wystąpień rodzica ma być sumą ilości wystapień potomków.
Składowa o nazwie

nastepny

raczej nie jest potrzebna.

P-82249

« 1 »

Strona 1 z 1

» Forum » Programowanie » [C, C++] Szukam pomocy