Newsgroup: it.scienza.informatica
Titolo: Compressione dati, com'è possibile ?



C'è qualcuno che mi sa spiegare, anche solo in linea teorica, com'è
possibile comprimere i dati ?

Mi spiego meglio, non riesco a capire come si riesca a memorizzare
la stessa quantità di informazione (non solo la quantità
ma anche la qualità: i file compressi con winzip,per fare un es,
una volta decompressi sono identici all'originale...per fortuna) in uno
spazio minore.

E ancora più stupefacente è il fatto che da un file compresso
si possa risalire all'originale, è come se si andasse contro a una
legge fondamentale della fisica, quella della conservazione dell'energia,
che in questo caso sarebbe la "conservazione dell'informazione".

In sintesi : non mi spiego come si possa estrarre dell'informazione
dal "nulla".

Grazie a chiunque voglia rispondermi.

--

Ludovico: 
Su...@tin.it


Web page: 
http://members.xoom.com/Ludos/index.html


Da dove proviene l'ordine e la bellezza che vediamo nel mondo ?

Isaac Newton


 


...



Be' come dici tu la "conservazione dell'informazione" c'e'. Non e' che si
tolgono informazioni ma le si memorizzano meglio. Ti faccio un esempio: per
memorizzare un testo si usa solitamente un byte (8bit) per carattere. Se tu
avvessi un testo con una distribuzione omogenea di tutti i possibili
caratteri (256) sarebbe perfetto. In un testo normale pero' alcuni caratteri
vengono usati di piu' e altri di meno il che permette, una volta analizzato
il file, di memorizzarli in modo piu' compatto: i caratteri piu' usati
vengono scritti con meno bit e quelli meno usati con piu' bit.
Tutto questo richiede tempo (per analizzare il file) e la decodifica
dipende dal file (non e' generalizzata) e dunque i file devono essere
decompressi prima di essere usati.
Ti faccio un esempio molto semplice:
- prendiamo un alfabeto con quattro lettere codificate nel seguente modo
	A	00
	B	01
	C	10
	D	11
- la frase AAAAAABBCD verrebbe codificata
	00 00 00 00 00 00 01 01 10 11
  per un totale di 20 bit
- analizzando il file si potrebbe trovare un'altra codifica
	A	0
	B	10
	C	110
	D	111
 
- nuova codifica
	0 0 0 0 0 0 10 10 110 111
  per un totale di 16 bit
  nota che benche' i caratteri siano codificati con lunghezze varibili la
decodifica puo' essere fatta in un solo modo ricreando la stringa originale.
		Matteo Corti
 
matteo...@acm.org

minore.
DIpende dalla ridondanza delle informazioni. Ad esempio, un file
composto da un milione di 1 occupa circa 1megabyte. Ma la stessa
informazione e' trasportata dalla frase "un milione di 1" che,
visibilmente, occupa molto meno spazio. Questo in quanto il file di
partenza era molto ridondante. E' chiaro che l'esempio che ho proposto
e' inverosimile, ma ne esistono altri molto piu' vicini alla realta'.
Considera i messaggi di questo newsgroup. Se eliminassimo l'ultima
lettera di tutte le parole (escluse, magari, la parole di una sola
lettera ;)) ciascuno di noi sarebbe in grado di comprendere ugualmente
il testo, ossia di ripristinare la lettera mancante: lo spazio
occupato diminuirebbe, mentre l'informazione trasmessa resterebbe
uguale; e' questo il principio su cui si basano le compressioni *SENZA
PERDITA DI DATI*.
Ciao,
      __
     (__
      __)tefano.



Ti ringrazio per l'esempio molto chiaro che mi hai fatto, adesso ho capito.
Solo che ora mi vengono in mente altri problemi !!

Ad esempio, restando sul tuo esempio:

Se ci fosse una quinta lettera la E ad esempio, come la si codificherebbe
? ho provato ma nessuna delle combinazioni a 4 bit (da 8 a 15 in binario)
funziona. Quando dico non funziona significa che la quadripletta può
essere interpretata in diversi modi (con quello che la precede e che viene
eventualmente dopo) in relazione alla codifica di A, B, C, D del tuo esempio.

Mi sono fermato a 4 bit perchè mi è sembrato che anche
andando avanti ci si sarebbe ritrovati con lo stesso problema (magari mi
sbaglio, spero...) [vedi tabella sotto]

Questo significa che nel caso di 5 lettere si dovrebbe adottare un'altra
codifica sin dall'inizio ? e c'è un modo standard (o delle regole)
per associare i 256 caratteri a dei bit (oltre chiaramente alla codifica
a 8 bit..) come hai fatto tu per A,B,C,D ? (o hai tirato a caso provando
a vedere se potevano sorgere ambiguità nella tua codifica ? [non
credo]).

Inoltre si può continuare a scrivere la tabella qui sotto ? (voglio
capire se c'è qualche legge nota)

n° bit per carattere:                  
1        2       
3        4       
5...

n° max di caratteri codificabili:   1       
1        2      
(0)       ?...

nel tuo es corrispondeva a :       A       
B     C,D     Ø     
(E)

 

Grazie ancora, Ludovico




-- 
______________________________________________________________________________
Matteo Corti			e-mail:
Scheuchzerstrasse 79		
matteo...@acm.org
8006 Zuerich		
Switzerland
				Home page (with PGP key):
phone: ++41 1 3620934		
http://www.vis.inf.ethz.ch/~mcorti
______________________________________________________________________________

       __)tefano.
-- 
# Giorgio Vecchiocattivi.
# Dip. Informatica, Universitá di Pisa. 

Scusa Ludovico, potresti evitare di mandare i tuoi post in HTML?
(guarda tra le impostazioni di netscape, c'e'` preferences->mail&group->
messages->By defualut send rich text, disabilitalo grazie)
La cosa bella e' che SHANNON (che si e' inventato tutto) ha dimostrato
che c'e' un limite alla compressione, e ha dato un algoritmo per arrivarci.
Quindi esiste un algoritmo meglio del quale non si puo' fare. Sono ammesse
solo variazioni sul tema.
Saluti.


c'e' nessun algoritmo che possa "intuire" la lettera mancante.
Dunque tu pensi che sia necessario avere un'anima?
Io sono di quelli che pensano che il cervello sia una macchina (un
automa a stati finiti, visto che i neuroni sono in numero finito)
e anche se nel suo funzionamento ci fosse qualcosa di non
meccanicistico trovo difficile credere che possediamo dei
"modi di pensiero" che non ricadano nella tesi di Church.
Quindi se riesco a rimettere a posto le ultime lettere senza errori
vuol dire che sto usando un algoritmo, non ti pare? 
Oltre, naturalmente, ad una grossa base di conoscenze sull'italiano
e sul mondo - ma questo vale per qualunque algoritmo di compressione
e in generale per qualunque codice: bisogna ad esempio sapere che
significa "milione" in "un milione di 1" o quantomeno avere
informazioni sull'algoritmo che e' stato usato per la codifica.
Tra parentesi, l'esempio era stato scelto meglio di quanto tu
pensi: mi pare di ricordare (da antichi testi di teoria
dell'informazione) che gli esperimenti per stimare empiricamente
la ridondanza dei linguaggi umani venivano condotti proprio
cosi': presentando un testo una lettera per volta e contando quante
volte il "soggetto" riusciva a indovinare la lettera successiva.

Un bel di' Ludovico scrisse:
L> C'č qualcuno che mi sa spiegare, anche solo in linea teorica, com'č
L> possibile comprimere i dati ?
L> 
Oppure, un altro algoritmo rispetto a quello/i gia' spiegati, e' di
utilizzare un indice.
Se ad esempio vuoi comprimere dei testi in italiano, procurandoti
un indice di tutte le parole, puoi sostiutuire ad ogni parola un numero.
Se non ricordo male, il vocabolario della Zanichelli riporta 25000 voci...
fino a 65536 possiamo codificarle con soli 2 byte per parola! :-)
Ovviamente questo non e' un gran bel metodo, in generale, perche'
a) il codice da comprimere deve essere molto specifico
b) occorre avere un indice e, a meno di crearne uno standard, bisogna
passare in sieme alle infos compresse anche l'indice usato :-)
ciao!
-- 
"Passa abbastanza tempo a confermare il bisogno ed il bisogno sparira'",
prognosi di Peter
-- 
Emanuele Cesena
d.a.m...@iol.it
    occhio all'antispam NOSPAM!
http://www.geocities.com/SiliconValley/Grid/8879

c'e' nessun algoritmo che possa "intuire" la lettera mancante.
Chi ha mai parlato di algoritmi. Io dico solo che come esseri umani
riusciamo a dedurre da soli l'informazione mancante. In quanto in
partenza e' ridondante.
Ciao,
      __
     (__
      __)tefano.

On Fri, 8 Jan 1999, Stefano Crimě wrote:
    (Nota: si discute di un esempio di algoritmo di compressione basato
     sull'eliminazione del carattere finale di ogni parola)

Vecchiocattivi ha ragione. Si parla propriamente di algoritmi di 
compressione "lossless" qualdo dalla sequenza compressa e' possibile
ricostruire esattamente (ovvero bit per bit) la sequenza originale
mediante un algoritmo.
L'algoritmo citato all'inizio non e' di questo tipo (ad esempio non e'
garantito che un lettore possa ricostruire il "genere" dell'oggetto o
persona di cui si parla, mancando le vocali finali di ogni parola).
In questo senso l'algoritmo e' simile al JPEG per la compressione di
immagini: la compressione avviene a spese di un "fattore di qualita'",
ovvero la qualita' dell'immagine viene ridotta, presumibilmente in misura 
tale da non renderla irriconoscibile.
					l.f.
--------------------------------------------------------------------------
       -- )     Luca Fini                            Tel: +39 055 2752 307
 ___    |\      Osservatorio Astrofisico di Arcetri  Fax: +39 055 2752 292
/   |   | |\_   L.go E.Fermi, 5 +-----------------------------------------
(___|___//___)  50125 Firenze  /   WWW: 
http://www.arcetri.astro.it/~lfini
 (_)      (_)   Italia        / e-mail: 
lf...@arcetri.astro.it
-----------------------------+--------------------------------------------
                              In a world without fences - who needs GATES?

              
http://www.bigfoot.com/~d.dui/

 solo variazioni sul tema.
Questa non la sapevo... veramente interessante!
Dove posso reperirne la documentazione? 
(meglio sul web, ma non ho problemi ad andare a spulciare in biblioteca).
E la famigerata "compressione frattale" come rientra nel quadro?
saluti,
	Denis

passare in sieme alle infos compresse anche l'indice usato :-)
Un vocabolario italiano puň essere standardizzato: chi produce il programma
compressore produce anche il decompressore che ha all'interno lo stesso
vocabolario.
conp...@tin.it

 writes:

La compressione frattale prevede perdita di dati? se si non rientra nei
casi di shannon, se no ha le stesse limitazioni.
In rete non ho mai trovato nulla del genere (non e' che l'abbia cercata mai)
Su qualsiasi libro di teoria dell'informazione comunque sicuramente c'e'.
Ti faccio sapere.
Ciao.


 wrote:
: Dove posso reperirne la documentazione? 
: (meglio sul web, ma non ho problemi ad andare a spulciare in biblioteca).
: E la famigerata "compressione frattale" come rientra nel quadro?
e' una discreta compressione *lossy* per immagini, rispetto al suo
concorrente jpeg (anch'esso lossy) ha il vantaggio di poter essere "zoomato"
senza far risultare un'ingrandimento una collezione di pixels giganti.
la compressione infatti riesce in qualche modo a "interpolare"  cio' che
nell'immagine originale non c'era (ovviamente fino a un certo punto!!) dando
al tutto un'aspetto "naturale".
a riguardo, a livello introduttivo (non mi sono mai spinto oltre, non sono
certo un'esperto di compressione ;), ho trovato interessanti le faq di
comp.compression, che puoi trovare su 
rtfm.mit.edu
. tra l'altro spiega come
in origine la compressione frattale richiedesse un congruo "aiuto" da una
persona che doveva guidare il processo...
purtroppo l'atteggiamento di chi detiene i diritti degli algoritmi di
compressione e' sempre stato molto chiuso, e quindi quel tipo di
compressione non si e' diffuso.
correggetemi se ho sbagliato :)
g
-- 
remove "levaquesto" to reply by mail. UPR 
http://www.linux.it/ospiti/upr
At the source of every error which is blamed on the computer you will find
at least two human errors, including the error of blaming it on the computer.

solo variazioni sul tema.
Strano, credevo fosse stato Huffman, che era il cane di Shannon :-))
Ciao
							Max
Massimo Sanna                               \
E-mail: 
s78...@athena.polito.it
              \
 
fdr...@cclinf.polito.it
              \
ICQ:    25037591                               \
Home:   
http://www.poli.studenti.to.it/~m.sanna
 \	
-------------------------------------------------
"Vedi Bongo, questo e' il progresso! Hai tutto quello che non vuoi, 
 quando non ti serve". 
                                              A. De Curtis
                ------
               | STOP | <-  "CLICK HERE TO SHUTDOWN"
                ------

in questo caso sarebbe la "conservazione dell'informazione".
Come ti dicevo la quantita' di informazione e' l'unica cosa che si
conserva!!
Poi ci sono algoritmi che, tagliando via informazione (lossy), riescono a
comprimere ancora di piu' (suono e immagini).


vocabolario.
Con tutte le coniugazioni e tutti i tempi verbali? E le sigle?
E' solo un discorso teorico che serve allo scopo, ma nulla +.
Ciao
Christian Salvaneschi
Casarza Ligure, Genova, Italy
e.mail: 
cr...@geocities.com
   web: 
http://www.geocities.com/SiliconValley/Lakes/5139

E' solo un discorso teorico che serve allo scopo, ma nulla +.
Ho una lista di termini italiani che occupa 2817 Kb (che potrebbe essere
zippata a 607 kb per il trasporto) e contiene 245143 parole, più che
sufficienti come base. Poi si potrebbe inserire qualche codice per indicare
le parole che non sono incluse scritte per esteso.
conp...@tin.it


wrote:

Forse hai ragione. Inserendo per esteso le parole ignote si ha
comunque una notevole compressione. Magari facendo coincidere simboli
corti alle parole + usate (articoli, congiunzioni ecc...)


 Ti faccio sapere.
grazie!
saluti,
	Denis

teorema mostri la compressione massima in un caso generico o medio.
La compressione e' possibile, ripeto, ogni volta che i dati sono
ridondanti (e' proprio eliminando la ridondanza che si diminuisce la
mole dei dati). Tieni presente, comunque, che la ridondanza non e' in
se', cosa malvagia. Del resto la trasmissione attraverso canali
rumorosi e' possibile grazie ad essa: tutti i codici con proprieta' di
autocorrezione non fanno altro che aumentare la ridondanza.
Ciao,
      __
     (__
      __)tefano.

 automa a stati finiti, visto che i neuroni sono in numero finito)
se il nostro cervello fosse un'automa a stati finiti ci faremmo molto poco
(Ahime!), lo vedrei meglio come una Macchina di Turing almeno potremmo
calcolare tutte le funzioni calcolabili (tesi di Church) !
Comunque io non credo che il cervello umano possa essere paragonato ad una
macchina, non fosse per altro che ne sappiamo ancora pochissimo
Ciao, Marco 

(per es. LZW e derivati).
Mi spieghi come funziona la compressione LZW? Grazie.
conp...@tin.it

 macchina, non fosse per altro che ne sappiamo ancora pochissimo
Esiste un ottimo libro sull'argomento:
"Godel, Escher, Bach: un'Eterna Ghirlanda Brillante"
di Douglas R. Hofstadter
ed. Adelphi
Bellissimo!
-- 
I don't sleep cuz sleep is the cousin of death
(Afghan Whigs)

 se', cosa malvagia.  
Non trovo il nesso di ciò con il discorso...
saluti,
	Denis

vuol dire che sto usando un algoritmo, non ti pare?
Sebbene io possa essere d'accordo con te con tutto quello che dici sul
cervello, comunque effettivamente nell'esempio di Crimì la perdita dei dati
c'è, e l'algoritmo di cui tu parli non funziona di per certo.
Ad esempio, se tu mi scrivessi un messaggio anonimo con scritto
stronz   :-)
Probabilmente penserei che stai parlando della mia ragazza dato che io non
lo sono, ma non potrei esserne certo (anzi, probabilmente sbaglierei) :-D
Ciao
Dade
Davide Mastromatteo : [ 
mastr...@bigfoot.com
 ] - ICQ : 21746800
Mastrosoft [Sotto Costruzione ----> 
www.bigfoot.com/~mastrosoft
                                                         ***
" Nell'ozio, nel sonno, in battaglia, verrà senza darti avvisaglia
la morte va a colpo sicuro non suona il corno nè il tamburo. "

"radice quadrata di 2" avrà una ridondanza pressoche' nulla
Allora non hai compreso il concetto di ridondanza.
Ciao,
      __
     (__
      __)tefano.

 Allora non hai compreso il concetto di ridondanza.
Ripeto: non ne ho avendone ancora vista la definizione formale, cercavo di
procedere a logica.
Comunque, se č cosě, del detto teorema ce ne facciamo veramente poco, perchč
*non* potremo mai sapere se una certa sequenza di dati nasconde una logica.
In fondo, se si suppone un universo determinista, ci ritroveremo con la
ridondanza totale (tutto ricostruibile dallo stato di partenza...)
saluti,
	Denis

ridondanza totale (tutto ricostruibile dallo stato di partenza...)
Ed infatti l'universo e' caotico.
Nel caso in cui si faccia l'approssimazione che l'universo sia
deterministico, ossia si prendono per valide le leggi di Newton sul
moto, il moto di un punto materiale e' pienamente individuato da
posizione e velocita' iniziale.
Ciao,
      __
     (__
      __)tefano.


Non ti so dire di preciso. So' solo che non necessita della conoscenza delle
probabilita' di uscita dei simboli. Si basa su sequenze di bit di lunghezza
qualsiasi che si ripetono, e nel cercare di riutilizzare le sequenze
precedentemente codificate.
Per esempio, se io ho gia' deciso di codificare la seq. 1000110 con i bit
1000, se trovo la sequenza 10001100110, i primi 7 bit li "conosco" gia' in
quanto li avevo gia' trovati e codificati con un numero minore di bit. Come
ti ho detto non so di preciso come funziona (implementazione), ma il
meccanismo e' questo. Se cerchi su Yahoo o Altavista non dovresti avere
difficolta' a trovare qualcosa di piu' dettagliato.


 Denis
ciao Denis, molto bella come immagine e fa pensare : scoprire le cause e
percorrerle all'indietro.
Purtroppo anche invertendo il tempo il disordine aumenta!
Di seguito voglio descrivere un programma, fatto tanti anni fa, (sono
abbastanza giovane, ma ho cominciato presto :) ), in Fortran.
Se lo considerate OT, lasciate pure questa lettera, altrimenti continuate la
lettura.
Allora : ci sono 255 particelle in una scatola di 1m-cubo. Ricaviamo random
la posizione iniziale sui tre assi x,y,z e le velocità iniziali vx,vy,vz.
Dopo ad intervalli di 1msec, ricalcoliamo le nuove posizioni. Se ci sono
particelle che occupano la stessa posizione si applica la cinematica degli
urti senza attrito (si può immaginare un raggio per le particelle, così
l'urto viene più facile).
Dopo un certo tempo le particelle sono ben distribuite nella scatola e
possiamo immaginare un file che contiene le posizioni ad ogni step.
Adesso invertiamo il tempo, cioè il prossimo tempo non è l'attuale "+"
1msec, ma l'attuale "-" 1msec, e continuiamo il calcolo.
All'inizio le particelle ripercorrono le vecchie traiettorie (si cede
leggendo il file delle posizioni), ma ben presto la situazione si disordina
di nuovo.
Il bello che si pensava che ciò valesse per i grandi numeri, invece ha
funzionato anche con 255 particelle.
(teorema H di Boltzman).
Per tornare all'argomento della compresione, credo che conosciate quel
ricercatore che afferma di aver trovato un algoritmo sconvolgente : mi
sembra che afferma di essere in grado di ridurre qualsiasi file ad una
dimensione di 100 bytes
http://space.tin.it/computer/ecriscio/pulsar.html
ciao a tutti da Giò





ciao a tutti da Giň
Ciao!








Per tornare all'argomento della compresione, credo che conosciate quel
ricercatore che afferma di aver trovato un algoritmo sconvolgente : mi
sembra che afferma di essere in grado di ridurre qualsiasi file ad una
dimensione di 100 bytes
http://space.tin.it/computer/ecriscio/pulsar.html
ciao a tutti da Giò

 probabilita' dell'i-esimo simbolo.
[snip]
Ok, ora tutto mi torna. :-)
In effetti son proprio scemo... la stessa def. l'avevo letta in un libro di
E.Morin sulla complessitŕ...
saluti e grazie,
	Denis

 rappresentare piů di 2^800 files differenti 
^___^
Semplice ed incisivo...
Poveretto, gli avrai rovinato la vita ;-)
saluti,
	Denis

 probabilita' dell'i-esimo simbolo.
Cosa si intende per probabilita' dell'i-esimo simbolo?
Nel caso di due simboli (0 e 1), e la sequenza 0101010101...
quali sono p_0 e p_1?  In questo caso si puo' prevedere
con sicurezza il simbolo successivo, pero' mi sembra strano
dire che p_0=0 e p_1=1 (o viceversa), e valori intermedi
forniscono H>0 (e quindi ridondanza<1).
	Mauro

forniscono H>0 (e quindi ridondanza<1).
Se consideri un'analisi di primo livello, ove i simboli sono 0 e 1,
non hai ridondanza, essendo i simboli equiprobabili.
Passando ad un'analisi di secondo livello le cose migliorano
notevolmente: infatti se consideri non piu' i simboli 0 e 1, bensi' i
simboli 00, 01, 10 e 11 (ossia consideri due simboli alla volta)
ottieni p_00=p_10=p_11=0 e p_01=1, H=0 e la ridondanza e' massima.
Del resto nel discorso sul linguaggio e sulle lettere che possono
essere omesse senza diminuire l'informazione, e' implicita un'analisi
di livello superiore al primo. Del resto, se consideri (nella lingua
italiana) i simboli q_ dove _ e' un qualsiasi carattere, ti accorgi
subito che hanno tutti probabilita' zero, tranne qq (che esiste solo
in soqquadro) e qu che ha una probabilita' del 99.999..%. Cio' vuol
dire che quando incontri una q, la probabilita' che il carattere
successivo sia u e' enorme...
La funzione H_n, dove n indica l'ordine dell'analisi, e' una funzione
non crescente che tende ad un limite quando n tende ad infinito.
E' chiaro che maggiore e' l'ordine maggiore e' la complessita'
dell'analisi (per il linguaggio, al primo livello abbiamo 26 simboli,
al secondo 26^2, al terzo 26^3, ecc. ecc.)
Ciao,
      __
     (__
      __)tefano.

>forniscono H>0 (e quindi ridondanza<1).
Si dice che la sorgente (quella che produce la sequenza) ha una memoria,
e nel tuo caso sara' che p(X_n=0|X_n-1=1)=1 (la prob che venga uno zero dopo 
un uno) e viceversa p(X_n=1|X_n-1=0)=1, in realta' si parla sempre 
dell'entropia della sorgente in questi casi.
			- Tommaso Schiavinotto -