Newsgroup: it.scienza.informatica
Titolo: algoritmi compressione

cosa pensate della tesi di enzo criscione, professore di informatica 4
all'università di macerata, che sostiene di avere creato un algoritmo di
compressione non lossy che comprime ad ogni iterazione e permette di
comprimere un cd in pochissimi byte...
le tv locali, compresa rai tre ne parlano come di un genio incompreso, a me
le sue tesi sembrano cozzare contro ogni base della teoria
dell'informazione. non vorrei avanzare la tesi di 
www.gameprog.it
 che lo
classifica come un umorista, ma francamente non capisco come una soluzione
così avanzata se fosse reale e generale non sia già stata utilizzata.
p.s.
quali sono i titoli per insegnare informatica all'università? sarei
interessato...

 interessato...
il normale corso di studi accademico:
dottorato di ricerca->ricercatore->professore associato->professore 
ordinario ma in pratica poi "insegnano" anche i dottorati.
Bisogna poi vedere "cosa" insegnano. Per insegnare un linguaggio di 
programmazione è più che sufficente un dottorando e sotto-utilizzato
un professore che in quelle ore potrebbe "scoprire" molte cose interessanti.
ciao,
daniele

mi date qualche link sulla sua idea per favore ??

 daniele
quindi una laurea in architettura e nessun dottorato e nessuna pubblicazione
di rilievo è piuttosto particolare, o no ?

 comprimere un cd in pochissimi byte...
Se vai su
http://groups.google.it/
e  cerchi
"enzo criscione"
trovi alcuni thread del 1998 che ne parlano,
compreso un mio intervento del quale mi ero assolutamente dimenticato.
Secondo me era un caso umano abbastanza patetico.
Non pensavo fosse ancora al lavoro su quella cosa.
A quel tempo affermava poter comprimere qualunque
CD in 100 bytes (!).
Solo che non voleva far vedere il programma a nessuno
escluso Bill Gates (!!!) per paura che glielo copiassero.
A suo tempo avevo pensato di "sfidarlo" a comprimere
un mio CD su un computer (gli avrei concesso non 100 bytes,
ma un intero floppy), portare il floppy su un altro computer
e decomprimerlo. Dopo di che avrebbe potuto formattare i dischi fissi
dei due computer per motivi di sicurezza. Ho rinunciato a
lanciare la sfida perche' non mi piace infierire.
Ciao,
g.

Voglio spezzare una piccola lancia a favore di questa idea.
Dire di poter comprimere qualsiasi cd in 100 byte a prima vista sembra
palesemente errato visto che 2^100byte e' gran lunga piu' piccolo di 2^1Gb
per cui tutte le combinazioni di 1Gb non stanno in 100 byte .
Pero togliendo il caso specifico non e' vero che dato un M > N dove M e' la
lunghezza della stringa da comprimere ed N e' la dimensione della stringa
compressa per ogni stringa di lunghezza M esistente non si riesca a
comprimerla in una stringa di lunghezza N.
Il trucco sta nel fatto che bisogna tener presente da dove arriva la stringa
lunga M da comprimere , una cosa e' dire tutte le stringhe possibili ed un
altra e' dire tutte le stringhe esistenti.
Infatti , vi e' la possibilita' che la stringa lunga M che si vuole
comprimere risulti prodotta sempre da un programma!
Se questo fosse vero le strighe di dimensione M sarebbero prodotte da un
programma la cui complessita' e' di dimensione K per cui se prendiamo un M
sufficientemente grande avremo che il programma piu' piccolo che produce
tutte le possibili stringhe di dimensione M e' piu grande di K , ne segue
che le stringhe esistenti di dimensione M sono una quantita' inferiore di
2^M .
All' aumentare di M le stringhe esistenti sarebbero sempre meno numerose
rispetto a 2^M e piu' precisamente potrebbero essere 2^N.
Per andare un po' sul pratico sfido chiunque a produrre tutte le stringhe
possibili lunghe 1Gb. E' teoricamente possibile ma praticamente impossibile
e sono le leggi fisiche che lo rendono impossibile .
Quindi , non so se le cose siano corrette per i numeri messi in gioco
(100byte ed 1Gb) ma ritengo che vi siano dei valori M ed N per cui questo e'
vero.
Spero di aver spiegato a sufficienza la mia posizione.
Ciao, Denis.

.  All rights reserved.
Saluti,
MARco   
http://mar.i.am/#isi16467.7145
?
-- 
x(t),y(t) = th(3t-34.5)*e^[-(3t-34.5)^2]/2-4.3+e^(-1.8/t^2)/(.8*atg(t-
3)+2)(t-1.8)-.3th(5t-42.5),(1.4e^[-(3t-34.5)^2]+1-sgn[|t-8.5|-.5]*1.5*
|sin(pi*t)|^[2e^(-(t-11.5)^2)+.5+e^(-(.6t-3.3)^2)])/(.5+t)+1  ; 0<t<14

> e sono le leggi fisiche che lo rendono impossibile .
quali??

.. Ma se anche fosse un file >> di 1 Giga cosa cambierebbe??
Divido il file in n Blocchi da 1 Giga, comprimo ogni blocco in un file di
100 bytes... li concateno fino a formare altri gruppi da un giga...
ricomprimo di nuovo ... riformo...
Mi ricorda tanto
God wrote pkunzip universe.zip
Dove, ovviamente, universe.zip è un file di 100 byte...
Dino.
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

. All right reserved.
1. Redistributions of any derived part of this publidcation must retain
   the above copyright notice, this list of conditions and disclaimer.
2. Redistributions must reproduce the above copyright notice, this list
   of conditions and the following disclaimer in the documentation
   and/or other materials provided with publication.
3. Neither the name of the author nor the names of its contributors
   may be used to endorse or promote products derived from the publication
   without specific prior written permission by the author.
THIS INFORMATION IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS PUBLICATION, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
Saluti,
MARco



Puo' darsi
Ciao , Denis.

...

non capisco..."particolare" cosa intendi? Che c'entra con la discussione?
Ciao...

 mappatura delle probabilita` dell'input".
Sono perfettamente d' accordo.
Io chiamerei la compressione lossless semplicemente "cambiamento del 
codice" o "ricodifica efficiente dell' informazione". Quella lossy 
"eliminazione dell' informazione non importante".
La compressione oltre il cosidetto limite di Shannon  è diventato l' 
equivalente informatico della quadratura del cerchio o del moto 
perpetuo: ogni volta che la scienza dichiara qualcosa impossibile c'è 
sempre qualche crackpot che afferma di aver trovato la soluzione.
Nel caso della compressione qualche anno fa c' era persino una azienda 
americana (la zeosync) che dichiarava di aver raggiunto risultati 
strabibilianti, ho controllato ora e non hanno più nemmeno l' homepage....

 ha scritto nel messaggio
news:29b97c72.04031...@posting.google.com...

i titoli di questo prof che ha una visione particolare della teoria
dell'informazione

 codice" o "ricodifica efficiente dell' informazione".
non cè bisogno di inventare, si chiama codifica di sorgente.

 writes:
      + Vincenzo wrote:
      > > Sono perfettamente d' accordo.
      > > Io chiamerei la compressione lossless semplicemente
      > > "cambiamento del codice"
      > > o "ricodifica efficiente dell' informazione".
biscia> non cè bisogno di inventare, si chiama codifica di sorgente.
Le suggerirei di astenersi da considerazioni sull'"inventare",
lei e` quello che ha portato la questione (seppur con incerta diffidenza),
ha dato il titolo al thread quindi lei e` il primo a non chiamare
quegli algoritmi con un buon nome.
Inoltre il nome indicato ora non fa alcun riferimento alla
probabilita`/frequenza (necessaria al fine di una
compressione mediamente probabile) quindi non disincentiva
baggianate sui cosiddetti "algoritmi di compressione".
Probabilmente non avra piu` risposte da me.
Comunque mi ha dato l'occasione per dire che intendo rispomdere
a Vincenzo su un confronto con il diverso approccio teorico di Shannon,
quando avro` piu` tempo, chiederei di farmi delle domande se qualcosa
non e` chiaro.
In riferimento al post raggiungibile con
http://groups.google.com/groups?selm=ywmfzcb...@fast.mm.homeunix.org
essenzialmente io ho distinto il caso di n finito (shannon no),
in cui ho potuto formulare e numerare in modo non approssimato
tutti i possiibili algoritmi a massima compressione teorica
(e formalmente per qualsiasi base numerale anche distinta tra
input e output, cosa rilevante perche` non necessariamente
l'output deve essere memorizzato con modello fisico a base 2),
spostandosi a base 2 il limite di miglior compressione media dovrebbe
essere coincidente, con la differenza che il mio prevede la casistica
non approssimata ai reali, con n finito.
Ho poi anche un dubbio sulla non considerata parallelizzazione
della trasmissione di informazione nel caso del limite di dati
trasmissibili nell'unita` di tempo (e` facile chiamare disturbo
(noise) del segnale quello che ha natura imprecisata su una portante
in frequenza che in realita` non e` necessariamente su scala
unidimensionale)
(v. 
http://lanl.arxiv.org/ps/quant-ph/0207121
, che io tradurrei
in "la teoria quantica serve per spiegare, non per inventare")
Naturalmente i principi di entropia sono validi nel contesto in cui
sono formalizzati, non dico che Shannon sbaglia.
(C)Copyright by Marco Munari mar 
i.am
All tbe best,
MARco  
http://mar.i.am#guestbook.html#isi16475.50054


 compressione non lossy che comprime ad ogni iterazione 
Prendo tre CD diversi, faccio al più tante iterazioni quanti i bit 
contenuti in un CD. Visto che ogni volta riduco, alla fine mi ritrovo 
con un bit che può essere 1 o 0. Quindi l'immagine compressa di almeno 2 
CD è uguale, per cui essendo non lossy l'algoritmo, anche la loro 
decompressione e uguale contraddicendo l'ipotesi di 3 CD diversi.
Fino a prova contraria 3 CD diversi esistono. ;)
 > e permette di
 > comprimere un cd in pochissimi byte...
Come sopra, poniamo lo comprima in 1000 byte.
Allora al mondo esistono 2^1000 possibili CD (basta creare tutte le 
possibili permutazioni di bit di 1000 byte e scomprimerle)
Bene, scommettiamo che riesco a scrivere un programma di due righe che 
genera almeno 2^(640*1024*1024*8) CD distinti?
Probabilmente Kolmogorov si sta rivoltando nella tomba!

Crescione non e' l'unico ad aver quasi realizzato un algoritmo del genere.
Io ci lavoro su da qualche anno e mi ritrovo +- con la sua stessa
intuizione, risultati incoraggianti ( 5% - 10% in meno sui bz2 ed i rar
ovviamente al massimo della loro compressione. ) ma con un approccio alla
risoluzione diverso.
Un suggerimento.... per capire come sia possibile un simile algoritmo
bisogna pensare in maniera differente dalla massa.
Ad es. se tutti gli algoritmi di compressione usano la probabilitą ed il suo
calcolo,... voi cominciate a pensare a qualcosa di deterministico che
sfrutti il calcolo combinatorio. :) e forse lo intravedete anche voi.
ultimo aiutino ---> n! < n^n => ln( n! ) / ln( 2 ) < ln( n^n ) / ln( 2 )
..... meditate .....


cosa comune agli inovatori, in bocca al lupo.



bellissimo! la dimostrazione per assurdo più elegante che abbia mai visto.
Complimenti!


non riconosce un nome comunemente utilizzato in letteratura ?

 > Ad es. se tutti gli algoritmi di compressione usano la probabilità ed il



   biscia> > ha scritto nel messaggio
   biscia> > news:0v17c.96871$O31.4...@news4.tin.it...
NB: il post di Antonello si colloca secondo la cronologia:
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&frame=right&th=7e41c90260818096&seekm=Sye8c.117117%24O31.5077361%40news4.tin.it#link11
Antonello> > > Crescione non e' l'unico ad aver quasi realizzato un
Antonello> > > algoritmo del genere.
Antonello> >
Antonello> > > Io ci lavoro su da qualche anno e mi ritrovo +- con la
Antonello> > > sua stessa intuizione, risultati incoraggianti ( 5% -
Antonello> > > 10% in meno sui bz2 ed i rar ovviamente al massimo
Antonello> > > della loro compressione. ) ma con un approccio alla
Antonello> > > risoluzione diverso.
Antonello> > >
   biscia> >
   biscia> > quindi con risultati credibili, senza annunci poco verosimili.
   biscia> >
ma voi due vi siete messi d'accordo?
Antonello> > > Un suggerimento.... per capire come sia possibile un
Antonello> > > simile algoritmo bisogna pensare in maniera differente
Antonello> > > dalla massa.
Antonello> > >
   biscia> >
   biscia> > cosa comune agli inovatori, in bocca al lupo.
Antonello> > > Ad es. se tutti gli algoritmi di compressione usano la
Antonello> > > probabilità ed il suo calcolo,... voi cominciate a
Antonello> > > pensare a qualcosa di deterministico che sfrutti il
Antonello> > > calcolo combinatorio. :) e forse lo intravedete anche voi.
Antonello> > >
Antonello> > > ultimo aiutino
Antonello> > > ---> n! < n^n => ln( n! ) / ln( 2 ) < ln( n^n ) / ln( 2 )
Antonello> > >
Antonello> > > ..... meditate .....
Antonello> p.s. dato che
Antonello> come lo finisco lo pubblico OPEN SOURCE sotto GPL ...
Antonello> se qualcuno se la cava con il calcolo combinatorio e non ha
Antonello> problemi a condividere quello che sviluppa la porta e'
Antonello> aperta.
Antonello, lei ha un problema, anzi e` un problema (per non usare
altri sostantivi):
non e` _molto_ preparato, e fin qui niente di male, ma purtroppo
si e` lasciato sopraffare da disonesta` intellettuale, e nel campo
dell'innovazione delle idee e` la peggior cosa. Cio` e` evidente verso l'alto.
Non creda di imbrogliare chi sa qualche ordine di grandezza piu` di lei,
il suo primo post era un insulto all'intelligenza (io avevo preferito
sorvolare), ma il suo secondo lo conferma.
Cerchi di avere maggiore onesta` intellettuale.
Se attinge quello che capisce da idee di altri dotati di una chiara
visione di insieme tale che nemmeno puo` immaginare, spacciando di
aver realizato qualcosa che la incoraggia a proseguire dopo un lavoro
di "due anni",
non cerchi poi il loro aiuto, che fa brutta figura.
Mi dispiace ma personaggi come Antonello e Crescione sono dannosi,
altro che innovativi.
Antonello in particolare inoltre sembra aver preso confusamente
l'uso dell'approccio combinatorio dal mio post perche` ha premuto "Rispondi"
immediatamente dopo aver letto il mio post che lo conteneva con informazioni
di copyright, ignorando pero` perfino totalmente di far riferimento al
mio contenuto e allacciandosi invece a Crescione.  I risultati poi si vedono.
Saluti,
MARco


 |sin(pi*t)|^[2e^(-(t-11.5)^2)+.5+e^(-(.6t-3.3)^2)])/(.5+t)+1  ; 0<t<14
Quale e' l'obbiettivo di volersi firmare con una formula,
servono fatti reali come il suo vero NOME e COGNOME !

 > |sin(pi*t)|^[2e^(-(t-11.5)^2)+.5+e^(-(.6t-3.3)^2)])/(.5+t)+1  ; 0<t<14
non se la prenda, solo una curiosità, che funzione è th(x) ? intende
tangente iperbolica ??

 writes:
biscia> non se la prenda, solo una curiosità,
biscia> che funzione è th(x) ?  intende tangente iperbolica ??
Avevo prospettato che probabilmente avrei evitato di rispondere a costui,
ma in tre righe vedo progressi (tranne l'anonimato, se non sbaglio),
rispondo nell'universale augurio di onesta` sincerita` pace e bene,
anche volentieri:
si`:  th = tanh = tgh = tangh = (exp(x)-exp(-x))/(exp(x)+exp(-x)),
      si puo` scrivere in tanti modi, ho usato il piu` sintetico
      anche se non e` molto usato...
Poi atg e` maggiormente chiamato atan o arctan, sgn e` sign (segno).
Il resto si dovrebbe capire (moltiplicazione sottointesa, .n = 0.n,
e^x = exp(x), |x|=abs(x), l'uso di parentesi quadre e tonde e` solo
per facilitare un po' la lettura)
La mia signature e` semplicemente la mia signature (nel vero senso
della parola).
A volte dico che l'interpolazione funzionale e` una semplice
applicazione del reverse engineering, anche di cui sono grande mastro.
Saluti,
MARco
-- 
 
http://mar.i.am/~u16505.49511/it.scienza.informatica,signature,it


       anche se non e` molto usato...
il resto era perfettamente comprensibile, mi stupiva solo quel th.(ps. in
certi ambienti di arriva ad un esotico HTAN )

 applicazione del reverse engineering, anche di cui sono grande mastro.
mi può dare qualche riferimento
grazie
-- 
              o         _        _            _
   _o        /\_      _ \\o     (_)\__/o     (_)
 _< \_      _>(_)    (_)/<_       \_| \      _|/' \/
(_)>(_)    (_)           (_)      (_)       (_)'  _\o_
----------- 
http://magicforum.altervista.org
 ----------