Newsgroup: it.comp.lang.c++
Titolo: compressione nicola

Comunque: c'e' un numero minimo di bit al di sotto del quale nessun
algoritmo di compressione puo' andare, ed e' il numero minimo di bit
necessari per rappresentare l'informazione contenuta nel tuo file.
Supponi di avere un file di testo di 500 caratteri: qualsiasi algoritmo
di compressione non puo' scendere sotto il minimo numero di bit
necessari per distinguere tutte le sequenze di al massimo 500 caratteri.
Se tu hai gia' compresso il file con un algoritmo decente, ti sei
avvicinato molto al limite teorico, ed e' improbabile che un altro
algoritmo applicato al tuo file compresso ti faccia guadagnare granche'.
Il discorso cambia se e' nota l'interpretazione del file: se sai che
contiene il nome "Nicola" ripetuto un certo numero di volte puoi
trasformarlo in un file che contiene soltanto questo numero, ma questo
ovviamente nessun algoritmo generico e' in grado di farlo.
Ciao,
Nicola
//----------------------------
parole giuste nicola,
c'è un limite per tutto, lo penso anch'io
ma tra una compressione e l'altra c'è da ascoltare e capire quello che
accade e cercare di forzare il limite della ridondanza
probabilmente quello che sto cercando è qualche programma o metodo che
prenda questa voglia di comprimere, in maniera diversa da quella usata
dall'algoritmo a dizionario, o almeno che differenzi il modo di
strutturare le informazioni codificate del file...
soltanto così si potrà avere una diversa compressione dall'ordinaria
struttura, se si raggiunge questo limite,
il solo rimbalzo tra un metodo ed un'altro porterà il file ad una
dimensione inferiore ai limiti posti dal primo algoritmo.
Con questo deduco che non necessariamente il secondo procedimento deve
per forza comprimere il file...potrebbe portarlo all'opposto...basta
esista una diversa distribuzione delle ridondanze.
esempio,
ho provato a verificare come venivano distribuiti  i caratteri di un
file zippato delle dimensioni di 9332 byte, (ovviamente ogni
compressione differisce da un'altra)
se dividiamo questa grandezza per 256, (tutti i simboli del computer)
dovremmo avere una distribuzione equilibrata appena superiore alle 36
presenze per simbolo,
ecco,
eccetto lo 0 che viene sempre usato molto di + degli altri caratteri,
nel zippato erano distribuiti con una tolleranza variabile dai  25 alle
50 presenze per carattere, e la maggiore concentrazione dei simboli
EVIDENZIAVA la circoscrizione verso il numero 36...
può essere tempo buttato ma sapere per certo,
che non esistono altri metodi oltre al dizionario è senzaltro
scoraggiante, nulla toglie la buona volontà di provare nuove strade.
bye duido
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

dimensione inferiore ai limiti posti dal primo algoritmo.
"rimbalzo tra un metodo e l'altro" ?
Ripeto: non ho seguito la discussione, ma se stai cercando
di raggiungere una compressione maggiore di quella degli
algoritmi basati su dizionario (come Lempel-Ziv-Welch) ti
faccio presente che un algoritmo come il LZW si definisce
"asintoticamente ottimo", nel senso che piu' aumenta la
quantita' di dati da comprimere, migliore e' la compressione
ottenuta.  "Ridistribuire la ridondanza" e' un concetto che
mi e' poco chiaro.
-- 
Andrea Laforgia (
walkie...@libero.it
)
"Usenet is a strange place" [Dennis Ritchie]

 mi e' poco chiaro.
In effetti ci sono dei metodi per tenere conto dell'entropia dei dati 
(la quantita' di informazione minima necessaria per rappresentarli), ad 
esempio l'algoritmo bzip2 funziona meglio sui dati piu' entropici di 
gzip o zip, o anche gli algoritmi ace o rar, ma asintoticamente hanno 
andamento simile. Come si diceva, maggiore compressione la si ottiene 
solo sapendo come e' generato un file: ad esempio, ricavare del testo da 
una immagine tramite ocr

Andrea, la fama ti precede, fa molto piacere che tu senta interessante
questo argomento,
non sai quanto vorrei avere delle risposte alle tue domande, ma forse
dovrei prima trovare le mie...
sto cercando qualcuno che abbia studiato l'ambiente compressione, magari
all'Università dove la disponibilità d'informazione è molto ampia...o
che magari sia specializzato nel campo, e che riesca a rispondere se
esiste o è mai stato studiato questo tipo di approccio.
credo che alcune risposte siano possibili solo da persone con queste
caratteristiche...ma forse proprio per la loro conoscenza è difficile
trovarli in questi percorsi.
comunque ogni riflessione è buona, purchè costruttiva.


 una immagine tramite ocr
perciò secondo te mario non si arriverà ad una mutazione della
ridondanza della compressione, ma si ottimizzerà sempre di + l'algoritmo
a dizionario fino a portarlo ai limiti dell'ottimizzabile?
posso chiedere anche a te...non hai mai sentito o letto in giro se
esistono metodi che riorganizzano l'equilibratura delle ridondanze in un
file compresso?


esiste o è mai stato studiato questo tipo di approccio.
Io la cosa che non ho capito (forse perchè si sono un pò intrecciati i
messaggi) è: quale è 'questo tipo di approccio' ?
Ciauz

 ha scritto nel messaggio
news:203242126....@news.iol.it...

Una nota:
L' esempio riguarda una compressione con perdita di dati, non reversibile.
Per restare in C++:
"for (int i = 0; i < 2000000000; i++) cout << i << endl;"
forma compressa di una particolare sequenza di due miliardi di numeri interi
tutti diversi.
----
Sergio Bianchi

 messaggi) č: quale č 'questo tipo di approccio' ?
Veramente raffaele, cercavo approfondimenti o consigli dal NG...
sto solo chiedendo se qualcuno studiando, o per lavoro, ha sentito
parlare o letto di un metodo che comprime con tecnica diversa da quella
a dizionario, oggigiorno sicuramente largamente implementata e
approfondita.
Questo vale anche per iniziative partite e mai concluse per svogliatezza
o mancanza di scambio soluzioni a problemi conseguiti...
Tu hai sottolineato "l'entropia" e io ho risposto che sarei stato molto
curioso di sentire il collegamento tra questo, e una compressione,
naturalmente usando termini che permettano una discussione reciproca.
bye duido


 approfondita.
http://www.hn.is.uec.ac.jp/~arimura/compression_links.html
-- 
"Everything is vague to a degree you do not realize till you have tried
  to make it precise"
"Ogni cosa č vaga in una misura di cui non ci si rende conto finché non
  si cerca di renderla precisa"
                                       Bertrand Russell
                                       The Philosophy of Logical Atomism

 approfondita.
Oltre ai metodi che si basano su dizionario esistono quelli 
a codici con lunghezza variabile (vedi Huffman/Shannon Fano, ecc..)
ma sono di gran lunga migliori i metodi basati su dizionario.
LZW, su dati formati da 8 bit per byte, supera di gran lunga
Huffman, che ha un limite preciso dell'87,5 % (compressione 1:8, 
non di piu').  In realta', e' l'affermazione "riorganizzare la
ridondanza delle informazioni" che mi da' ai brividi.
Se ho un file compresso, sicuramente avro' all'interno di 
esso dei caratteri ripetuti.  Se quello che cerchi di fare
e' "riorganizzare" questi byte in sequenze tali, da poterli 
comprimere nuovamente, il costo e' molto maggiore del beneficio, 
in termini di dimensioni del file compresso generato.


 in termini di dimensioni del file compresso generato.
Andrea vedo con piacere che segui perfettamente il metodo e precedi le
mie conclusioni, quello che hai appena confermato infatti l'ho provato
in principio attraverso una codifica, ma col risultato del file ne
generavo uno molto + grande e comunque anche ricompresso non lo rendevo
inferiore all'originale, anche se di poco...
questo fa pensare che il metodo non è quello giusto, comunque fa molto
piacere che tu abbia centrato l'argomento, tu hai mai sentito parlare di
qualche programma capace di questo metodo?
bye duido


fabio mi dispiace ma l'inglese non lo parlo...


 qualche programma capace di questo metodo?
No, perche' non e' compatibile con teoria alla base della 
compressione.


 compressione.
Andrea credo che questa curiosità sia dovuta al pizzicare
dell'intuizione, e le teorie si evolvono...non ho trovato niente del
genere da studiare, ma forse la vedo così facile perchè non ho seguito
una strada diversa dagli altri o forse in fondo c'è un muro,
ogni giorno cerchiamo l'idea che permetta l'evoluzione, il pensiero è
gia là, seguirlo è semplice, serve solo il tempo di raggiungerlo, e
spero che il mio sia sufficiente...comunque vada, se non dovessi
riuscire, il mio lavoro lo avranno a tutti i programmatori del NG, forse
qualcuno finirà di masticare quello che ho già iniziato.
l'uomo è una cosa magnifica, ma senza una donna non da il massimo...il
giorno è stupendo ma serve la notte per renderlo tale..credo che un
singolo metodo abbia bisogno del suo diverso per ottenere il massimo...
ho letto che ogni cosa finisce, sta all'uomo trovare una soluzione, la
compressione a dizionario ha un limite, e penso sia molto vicino.
permettimi una riflessione personale, ritengo che l'uomo italiano sia
molto fortunato,
fin dalla nascita parla una lingua che permette una strutturazione
espressiova superiore a molte altre,
inconsciamente già predisposti per una strutturazione comprensiva
superiore alla media mondiale...Fermi...c'è l'atomica ;)
bye duido


 superiore alla media mondiale...Fermi...c'è l'atomica ;)
Idem.
Secondo me dovresti smettere di assumere sostanze ;)
Non vedo cosa c'entri questo col discorso di partenza.


vedo che la discussione non può proseguire perciò lascerò a te l'ultima
parola.
sono le persone che cercano l'impossibile che rendono il possibile.
molte teorie si sono dovute rimproverate a soluzioni innovative che nel
tempo si sono evolute...
se l'impossibile resta tale è forse perchè non riusciamo a guardarlo
dalla giusta prospettiva?
difficile vedere una montagna che dista 4000 Km se la strada che ti
hanno indicato ti ha portato a quella distanza dalla montagna...non
credi?
questo dovrebbe farti pensare che non tutto ciò che è scritto e impari è
discutibilmente impossibile.
bye bye duido


 fabio mi dispiace ma l'inglese non lo parlo...
Hum... provvedi al più presto allora, senza inglese non si va molto 
lontani...
-- 
"Everything is vague to a degree you do not realize till you have tried
  to make it precise"
"Ogni cosa è vaga in una misura di cui non ci si rende conto finché non


 credi?
Ok, allora fammi vedere questa "montagna".
Io ti ho fatto presente (intuendo che cosa volessi fare) che
cio' che stai pensando di fare non porta ai risultati che 
speri e questo non perche' lo pensi io, ma perche' e' la logica
matematica alla base della compressione dei dati che non lo 
consente.  Tu insisti.  A questo punto aspetto delle 
prove oggettive della tua teoria.  Se mi dimostri con dati 
oggettivi che sei capace di comprimere secondo un nuovo algoritmo, 
saro' lieto di difendere la tua teoria.  
Puo' darsi che a me sfugga qualcosa, pero', per cortesia, se
chiedi consigli su un possibile "metodo innovativo di compressione",
se questo puo' essere tale, se c'e' qualcosa a riguardo, ecc... ecc...,
non avere la superbia di pensare che questo metodo debba esistere
per forza.


 applicazione pratica) e' poco quanto niente.
umm, permettimi di contraddirti: i numeri di fibonacci nacquero per 
sapere quante coppie di conigli ci sarebbero stati dopo tot tempo da una 
coppia di conigli, le geometrie di riemann trovarono applicazione solo 
dopo che Einstein rivoluziono' la fisica, la teoria delle funzioni 
ricorsive divenne utile solo dopo l'avvento dei calcolatori... la tua e' 
una visione piuttosto "utilitaristica", ma non sai a priori cosa ti 
potra' servire in futuro
Ne' puoi esser certo dell'impossibilita' di qualcosa, o dell'inutilita': 
celebri gli esempi della trasmissione di qualcosa senza supporto fisico, 
reputata impossibile dalla fisica del 1700 smentita dalle onde e.m. nel 
vuoto, o del presidente dell'IBM che disse non sarebbero mai serviti 
piu' di una decina di PC al mondo...
Certo, esistono le cose matematicamente impossibili, ma per restare al 
tuo esempio un Mbyte in un byte c'entra: dipende da quale Mb
ad esempio(MSB first):
1011 0000
se prendi le prime 4 cifre come il numero di caratteri, in esponente di 
10, e il resto dal valore del byte, eccoti 10^7 byte di '\0'
e di esempi del genere ce ne sono molti, ad esempio prendendo alcuni 
tipi di rotazione dei bit si ottengono sequenze anche lunghe di byte 
diversi. Non so di quale utilita' tutto cio' sia ad un algoritmo di 
compressione generico, pero' e' possibile comprimere "alcuni" tipi di Mb 
(o Terabite, addiritura) in un byte. Dunque e' impossibile comprimere un 
generico Mbyte di dati in un byte? la risposta e' "nella stragrande 
maggioranza dei casi, e' impossibile"
L'errore piu' grande che si possa fare e' generalizzare, specie nel 
negare che qualcosa sia "possibile"

 tuo esempio un Mbyte in un byte c'entra: dipende da quale Mb
un esempio di compressione ancora maggiore: in ogni cellula del tuo 
corpo c'e' il necessario per ricostruire un organismo funzionante 
completo, addirittura duplicato. e qui siamo davanti ad una compressione 
dell'ordine delle decine di miliardi di volte.

 maggioranza dei casi, e' impossibile"
Vedi sopra: il discorso che stai facendo e' puramente 
teorico, non ha alcuna implicazione pratica.  Supporre che
vi sia 1 caso (o 16 casi) in cui 1 Mbyte di dati sia comprimibile 
in 1 byte, non vuol affatto dire che questa tecnica si utilizzabile
come tecnica di compressione generalizzata.


 dell'ordine delle decine di miliardi di volte.
La riproduzione cellulare risponde a un principio di duplicazione
delle cellule.  Per quanto la cosa possa sembrarti soprendente,
in realta' non e' un paragone sostenibile con l'informatica.
Le cellule si riproducono sempre allo stesso modo e producono
altre cellule con caratteristiche simili.  Il prodotto della
riproduzione (che puo' avvenire milioni di volte) e' un essere
dalle caratteristiche uguali o simili a colui che l'ha generato.
Non e' possibile applicare lo stesso principio all'informatica,
a meno di stabilire una regola base di compressione, per 
rappresentare la quale e' necessario molto piu' spazio di quello 
che si guadagna con le singole compressioni.


 negare che qualcosa sia "possibile"
Ci sono cose che si possono tranquillamente negare, cioè quelle che vanno
contro le leggi matematiche. Una volta che ho definito cosa significa
"efficienza" di un algoritmo di compressione, posso affermare che nessun
algoritmo riuscirà mai a comprimere in modo efficiente un MB di dati in un
solo byte.
Marco

 ha scritto nel messaggio
news:2037009.3...@news.iol.it...

All'interno di una cellula ci sono molte più informazioni di quante ce ne
sono in un byte. Quando si dice che non si può comprimere un MB in un byte,
non si dice che sarà sempre impossibile ottenere un rapporto di compressione
di 1048576:1 (probabilmente potrà essere possibile comprimere un TB in un
MB, conoscendo in anticipo la natura dei dati). Quello che si dice è
soltanto che l'unità di partenza, il byte, non può contenere le informazioni
adatte a consentire un rapporto di compressione così elevato.
Se la cellula contenesse solo un milionesimo delle informazioni che in
realtà possiede (tramite il DNA), dubito che ne uscirebbe un uomo. E se ne
uscisse, sarebbe talmente brutto e storpio da essere soppresso dalla
selezione naturale... ;-)
Marco

 come tecnica di compressione generalizzata.
non lo metto in dubbio, era solo un esempio, ma riguardo alle cose 
giudicate inutili, ti rimando alla lettura di qualche biografia di 
riemann, o piu' recentemente delle teorie di peano, di Minkowsky, di 
rayleigh, sul caos e attrattori strani, che ebbero utilizzo soprattutto 
grazie alle opere di mandelbrot nel 1950.
O anche la logica vaga, da cui prese il via la logica fuzzy, con tutto 
quel che ne e' seguito: il povero black nei primi decenni di questo 
secolo aveva inventato questa logica a valori continui da 0 a 1, passata 
sotto il piu' totale disinteresse come inutile. e il suo autore e' morto 
prima di vederne un solo utilizzo pratico
Ripeto: non volglio stare a far polemica, e' solo che non si puo' sapere 
a chi la storia dara' ragione.

 che si guadagna con le singole compressioni.
Te lo dico in anticipo e lo sottolineo : andiamo nel regno delle 
ipotesi
una volta stabilito l'insieme delle regole che permettano compressioni 
di particolari insiemi di centinaia, migliaia o milioni di MB in pochi 
byte, se questo insieme esistesse, e avesse anche alcuni GB di 
estensione, la sua dimensione rimarrebbe costante, e allora il guadagno 
cumulativo di tutte le compressioni effettuate sarebbe comunque maggiore 
della sua dimensione. 
Quindi non e' tanto se sia piu' grande della compressione che importa, 
ma se e' possibile trovare un tale insieme. 
Per quel che mi riguarda, non saprei trovare una dimostrazione rigorosa 
ne' della sua esistenza, ne' della sue inesistenza, e anzi, se ne sei 
capace, ti prego di farlo

 secolo aveva inventato questa logica a valori continui da 0 a 1,
secolo scorso, ovviamente

giudicate inutili,
Mario, stai cominciando a stancarmi: io non ho affatto
giudicato "inutile" alcunche'.  Sto semplicemente facendo
delle considerazioni su cio' che mi e' sembrata
un'impostazione sbagliata del problema.  Giusto per
riportare il tema in-topic, visto che sei stato capace di
spingerci fino nei meandri del corpo umano, in un off-topic
mostruoso, ti ricordo che "riorganizzare la ridondanza" (che
e' cio' che vuol fare il nostro amico) non puo' produrre dei
risultati positivi, per il semplice fatto che ti ci vogliono
piu' risorse per conservare informazioni sull'ordine di
partenza, che quelle che risparmi.
E' l'impostazione di base che e' sbagliata e contrasta
palesemente con un principio molto chiaro: l'informazione
non puo' sparire: deve essere comunque contenuta da qualche
parte.  E con questo concludo, non voglio discutere di
biologia o di fisica.
-- 
Andrea Laforgia (
walkie...@libero.it
)
"Usenet is a strange place" [Dennis Ritchie]

byte
Non posso stabilire un insieme di regole: fammi vedere, di
grazia, come faresti.  Per farti un esempio, io posso
considerare un file binario, dividerlo in 256 pezzi e
stabilire un codice per ogni spezzone di byte.  Ok,
scrivendo una sequenza degli stessi 256 byte, in base alla
regola che associa ad ogni sequenza di byte un codice, posso
comprimere QUALSIASI file di qualsiasi dimensione (fosse
anche miliardi di miliardi di byte) in 256 byte.
Ora, questa regola deve essere CONTENUTA da qualche parte.
Sia il compressore, che il decompressore devono esserne a
conoscenza.  Se devo distribuirla insieme al file compresso,
allora non val proprio la pena comprimerlo, perche' lo farei
esplodere nelle dimensioni.  In ogni caso, stabilita questa
regola, posso comprimere SOLO quel file o una qualsiasi
composizione di quelle sequenze.  E' intuitivo che, piu'
grande e' il file, piu' problematica e' la compressione.
Se io so di dover comprimere SEMPRE E SOLO sequenze di
questo tipo allora l'algoritmo va bene, ma e' un uso
SPECIALIZZATO e non GENERICO della compressione.
Assolutamente inutilizzabile in altri contesti.
Per farti ancora un esempio, l'algoritmo di Huffman esiste
in due varianti: a codici con lunghezza dinamica (calcolati
al volo sul file da comprimere) e a lunghezza fissa (adotta
sequenze fisse di bit per ogni simbolo presente nel flusso
di dati da comprimere).
Il primo caso richiede la distribuzione della "regola" di
compressione (che e' un albero binario) insieme al file
compresso, il secondo caso no.
Nel secondo caso, proprio per la mancanza dell'albero, la
compressione e' maggiore che nel primo caso, ma l'algoritmo
e' applicabile SOLO a DETERMINATI contesti (vedi la
compressione di testi in inglese, in cui si sa quali sono le
frequenze medie delle lettere presenti nelle parole e quindi
si possono costruire sequenze di bit piu' lunghe per le
lettere meno presenti e piu' corte, per esempio, per la
'e').  Nel caso degli algoritmi di compressione a
dizionario, i "rate" di compressione sono cosi' alti perche'
(almeno nel caso di LZW) non c'e' bisogno di memorizzare la
"regola" con cui il file e' stato compresso, ma il
dizionario e' ricostruibile mentre si decomprime il file.
Con questo spero di porre fine alla discussione, che si e'
spinta su temi decisamente fuorvianti.
Quando avrete rivoluzionato le teorie alla base della
compressione, fatemi un fischio, sono pronto a stringervi la
mano.


 ha scritto nel messaggio
news:3c973db4...@news.tin.it...

Vorrei aggiungere a questa discussione alcune considerazioni,  nell' intento
di contribuire al raggiungimento di una conclusione:
 Possiamo considerare un algoritmo di compressione (reversibile) come una
relazione biunivoca tra due insiemi, le stringhe binarie  espanse e le
stringhe binarie compresse.
Da ciò discende che vi possono essere diverse relazioni uno a uno e quindi
diversi modi di comprimere ed espandere e che in generale esisterà sempre un
algoritmo ottimo per quella particolare stringa, in grado di associarla alla
stringa compressa di minima lunghezza. Se è  comunque possibile pensare che
esista un algoritmo ottimo per un particolare sottoinsieme  di stringhe
(scriverlo è un altro paio di maniche) questo non aiuta a sviluppare un
compressore generale "miracoloso":
Per ogni algoritmo esiste sempre una stringa che non si può comprimere. Se
infatti  l'insieme di stringhe da comprimere è di lunghezza N ad ognuna di
esse dovrebbe essere associata una stringa di lunghezza inferiore. Ma l'
insieme delle stringhe di lunghezza inferiore è composto da stringhe di
lunghezza 0 (2^0), di lunghezza 1 (2^1), di lunghezza 2 (2^2) e così via
fino a N-1.
La sommatoria delle quantità tra 0 e N - 1 vale (2^N) - 1. Una in meno
rispetto alle 2^N stringhe di lunghezza N da comprimere.
Si tratta quindi di assegnare le stringhe più brevi nella maniera più
vantaggiosa e un algoritmo di compressione generale (per sequenze di
qualsiasi tipo) avrà sempre prestazioni simili ai sistemi esistenti che
questo fanno in sostanza. Quando invece trattiamo in prevalenza un certo
tipo di stringhe possiamo pensare a qualcosa di meglio ma non parliamo però
di un sistema di compressione generico. Inoltre lo sviluppo di un tale
sistema non è affatto banale  tenendo presente poi che un sistema per essere
utilizzabile deve avere un ragionevole rapporto tra tempo di calcolo in
compressione e decompressione. E se vado a cercare una struttura algoritmica
sottostante in stringhe molto lunghe non mi aspetto certamente tempi di
analisi brevi, direi anzi che il comportamento di tali sistemi tenderebbe ad
avere assimmetrie simili ai sistemi di crittografia.
----
Sergio Bianchi