Newsgroup: it.comp.lang.c
Titolo: Implementazione ZIP

Ciao a tutti.
Sto cercando un'implementazione facile facile dell'algoritmo utile alla 
compressione/decompressione dei dati
Naturalmente ho cercato su internet, ma quello che ho trovato è stato solo 
codice scritto in altri linguaggi o codice non di immediata compressione.
Spero possiate aiutarmi
Grazie anticipatamente
Roberto

 Spero possiate aiutarmi
Potresti guardare i sorgenti della libreria libz
E.

 Potresti guardare i sorgenti della libreria libz
si, ma spervao in qualcosa di semplice dato che non posso rifarmi a chissà 
quante librerie.
Tutto questo perchè devo effettuare la compressione in un sensore e non ho 
chissà quanto spazio in
memoria (fissa e ram).
Devo anche ridurre all'osso il costo computazionale dato che il sensore 
lavora a 7Mhz e dato che la potenza mi serve per ben altre operazioni.
Quindi avrei bisogno dell'algoritmo "pulito pulito" senza chissà quali 
fronzoli e opzioni.
Mi andrebbe bene anche un algoritmo di compressione simile allao zip.
Tempo fa avevo sviluppato l'lzw in matlab (lo zip se non sbaglio usa LZ77).
Spero di trovare qualcosa già scritta prima di dover creare una mia 
implementazione 

 fronzoli e opzioni.
...mi sa che la cosa ti richiederà un po' di tempo. Ma devi fare la 
compressione o solo la decompressione? Perché la decompressione dovrebbe 
essere molto più facile e veloce...
E.

 ha scritto nel messaggio

ma cosa devi comprimere?
perche' ci sono diversi algoritmi di compressione leggeri (che
chiaramente comprimono meno).
e poi dipende se puoi comprimere e poi spedire, oppure se devi
comprimere uno stream.
ci sono algoritmi che usano un dizionario, altri che non lo usano (i
primi di solito comprimono di piu').
devi fare una compressione lossless o puoi farne una lossy?
esempi:
- run length encoding
- variable length encoding
- Huffman
- Shannon-Fano
- LZ77
- LZ78
- LZW (occhio che questo era brevettato, ma forse il brevetto e'
scaduto)
i primi 4 non usano il dizionario.
lo zip usa LZ77 + Huffman (o Shannon-Fano, non ricordo). anche lo
gzip.
il jpg usa (dopo la compressione tramite trasformata discreta del
coseno) Huffman per l'encoding su file.
pero', come ho detto prima, cosa conviene fare dipende dal contenuto
da comprimere, dalla lunghezza,...
Ciao Jack

 essere molto più facile e veloce...
Nel caso la decompressione abbia vincoli di velocità, si può ricorrere a
LZO, una variante del Lempel-Ziv-Welch (che come qualcuno ha detto,
giustamente, è sotto brevetto e ha causato problemi, ad esempio, nell'uso
commerciale del formato .gif). Si tenga presente che Huffman, di solito (e
in generale gli algoritmi non basati su dizionario, ma su alberi) comprime
molto meno del LZ (per un flusso di dati da 8 bit, il limite massimo di
compressione è di 1 a 8, quindi del 87,5%). 
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 compressione è di 1 a 8, quindi del 87,5%).
ma quelli basati su dizionario normalmente sono piu' pesanti e lenti
(afaik). oppure no?
Ciao Jack

devi fare una compressione lossless o puoi farne una lossy?
assolutamente senza perdita
Colgo l'occasione di questo post per ringraziarvi tutti della collaborazione

 compressione o solo la decompressione?
Compressione in fase di spedizione e decompressione in ricezione 

 comporta un costo energetico)
Penso che potresti farti un algoritmo apposta. Un float è memorizzato 
come mantissa/esponente. Mi immagino che i bit della mantissa siano 
sostanzialmente casuali. L'esponente invece è tipicamente un numero 
vicino ad 1 e potresti quindi comprimerlo... Non vedo altra ridondanza 
in un float...
E.

 (afaik). oppure no?
Che vuol dire "pesante" in questo contesto? Che io sappia, non sono più
lenti di altri algoritmi, specie se si basano su strutture dati "veloci"
come le hash map. In ogni caso, siamo abbondantemente off-topic. Da qui
non posso impostare il follow-up, ma sarebbe bene portarlo su
it.comp.programmare.


 in un float...
Ho detto una stupidata perché il singolo float non lo comprimi molto, ma 
probabilmente il tuo stream contiene molti float uguali tra loro (magari 
molto spesso zero)... Forse un albero di Huffman a 32 bit?
E.

 molto spesso zero)... Forse un albero di Huffman a 32 bit?
Lascia perdere... un albero di Huffman a 32 bit occuperebbe 4 Giga
E.

 molto spesso zero)... Forse un albero di Huffman a 32 bit?
L'algoritmo di Huffman ha una controindicazione: va spedito anche
l'albero, in testa ai dati compressi, pena l'impossibilità di
decomprimere. L'algoritmo LZ, invece, non ha bisogno di metastrutture nel
flusso compresso, può semplicemente risalire al flusso originale,
ricostruendo il dizionario a mano a mano che legge i dati compressi.


 Lascia perdere... un albero di Huffman a 32 bit occuperebbe 4 Giga
LOL
Grazie comunque per il ragionamento 

 Lascia perdere... un albero di Huffman a 32 bit occuperebbe 4 Giga
In che senso?
L'albero occupa tanto spazio, quanti sono i dati con cui lo riempi.


 Grazie comunque per il ragionamento
Non è detto che un albero di Huffman occupi tanto spazio, dipende dal
flusso da comprimere. E' praticamente impossibile che un albero di Huffman
arrivi a tanta occupazione di spazio. 


 
TinyOS?
-- 
"Le opinioni dei fanatici prescindono dai fatti"
python -c "print 'bG9ybWF5bmFAZ21haWwuY29t'.decode('base64')"

 decomprimere. 
Sì, è vero...
E.

 TinyOS?
Oh yes! 

 Oh yes!
Ci ho lavorato un bel po' per la mia tesi...È molto carino, ma ha un 
sacco di limitazioni, in particolare non puoi allocare memoria.
Per pura curiosità, su che piattaforma lavori?È un progetto accademico o 
commerciale?
Ciao


 Ciao
Ahi! Mi dai una brutta notizia!
Non sapevo che non si potesse allocare memoria (penso ti riferisca a quella 
dinamica)
Anch'io ci sto lavorando per la tesi: ho implementato un protocollo di 
comunicazione per reti ibride che usano sensori Micaz e una board un po' più 
potente (Stargate).
Entra in gioco anche il problema del risparmio energetico e quindi sto 
utilizzando un algoritmo intelligente basato sull'utilizzo di Support vector 
machines al fine di effettuare delle predizioni sui dati che quindi evitino 
l'invio degli stessi.
Il protocollo funziona benissimo utilizzando una semplice predizione 
effettuata con una regressione lineare. Adesso devo utilizzare la storia 
delle SVM, ma finora ho provato tutto su Matlab.
Ora tu mi dici che non è possibile allocare memoria...e io come le 
implemento le SVM in nesC? :-/
Una soluzione si troverà...spero!
Io studio a Palermo (e sono di Palermo). Tu dove hai studiato?
(forse è meglio che proseguiamo in privato : gioeroby___ aT_____l* i* b* e* 
r* o . i*t) 

 implemento le SVM in nesC? :-/
Non so cosa sia TinyOS e cosa sia nesC. Ma se non hai la memoria 
dinamica quello che puoi fare è farti il tuo gestore di memoria 
personale... sostanzialmente definisci tu la malloc in modo che operi su 
un buffer statico.
E.

Nel mezzo del cammin di nostra vita, mi ritrovai con ?manu* che diceva:

Infatti...
TinyOS (
www.tinyos.net
) è un OS per sensori wireless, ancora in fase di 
sviluppo e con molte limitazioni(dettate soprattutto dalle limitate 
prestazioni di questi sensori, nel mio caso erano avr a 8 bit e 4 mhz di 
clock). NesC è il dialetto del C da utilizzare con TinyOS


 Ahi! Mi dai una brutta notizia!
Mi sa che te ne devo dare un'altra: se mi ricordo bene l'utilizzo dei 
float era altamente sconsigliato, perchè non sono supportati nativamente 
dall'hardware, e quindi portavano a un netto peggioramento delle 
prestazioni (velocità di calcolo, consumo di batteria). Ci sono diversi 
topic nella ml di TinyOS, magari controlla lì che qualcuno ha postato 
delle soluzioni efficaci


 statico.
uhm...non so niente di questo metodo per l'allocazione della memoria. puoi 
suggerirmi qualche risorsa?
Grazie mille per il prezioso contributo! 

 delle soluzioni efficaci
ah si...
sta storia dei float mi è nota.
In effetti sono simulati ed è per questo che stiamo studiando delle tecniche 
per limitare l'uso dei calcoli in float.
Comunque quello che ci preme maggiormente è la riduzione dei messaggi 
inviati dato che, almeno in teoria, non c'è nulla che consumi più della 
trasmissione/ricezione (l'obiettivo è quello dtenere spenta la radio e 
accenderla solo quando è necessario)
Pertanto, se poi ci sono calcoli in float....amen :-) 

 Grazie mille per il prezioso contributo!
Quello che ti suggeriva manu (credo) e' di avere un bufferone statico
che rappresenta in qualche modo la tua heap e definirti delle funzioni
ad-hoc ( malloc e free ) per gestire questo bufferone. Purtroppo non
e' una cosa banale specialmente se c'e' una forte frammentazione del
buffer...
Daniele

suggerirmi qualche risorsa?
Be', non c'è molto da sapere: preallochi una zona di memoria, creando
staticamente un array e poi dirotti le chiamate a malloc su una tua
myMalloc() che prende spazio dall'array. Spazio che viene restituito
con una myFree(). Ovviamente dovrai tenere traccia dei blocchi
allocati, perché sia myMalloc() che myFree() hanno bisogno di
conoscere quale e quanta memoria è allocata. 

 suggerirmi qualche risorsa?
Devi fare uno heap. Hai a disposizione una zona di memoria, potrebbe essere:
unsigned char arena[ARENA_SIZE];
e devi implementare le funzioni malloc e free, per gestire questa 
memoria. Un metodo molto semplice (e molto elegante) è quello di 
costruire una lista degli intervalli inutilizzati di memoria. E' molto 
elegante perché ti permette di utilizzare la memoria inutilizzata per 
mantenere informazioni sull'occupazione di memoria.
Per implementare malloc devi scorrere la lista degli intervalli 
inutilizzati finché non trovi un intervallo abbastanza grande per 
contenere la tua richiesta.
A quel punto togli l'intervallo (o parte di esso) dalla lista degli 
intervalli inutilizzati, scrivi la dimensione della memoria richiesta 
all'inizio dello spazio libero e restituisci il puntatore alla locazione 
di memoria successiva.
Per implementare free basta che vai a leggere la dimensione 
dell'intervallo di memoria riservato (si trova immediatamente prima del 
puntatore) e inserisci quell'intervallo di memoria nella lista degli 
intervalli inutilizzati. Sarà anche bene mantenere ordinati gli 
intervalli, così ti accorgi se due intervalli combaciano e li puoi riunire.
E.

 Grazie mille per il prezioso contributo! 
Qui puoi trovare una realizzazione per un driver del kernel di Minix 
(dove non è disponibile la malloc/free).  Viene allocato un buffer 
statico che, dopo opportuna inizializzazione con init_buff(), è usato 
con alloc_buff() e free_buff() per allocare/liberare porzioni di 
qualsiasi dimensione. Attenzione che a lungo andare, come ti hanno già 
scritto. potrebbe frammentarsi a tal punto da non trovare un blocco 
della dimensione richiesta.
http://giovanni.homelinux.net/development/index.html
http://giovanni.homelinux.net/development/dpeth/netbuff.c
Ciao
Giovanni
-- 
   A computer is like an air conditioner,
   it stops working when you open Windows.
   Registered Linux user #337974  < 
http://giovanni.homelinux.net/
 >

 richiesta.
non sembra un cosa banale...
magari cerco qualche codice d'esempio dato che credo d'aver capito solo la 
teoria..
Grazie, davvero, a tutti voi 

 
Il file che ho linkato è derivato da un esempio trovato sulla prima 
versione del K&R.


 decomprimere. 
Per la precisione, esiste anche la versione dinamica (o adattiva)
di Huffman in cui l'albero viene costruito via via che i dati
partono e arrivano e che quindi non richiede di inviare nulla prima.
Pero' in questo caso direi che trattandosi di numeri float
forse uno studio preliminare della distribuzione dei dati
potrebbe giovare ed indicare che metodo di compressione scegliere.
Se i numeri sono praticamente a caso allora tanto vale risparmiare
la batteria del sensore evitando inutili calcoli.
Trattandosi poi di valori numerici uno potrebbe inventarsi
dei metodi ad-hoc, che magari permettono una compressione non
ottimale, ma sono facili da implementare e leggeri come calcoli.
Faccio un esempio scemo (in mancanza di maggiori informazioni).
Se il sensore dovesse inviare una caterva di
rilevazioni di temperatura, e' verosimile che da una all'altra
ci sia uno scarto minimo, quindi  basterebbe codificare un valore
ogni tot e poi solo gli incrementi, addirittura con una banale
codifica RLE, molto piu' facile da implementare di zippi vari.
ciao,
g.

 codifica RLE, molto piu' facile da implementare di zippi vari.
a tal proposito sto utilizzando le support vector machines.
Invece di inviare la caterva di temperature invio solo un insieme 
rappresentativo (i support vector)
In questo modo dispongo anche di una modellazione dei dati che mi consentono 
quindi di predire il dato sensoriale e quindi evitare l'eventuale 
spedizione.
Quello che devo implementare (in nesC) è proprio la suppor vector machine.
Grazie ancora