[C] algoritmo per comprimere un file

[tecno789]

Salve a tutti, vorrei poter fare un programma che dato in input un file mi possa dare in output un file compresso, cioè che pesa meno in termini di byte, come posso realizzare ciò in C??? Premetto che sto cercando di capire il RLE ma proprio non so come metterlo in pratica, penso che voi mi possiate dare una mano consistente!

grazie

[demos88]

Beh l'argomento "compressione dei dati" è un campo di ricerca molto attivo dell'informatica. Ci sono tantissimi algoritmi diversi (molti proprietari).
L'RLE è uno dei più semplici, ma funziona bene solo in alcune circostanze.
RLE non fa altro che raggruppare unità di dati consecutive uguali, in altre parole, se trasmetto la sequenza:
AAAAAAAAAABBBCCCCCCCCCCCCCCCCAAAABBACCCC (40 carattewri ASCII8 => 60bytes)
la versione compressa sarà
10A3B16C4A2B1A4C (14 bytes: scrivo in un byte quante volte si ripete consecutivamente uno stesso valore, il byte successivo contiene il dato)

E' facile notare che se in media le sequenze contigue sono più corte di 2 elementi, la compressione è controproducente (e questo capita praticamente sempre nei file binari). L'RLE risulta più efficace nella compressione di immagini con numero di colori ridotto, per esempio è usata per i fax che trasmettono in bianco e nero documenti che molto spesso contengono lunghe sequenze di pixel bianchi (ma anche nei fax, questa compressione è combinata con altre)

Potresti provare a vedere l'Huffman, è intuitivo (a patto di conoscere come funzionano gli alberi binari). Comunque c'è molta teoria dietro tutto questo, non è semplice :)
Se ti serve una compressione "professionale" magari trovi qualche libreria già free in internet...

[ndakota]

In fondo a questa pagina puoi scaricare una versione in C.

http://michael.dipperstein.com/rle/index.html

Edit: Ho risposto in questo modo ma in realtà non ho capito se vuoi un codice da usare effettivamente o vuoi capire come funziona e arrivare a scrivere il codice da solo :stordita:

[tecno789]

Beh l'argomento "compressione dei dati" è un campo di ricerca molto attivo dell'informatica. Ci sono tantissimi algoritmi diversi (molti proprietari).
L'RLE è uno dei più semplici, ma funziona bene solo in alcune circostanze.
RLE non fa altro che raggruppare unità di dati consecutive uguali, in altre parole, se trasmetto la sequenza:
AAAAAAAAAABBBCCCCCCCCCCCCCCCCAAAABBACCCC (40 carattewri ASCII8 => 60bytes)
la versione compressa sarà
10A3B16C4A2B1A4C (14 bytes: scrivo in un byte quante volte si ripete consecutivamente uno stesso valore, il byte successivo contiene il dato)

E' facile notare che se in media le sequenze contigue sono più corte di 2 elementi, la compressione è controproducente (e questo capita praticamente sempre nei file binari). L'RLE risulta più efficace nella compressione di immagini con numero di colori ridotto, per esempio è usata per i fax che trasmettono in bianco e nero documenti che molto spesso contengono lunghe sequenze di pixel bianchi (ma anche nei fax, questa compressione è combinata con altre)

Potresti provare a vedere l'Huffman, è intuitivo (a patto di conoscere come funzionano gli alberi binari). Comunque c'è molta teoria dietro tutto questo, non è semplice :)
Se ti serve una compressione "professionale" magari trovi qualche libreria già free in internet...

grazie mille ottima spiegazione, si infatti c'è molta teoria, io ne volevo fare uno per poter vedere se "funzionava", nel senso vedere se il file in output è più leggero di quello in ingresso.
In fondo a questa pagina puoi scaricare una versione in C.

http://michael.dipperstein.com/rle/index.html

Edit: Ho risposto in questo modo ma in realtà non ho capito se vuoi un codice da usare effettivamente o vuoi capire come funziona e arrivare a scrivere il codice da solo :stordita:

no voglio scrivermelo da solo ovviamente, altrimenti prendo winRar :D

[Mirkolo]

La compressione RLE è forse la più semplice ed intuitiva, quindi parti pure con quella per farti le ossa :) L'implementazione più famosa penso sia la PackedBits di Apple, usata in molti campi. Ad esempio, il tanto famoso formato PSD di Adobe salva le righe delle immagini (solo con profondità a 8bit però) in PackedBits. L'algoritmo di decompressione funziona così: se il primo byte letto L è minore di 128, i successivi L+1 byte vengono copiati in output così come sono, mentre se è maggiore di 128 il byte successivo viene ripetuto in uscita 257-L volte. Questo permette di tranne vantaggio dalla sequenza di byte ripetuti, ma al tempo stesso non raddoppiare la dimensione del file compresso se i byte sono tutti diversi tra loro. Sulla base di queste regole puoi ricavarti il compressore. Da notare che non esiste un modo univoco di comprimere, ma facendo un paio di considerazioni puoi arrivare a capire quale è quello più efficiente.

Viene usato da Adobe nei PSD e in altri formati grafici proprio perchè certe grafiche (es. uno screenshoot del tuo desktop) hanno molti pixel vicini dello stesso colore. Ma se provi a comprimerci una foto otterrai risultati insoddisfacenti. In quei casi, se si vuol restare nel campo loseless, bisogna creare algoritmi ad hoc basati sulla natura del segnale (vedi flac per l'audio).

Gli altri sistemi sono basati generalmente su due fatti: 1) la codifica di più byte assieme tramite dizionari, 2) la codifica entropica. Quest'ultima si basa sul fatto che, ad esempio, non tutti i simboli saranno presenti con la stessa frequenza sulla tua sorgente. Quindi, anzichè associare lo stesso numeri di bit a tutti i simboli, conviene associare codifiche più corte a quelli più probabili, e codifiche più lunghe a quelli meno. Cerca Huffman su google per avere qualche esempio o una miglior spiegazione. Se poi l'argomento ti appassiona leggiti qualcosa sui codificatori aritmetici, che sono anche piuttosto semplici da capire e più efficienti di Huffman.

Anni fa avevo provato a partecipare allo Hutter Prize, una specie di gara dove ti pagavano in proporzione a quanto riuscivi a migliorare la compressione di 100mb di Wikipedia. Ho imparato molte cose, ma è stato un bagno di sangue avvicinarsi ai risultati degli altri partecipanti :)

[tecno789]

La compressione RLE è forse la più semplice ed intuitiva, quindi parti pure con quella per farti le ossa :) L'implementazione più famosa penso sia la PackedBits di Apple, usata in molti campi. Ad esempio, il tanto famoso formato PSD di Adobe salva le righe delle immagini (solo con profondità a 8bit però) in PackedBits. L'algoritmo di decompressione funziona così: se il primo byte letto L è minore di 128, i successivi L+1 byte vengono copiati in output così come sono, mentre se è maggiore di 128 il byte successivo viene ripetuto in uscita 257-L volte. Questo permette di tranne vantaggio dalla sequenza di byte ripetuti, ma al tempo stesso non raddoppiare la dimensione del file compresso se i byte sono tutti diversi tra loro. Sulla base di queste regole puoi ricavarti il compressore. Da notare che non esiste un modo univoco di comprimere, ma facendo un paio di considerazioni puoi arrivare a capire quale è quello più efficiente.

Viene usato da Adobe nei PSD e in altri formati grafici proprio perchè certe grafiche (es. uno screenshoot del tuo desktop) hanno molti pixel vicini dello stesso colore. Ma se provi a comprimerci una foto otterrai risultati insoddisfacenti. In quei casi, se si vuol restare nel campo loseless, bisogna creare algoritmi ad hoc basati sulla natura del segnale (vedi flac per l'audio).

Gli altri sistemi sono basati generalmente su due fatti: 1) la codifica di più byte assieme tramite dizionari, 2) la codifica entropica. Quest'ultima si basa sul fatto che, ad esempio, non tutti i simboli saranno presenti con la stessa frequenza sulla tua sorgente. Quindi, anzichè associare lo stesso numeri di bit a tutti i simboli, conviene associare codifiche più corte a quelli più probabili, e codifiche più lunghe a quelli meno. Cerca Huffman su google per avere qualche esempio o una miglior spiegazione. Se poi l'argomento ti appassiona leggiti qualcosa sui codificatori aritmetici, che sono anche piuttosto semplici da capire e più efficienti di Huffman.

Anni fa avevo provato a partecipare allo Hutter Prize, una specie di gara dove ti pagavano in proporzione a quanto riuscivi a migliorare la compressione di 100mb di Wikipedia. Ho imparato molte cose, ma è stato un bagno di sangue avvicinarsi ai risultati degli altri partecipanti :)

wow che spiegazione grazie!!!!

si ho letto anche io che wikipedia organizzava gare del genere, ma ovviamente non ho le skills :) adatte...