Codifica di Huffman

di il
7 risposte

Codifica di Huffman

Salve a tutti, tra meno di un mese ho l'esame di Algoritmi e per quella data devo creare un programma in C++ che effettui la codifica di Huffman.

Il nostro prof ci ha dato delle limitazioni, infatti non possiamo utilizzare la STL per la coda di priorità ma dobbiamo crearla noi tramite un min-heap.

Il codice è molto semplice perchè ho appena iniziato. Per adesso il testo è richiesto in input, successivamente lo aprirò da file.

Preso il testo, verifico la frequenza di tutti i caratteri e creo un vector. Successivamente dovrei effettuare l'heapify per portarmi il minimo elemento al primo posto nel vector così da poter andare a costruire l'albero di huffman.

Il problema è ho scritto il codice e questo sembra funzionare perchè il programma parte ma non vengono effettuati gli scambi..

Ecco il codice:

classe.h
class ELEMENTO
{
      private:
              char carattere;
              int frequenza;
              ELEMENTO *left;
              ELEMENTO *right;
      public:
             ELEMENTO()
             {
                  frequenza=0;
                  left=NULL;
                  right=NULL;
             }
             
             ELEMENTO(char x, int y)
             {
                  carattere=x;
                  frequenza=y;
             }
             
             ELEMENTO(const ELEMENTO &orig){carattere=orig.carattere; frequenza=orig.frequenza; left=orig.left; right=orig.right;};
             
             ~ELEMENTO(){};
             
             void ins_char(char x)
             {
                  carattere=x;
             }
             
             void aggiorna_freq()
             {
                  frequenza++;
             }
             
             void ins_left(ELEMENTO x)
             {
                  *left=x;
             }
             
             void ins_right(ELEMENTO x)
             {
                  *right=x;
             }
             
             char visualizza_char()
             {
                  return carattere;
             }
             
             int visualizza_freq()
             {
                  return frequenza;
             }
};
main.cpp
int main()
{
    string testo;
    
    cout<<"Inserisci il testo da codificare: "; //inserisco il testo
    getline(cin,testo);
    
    int size;
    size=testo.size()*8; //calcolo lo spazio occupato in memoria
    
    cout<<endl<<"Il testo occupa "<<size<<" bit di memoria.\n"<<endl<<endl;
    
    vector <ELEMENTO> caratteri; //creo il vettore delle frequenze dei caratteri
    
    caratteri.push_back(ELEMENTO(' ',0)); //il primo nodo in un heap mediate vettore deve essere nullo
    
    for(int i=0; i<testo.size(); i++)
    {
            bool ver=false; //variabile di verifica
            
            if(caratteri.size()==1) //se il vettore è vuoto inserisco l'elemento normalmente...
            {
                 caratteri.push_back(ELEMENTO(testo[i],1));
            }
            else //altrimenti sono costretto a verificare prima se l'i-esimo carattere è già stato inserito nel vettore
            {
                for(int j=1; j<caratteri.size(); j++)
                {
                     if(testo[i]==caratteri[j].visualizza_char()) //se l'i-esimo carattere è presente nel vettore..
                     {
                          caratteri[j].aggiorna_freq(); //aggiorno semplicemente il numero di frequenza
                          ver=true; //e assegno valore true alla variabile di verifica
                     }
                }
                
                if(ver==false) //se la variabile di verifica è falsa vuol dire che l'i-esimo elemento non è presente nel vettore
                {
                     caratteri.push_back(ELEMENTO(testo[i],1)); //quindi lo inserisco normalmente
                }
            }
    }
    
    for(int i=1; i<caratteri.size(); i++)
    {
            cout<<"Carattere: "<<caratteri[i].visualizza_char()<<" - Frequenza: "<<caratteri[i].visualizza_freq()<<"\n";
    }
    
    for(int j=(caratteri.size())-1;j>1;j=j-2) 
    {//in questo modo ci permette di salire nell’ albero, evitando di attivare la
     //funzione anche al fratello del nodo corrente già heap-izzato e
     //quindi di passare ad un altro figlio avente padre diverso (in pratica utilizza la procedura heap su 3 nodi alla volta )
          heapify(caratteri,j);
    }
    
    cout<<endl<<endl<<"Min-Heap:"<<endl;
    for(int i=1; i<caratteri.size(); i++)
    {
            cout<<"Carattere: "<<caratteri[i].visualizza_char()<<" - Frequenza: "<<caratteri[i].visualizza_freq()<<"\n";
    }
                                                                                        
    
    cout<<endl<<endl<<endl;
    system("PAUSE");
    return 0;
}
heapifu.cpp
void heapify(vector <ELEMENTO> a, int nodo)
{
     int padre,fratello,min;
     ELEMENTO scambia;
     int i;
     while(nodo<=(a.size())-1) 
     {// esce dal while quando raggiunge una foglia
         padre=nodo/2; //assegnazione di padre
         
         fratello=nodo%2;//assegnazione di frattelo relativamente a nodo
         if(fratello==0) 
         {// se nodo è pari allora cerca il fratello destro
             fratello=(padre*2)+1;
         }
         else 
         {// nodo dispari, cerchiamo fratello sinistro
             fratello=padre*2;
         }
         
         if(fratello>(a.size())-1 || a[fratello].visualizza_freq()>a[nodo].visualizza_freq()) 
         {// fratello non esiste o confronto tra i due fratelli o nodo > fratello
             min=nodo; //assegnzione fratello
         }
         else
         {
             min=fratello; // se il fratello esiste o e’ maggiore allora max = fratello
         }

         if(a[min].visualizza_freq()<a[padre].visualizza_freq()) 
         {// confronto tra padre e max nel caso caso dell’ if...scambio!!!
             scambia=a[min];
             a[min]=a[padre];
             a[padre]=scambia;
         }
         
         nodo=min*2;
     } // discende nell’ albero per confrontare max che ora è un nuovo nodo con i nuovi figli assegnategli

}
Credevo fosse un problema di costruttore, ma nella classe è presente il costruttore copia quindi la parte del codice dove vengono effettuati gli scambi dovrebbe funzionare..

Grazie per eventuali risposte

7 Risposte

  • Re: Codifica di Huffman

    Il vector va passato per reference:
    
    void heapify(vector <ELEMENTO> &  a, int nodo)
    
    altrimenti le modifiche all'interno della funzione non si ripercuotono all'esterno.
  • Re: Codifica di Huffman

    Grazie!!

    Un'altra cosa..

    Devo aprire un file che si chiama "testo.txt". Se inserisco "testo" al primo tentativo mi apre il file correttamente, se invece al primo tentativo scrivo un nome sbagliato lui ovviamente mi avvisa che il file non è stato aperto perchè non esiste, però poi se successivamente vado ad inserire il nome esatto ossia "testo" lui continua a dirmi che non è stato possibile aprire il file. In pratica l'unico modo per aprire il testo è inserire il nome corretto al primo colpo.. Siccome il mio prof cercherà di fare l'impossibile per trovare qualche bug, io proprio non riesco a capire dove sia l'errore:
    
    string buffer;
    string testo;
    string name;
    bool file=false; //variabile per verificare l'avvenuta apertura del file
    ifstream input;
    
    while(file==false)
    {
    cout<<"Inserisci il nome del file da aprire (senza formato): ";
    cin>>name;
    cout<<endl;
    
    name+=".txt"; //aggiungo il formato del file
    
    input.open(name.c_str(),ios::in); //apro il file in modalità di lettura
    
    if(input==NULL)
    {
    cout<<"Errore durante l'apertura del file. Il file potrebbe non esistere.";
    }
    else
    {
    cout<<"Apertura file avvenuta correttamente.";
    file=true; //con questo valore uscirò dal while
    }
    
    cout<<endl<<endl;
    system("pause");
    system("cls");
    }
    ......................
  • Re: Codifica di Huffman

    E' un comportamento normale. Se ifstream fallisce l'apertura del file, internamente fa il set di un bit che impedisce a un successivo uso dello stesso stream di aprire un altro file.

    Dovrebbe essere sufficiente un:
    
    input.clear();
    
    maggiori dettagli qui:
    http://www.cplusplus.com/reference/iostream/ios
    e
    http://www.cplusplus.com/reference/iostream/ifstream/open/
  • Re: Codifica di Huffman

    Grazie mille per le risposte. Mi hanno aiutato a risolvere i problemi..

    Adesso credo di essere riuscito a creare l'albero di Huffman in questo modo
    #include <cstdlib>
    #include <iostream>
    #include <string>
    #include <vector>
    #include "classe.h"
    #include "dichiarazioni.h"
    
    using namespace std;
    
    void albero_huffman(vector <ELEMENTO> &coda)
    {
        while(coda.size()>2)
        {
        
             ELEMENTO nodo;
        
             for(int j=(coda.size())-1;j>1;j=j-2) //questo ciclo forma il nostro min-heap
             {//in questo modo ci permette di salire nell’ albero, evitando di attivare la
             //funzione anche al fratello del nodo corrente già heap-izzato e
             //quindi di passare ad un altro figlio avente padre diverso (in pratica utilizza la procedura heap su 3 nodi alla volta )
                  heapify(coda,j);
             }
             
             nodo.somma_freq(coda[1].visualizza_freq());
             nodo.ins_left(coda[1]);
        
             coda.erase(coda.begin()+1);
        
             for(int j=(coda.size())-1;j>1;j=j-2) //questo ciclo forma il nostro min-heap
             {//in questo modo ci permette di salire nell’ albero, evitando di attivare la
             //funzione anche al fratello del nodo corrente già heap-izzato e
             //quindi di passare ad un altro figlio avente padre diverso (in pratica utilizza la procedura heap su 3 nodi alla volta )
                 heapify(coda,j);
             }
             
             nodo.somma_freq(coda[1].visualizza_freq());
             nodo.ins_right(coda[1]);
        
             coda.erase(coda.begin()+1);
        
             coda.push_back(nodo);
             
        }
    
    }
    
    
    creo di volta in volta un nodo e gli sommo le frequenze dei primi 2 elementi del vettore per poi eliminarli (il prof mi ha chiesto di usare una struttura heap)

    Essendo questa la struttura della classe
    #include <cstdlib>
    #include <iostream>
    
    using namespace std;
    
    class ELEMENTO
    {
          private:
                  char carattere;
                  int frequenza;
                  ELEMENTO *left;
                  ELEMENTO *right;
          public:
                 ELEMENTO()
                 {
                      frequenza=0;
                      left=NULL;
                      right=NULL;
                 }
                 
                 ELEMENTO(char x, int y)
                 {
                      carattere=x;
                      frequenza=y;
                 }
                 
                 ELEMENTO(const ELEMENTO &orig){carattere=orig.carattere; frequenza=orig.frequenza; left=orig.left; right=orig.right;};
                 
                 ~ELEMENTO(){};
                 
                 void ins_char(char x)
                 {
                      carattere=x;
                 }
                 
                 void aggiorna_freq()
                 {
                      frequenza++;
                 }
                 
                 void somma_freq(int x)
                 {
                      frequenza+=x;
                 }
                 
                 void ins_left(ELEMENTO x)
                 {
                      left=&x;
                 }
                 
                 void ins_right(ELEMENTO x)
                 {
                      right=&x;
                 }
                 
                 ELEMENTO visualizza_left()
                 {
                      return *left;
                 }
                 
                 ELEMENTO visualizza_right()
                 {
                      return *right;
                 }
                 
                 char visualizza_char()
                 {
                      return carattere;
                 }
                 
                 int visualizza_freq()
                 {
                      return frequenza;
                 }
    };
    vorrei sapere se sono giusti i puntatori.. precisamente i metodi ins_left(x) e ins_right(x).. mi servono per collegare i nuovi nodi con i figli di destra e di sinistra.. il programma parte e come unico elemento del vettore mi da il nodo con la somma di tutte le frequenze dei caratteri (quindi dovrebbe essere giusto) ma non riesco a scorrere l'albero.. Non posso usare iteratori e se uso i puntatori non mi riconosce i metodi della classe.
  • Re: Codifica di Huffman

    No, non è corretto. Stai affidando a left e right una copia di ELEMENTO creata sullo stack delle funzioni e che quando esce di scope non esiste più. Di conseguenza left e right punteranno a spazzatura. L'unico modo per evitarlo è un'allocazione dinamica (con tutto quello che ne consegue).
    Considerando che non vai a modificare - ELEMENTO x - puoi passarlo come const reference.
    Il tutto dovrebbe assomigliare a:
    
    void ins_left(const ELEMENTo& x) {
        left = new ELEMENTO(x);
    }
    
    e specularmente per ins_right
  • Re: Codifica di Huffman

    MI è riuscito.. Ho effettuato una visita preorder e me li visita tutti..

    Adesso comedevo procedere? Il nostro prof ci ha spiegato il meccanismo, cioè ogni volta che scendo nel figlio destro aggiungo 1 e ogni volta che scendo nel figlio sinistro aggiungo 0..

    Il codice per formarmi la stringa di bit di ogni carattere credo di riuscirlo a fare, poi basterà unirli nel modo giusto per ricavarsi la stringa esatta..

    Ma il mio dubbio è questo.. La stringa di bit in che variabile la salvo? L'unica soluzione che mi viene in mente è salvarla in un vettore.. Però non ci vedo molto senso..

    Il programma deve essere in grado sia di codificare che di decodificare quindi io apro un file di testo e devo salvare in uscita in un altro file la stringa di bit codificata e anche l'albero di huffman relativa al testo preso in input (che mi servira per decodificare il file)...

    Ma se io voglio codificare una parola di 5 lettere quindi 40 bit, nel file "compresso" salvo l'albero e un vettore con la stringa di 0 e 1 all'interno, mi viene più di 40 bit quindi che compressione è?

    Questa è la mia idea ma credo sia del tutto sbagliata.. Purtroppo su internet e sui libri la codifica di Huffman viene spiegata come la creazione dell'albero di Huffman..

    C'è qualcuno che con un poco di buona volotà riesce a spiegarmi la logica per finire il programma (ovviamente non il codice).

    Grazie per eventuali risposte..
  • Re: Codifica di Huffman

    Sono riuscito ad andare avanti.. In pratica ho terminato la codifica, devo solo salvare i bit in un file, però ho dei problemi.. Se apro un testo di poche parole il programma mi codifica il testoi in pochi bit, se il testo risulta essere troppo grande, il codificatore mi utilizza il doppio dei bit di partenza xD però è strano perchè il ragionamento fila..
    #include <cstdlib>
    #include <iostream>
    #include <string>
    #include <vector>
    #include "classe.h"
    #include "dichiarazioni.h"
    
    using namespace std;
    
    bool ver=false; //variabile globale che mi serve per uscire dalla ricerca quando trovo il carattere cercato. 
    
    void codifica (string testo, ELEMENTO *head)
    {
         vector <int> stringa_bit;
         
         for(int i=0;i<testo.size();i++)
         {     
              ver=false;
              vector <int> bit; 
              preorder_ric(head,bit,head->visualizza_freq(),testo[i]);
              
              for(int t=0;t<bit.size();t++)
              {
                   stringa_bit.push_back(bit[t]); 
              }     
         }
         
         for(int z=0; z<stringa_bit.size(); z++)
         {
              cout<<stringa_bit[z];
         }  
         
         cout<<endl<<endl<<"Il testo occupa "<<stringa_bit.size()<<" bit di memoria";
    }
    
    void preorder_ric (ELEMENTO *ptr, vector <int> &bit, int rad, char chiave) //funzione di letura preorder ricorsiva
    {
             if(ptr!=NULL && ver==false)
             {
                  if((ptr->visualizza_char())==chiave) ver=true;
        
                  if(ptr->visualizza_left()!=NULL && ver==false) //se il nodo corrente ha un figlio sinistro..
                  {
                       bit.push_back(0); //aggiorno il percorso con uno 0
                       preorder_ric(ptr->visualizza_left(),bit,rad,chiave); //e lo vado a visitare
                  }
                  if(ver==false)
                  {
                  bit.erase(bit.begin()+bit.size()-1); //se invece il nodo corrente non ha figlio sinistro elimino l'ultimo spostamento
                  if(ptr->visualizza_freq()==rad) bit.pop_back(); //se mi trovo alla radice azzero il percorso
                  bit.push_back(1); //aggiorno il percorso con 1
                  preorder_ric(ptr->visualizza_right(),bit,rad,chiave); //vado a visitare il figlio destro
                  }
             }
    
    }
    
    Mi sapete indicare dove sbaglio? Questo è la parte di codice che mi cerca il carattere nell'albero e mi forma la stringa di bit
Devi accedere o registrarti per scrivere nel forum
7 risposte