Newsgroup: it.comp.lang.c
Titolo: codice di Huffman

Studiando gli algoritmi Greedy, ho trovato il suddetto algoritmo e l'ho
trovato molto interessante; vorrei provare a scrivere un prg che
costruisca un albero binario pieno che rappresenta i codici prefissi a
lunghezza variabile di un file, ma non so come trattare stringhe di bit
di lunghezza variabile. Dovrei poter scrivere e leggere queste stringhe
dal file un bit alla volta, ma non ho idea di come si possa fare.
Qualcuno sa darmi qualche suggerimento a proposito? Uso DJGPP con win95,
e non ho problemi ad usare funzioni non standard.
Grazie per le eventuali risposte. Ciao, Luca.
-- 
*******************************************************
  "C'e' un vecchio detto a riguardo delle reti che    
  recita: i problemi di banda possono essere risolti  
  con il denaro. I problemi di latenza sono piu' dif- 
  ficili poiche' la velocita' della luce e' una cos-  
  tante e non e' possibile corrompere Dio."           
 
                                     David Clark, MIT 
  Reply to 
bia...@maganet.net
*******************************************************

e non ho problemi ad usare funzioni non standard.
Il principio e' semplice : qual'e' l'unita' minima di informazione che si puo'
leggere o scrivere ? un byte.
Quindi i bit vanno "bufferizzati" in byte.
In lettura si legge un byte, se ne rilascia un bit alla volta e quando sono
"finiti" se ne legge uno nuovo.
In scrittura si deposita un bit alla volta nel byte, e quando e' pieno (ovvero
se ne raggiungono 8, la dimensione in bit del byte) si scrive il byte e si
svuota.
Skyscraper (apprezzatelo adesso : eviterete la coda)
----------------------------------------------------
 
andrea_...@bigfoot.com
----------------------------------------------------
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

dal file un bit alla volta, ma non ho idea di come si possa fare.
Ti ho scritto il programma che segue per farti vedere come si costruiscono i
codici di Huffman. 
(te l'avrei spedito prima ma bisogna considerare i tempi di debug ! che diamine
! ;)))
Ho compilato il programma col DJGPP sotto Win95 e non credo dovresti avere
problemi.
Non l'ho testato anche per i file binari, ma dovrebbe funzionare.
In ogni caso riportami i bug, se ne trovi.
Per testarlo prova a scrivere in un file "HUFFMAN.TXT" la stringa "ABRACADABRA"
e lancia il programma.
Sulla mia macchina, contando anche il carattere "\n" ha dato il seguente output
:
car =  97 ; freq = 5 ; codice huffman = 0
car = 100 ; freq = 1 ; codice huffman = 100
car =  10 ; freq = 1 ; codice huffman = 1010
car =  99 ; freq = 1 ; codice huffman = 1011
car =  98 ; freq = 2 ; codice huffman = 110
car = 114 ; freq = 2 ; codice huffman = 111
Nel tuo caso, visto che usi Win95, i valori di "car" dovrebbero essere uguali.
In ogni caso, come puoi vedere, il risparmio rispetto alla codifica originale e'
di (1 - 28 bit / 96 bit )*100 = 70 % (quasi 71) ed e' notevole !
Il programma e' il seguente e potrebbe essere esteso facilmente, per diventare
un programma di compressione :
/* HUFFMAN.C                 */
/* calcolo codici di Huffman */
#include <stdio.h>
typedef unsigned char BYTE ;
typedef unsigned long ULONG ;
struct foglia {
                 BYTE car ;
                 ULONG freq ;
                 struct foglia * foglia_madre ;
                 struct foglia * foglia_sinistra ;
                 struct foglia * foglia_destra ;
              } ;
typedef struct foglia * ptr_foglia ;
const ULONG ULONG_MAX = (-1 >> 1) ;
ULONG bit_stream = 0L ; /* variabili globali ...          */
int   numero_bit = 0 ;  /* ...utilizzate da scrivi_bits() */
int peso_minimo ( ptr_foglia vettore[], int n, int jmp_idx )
/* restituisce l' indice nel vettore dei puntatori foglia
   la cui foglia ha peso minimo.
   "n" e' il numero dei puntatori foglia 
   "jmp_idx" e' l'indice da saltare */
{
    ULONG min_freq = ULONG_MAX ;
    int i, p ;
    for ( i = 0; i < n ; i++ )
        if ( (vettore[i]->foglia_madre == NULL) &&
             ( vettore[i]->freq < min_freq ) &&
             (i != jmp_idx) )
        {
           min_freq = vettore[i]->freq ;
           p = i ;
        }
    return ( p ) ;
}
ptr_foglia crea_albero ( ptr_foglia vettore[], int n )
/* crea l'albero binario di Huffman a partire
   dal vettore dei puntatori foglia */
{
       int idx1, idx2, max = n ;
       ptr_foglia temp ;
       /* finquando non rimane un solo ramo */
       while ( max > 1 )
       {
             /* alloca spazio per il "ramo" */
             temp = ( ptr_foglia ) malloc ( sizeof(struct foglia) );
             /* cerca la prima foglia piu' leggera */
             /* -1 e' l'indice tra 0..n-1 che va saltato */
             idx1 = peso_minimo( vettore, n, -1 ) ;
             /* cerca la seconda foglia piu' leggera */
             /* valgono tutti gli indici meno quello gia' trovato */
             idx2 = peso_minimo( vettore, n, idx1 ) ;
 
             /* non e' strettamente necessario, ma mi piace ;) */
             temp->car = 0 ;
             /* il ramo e' ancora orfano */
             temp->foglia_madre = NULL ;
             /* le due foglie diventano figlie */
             vettore[idx1]->foglia_madre = temp ;
             vettore[idx2]->foglia_madre = temp ;
             /* il ramo ha come frequenza la somma di quelle */
             /* delle due figlie                             */
             temp->freq = vettore[idx1]->freq + vettore[idx2]->freq ;
             /* il ramo diventa mamma */
             temp->foglia_sinistra = vettore[idx1] ;
             temp->foglia_destra = vettore[idx2] ;
             /* il ramo viene sostituito ad una figlia */
             vettore[idx1] = temp ;
             /* quindi gli elementi del vettore sono decrementati di 1 */
             --max ;
       }
       /* l'ultimo ramo elaborato e' in realta' tutto l'albero */
       return vettore[idx1] ;
}
void scrivi_bits ( ULONG buffer, int n )
/* scrive i bit del valore contenuto in "buffer".
   "n" e' il numero di bit che lo compongono */
{
     char bit_string[n] ;
     bit_string[n] = '\0' ;
     while ( n )
     {
           bit_string[ --n ] = ( buffer & 1 ) ? '1' : '0' ;
           buffer >>= 1 ;
     }
     printf( bit_string ) ;
}
void scrivi_codici_huffman ( ptr_foglia nodo )
/* scrive il codice di huffman relativo ad ogni nodo terminale
   dell'albero binario di cui "nodo" e' radice */
{
     if ( nodo->foglia_sinistra != NULL )
     {
        /* ad ogni ramo di sinistra e' associato il valore 0 */
        bit_stream <<= 1 ; ++numero_bit ;
        scrivi_codici_huffman( nodo->foglia_sinistra ) ;
        bit_stream >>= 1 ; --numero_bit ;
     }
     if ( nodo->foglia_destra != NULL )
     {
        /* ad ogni ramo di destra e' associato il valore 1 */
        bit_stream = (bit_stream << 1) | 1 ;
        ++numero_bit ;
        scrivi_codici_huffman( nodo->foglia_destra ) ;
        bit_stream >>= 1 ;
        --numero_bit ;
     }
     if ( (nodo->foglia_sinistra == NULL) &&
          (nodo->foglia_destra == NULL) )
     {
          printf("car = %3d ; freq = %lu ; codice huffman = ",
                nodo->car, nodo->freq ) ;
          scrivi_bits ( bit_stream, numero_bit ) ;
          printf("\n");
     }
}
int main ( void )
{
    FILE *in_fp, *out_fp ;
    ULONG freq [256] ;
    ptr_foglia * vettore_foglia, radice_albero ;
    char c ;
    int i, j, n = 0 ;
    /* azzera le frequenze */
    for ( i = 0; i < 256; i++ ) freq[i] = 0 ;
    /* apre lo "stream" di ingresso */
    if ( ( in_fp = fopen ( "huffman.txt", "rt" )) == NULL )
    {
       fprintf(stderr, "errore nell\'apertura dello stream di input\n");
       exit ( 1 ) ;
    }
    /* incrementa la frequenza di ogni carattere presente */
    /* calcola inoltre n = numero di caratteri presenti */
    while ( ( c = getc( in_fp ) ) != EOF )
          if (freq[c]++ == 0) ++n ;
    /* inizializza il vettore delle foglie */
    vettore_foglia = ( ptr_foglia * ) malloc ( sizeof( ptr_foglia ) * n ) ;
    /* inizializza il vettore delle foglie in base alle frequenze */
    for ( i = 0, j = 0 ; i < 256; i++ )
        if ( freq [i] )
        {
           vettore_foglia[j] = (ptr_foglia) malloc( sizeof(struct foglia) );
           vettore_foglia[j]->car = ( BYTE ) i ;
           vettore_foglia[j]->freq = freq[i] ;
           vettore_foglia[j]->foglia_madre = NULL ;
           vettore_foglia[j]->foglia_sinistra = NULL ;
           vettore_foglia[j]->foglia_destra = NULL ;
           ++j ;
        }
    /* facile, no ? :) */
    radice_albero = crea_albero ( vettore_foglia, n ) ;
    scrivi_codici_huffman ( radice_albero ) ;
    if ( fclose(in_fp) )
    {
       fprintf(stderr, "errore nella chiusura dello stream di input\n");
       exit ( 1 ) ;
    }
    return 0 ;


      char bit_string[n] ;
Lo standard (ancora) non lo prevede. Puoi sostituirlo semplicemente con
un'allocazione dinamica.
Il resto sembra tutto ok. Complimenti.
EMG

Grazie per la risposta, davvero molto *esaustiva* :-)
P.S. L'ho provato con i file binari, modificando "rt" con "rb" in fopen,
ma non capisco perche' il prg si interrompe al primo 0 binario che
incontra. Non mi risulta che la getc restituisca un EOF quando trova uno
0, quindi il ciclo :
    /* incrementa la frequenza di ogni carattere presente */
    /* calcola inoltre n = numero di caratteri presenti */
    while ( ( c = getc( in_fp ) ) != EOF )
          if (freq[c]++ == 0) ++n ;
dovrebbe arrivare fino alla fine del file in_fp. Boh! ci guardero'
meglio.
Ciao, Luca


un'allocazione dinamica.
Va bene, lo sostituiamo con 
char * bit_string = malloc( n + 1 ) ;


          if (freq[c]++ == 0) ++n ;


 incontra.
Ho fatto la prova anch'io e non si ferma affatto. Legge regolarmente
tutto il file.
EMG

 char * bit_string = malloc( n + 1 ) ;
Perché più uno?
EMG

 elaborato come unsigned char e per questo bisogna usare "fgetc()".
A me risulta che getc() abbia sempre restituito un int.
EMG

 
Dopo aver fatto questa modifica, il compilatore (uso DJGPP con RHIDE) mi
da il seguente warning:
*Comparison is always 1 due to limited range of data type*
e quindi se provo ad eseguire il prg, questo non termina. Non dovrei
quindi usare un int per rappresentare c?


A me risulta che getc() abbia sempre restituito un int.
Si, restituisce l'int, pero' io so che legge un char con segno.
fgetc() invece restituisce lo stesso un int, ma legge un unsigned char.
Sara' per questo ? mah !...


Perchi piy uno?
Contavo anche lo zero finale, ma in effetti adesso non ricordo se era gia'
contato negli n, credo di no, quindi andrebbe bene
char * bit_string = malloc ( n ) ;
pero' n dovrebbe essere passato contando anche lo zero finale.
Oppure adattato con un ++n ; prima della allocazione.


quindi usare un int per rappresentare c?
..ops...si' e' vero devi usare un int per contemplare il -1 (cioe' EOF).


 quindi usare un int per rappresentare c?
Direi che sarebbe meglio.
EMG

 fgetc() invece restituisce lo stesso un int, ma legge un unsigned char.
Ma questo dove l'hai letto? A me risulta che siano perfettamente uguali
solo che la prima è una macro e la seconda una funzione. Sbaglio?
EMG

solo che la prima h una macro e la seconda una funzione. Sbaglio?
Sull'help del RHIDE e' riportato testualmente :
int getc(FILE *file);
Return Value
------------
The character ([0..255]) or `EOF' if eof or error.
int fgetc(FILE *file);
Description
-----------
Returns the next character in the given FILE as an unsigned char.
Return Value
------------
The given char (value 0..255) or `EOF' at end-of-file.


Enrico Maria Giordano (
e.m.gi...@flashnet.it
) wrote:
: Skyscraper wrote:
: > Si, restituisce l'int, pero' io so che legge un char con segno.
: > fgetc() invece restituisce lo stesso un int, ma legge un unsigned char.
: Ma questo dove l'hai letto? A me risulta che siano perfettamente uguali
: solo che la prima è una macro e la seconda una funzione. Sbaglio?
Da come la sapevo io, getc() /puo'/ essere una macro. Per il resto,
fgetc() e getc() dovrebbero essere equivalenti.
Ciao ciao,
Andrea
-- 
"...Unix, MS-DOS, and Windows NT (also known as the Good, the Bad, and 
 the Ugly)."
(by Matt Welsh)

 The given char (value 0..255) or `EOF' at end-of-file.
Scusa, ma se fgetc() deve poter restituire anche EOF oltre a tutti i
valori accettabili per un unsigned char è ovvio che non può restituire
un unsigned char. E dato che una funzione in C non può restituire due
tipi diversi a seconda della situazione è chiaro che il tipo restituito
da fgetc() deve essere necessariamente int.
EMG

 Da come la sapevo io, getc() /puo'/ essere una macro.
Si, certo.
EMG

da fgetc() deve essere necessariamente int.
Questo e' ovvio, come e' ovvio per getc().


 In realta' mi sa che ci stiamo incasinando.
Può essere. Ma a me sembra di aver sempre asserito che getc() e fgetc()
restituissero lo stesso tipo di dato. Forse ho capito male che tu
asserivi una cosa diversa?
EMG

asserivi una cosa diversa?
In realta' io parlavo di lettura, cioe' mi sembrava che "fgetc()" leggesse un
"unsigned char" a differenza di "getc()", ma in realta' ho letto sulla
pubblicazione ufficiale della libreria che sono la stessa cosa (anzi andrebbe
usata "getc()" ).
Il testo ufficiale riporta :
Function: int fgetc (FILE *stream) 
This function reads the next character as an unsigned char from the stream
stream and returns its value, converted to an int.
If an end-of-file condition or read error occurs, EOF is returned instead. 
Function: int getc (FILE *stream) 
This is just like fgetc, except that it is permissible (and typical) for it to
be implemented as a macro that evaluates the stream argument more than once.
getc is often highly optimized, so it is usually the best function to use to
read a single character. 


quindi usare un int per rappresentare c?
Ciao Bianco !
Ho ripreso il programma sotto mano per convertirlo in compressore, e mi sono
accorto che il problema era nell'apertura del file.
Per i file binari il parametro "rt" di fopen() deve diventare "rb" !
"c" deve essere dichiarato come "int".
Ciao !...


 
Sai, e' da un po' che ho fatto queste due modifiche, la prima l'avevo
indicata nel post del 18/2/99, e la seconda in quello del 19/2/99, dopo
aver chiesto consiglio. Il fatto e' che non mi tornano i conti. Adesso
pare che non si fermi piu' al primo 0 binario che incontra nel file,
pero' secondo me il file non lo scorre tutto ugualmente, perche' ho
provato ad aprire un file di circa 300K e la somma delle ricorrenze dei
vari caratteri non arriva neppure al migliaio, cosa al quanto
improbabile! Non sono proprio riuscito a capire dove sia il problema;
appena ho un po' di tempo provo a darci un'occhiata, ma per il momento,
visto che il 1 marzo ho l'appello di *Algoritmi e Strutture Dati*,
dovro' lasciare Huffman un po' da parte!
Ciao e grazie ancora.


dovro' lasciare Huffman un po' da parte!
Non credo che ci sia qualche problema, forse hai sbagliato qualcosa nel fare la
somma delle ricorrenze.
Ti dico questo perche' ho confrontato i risultati di compressione con quelli di
un normale compressore ed ottengo i seguenti risultati (per il file GDB.EXE
lungo 814592 byte) :
/* output del mio programma */
file total length      : 814592
file compressed length : 666277
compression ratio      : 18.207274 %
/* misura del file compresso dal secondo programma */
GDB      CMP       669.049  24/02/99  13.39 gdb.cmp
Quindi, come vedi, il calcolo e' fatto bene.
(ho testato il programma anche con altri file)
Skyscraper (
andrea_...@bigfoot.com
)
/*******************************/
/* sorri for mai inglish... :) */
/*******************************/
