Kodowanie Huffmana
Logowanie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zapomniałem hasła
» Forum » Programowanie » [C, C++] Szukam pomocy

Kodowanie Huffmana

Ostatnio zmodyfikowano 2011-06-01 15:39
Autor Wiadomość
drake0thiel
Temat założony przez niniejszego użytkownika
Kodowanie Huffmana
» 2011-05-30 03:02:40
Witam,

Chciałem prosić was, drodzy forumowicze, o pomoc. Muszę napisać program, który zakoduje mi plik kodowaniem Huffmana, a później kolejny, który go rozkoduje. Problem jest taki, że gdzieś w środku tych programów jest błąd. Przeglądałem je już chyba milion razy i nadal nie wiem, co jest z nimi nie tak. To znaczy: kodowanie i dekodowanie przebiega pomyślnie, kompresja jest nawet dobra, jednak plik wyjściowy nie jest taki sam, jak plik wejściowy. Jeśli ktoś by mógł mi pomóc, byłbym bardzo wdzięczny.

kodowanie:
C/C++
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

#define buf 1000

using namespace std;


//struktura zawierajaca symbole
struct symbole
{
    int znak;
    int czestosc;
    string klu;
};
//struktura pozwalajaca na utworzenie korzenia
struct korzen
{
    korzen * gora;
    korzen * lewo;
    korzen * prawo;
    korzen * next;
    korzen * prev;
    int zn;
    int cz;
    string key;
    string zast;
};

//sortowanie babelkowe
int sorting( struct symbole tablica[], int k )
{
    int i;
    int z = 0;
    int temp_znak;
    int temp_czestosc;;
    for( i = 0; i < k - 1; i++ )
    {
        if( tablica[ i ].czestosc > tablica[ i + 1 ].czestosc )
        {
            temp_znak = tablica[ i ].znak;
            temp_czestosc = tablica[ i ].czestosc;
            tablica[ i ].znak = tablica[ i + 1 ].znak;
            tablica[ i ].czestosc = tablica[ i + 1 ].czestosc;
            tablica[ i + 1 ].znak = temp_znak;
            tablica[ i + 1 ].czestosc = temp_czestosc;
            z++;
        }
    }
    return z;
}

//funkcja ustawiajaca tablice w porzadku znakowym
int resort( struct symbole tablica[], int k )
{
    int i;
    int z = 0;
    int temp_znak;
    int temp_czestosc;
    string tem_klu;
    for( i = 0; i < k - 1; i++ )
    {
        if( tablica[ i ].znak > tablica[ i + 1 ].znak )
        {
            tem_klu = tablica[ i ].klu;
            temp_znak = tablica[ i ].znak;
            temp_czestosc = tablica[ i ].czestosc;
            tablica[ i ].znak = tablica[ i + 1 ].znak;
            tablica[ i ].czestosc = tablica[ i + 1 ].czestosc;
            tablica[ i ].klu = tablica[ i + 1 ].klu;
            tablica[ i + 1 ].klu = tem_klu;
            tablica[ i + 1 ].znak = temp_znak;
            tablica[ i + 1 ].czestosc = temp_czestosc;
            z++;
        }
    }
    return z;
}

//sortowanie dynamicznej tablicy - potrzebne do tworzenia drzewa huffmana
int bubelsort( korzen * head )
{
    int k = 0;
    int li = 0;
    string z;
    korzen * tem = NULL;
    while( head->next )
    {
        if( head->cz > head->next->cz )
        {
            z = head->zast;
            head->zast = head->next->zast;
            head->next->zast = z;
            li = head->cz;
            head->cz = head->next->cz;
            head->next->cz = li;
            li = head->zn;
            head->zn = head->next->zn;
            head->next->zn = li;
            tem = head->lewo;
            head->lewo = head->next->lewo;
            head->next->lewo = tem;
            tem = head->prawo;
            head->prawo = head->next->prawo;
            head->next->prawo = tem;
            k++;
        }
        head = head->next;
    }
    return k;
}

//funkcja wypisujaca drzewo na ekran
void pisz( korzen * glowa, int it )
{
    int i = 0;
    if( !glowa )
    {
        return;
    }
    pisz( glowa->prawo, it + 1 );
    for( i = 0; i < it; i++ )
    {
        cout << " ";
    }
    cout << glowa->zast << " ";
    if( glowa->zn != 666 ) cout << glowa->zn << " ";
   
    cout << glowa->cz << "/ " << glowa->key << endl << endl;
    pisz( glowa->lewo, it + 1 );
}

//funkcja tworzaca dla kazdego wezla kod
void kod( korzen * glowa )
{
    if(( !glowa->lewo ) &&( !glowa->prawo ) )
    {
        return;
    }
    glowa->prawo->key = glowa->key + '0';
    glowa->lewo->key = glowa->key + '1';
    kod( glowa->prawo );
    kod( glowa->lewo );
}

//funkcja przypisujaca do tablicy klucze kodowe
void zakod( korzen * glowa, struct symbole model[ 256 ] )
{
    int n;
    if(( !glowa->lewo ) &&( !glowa->prawo ) )
    {
        model[ glowa->zn ].klu = glowa->key;
    }
    if( glowa->prawo ) zakod( glowa->prawo, model );
   
    if( glowa->lewo ) zakod( glowa->lewo, model );
   
    return;
}



int main()
{
    unsigned char bufor_wejscia[ buf ];
    int k = 0;
    int i = 0;
    int j = 0;
    int z = 1;
    int h = 0;
    int g = 0;
    int n = 0;
    float procent;
    unsigned char kon = 0;
    string wyj;
    int licz = 0;
    korzen * head = NULL;
    korzen * tail = NULL;
    korzen * temp = NULL;
    korzen * nowy = NULL;
    FILE * plik = NULL;
    FILE * klip = NULL;
    FILE * klucz = NULL;
    plik = fopen( "WE.txt", "rb" );
    klip = fopen( "WY.txt", "wb" );
    //klucz=fopen("Klucz.txt", "w");
    struct symbole model[ 256 ];
   
    //wypelnianie tablicy struktur
    for( i = 0; i < 256; i++ )
    {
        model[ i ].znak = i;
        model[ i ].czestosc = 0;
    }
   
   
    //funkcja dodajaca znaki
    while( k = fread( bufor_wejscia, sizeof( unsigned char ), buf, plik ) )
    {
        //funkcja liczaca czestosc znakow
        for( i = 0; i < k; i++ )
        {
            for( j = 0; j < 256; j++ )
            {
                if( bufor_wejscia[ i ] == model[ j ].znak )
                {
                    model[ j ].czestosc++;
                }
            }
        }
        licz += k;
    }
   
    cout << "pobrany plik zajmuje " << licz << " bajtow" << endl;
    //funkcja sortująca model zrodla
    do
    {
        z = sorting( model, 256 );
    }
    while( z );
   
    z = 0;
    fclose( plik );
   
    //tworzenie drzewa kodowego
   
    for( z = 0; z < 256; z++ )
    {
        if( model[ z ].czestosc )
        {
            temp = new korzen();
            temp->zn = model[ z ].znak;
            temp->cz = model[ z ].czestosc;
            temp->key = 'e';
            temp->zast = temp->zn;
            temp->lewo = NULL;
            temp->prawo = NULL;
            temp->prev = NULL;
            temp->next = NULL;
            if( head == NULL )
            {
                head = temp;
            }
            if( tail == NULL )
            {
                tail = temp;
            }
            else
            {
                temp->prev = tail;
                tail->next = temp;
                tail = tail->next;
            }
           
        }
    }
   
    i = 1;
    temp = head;
   
    //tworzenie drzewa huffmana
    while( temp->next )
    {
        do
        {
            j = bubelsort( temp );
        }
        while( j );
       
        nowy = new korzen();
        nowy->key = 'e';
        nowy->prawo = temp;
        nowy->lewo = temp->next;
        nowy->next = temp->next->next;
        temp->gora = nowy;
        temp->next->gora = nowy;
        nowy->zast = '#';
        nowy->zn = 666;
        nowy->cz = temp->cz + temp->next->cz;
        nowy->zast +=( 48 + i );
        temp = nowy;
        i++;
        temp = nowy;
    }
    kod( temp );
   
   
    do
    {
        z = resort( model, 256 );
    }
    while( z );
   
    zakod( temp, model );
   
   
   
    cout << endl << endl << endl;
   
    //kodowanie samo w sobie
    plik = fopen( "WE.txt", "rb" );
   
    //funkcja wypisujaca do pliky WY.txt binarnie zapisany kod
    h = 0;
    while( k = fread( bufor_wejscia, sizeof( unsigned char ), buf, plik ) )
    {
        //funkcja liczaca czestosc znakow
        for( i = 0; i < k; i++ )
        {
            for( j = 0; j < 256; j++ )
            {
               
                if( bufor_wejscia[ i ] == model[ j ].znak )
                {
                    z = 1;
                    while( model[ j ].klu[ z ] )
                    { h++;
                        if( model[ j ].klu[ z ] == '1' )
                        {
                            wyj = wyj + '1';
                        }
                        else
                        {
                            wyj = wyj + '0';
                        }
                        z++;
                       
                        if( h == 8 )
                        {
                            kon = NULL;
                            if( wyj[ 0 ] == '1' ) kon = kon + 128;
                           
                            if( wyj[ 1 ] == '1' ) kon += 64;
                           
                            if( wyj[ 2 ] == '1' ) kon += 32;
                           
                            if( wyj[ 3 ] == '1' ) kon += 16;
                           
                            if( wyj[ 4 ] == '1' ) kon += 8;
                           
                            if( wyj[ 5 ] == '1' ) kon += 4;
                           
                            if( wyj[ 6 ] == '1' ) kon += 2;
                           
                            if( wyj[ 7 ] == '1' ) kon += 1;
                           
                            fprintf( klip, "%c", kon );
                            wyj = "";
                            h = 0;
                            n++;
                        }
                    }
                }
            }
        }
    }
    cout << endl << endl;
    z = 0;
    while( wyj[ z ] ) z++;
   
    z = z % 8;
    z = 8 - z;
   
    //fprintf(klucz, "puste %d", z);
   
    for( i = z; i > 0; i-- )
    {
        wyj = wyj + '1';
    }
    z = 0;
    //pisz(temp,0);
    while( wyj[ z ] ) z++;
   
    n++;
    procent =(( float ) n / licz );
    procent *= 100;
    cout << "zapisany plik zajmuje " << n << " bajtow" << endl << endl;
    if( z / 8 < licz ) cout << "KOMPRESJA UDALA SIE" << endl << "Procent kompresji wynosi: " << 100 - procent << "%" << endl;
   
    z = 0;
    while( wyj[ z ] )
    {
        kon = 0;
        if( wyj[ z ] == '1' ) kon = kon + 128;
       
        if( wyj[ z + 1 ] == '1' ) kon += 64;
       
        if( wyj[ z + 2 ] == '1' ) kon += 32;
       
        if( wyj[ z + 3 ] == '1' ) kon += 16;
       
        if( wyj[ z + 4 ] == '1' ) kon += 8;
       
        if( wyj[ z + 5 ] == '1' ) kon += 4;
       
        if( wyj[ z + 6 ] == '1' ) kon += 2;
       
        if( wyj[ z + 7 ] == '1' ) kon += 1;
       
        fprintf( klip, "%c", kon );
        z = z + 8;
    }
    fprintf( klip, "\nKoniec\n" );
    //wypisywanie na ekran i do pliku modelu zrodla
    for( z = 0; z < 256; z++ )
    {
        g = 1;
        //fprintf(klip, "%c ", model[z].znak);
        while( model[ z ].klu[ g ] )
        {
            fprintf( klip, "%c", model[ z ].klu[ g ] );
            g++;
        }
        if( !model[ z ].klu[ 1 ] ) fprintf( klip, "X" );
       
        fprintf( klip, "\n" );
    }
   
   
   
    system( "pause" );
    return 0;
}



dekodowanie:
C/C++
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdio.h>
#include <windows.h>
#include <stdlib.h>

using namespace std;

//struktura zawieraj±ca model
struct symbole
{
    int znak;
    int czestosc;
    string klu;
};


int main()
{
   
    char bufor[ 100 ];
    symbole model[ 256 ];
    string wej;
    int we;
    string klops = "";
    int k;
    int i;
    int j;
    fstream plik, klip, piku;
    plik.open( "WY.txt", std::ios::in | std::ios::binary );
    piku.open( "tymcz.txt", std::ios::out | std::ios::trunc | std::ios::binary );
    klip.open( "Odkodowanie.txt", std::ios::out | std::ios::trunc | std::ios::binary );
    //getline(plik, wej);
    plik >> wej;
    while( wej != "Koniec" )
    {
        piku << wej;
        plik >> wej;
    }
    cout << wej << endl;
    system( "pause" );
    piku.close();
    for( i = 0; i < 256; i++ )
    {
        plik >> wej;
        model[ i ].klu = wej;
        model[ i ].znak = i;
    }
    wej = "";
    plik.close();
    for( i = 1; i < 256; i++ )
    {
        cout << model[ i ].znak << "-> " << model[ i ].klu << endl;
    }
    piku.open( "tymcz.txt", std::ios::in | std::ios::binary );
    piku.read( bufor, 100 );
    k = piku.gcount();
    while( k )
    {
        for( i = 0; i < k; i++ )
        {
            if( bufor[ i ] & 128 )
            {
                wej = wej + '1';
            }
            else
            {
                wej = wej + '0';
            }
            for( j = 0; j < 256; j++ )
            {
                if( wej == model[ j ].klu )
                {
                    klip <<( unsigned char ) j;
                    wej = "";
                }
            }
            //cout<<wej<<endl;
            if( bufor[ i ] & 64 )
            {
                wej = wej + '1';
            }
            else
            {
                wej = wej + '0';
            }
            for( j = 0; j < 256; j++ )
            {
                if( wej == model[ j ].klu )
                {
                    klip <<( unsigned char ) j;
                    wej = "";
                }
            }
            //cout<<wej<<endl;
            if( bufor[ i ] & 32 )
            {
                wej = wej + '1';
            }
            else
            {
                wej = wej + '0';
            }
            for( j = 0; j < 256; j++ )
            {
                if( wej == model[ j ].klu )
                {
                    klip <<( unsigned char ) j;
                    wej = "";
                }
            }
            //cout<<wej<<endl;
            if( bufor[ i ] & 16 )
            {
                wej = wej + '1';
            }
            else
            {
                wej = wej + '0';
            }
            for( j = 0; j < 256; j++ )
            {
                if( wej == model[ j ].klu )
                {
                    klip <<( unsigned char ) j;
                    wej = "";
                }
            }
            //cout<<wej<<endl;
            if( bufor[ i ] & 8 )
            {
                wej = wej + '1';
            }
            else
            {
                wej = wej + '0';
            }
            for( j = 0; j < 256; j++ )
            {
                if( wej == model[ j ].klu )
                {
                    klip <<( unsigned char ) j;
                    wej = "";
                }
            }
            //cout<<wej<<endl;
            if( bufor[ i ] & 4 )
            {
                wej = wej + '1';
            }
            else
            {
                wej = wej + '0';
            }
            for( j = 0; j < 256; j++ )
            {
                if( wej == model[ j ].klu )
                {
                    klip <<( unsigned char ) j;
                    wej = "";
                }
            }
            //cout<<wej<<endl;
            if( bufor[ i ] & 2 )
            {
                wej = wej + '1';
            }
            else
            {
                wej = wej + '0';
            }
            for( j = 0; j < 256; j++ )
            {
                if( wej == model[ j ].klu )
                {
                    klip <<( unsigned char ) j;
                    wej = "";
                }
            }
            //cout<<wej<<endl;
            if( bufor[ i ] & 1 )
            {
                wej = wej + '1';
            }
            else
            {
                wej = wej + '0';
            }
            for( j = 0; j < 256; j++ )
            {
                if( wej == model[ j ].klu )
                {
                    klip <<( unsigned char ) j;
                    wej = "";
                }
            }
            //cout<<wej<<endl;
           
           
        }
        piku.read( bufor, 100 );
        k = piku.gcount();
       
    }
    piku.close();
    system( "del tymcz.txt" );
    return 0;
}

Aby uruchomić programy należy w tym samym folderze zamieścić plik WE.txt z zapisanymi danymi.

O ile dla małych plików, rzędu 50 znaków nie ma problemów, to dla książek już robią się niezrozumiałe wyrazy.

Z góry dziękuję za pomoc.



//problem rozwiązany, temat do zamknięcia...
P-33649
DejaVu
» 2011-05-30 03:26:47
Może bufory masz za małe? :) Jeżeli dla tekstu krótkiego działa, a dla długiego nie to może być to sensowny powód.

/edit:
Poza tym plik wyjściowy może się różnić od wejściowego np. sposobem zakończenia nowego wiersza :) Pliki więc będą binarnie różne, choć tekst będą zawierały ten sam.
P-33650
drake0thiel
Temat założony przez niniejszego użytkownika
» 2011-05-30 07:53:20
Problem jest taki, że nawet tekstu nie zawierają takiego samego...
P-33651
DejaVu
» 2011-05-30 12:43:24
Więc to co piszesz jest sprzeczne z następującym zdaniem:
To znaczy: kodowanie i dekodowanie przebiega pomyślnie, kompresja jest nawet dobra (...)
Jeżeli jest błąd w algorytmie to nie pozostaje nic innego jak go zweryfikować z książkową implementacją :)
P-33654
drake0thiel
Temat założony przez niniejszego użytkownika
» 2011-05-30 13:05:16
Pisząc pomyślnie, miałem na myśli, że program się kompiluje i działa dość sprawnie (w sensie nie wiesza się i nie zżera pamięci). Jeśli miałbym porównywać to z książkową implementacją, to musiałbym chyba własną książkę napisać, ponieważ jest to wolna mieszanka c i cpp.
P-33657
DejaVu
» 2011-05-30 14:40:51
Algorytm jest zawsze ten sam. Nikt nie będzie analizował za Ciebie Twojego kodu zważywszy na fakt, że błąd dotyczy tylko i wyłącznie źle wykonanej implementacji algorytmu powszechnie znanego i dobrze opisanego na wielu stronach internetowych.
P-33658
DejaVu
» 2011-06-01 15:39:51
Jak już założyłeś temat to nie usuwaj z niego kodu - chyba, że koniecznie chcesz skończyć żywot użytkowania tego forum. Problemy są powtarzalne i zostawia się je dla 'potomnych'. To nie jest forum na indywidualne rozwiązywanie problemów, a potem ich kasowanie.

/edit:
A treść pierwszego posta przywróciłem.
P-33735
« 1 »
  Strona 1 z 1  
» Forum » Programowanie » [C, C++] Szukam pomocy
© Wszelkie prawa zastrzeżone 2005-2024