[C++] Algoritmo di Huffman e come implementarlo

[zeno3083]

Cerco una buona documentazione sull'algoritmo di Huffman per la compressione dati, e se spieghi come è possibile implementarlo in c++.

[FinalFantasy]

http://it.wikipedia.org/wiki/Codifica_di_Huffman

[zeno3083]

Salve avrei un piccolo problema nell'inplementazione dell'algoritmo fi HUFFMAN, dopo essermi creato il mio albero delle ricorrenze come faccio a dire al compilatore di utilizzare meno bit per i caratteri più frequenti, e di più per quelli meno frequenti.

Non c'è la faccio +
Ho bisogno di aiuto

[zucchino]

come hai scelto di codificare i simboli?

se posti il codice forse riusciamo ad aiutarti.

[zeno3083]

Postare il codice potrei pure farlo ma è un po lungo?
A me non interessa tanto come scriverlo, ma dal punto di vista teorico, come potrei implementarlo.

[Andrea1979]

bhè, non ti resta che "percorrerlo", la codifica l'hai già fatta nel momento in cui hai costruito l'albero.
esempio

esempio_di_codice_ad_uso_forum

Ricorrenze:
a = 1    i = 3    s = 2
c = 2    m = 2    u = 1
d = 3    o = 3    _ = 5
e = 3    p = 1
f = 1    r = 1

Riordiniamo secondo frequenza:
a = 1    c = 2    d = 3    _ = 5
f = 1    m = 2    e = 3
p = 1    s = 2    i = 3
r = 1             o = 3
u = 1

A questo punto si comincia a costruire l'albero, mettendo insieme gli elementi con ricorrenza minore (per esempio af, pr etc etc). Scrivo un po' di possibili alberi intermedi
Alberi intermedi

af = 2    uaf = 3    uafcpr = 7    deio = 12
pr = 2    cpr = 4    ms_ = 9       uafcprms_ = 16
          ms = 4  deio = 12
          de = 6
          io = 6

salvo errori.

Quindi dal mio albero, mi corrisponde, sempre salvo errori

e = 001
s = 1101
m = 1100
p = 10110
i = 010
o = 011

etc etc

[zeno3083]

Salve ragazzi vi ringrazzio per il vostro aiuto e ne avrei ancora bisogno, ho ancora un problema sono riuscito a implementarmi l'algoritmo di huffmann(salvo orrori) ma ho ancora un problema, dopo che implemento l'albero come mi creo il mio nuovo file compresso?

Vi posto il codice dell'algoritmo non tralasciando niente errori compresi:

int main (int argc, char * const argv[]) {
        char nomefile[30];  //nome del file
        ifstream lettura;  //creo un oggetto ifstream(lettura dei dati da un file sequenziale)
    
        map<const char, int > freqMap;  //map(chiave,valore)
        map<const char, int > ::iterator it;
        priority_queue< HuffNode, vector<HuffNode>, greater<HuffNode> > q;//???????
        HuffNode *hNode;

        char ch;
    
        cout << " Inserisci il nome del File.  \n";
        cin >> nomefile;
        lettura.open(nomefile);

        if (lettura.fail()){  //verfica se c'è un errore nell'apertura del file
                cout << "Errore nell'apertura del file \n";
                exit(1);
        }

        inStream.get(ch);
        while( !inStream.eof()) {  //verifica se siamo alla fine del file
                it = freqMap.find(ch);
                if (it == freqMap.end())
                        freqMap[ch] = 1;
                else
                        freqMap[ch]++;
                inStream.get(ch);
        }

        int numSym = 0; //Conta il numero di simboli

        it = freqMap.begin();
        //copia i valore della map nella coda di priorità
        while(it != freqMap.end()){
                hNode = new HuffNode(it->first, it->second);
                q.push(*hNode);
                numSym += it->second;
                it++;
        }
        //svuota la map
        freqMap.clear();
        //mi creo l'albero di huffman
        while(q.size>1){
                        HuffNode *left = new HuffNode( q.top() );
                        q.pop();
                        HuffNode *right = new HuffNode( q.top() );
                        q.pop();
                        q.push( HuffNode( left, right ) );
                        }
        
}
}

HELP ME!

[zeno3083]

RAGAZZI NESSUNO CHE MI DA UNA MANO NON SO PIU' DOVE SBATTERE LA TESTA :dhò

[zeno3083]

Raga come faccio a scrivere bit in un file?

[ibykos]

Ciao!

Se vuoi in C puoi utilizzare i campi di bit per memorizzare dati lunghi meno di un byte.
Non trattandosi di un tipo naturale, è possibile che la gestione di questo tipo di dato rallenti il programma.