Newsgroup: it.comp.lang.c
Titolo: [Forse OT] Compressione con Huffman

Ho realizzato un programmino per comprimere con l'algoritmo di Huffman ma
purtroppo spesso i file in uscita sono molto + grossi di quelli in entrata.
I casi sono 2: o io sbaglio o quest'algoritmo è adatto solo a pochissimi
tipi di file (tipo le immagini disegnate al computer).
Infatti a sostituire i byte con stringhe di bit a seconda della frequenza
non penso che sia molto conveniente se:
il più frequente   0
il secondo           10
....
il penultimo         [254 uni]0
l'ultimo                 [255 uni]
quindi 1 byte può anche occuparne 32! e in caso di file molto grossi la
quantità di ripetizioni per byte è eterogenea.
Insomma, non ho capito questo algoritmo? E se invece Huffman è così, dove
posso trovare un tutorial su di uno migliore (tipo LZH/LZO)?
Grazie

posso trovare un tutorial su di uno migliore (tipo LZH/LZO)?
La letteratura su LZ e le sue varianti e' copiosa.
Tuttavia ricordati che per applicazioni commerciali, questo algoritmo
necessita di licenza (e quindi che si sborsino dei soldini).

 tipi di file (tipo le immagini disegnate al computer).
Credo che tu abbia capito bene.
EMG

Credo che tu abbia capito bene.
Ribadisco : la compressione di Huffman e' adatta anche ad applicazioni
data-safe (per data-lossy si applica principalmente nell'algoritmo dei
.JPG). 

 Prendi spunto da questo :
In effetti l'avevo capito un po' male  (non riordinavo i nodi dopo la somma)
percui facevo:
1 7 18 22 (frequenze)
8 18 22
26 22
48
e quindi
      48
    /    \
  26  22
 /
...
invece di  48
                 /   \
              22  26
                     / \
                   .......
Però spesso il rapporto di compressione è di 1,2/1,5.
Ma come si fa a renderlo lossy? (mi servirebbe per immagini a 64Kcolori)
Ero convinto che la JPG trasformasse ogni gruppo 8x8 in una formula
matematica
(cosinusoidale mi pare).
Ah, ma se uso LZ in un programma gratuito non devo fare niente vero?
Grazie TJK

Ah, ma se uso LZ in un programma gratuito non devo fare niente vero?
Credo tu debba pagare le royalties comunque.

Credo tu debba pagare le royalties comunque.
Ci sono due tipi di algoritmi LZ, chiamati di solito LZ77 e LZ78. Nessuno 
dei due, per quanto ne so, e' vincolato da brevetto, mentre invece e' molto 
piu' complicata la situazione quando si considera l'*implementazione* 
dell'algoritmo. Su LZ77 si basano i formati zip, arj, lzh, ecc. comprese le 
librerie ZLIB che sono freeware e non usano brevetti. Per LZ78 ho vaghi 
ricordi di implementazioni "alternative" ma la piu' diffusa e' senz'altro 
quella LZW (Lempel-Ziv-Welch, con l'idea di costruire un dizionario "strada 
facendo" utilizzando "catene" di codici) ed e', purtroppo, brevettata.
Per l'OP: prova a scaricare la libreria ZLIB, e' abbastanza facile da usare e 
non devi preoccuparti di brevetti o altre cose (a detta dell'autore della 
libreria, infatti, quella e' stata la parte che ha richiesto piu' tempo).

facendo" utilizzando "catene" di codici) ed e', purtroppo, brevettata.
Esatto, dalla Unisys, per la quale Welch lavorava.

Esatto, dalla Unisys, per la quale Welch lavorava.
A quel tempo Welch lavorava per la Sperry e successivamente (quando ha 
pubblicato il suo articolo, che e' ovviamente successivo al brevetto) per la 
Digital.

Digital.
Ma il brevetto credo sia della Unisys, o no ?


Purtroppo ora si'... e per usare LZW bisogna pagare... :-(