Witam!
Mam program ktory ma za zadnie kompresowac i dekompresowac pliki z uzyciem kodowanie huffmana. Kompresje jakos udało mi sie napisac zas z dekompresja mam problemy. Wiem ze w sieci istnieje duzo takich tematow ale zaden dla mnie nie byl przydatny.Daltego prosze o pomoc. PLik test.txt jest plikiem wejsciowym w ktorym wprowadzamy dane w pliku czestosci.txt wystepuja czestosci wprowadzonych znakow plik tab.cod w ktorym zapisana jest tablica kodowa plik huffmantest.txt w ktorym zapisane sa zakodowane znaki z pliku test. Program wywolujemy przez konsole np c:\ huffman.exe test.txt huffmantest.txt. Prosilbym o jak najszybsza pomoc. z gory dzieki.
#include<stdio.h>
#include<stdlib.h>
#define ROZMIAR_BUFORA 1024
#define PLIK_CZ "czestosci.txt"
#define PLIK_TAB "tab.cod"
#define BITY 8
// struktura do przechowywania czestosci znaku
struct el {
char zn; // znak
int cz; // czestosc
struct el *next; // wskazanie na kolejny element
};
// struktuta so przechowywania danych z tabeli kodowej
struct el2 {
unsigned int kod;
int dl; // dlugosc kodu
char symbol;
};
// struktura drzewiasta, niezedna to stworzenia drzewa huffmana
struct huff {
char zn; // znak
float prawd; // prawdopodbienstwo wystapienia
struct huff *left, *right; // okresla lewy i prawy nastepnik
};
// struktura, ktora bedze przechowywac drzewa prawdopodobienstwa wystapienia znakow
struct huff_list {
struct huff *node;
struct huff_list *next;
};
// definicje typow
typedef struct el *elPtr;
typedef struct huff *huffPtr;
typedef struct huff_list *huff_listPtr;
// DEKLARACJE FUNKCJI
void WyznaczCzestosci(char b[], elPtr *root, int n); // wynzaczanie czestosci
void Zapisz(elPtr *root, FILE *f); // zapisanie czestosci do pliku
int Porownaj(const void *a, const void *b); // porownywanie wartosci (potrzebne do qsorta)
void Wstaw(elPtr *root, char zn, int cz); // wstaw nowy element do listy czestosci
int Sprawdz(elPtr *root, char zn); // sprawdzenie czy dany zn znajduje sie juz na liscie
void Posortuj(elPtr *root); // sortowanie listy
void UtworzTabliceKodowa(int lwz, elPtr *root); // utworzenie tablicy kodwej
void Kompresuj(FILE *f, FILE *f_out); // kompresja pliku
void ZapiszPaczke(unsigned int kod, int dl, FILE *f_out); // paczka -> plik (uzywane przy kompresji)
void usun(huff_listPtr *root, float sum);
void WyznaczKody(huffPtr root, char c[], int lenc, FILE *f, int lwz);
char paczka = 0; // paczka (char = 1 bajt = 8 bitów)
unsigned int kod = 0;
int wolne_bity = BITY; // na poczatku wszystkie bity w paczce sa wolne
int n; // do przechowywania ilosci symboli
// GLOWNY PROGRAM
int main(int argc, char *argv[])
{
FILE *file_in, *file_out, *file_cz; // deklaracja uchwytow plikow
char bufor[ROZMIAR_BUFORA]; // bufor (rozmiar = 1024)
int n, czestosc, i, lwz=0; // n - ilosc wczytanych bajtow, lwz - liczba wszystkich znakow
elPtr root = NULL; // wskazanie na strukture, root bedzie korzeniem listy
// sprawdzenie poprwanosci wpisania argumentow
if (argc != 3) {
printf("Podano zla liczbe argumentow!\n");
printf("Skladnia: %s plik_wejsciowy plik_wyjsciowy\n", argv[0]);
return 0;
}
if (file_in = fopen(argv[1], "rb")) { // otworzenie pliku wejsciowego
do {
n = fread(bufor, sizeof(char), ROZMIAR_BUFORA, file_in);
lwz += n;
WyznaczCzestosci(bufor, &root, n); // wyznaczanie czestosci
} while (n);
//printf("%d\n", lwz);
Posortuj(&root); // sortowanie listy czestosci
if (file_cz = fopen(PLIK_CZ, "w")) { // otworzenie pliku z czestosciami
Zapisz(&root, file_cz); // zapisanie do pliku informacji o ilosci znakow
UtworzTabliceKodowa(lwz, &root);
fclose(file_cz);
} else { printf ("Nie udalo sie otworzyc pliku z czestosciami!\n"); return 1; }
if (file_out = fopen(argv[2], "wb")) { // otworzenie pliku wynikowego do zapisu
Kompresuj(file_in, file_out);
} else { printf ("Nie udalo sie otworzyc pliku wynikowego!\n"); return 1; }
fclose(file_in);
} else { printf("Nie udalo sie otworzyc pliku wejsciowego!\n"); return 1; }
//printf("Zakonczono generowanie wyniku.\n");
/*system("PAUSE");
return EXIT_SUCCESS;*/
}
// DEFINICJE FUNKCJI
void WyznaczCzestosci(char b[], elPtr *root, int n) {
int i;
for (i=0;i<n;i++)
if (!Sprawdz(root, b[i])) Wstaw(root, b[i], 1);
}
void Zapisz(elPtr *root, FILE *f) {
elPtr tmp;
tmp= *root;
while (tmp) {
fprintf(f, "%c %d\n", tmp->zn, tmp->cz); // zapisanie czestosci znaku jako liczby calkowitej
tmp = tmp->next;
}
}
int Porownaj(const void *a, const void *b) {
elPtr intOne = *(elPtr*)a;
elPtr intTwo = *(elPtr*)b;
if (intOne->cz < intTwo->cz)
return -1;
if (intOne->cz == intTwo->cz)
return 0;
return 1;
}
void Wstaw(elPtr *root, char zn, int cz) {
elPtr newPtr, tmp;
// ustawienie danych elementarnych nowego elementu
newPtr = (elPtr)malloc(sizeof(struct el));
newPtr->zn = zn;
newPtr->cz = cz;
newPtr->next = NULL;
if (!*root) *root = newPtr;
else {
tmp = *root;
while(tmp->next) tmp = tmp->next;
tmp->next = newPtr;
}
}
// sprawdzenie czy zadany element znajduje sie na liscie
int Sprawdz(elPtr *root, char zn) {
elPtr tmp;
if (!*root) return 0;
else {
tmp = *root;
if (tmp->zn == zn) {
tmp->cz++;
return 1;
}
while (tmp->next) {
tmp = tmp->next;
if (tmp->zn == zn) {
tmp->cz++;
return 1;
}
}
return 0;
}
}
void Posortuj(elPtr *root) {
elPtr tmp;
int i=0;
n=0; // liczba elementow
// zliczenie elementow
tmp = *root;
while (tmp) {
n++;
tmp = tmp->next;
}
elPtr tab[n]; // tablica przechowujaca pointery do elementow listy
//zapisanie elementow listy do tablicy
tmp = *root;
while (tmp) {
tab[i] = tmp;
i++;
tmp = tmp->next;
}
// posortowanie tablicy
qsort((void*)tab, n, sizeof(elPtr), Porownaj);
// odtworzenie listy w kolejnosci niemalejacej
*root = tab[0];
for (i=0;i<n;i++) {
if (i==n-1) tab[i]->next = NULL;
else tab[i]->next = tab[i+1];
}
}
void UtworzTabliceKodowa(int lwz, elPtr *root) {
FILE *tab_cod; // plik z tablica kodowa
elPtr tmp; // do poruzania sie po liscie czestosci
huff_listPtr newPtr, root_h = NULL, tmp_h; // root_h - koren listy drzew, tmp_h - do poruszania sie po liscie drzew
float sum; // suma prawdopodobienstw
char c[32]; // do przechowywania kodu
tmp = *root;
while (tmp) {
newPtr = (huff_listPtr)malloc(sizeof(struct huff_list)); // nowy element listy
newPtr->next = NULL;
newPtr->node = (huffPtr)malloc(sizeof(struct huff)); // wskaznik na korzen drzewa (jako element listy)
newPtr->node->zn = tmp->zn; // przypisanie znaku do wezla
newPtr->node->prawd = (float)(tmp->cz) / (float)(lwz); // prawd. wystapienia znaku
newPtr->node->left = newPtr->node->right = NULL; // tylko korzen, wskazniki na potomkow wskazuja na NULL
if (!root_h) root_h = newPtr;
else {
tmp_h = root_h;
while(tmp_h->next) tmp_h = tmp_h->next;
tmp_h->next = newPtr;
}
tmp = tmp->next;
}
// w tej chwili lista zapelniona jest korzeniami drzew
printf ("Wypisanie prawdopodobienstw \n" );
tmp_h = root_h;
while (tmp_h) {
printf("%f\n", tmp_h->node->prawd);
tmp_h = tmp_h->next;
}
// tworzenie drzewa huffmana
while (root_h->next) { // dopoki w liscie istnieje wiecej niz jedno drzewo
tmp_h = root_h;
sum = tmp_h->node->prawd + tmp_h->next->node->prawd;
usun(&root_h, sum);
}
// w tej chwili jedynym elementem listy jest wskazanie na korzen drzewa Huffmana
tab_cod = fopen(PLIK_TAB, "wb"); // otworzenie pliku z tablcia kodowa do zapisu
fwrite(&n, sizeof(int), 1, tab_cod);
WyznaczKody(root_h->node, c, 0, tab_cod, lwz);
fclose(tab_cod);
/*tmp_h = root_h;
printf("Wypisanie zawartosci drzew listy: \n");
while (tmp_h) { // wypisanie zawrotsci drzew listy :-)
printf("%c - %f\n", tmp_h->node->zn, tmp_h->node->prawd);
tmp_h = tmp_h->next;
}*/
}
void Kompresuj(FILE *f, FILE *f_out) {
FILE *tab_cod;
int le, i; // le - liczba elemntow w tablicy
char tmp;
tab_cod = fopen(PLIK_TAB, "rb");
fread(&le, sizeof(int), 1, tab_cod); // odczytanie liczby elementow
printf("%d\n", le);
struct el2 *tab = (struct el2 *)calloc(sizeof(struct el2), le); // dynamiczna alokacja tablicy
for (i=0;i<le;i++) { // uzupelnianie tablicy wartosciami z tabeli kodowej w formacie symbol|dlugosc|kod
fread(&tab[i].symbol, sizeof(char), 1, tab_cod);
fread(&tab[i].dl, sizeof(int), 1, tab_cod);
fread(&tab[i].kod, sizeof(unsigned int), 1, tab_cod);
}
fclose(tab_cod);
// wypisanie tabeli kodwej
printf ("Tabela kodowa: \n");
for (i=0;i<le;i++) {
printf("%c-%d-%d\n", tab[i].symbol, tab[i].dl, tab[i].kod);
}
rewind(f); // przewiniecie pliku
do { // czytanie pliku i kompresja w locie
tmp = fgetc(f);
for (i=0;i<le;i++) {
if ((tab+i)->symbol == tmp) {
ZapiszPaczke((tab+i)->kod, (tab+i)->dl, f_out);
break;
}
}
} while (tmp != EOF);
if (wolne_bity != 0) fwrite(&paczka, sizeof(char), 1, f_out); // gdy zostala niepelna paczka
}
void ZapiszPaczke(unsigned int kod, int dl, FILE *f_out) {
//printf("%d - %d\n", dl, kod);
if (wolne_bity >= dl) {
paczka |= (kod<<(wolne_bity-dl));
wolne_bity -= dl;
if (wolne_bity == 0) {
fwrite(&paczka, sizeof(char), 1, f_out);
//fprintf(f_out,"%c",paczka);
paczka = 0;
wolne_bity = BITY;
}
} else {
paczka |= (kod>>(dl-wolne_bity));
fwrite(&paczka, sizeof(char), 1, f_out);
//fprintf(f_out,"%c",paczka);
paczka = 0;
paczka |= (kod<<(BITY-dl+wolne_bity));
wolne_bity += BITY - dl;
}
}
void usun(huff_listPtr *root, float sum) {
huff_listPtr tmp, newPtr;
tmp = *root;
newPtr = (huff_listPtr)malloc(sizeof(struct huff_list)); // stworzenie nowego elementu...
newPtr->node = (huffPtr)malloc(sizeof(struct huff)); // a w nim nowego wezla
newPtr->node->prawd = sum; // sumowanie prawdopodobienstw
newPtr->node->left = tmp->node; // ustanowienie nowego lewego potomka
newPtr->node->right = tmp->next->node; // ustanowienie nowego prawego potomka
newPtr->next = tmp->next->next;
newPtr->node->zn = 0;
free(tmp->next);
free(tmp);
*root = newPtr;
}
void WyznaczKody(huffPtr root, char c[], int lenc, FILE *f, int lwz) {
int i;
if(!(root->left)) {
kod = 0;
fwrite(&root->zn, sizeof(char), 1, f);
fwrite(&lenc, sizeof(int), 1, f);
//printf("%c : ", root->zn);
for(i = 0;i<lenc;i++) {
//printf("%c", c[i]);
if (c[i] == '0') kod |= (0<<i);
if (c[i] == '1') kod |= (1<<i);
}
fwrite(&kod, sizeof(unsigned int), 1, f);
//printf("\n");
}
else {
c[lenc] = '0'; WyznaczKody(root->left,c,lenc + 1, f, lwz);
c[lenc] = '1'; WyznaczKody(root->right,c,lenc + 1, f, lwz);
}
}