Newsgroup: it.comp.java
Titolo: OT semplice compressione

scusate se sono OT..
ma sicome intendevo usare questo linguaggio per farlo (se possibile)
vorrei comprimere una stringa contenente solo numeri punti e virgole tipo:
2588.5,85425,0525,4555.5566,268.56,546546.64697,
 non voglio usare moduli ecc.. (devo poi magari fare l'inverso con altri
linguaggi)
vorrei proprio un algoritmo per comprimere/decomprimere e nello stesso tempo
magari nascondere i dati
non cerco cose complicate!
Qualcuno ha idea di come si potrebbe fare una cosa simile?
grazie
*********

Il meccanismo piň semplice č il run-lenght encoding. Per esempio avendo 100
volte il numero 10 basta scrivere 100 poi 10 invece di ripeterlo. E' un
meccanismo che funziona bene con le immagini (le BPM supportano questo modo
di compressione) ma male con il resto. Alternativamente puoi usare (per il
testo) una lookup table con riferimenti alle parole piů usate (es. invece di
scrivere "the" mille volte in un testo gli associ un valore e scrivi solo
quello).
Per la crittazione ci sono vari metodi, matematicamente complessi. Comunque
sono quasi tutti basati su applicazioni biettive (anche i nazi facevano
cosě!) troppo lunghe da spiegare qui: se hai bisogno fammelo sapere.
--
ByEZ,
MindFlavor ( 
mindflav...@hotmail.com
 )
URL: 
http://web.tiscalinet.it/mindflavor

 sono quasi tutti basati su applicazioni biettive
Mica tutti, prendi la crypt() di Unix...
Massimo



vediamo se posso esserti d'aiuto
quello di cui hai bisogno e' un algoritmo di codifica
per una sorgente discreta che emette questi simboli
{"0","1","2","3","4","5","6","7","8","9",".",","}
per realizzare il codificatore ottimo bisognerebbe 
conoscere le caratteristiche statistiche della sorgente,
ma dato che non hai fornito indicazioni al riguardo
ipotizzo che i simboli siano equiprobabili e che
la sorgente non abbia memoria (anche perche' 
se avesse memoria sarebbe un casino)
sono 12 simboli, quindi la probabilita' 
di emissione di un simbolo e' p = 1/12 
si puo' calcolare l'entropia della sorgente
H = p1 * log2 (1/p1) + ... + p12 * log2 (1/p12) = log2 (1/p) = 
= log10 (1/p) / log10 (2) = 3.585 bit di informazione / simbolo
il codificatore ottimo ha efficienza 
n = 1 bit di informazione / bit emesso 
e quindi dal teorema della codifica di sorgente 
segue che la lunghezza media del codice ottimo e' 
L = H / n = 3.585 bit 
questo e' il limite a cui si puo' arrivare!
(nota che 2^3.585 = 12)
non esiste un algoritmo per determinare 
il codificatore quindi bisogna arrangiarsi
la soluzione banale e' questa :
"0" 	0000
"1" 	0001
"2"	0010
"3"	0011
"4"	0100
"5"	0101
"6"	0110
"7"	0111
"8"	1000
"9"	1001
"."	1010
","	1011
la lunghezza media del codice e' L' = 4 bit
l'efficienza del codice e'
n' = H / L' = 0.896 bit di informazione / bit emesso = 89.6%
un'altra soluzione e' questa :
"0" 	000
"1" 	001
"2"	010
"3"	011
"4"	100
"5"	101
"6"	110
"7"	11100
"8"	11101
"9"	11110
"."	111110
","	111111
la lunghezza media del codice e' ancora
L'' = (3 * 7 + 5 * 3 + 6 * 2) /12 = 4 bit
l'efficienza del codice e' ancora
n'' = 0.896 bit di informazione / bit emesso = 89.6%
le due soluzioni sono quindi equivalenti, la prima 
pero' e' sicuramente piu' semplice da realizzare :)
per concludere dovresti provare a vedere 
come si comporta un comune zippatore ;)
se invece devi proprio implementarti un algoritmo
allora per poter fare di meglio bisogna usare una
codifica piu' complessa che alla fine dovrebbe
assomigliare all'algoritmo usato nello zip
a graaandi linee dovresti fare cosi' :
1) codifichi ogni simbolo su 4 bit
e compatti le sequenze di bit
l'algoritmo prende in ingresso un flusso di bit,
individua sequenze mai viste, le rappresenta
come unione di una sequenza nota piu' un bit
di innovazione e le memorizza in un code book.
alcune sottosequenze diventano inutili dopo un 
po' e possono essere eliminate dal code book.
in uscita viene emesso il numero della sequenza 
piu' il bit di innovazione. un algoritmo simile pero'
diventa conveniente su lunghe sequenze di bit.  
2) compatti le sequenze di caratteri numerici
l'algoritmo prende in ingresso un flusso di caratteri
individua sequenze mai viste, le rappresenta
come unione di una sequenza nota piu' un carattere
di innovazione e le memorizza in un code book. 
alcune sottosequenze diventano inutili dopo un 
po' e possono essere eliminate dal code book.
in uscita viene emesso il numero della sequenza 
piu' il carattere di innovazione. 
(non so dirti di piu' di questo)
naturalmente dopo aver scritto il tuo codificatore
verifica se la lunghezza media del codice e' 
3.585 cosi' saprai se hai ragiunto l'ottimo ;)
ciao_O
 
http://digilander.iol.it/schiele

 assomigliare all'algoritmo usato nello zip
Una banale codifica utilizzando i codici di Huffman, magari adattiva così fà più
figo? :) Se non mi inganno garantisce il codice più corto possibile.
Ciao,
 Stefano
----------
"X WindowSSS, teSSSoro mio... lo odieremo per SSSempre"
Bill Gollum
----------

figo? :) Se non mi inganno garantisce il codice più corto possibile.
posto che avevo un esame attinente il giorno 
seguente da cui la mia articolata risposta...
non conosco in modo approfondito l'argomento
ma penso che l'algoritmo usato nello zip non
sia quello di Huffman (che non e' adattativo)
ma bensi' quello di Lempel - Ziv che e' adattativo
cioe' non richiede di conoscere le caratteristiche 
statistiche della sorgente (Huffman invece si
basa proprio sul fatto di conoscere la probabilita'
dei simboli). Naturalmente questo e' quello che
dicono i miei appunti (a dir la verita' sono appunti
di un mio amico perche' la lezione si tenne a mia
insaputa il giorno 3 gennaio 2000, cioe' quando
io pensavo di essere ancora in vacanza).
la codifica di Lempel - Ziv dovrebbe essere
la migliore per sorgenti di cui non si sa nulla
e soprattutto se la sorgente ha memoria.
dato che mi diverto con queste cose non mi 
dispiacerebbe provare a scrivermi un codificatore 
ma non ho molto tempo per farlo quindi provo a 
lanciare l'idea a tutto il ng...
no! fermi...
posate quei pomodori...
ciao_)
http://digilander.iol.it/schiele

 lanciare l'idea a tutto il ng...
SSSSST! Poi Castagna ti sente... :))


 seguente da cui la mia articolata risposta...
Teoria dell' Informazione ? :)
Simone.
--------------------------------------------------------------
....e Dio disse : "pkunzip universo.zip"
ICQ: 19598133
Webmaster di
 
www.drfalken.com
 
www.pas-os.com
--------------------------------------------------------------

Teoria dell' Informazione ? :)
Comunicazioni Elettriche
(comprende in piccola parte la teoria dell'informazione)
ciao_O
http://digilander.iol.it/schiele

 wrote in message
3a8bd521...@news.tiscalinet.it...
