Newsgroup: it.comp.lang.c
Titolo: Algoritmo di Compressione Cercasi!!

Qualsiasi algoritmo (es. ZIP, ARJ, RAR, ecc.) andrebbe bene purchè
discretamente efficiente.
Grazie.
               --Please also reply via E-Mail--
                      4169522043485253

 Grazie.
Prova a cercare in rete o su un testo di algoritmi i codici di Huffmann
(non ricordo se si scrive cosi'). Per quel che ricordo e' un algoritmo
ottimo, ossia non si puo' fare di meglio a meno di costanti.
-- 
 Ciao, Luca.
 Reply to 
luca....@tiscalinet.it
 UIN : 43385135

ottimo, ossia non si puo' fare di meglio a meno di costanti.
Ho capito cosa vuoi dire, ma detto cosi' lascia supporre che l'Huffman
sia il migliore, in realta' non e' vero.
Ha solo la caratteristica (come tutti gli algoritmi di compressione)
di "cristallizzare" il codice compresso, ovvero di impedire
un'ulteriore compressione dello stesso, sottoponendolo nuovamente al
processo di compressione.
L'algoritmo di Huffman non e' senz'altro il piu' efficiente (il suo
limite teorico, nella migliore delle ipotesi, e' dell' 87.5%,
considerando il byte come un gruppo di 8 bit ; aumenta con l'aumentare
del numero di bit necessari a rappresentare le informazioni).
Il Lempel-Ziv-Welch riesce a comprimere molto meglio ed e' adoperato
dai programmi come WinZip, ARJ, Rar, ecc...
Generalmente questi programmi fanno uso anche di altri algoritmi (il
Run Length Encoding, molto semplice da implementare, e Lo
Shannon-Fano, simile alla codifica di Huffman).
Purtroppo il LZW e' sottoposto a copyright da parte della Unisys e
quindi per applicazioni commerciali bisogna versare una certa quota
che adesso non ricordo.
Questo e' uno dei motivi per cui si sta cercando di utilizzare un
formato di memorizzazione delle immagini alternativo al .GIF (che
implementa, appunta, una variante del LZW).
Comunque, se vuoi sapere come funziona l'LZW scrivimi in privato.
--- huffman.c :
/************************************************************
 * 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 ;
}
--------------------------------------------------------
* Andrea Laforgia        (
andrea_...@bigfoot.com
) *
--------------------------------------------------------

 dai programmi come WinZip, ARJ, Rar, ecc...
!!!!!!!!!!!! =:-((
Ciao
--
Alessandro Monti

 !!!!!!!!!!!! =:-((
Anche questo risulta anche a me.
EMG

 Anche questo risulta anche a me.
Stesso libro, pagina più pagina meno.
--
Alessandro Monti

 Stesso libro, pagina piů pagina meno.
Vuoi dire che su quel libro c'č scritto espressamente che il metodo di
Lempel-Ziv-Welch č peggiore dell'Huffman? Se č cosě buttalo via. :-)
EMG

!!!!!!!!!!!! =:-((
Infatti e' cosi', si vede che non sei abbastanza esperto in questo
campo della programmazione ( ;) senza offesa, ma scrivo programmi di
compressione da parecchi anni, ormai ;) )


 compressione da parecchi anni, ormai ;) )
E non ti è mai venuto in mente di considerare parole più lunghe di 8 bit?
Anche i 2 teoremi di Shannon suggeriscono di usare parole più lunghe
possibili (qui è interessato il primo).
Comunque ammettendo tutti i limiti che poni, come farebbe LZW a superare
Huffman, quando riconosci che Huffman raggiunge il limite teorico
dell'87,5%? Non mi dire che LZW considera più di 8 bit mentre Huffman solo
8!!!!
Tutti gli altri, tipo run-lenght et similia, hanno dei limiti ben
conosciuti, e soprattutto mancano di generalità. Per alcuni file molto
particolari possono essere buoni, ma in generale falliscono miseramente.
Come dici, in effetti non mi è mai capitato di implementare algoritmi di
questo tipo, e forse se ci provassi otterrei che il R-L è migliore di
qualsiasi altro :) , ma mi ricordo bene ciò che ho studiato (e verificato in
esercizi con carta e penna).
Senza offesa, ma la teoria è la teoria.
--
Alessandro Monti

 Lempel-Ziv-Welch è peggiore dell'Huffman? Se è così buttalo via. :-)
Si. Anche per questo con tutte le dimostrazioni del caso.
Se poi nelle tue implementazioni huffman sia andato peggio di LZ, non so che
dirti.
LZ "probabilmente" funziona meglio nel caso medio e SOLO se poni un limite
massimo alla lunghezza del codice (poniamo 10 bit), anche se non capisco che
senso possa avere.
Ripeto: Huffman *-è-* l'ottimo. LZ è veloce e ha generalmente un buon
rapporto di compressione, ma non è difficile trovare dei casi in cui
fallisce miseramente. Se non ricordo male, LZ assume che la maggior parte
dei simboli abbiano una
probabilità di 1/(2^n), e in tal caso è ottimo, negli altri casi no.
--
Alessandro Monti

 Ripeto: Huffman *-è-* l'ottimo.
Allora dimostralo. Dicci dove scaricarne un'implementazione (in sorgente
ovviamente) che funzioni meglio del RAR (il migliore che ho trovato
finora). Sarò ben lieto di adottarlo da quel momento in poi per i miei
archivi compressi.
EMG

Senza offesa, ma la teoria è la teoria.
La teoria si comprende in modo corretto se associata alla pratica,
altrimenti rimane un mero insieme di falsi convincimenti senza una
base fondata.


LZ "probabilmente" funziona meglio nel caso medio e SOLO se poni un limite
Non e' vero, LZ funziona quasi sempre meglio di Huffman.
O hai studiato dal libro sbagliato, o hai frainteso cio' che c'e'
scritto. Se non ci credi, reperisci della documentazione in rete ed
informati.


Ok, mi avete convinto a riguardarmi bene gli algoritmi, probabilmente mi è
sfuggito qualcosa.
Scusate la tenacia, ma è dura cambiare idea quando si è sicuri di una cosa
studiata; comunque di fronte a così tante opinioni contrarie mi è venuto il
"piccolo dubbio"
--
Alessandro Monti


Bene. Se trovi qualcosa di nuovo dimmelo. Come ho già detto, sarei molto
contento di trovare un compressore migliore del RAR o dello ZIP.
EMG

 contento di trovare un compressore migliore del RAR o dello ZIP.
Non dovrebbe essere difficile; comprimendo 820 kBytes composti
largamente da testo e per una piccola parte da immagini, zip produce
217k di output (73% in meno), gzip 216k (74%) e bzip2 173k (79%).
Il sorgente di gzip e bzip2 e' liberamente distribuito sotto la GPL;
il primo nei soliti siti GNU (e.g. 
prep.ai.mit.edu
), il secondo e' in
sourceware.cygnus.com
 sotto /pub/bzip2 .  Entrambi in formato tar.gz,
temo :-)
-- 
Maurizio Loreti                      
http://wwwcdf.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

 temo :-)
Va beh, tanto ormai ho gzip che dovrebbe essere sufficiente per
scompattare quel formato, o no?
EMG

 Però a me interessano più che altro le prestazioni sui file eseguibili.
MLO@mlinux 152 $ wc -c /usr/local/bin/emacs
4782253 /usr/local/bin/emacs
MLO@mlinux 153 $ zip -q - /usr/local/bin/emacs | wc -c
1634741
MLO@mlinux 154 $ gzip -9c /usr/local/bin/emacs | wc -c
1625295
MLO@mlinux 155 $ bzip2 -9c /usr/local/bin/emacs | wc -c
1482899
wc -c conta il numero di bytes; la compressione e', nell'ordine, del
65.8%, 66.0%, 69.0% (se definita come 1-output/input).


 65.8%, 66.0%, 69.0% (se definita come 1-output/input).
Evidentemente o il zip che ho io comprime più del tuo oppure il gzip che
ho io comprime meno del tuo. Comunque non c'è molta differenza.
Interessante è invece il bzip2 ma io, come prevedevo, non riesco neanche
a vedere i sorgenti che ho prelevato. Il gzip mi dice che non trova il
file... boh, un sacco di punti e sigle strane. Decisamente nel mondo
Unix sanno come tener lontana la gente... :-)
EMG

"piccolo dubbio"
Credo che la questione si possa chiarire definitivamente leggendo la
serie di articoli dal titolo "Compressione di Huffman" di Corrado
Giustozzi, tratti dalla rubrica sul linguaggio C di MCmicrocomputer n.
87 di luglio/agosto 1989 : 
"[...]Esiste una formale dimostrazione matematica del fatto che questa
costruzione [quella di Huffman] dà sempre origine ad un codice dotato
di quelle particolari proprietà che lo rendono idoneo allo scopo che
tutti ci aspettiamo. Essa tra l'altro dimostra anche che il codice
così ottenuto non è solo "adatto allo scopo" ma risulta in effetti
ottimale in senso asssai generale : ossia esso, fra tutti i possibili
codice a lunghezza variabile che si possono escogitare, è quello che,
applicato al particolare file su cui è stato costruito, ne fornisce la
rappresentazione più compatta. [...]
A questo punto mi sembra il caso di inserire un breve commento su
questa dimostrazione di ottimalità che spesso tende a fuorviare chi la
sente. Credo sia giusto chiarire subito come stanno le cose per
evitare clamorose incomprensioni sull'algoritmo che stiamo per
implementare.
La dimostrazione poc'anzi citata non afferma, come molti credono, che
i codici di Huffman siano i migliori in assoluto, ossia che
garantiscano sempre e comunque la compressione maggiore.
Essa, come ho tenuto a sottolineare enunciandola, afferma solo che
essi sono i migliori *fra tutti i codici a lunghezza variabile*.
La differenza è sostanziale : in altre parole la dimostrazione non
esclude affatto che possano esistere algoritmi differenti, purchè
basati su principi diversi da quelli dei codici a lunghezza variabile,
mediante i quali si possano ottenere compressioni maggiori di quelle
ottenibili con un codice di Huffman.
Mi spiego con un esempio eclatante ed esagerato che però permette di
chiarire bene la vicenda. Supponiamo di avere un file composto da
diecimila caratteri uguali. Utilizzando un codice di Huffman esso può
al massimo essere ridotto ad una successione di diecimila bit, pur
ammettendo in linea di principio di poter raggiungere il limite
teorico di un codice minimale che utilizzi per l'appunto un solo bit
per rappresentare l'unico carattere nel file.[...] Ma è chiaro che in
questa particolare situazione un semplicissimo algoritmo di Run Length
Encoding risulta drasticamente più efficiente [...] ma ciò non viola
la dimostrazione perchè l'algoritmo RLE in effetti non utilizza codici
a lunghezza variabile.
La dimostrazione ci dice dunque solo ed unicamente che volendo
adoperare una codifica basata su codici a lunghezza variabile la
nostra scelta migliore è quella di un codice di Huffman, ma non si
pronuncia (e d'altronde come potrebbe ?) sui risultati ottenibili con
metodi differenti. In effetti esistono algoritmi mediamente più
efficienti di quello di Huffman, ad esempio quello assai più recente
denominato Lempel-Ziv, ma tutti si basano su altre strategie,
generalmente orientate ad isolare ed eliminare la ridondanza che
appare a livello di strutture di ordine superiore rispetto ai singoli
caratteri nel file".


 Unix sanno come tener lontana la gente... :-)
Sapessi come ci riesce bene Bill Gates a tenere lontana la gente ... ;-)
Raffaele

 Unix sanno come tener lontana la gente... :-)
Perche`, il mondo Windows l'avvicina? :))
Prova a scompattare un file autoscompattante (sic!) di Windows in Unix. ^_^
Btw se non ricordo male di solito non avevo problemi ad aprire i file TAR
compressi con WinZip. 
Inoltre dovrebbe esserci una versione di bzip2 gia` compilata per Windows
al seguente indirizzo:
http://sourceware.cygnus.com/bzip2/index.html
Prova a darci un'occhiata.
Ciao.
====================================================================
bzip2  compresses  files  using the Burrows-Wheeler block-
       sorting text compression algorithm,  and  Huffman  coding.
       Compression  is  generally  considerably  better than that
       achieved by more conventional LZ77/LZ78-based compressors,
       and  approaches  the performance of the PPM family of sta-
       tistical compressors.
====================================================================
-- 
gi@der    [< was it a cat I saw >]  (L. Carroll)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
E-mail:   giader(at)
linuxfan.com
       {Giacomo Delre}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 al seguente indirizzo:
Allora, grazie all'amico Raffaele Cicchese ho potuto provare il bzip2.
Però purtroppo l'ho trovato, anche se di pochissimo (1 Kb di differenza
su 1 Mb di file da comprimere) inferiore al solito rar. Quindi un
risultato del tutto diverso da quello riportato dall'amico Maurizio
Loreti. Come si può spiegare ciò?
EMG

 Loreti. Come si può spiegare ciò?
Differente input, differente output...  incidentalmente, non ho mai
sostenuto che quello che ho a disposizione io fosse migliore di quello
che ha a disposizione EMG; ho detto solo che di meglio di zip c'era
qualcosa.
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html


 i codici di Huffman siano i migliori in assoluto, ossia che
Beh, questo mi tira un po' su. Almeno eravamo in molti a crederci :)
Grazie della spiegazione.
--
Alessandro Monti

tra tutto sto' casino io cercavo di vedere un URL che indicasse dei
sorgenti o dei manuali sulle metodologia di compressione... non e' che
qualcuno puo' indicarmeli ?
Bye.

Qui ho un link: 
http://wildsau.idv.uni-linz.ac.at/mfx/compress.html
spero che ti possa servire :)
Ti consiglio comunqua di chiedere su comp.compression...
--
Posted from 
bikini.edu.al.unipmn.it
 [193.206.63.17]
via Mailgate.ORG Server - 
http://www.mailgate.org