Newsgroup: it.comp.lang.c
Titolo: Aiuto per algoritmi di codifica...

Scusate, ma c'e' qualcuno che sa come (o sa dove in
rete..) implementare Huffman code e il Run Length
economy code..????
Grazie tante a tutti!
Bjk
=====
______________________________________________________________________
Do You Yahoo!?
Il tuo indirizzo gratis e per sempre @
yahoo.it
 su 
http://mail.yahoo.it
--
Posted from 
web1202.mail.yahoo.com
 [128.11.23.138]
via Mailgate.ORG Server - 
http://www.mailgate.org

 =====
In rete ti trovano senza problemi delle implementazioni
in vari contesti: ad esempio i sorgenti delle utility
per files MP3.
Io comunque sono soddisfatto di come il libro di Sedgewich
tratta l' argomento (e tutti gli altri).
Tel li descrivo a grandi linee perche' non ho con me il
libro e poco tempo:
Run length quando trova una sequenza di caratteri uguali
superiore ad una certa lunghessa (che si ritiene conveniente
codificare) usa un carattere usato come ESCAPE per segnalare
che si e' in presenza di una codifica, seguito dal carattere
e dal contatore di occorrenze. Naturalmente la codifica per
essere vantaggiosa deve aver luogo solo se un char di escape +
un char di simbolo + sifeof ( size_t ) e' minore della sequenza
da codificare. Inoltre si pone il problema di mascherare il
carattere usato com ESCAPE (che deve essere scelto molto bene,
il meno occorrente). Per mascherarlo si puo' usare il contatore
uguale a 0, ma cio' fa dilatare files con molti ESCAPE o files
gia' codificati. Credo che sia la codifica usata per Jpeg.
Huffmann si basa sulla costruzione di trie di codifica e
l' algoritmo trova la migliore trie di codifica possibile per
quel testo. Vanno contate le occorrenze di ogni carattere, poi
si crea una struttura che si puo' schematizzare con un grafo ad
albero in questo modo: l' occorrenza di ogni carattere viene usata
come peso di un nodo elementare e ad ogni passaggio coppie di nodi
la cui somma dei pesi e' minore di tutte le coppie costruibili in
quella fase vengono collegate come figli ad un nodo che avra' come
peso la somma del numero delle occorrenze (o pesi) dei nodi figli.
Questo fino ad avere un unico grande albero che sara' il trie di
codifica. Il nodo radice avra' come peso il numero di caratteri
del testo e ogni carattere sara' codificato con bits ottenuti
seguendo la spezzata dalla radice al nodo, 0 se SX o 1 se DX.
Immagino che spiegato cosi non possa essere chiaro.
Consiglio il libro di Sedgewich, Addison-Wesly-Masson. Magari se ti
serve ISBN domani te lo posto.
ciao.

Grazie tante a tutti!
Per quanto riguarda l'RLE ti ho scritto di seguito un semplicissimo
programma di esempio (sottolineo la parola "semplicissimo", anche
perchè l'ho scritto in fretta e furia ! ;))
Per quello che, invece, riguarda la codifica di Huffman, posto di
seguito un programma che esegue il calcolo dei codici di Huffman.
--------------------------- RLE.C ---- inizio
#include <stdio.h>
#include <string.h>
void add_char( char * s, char c )
{
     int l = strlen( s ) ;
     s[l++] = c ;
     s[l] = '\0' ;
}
int main()
{
    char text[] = "XXXABBBBRRRAAACADAAAAABRRRRRAAAAAGGGGHHHHH." ;
    /* il punto viene usato come segnalatore di fine stringa */
    char packed_text[100] ;
    char escape_seq[] = "****" ;
    int i = 0, n = 0, old = 0 ;
    packed_text[0] = NULL ;
    while ( text[i] )
    {
        if ( text[i] == old )
           ++n ;
        else
        {
           if ( n > 1 )
           {
              sprintf( escape_seq, "*%c%02d", old, n ) ;
              strcat( packed_text, escape_seq ) ;
           }
           else
           {
              add_char( packed_text, old ) ;
           }
           old = text[i] ;
           n = 1 ;
        }
        i++ ;
    }
    puts( text ) ;
    puts( packed_text ) ;
    return 0 ;
}
--------------------------- RLE.C ---- fine
--------------------------- HUFFMAN.C ---- inizio
/************************************************************
 * huffman.c - Esempio di calcolo di codici di Huffman      *
 * -------------------------------------------------------- *
 * ALCLIB v1.1 - Andrea Laforgia C Library                  *
 * (C)1999 Andrea Laforgia (
andrea_...@bigfoot.com
)    *
 * -------------------------------------------------------- *
 * NOTE : le variabili statiche :                           *
 *                                                          *
 *         static ULONG  stat_file_tot_len = 0L ;           *
 *         static ULONG  stat_file_cmp_len = 0L ;           *
 *         static double stat_cmp_ratio    = 0.0 ;          *
 *                                                          * 
 * sono state aggiunte in un secondo momento per ragioni di *
 * debug e non sono indispensabili.                         *
 *                                                          *
 * Dato che i codici di Huffman a lunghezza variabile si    *
 * adoperano in alcuni programmi di compressione, mi e'     *
 * servito confrontare la misura con cui questo programma   *
 * "comprime" la rappresentazione delle informazioni in     *
 * input, con quella di un compressore, per accertarmi che  *
 * il programma lavorasse nel modo giusto.                  *
 ************************************************************/
#include <stdio.h>
#include <stdlib.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) ;
static ULONG  stat_file_tot_len = 0L ;
static ULONG  stat_file_cmp_len = 0L ;
static double stat_cmp_ratio    = 0.0 ;
static ULONG bit_stream = 0L ; /* variabili globali ...          */
static int   numero_bit = 0 ;  /* ...utilizzate da scrivi_bits() */
int peso_minimo ( ptr_foglia vettore[], int n, int jmp_idx )
/* restituisce gli indici nel vettore dei puntatori foglia
   con peso minimo.
   "n" e' il numero dei puntatori foglia */
{
    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 */
             idx2 = peso_minimo( vettore, n, idx1 ) ;
             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 ;
       }
       return vettore[idx1] ;
}
void scrivi_bits ( ULONG buffer, int n )
/* scrive i bit da cui e' costituita la variabile "buffer".
   "n" e' il numero di bit che la compongono */
{
     char * bit_string = malloc( n + 1 ) ;
     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, ULONG bit_stream,
                                              unsigned numero_bit )
/* 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 */
        scrivi_codici_huffman( nodo->foglia_sinistra,
                               bit_stream << 1, numero_bit + 1) ;
     }
     if ( nodo->foglia_destra != NULL )
     {
        /* ad ogni ramo di destra e' associato il valore 1 */
        scrivi_codici_huffman( nodo->foglia_destra,
                               (bit_stream << 1) | 1, numero_bit + 1)
;
     }
     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 ) ;
          stat_file_cmp_len += ((ULONG)numero_bit) * nodo->freq ;
          printf("\n");
     }
}
void scrivi_albero( ptr_foglia radice )
{
    if ( radice )
    {
       if ( ( radice->foglia_sinistra ) ||
            ( radice->foglia_destra ) )
       {
            printf("0"); stat_file_cmp_len++ ;
            scrivi_albero( radice->foglia_sinistra );
            scrivi_albero( radice->foglia_destra );
       }
       else
       {
            printf("1");
            if (radice->car == '\n') printf("\\n");
            else printf("%c", radice->car ) ;
            stat_file_cmp_len += 9 ;
       }
    }
}
int main ( int argc, char **argv )
{
    FILE *in_fp ;
    ULONG freq [256] ;
    ptr_foglia * vettore_foglia, radice_albero ;
    int 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 ( argv[1], "rb" )) == 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 = 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 ;
        }
    radice_albero = crea_albero ( vettore_foglia, n ) ;
    scrivi_codici_huffman ( radice_albero, 0L, 0 ) ;
    printf("\nalbero : ");
    scrivi_albero ( radice_albero ) ;
    printf("\n");
    if ( fclose(in_fp) )
    {
       fprintf(stderr, "errore nella chiusura dello stream di
input\n");
       exit ( 1 ) ;
    }
    for (c = 0; c <= 255; c++)
        stat_file_tot_len += freq [c] ;
    stat_file_cmp_len = (stat_file_cmp_len >> 3) +
                        ( (stat_file_cmp_len % 8 ) ? 1 : 0 ) ;
    printf("\nfile total length      : %lu\n", stat_file_tot_len);
    printf("file compressed length : %lu\n", stat_file_cmp_len);
    stat_cmp_ratio = (1 - (double)stat_file_cmp_len /
(double)stat_file_tot_len) * 100;
    printf("compression ratio      : %lf\n", stat_cmp_ratio);
    return 0 ;
}
--------------------------- HUFFMAN.C ---- fine
--
Andrea Laforgia        (
andrea_...@bigfoot.com
)

volte :-)
E' vero, chiedo scusa per la lunghezza del codice e per il tempo che
vi faccio perdere nello scaricare un msg così lungo ! ;)
--
Andrea Laforgia        (
andrea_...@bigfoot.com
)

 
Forse hai frainteso, non era un'osservazione negativa nei tuoi
confronti, ma solo una constatazione. Qualche K di codice fa sempre
comodo, si impara sempre qualcosa.
-- 
 Ciao, Luca.
 Reply to 
luca....@tiscalinet.it

comodo, si impara sempre qualcosa.
Anche questo è vero, ma avevo intenzione, in tutta onestà, di aprire
una pagina Web dalla quale far scaricare i vari prgs.
Mi sento un pò imbarazzato quando devo spedire codice così lungo ; non
mi piace farlo per via privata, perchè mi sembra che il ng debba
aiutare anche gli altri programmatori.
Oppure sarebbe utile creare un ng adatto ( del tipo
"it.comp.lang.c.sources" ).
--
Andrea Laforgia        (
andrea_...@bigfoot.com
)

 Mi sento un pň imbarazzato quando devo spedire codice cosě lungo ;
Guarda, tra i tanti off-topic, leggere un po' di sorgenti C come si deve
č una boccata d'aria pura. :-)
EMG