Newsgroup: it.comp.lang.c++
Titolo: [OT] entropia di un file

So di essere OT e di avere poche chance di risposta, ma comunque provo :-)
non e' che qualcuno ha notizia di una qualche funzione che mi calcoli in 
modo spicciolo (possibilmente affidabile ma comunque rapido) l'entropia di 
un file?
mi spiego: l'entropia indica il grado di disordine, quindi di 
prevedibilita' dei byte del file; mi serve per stabilire quanto un file e' 
comprimibile...
vi prego, non mi dite "comprimilo e vedi che esce fuori"... avrei bisogno 
di qualcosa di piu' rapido...
se qualcuno poi da indicarmi qualche gruppo piu' appropriato per la 
domanda...
tks a lot e scusate il disturbo..
Pinolo

 comprimibile...
Non sono del tutto convinto che si possa parlare di entropia di un file
in senso assoluto. Hai una formula?
Ciao,
Nicola

Nicola Musatti <Nicola....@ObjectWay.it> writes:

Press et al., Numerical recipes in C, pagina 903 e seguenti (Huffmann
coding), contiene qualche cenno; l'entropia e' legata alla massima
compressibilita' *teorica* di una sequenza a partire dalla
probabilita' dei singoli elementi da cui la sequenza e' costituita.
Nemmeno io penso che si possa parlare di valore assoluto dell'entropia
di un file (unico e perfettamente determinato).
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Dept. of Physics, Univ. of Padova, Italy          loreti at pd dot infn dot it

 di un file (unico e perfettamente determinato).
Il problema fondamentale e' quello dell'interpretazione: in soldoni, se
sai cosa rappresenta il file lo comprimi piu' efficientemente. Cosi'
comprimere un file di 1 GB in un bit e' semplicissimo: 0 rappresenta
quel file li', a tutti gli altri file anteponi 1. Se sai che file e' la
compressione e' ottima perche' il file ha probabilita' 1 di essere
quello giusto e tutti gli altri probabilita' 0.
Altrimenti bisogna ragionare sulla distribuzione di probabilita' per i
file lunghi al massimo n byte, ma in assenza di ulteriori vincoli temo
sia difficile ottenere risultati utili.
Tanti anni fa mi dilettavo con l'idea di considerare la computazione
come analogo dell'applicazione di energia ad un sistema per abbassarne
l'entropia e di poter misurare la complessita' computazionale come
funzione dell'entropia dei dati in ingresso e quella dei dati in uscita.
Non sono mai andato al di la' del "wishful thinking", pero'.
Ciao,
Nicola

 Non sono mai andato al di la' del "wishful thinking", pero'.
Meglio :-)  Ho scarsa stima dei teorici (in qualunque campo, e nel
calcolo numerico in particolare [1])...
-------------------------
[1] con l'eccezione di qualcuno, tipo colui che e' stato cosi'
    intelligente da dire "Beware of bugs in the above code; I have
    only proved it correct, not tried it."


 
ok... ho scatenato un dibattito filosofico...:-)
il fatto e' che l'entropia di un file va ben oltre il singolo file... ad es 
l'entropia (sempre teorica) di un QUALSIASI mp3 e' BEN diversa 
dall'entropia di un qualsiasi file di testo (e quando dico qualsiasi 
intendo proprio qualsiasi...)
comunque quello che mi serviva si ferma ben prima del valore ideale... mi 
serviva solo una stima approssimata di quanto un aggeggio qualsiasi tipo 
PKZIP mi avrebbe compresso un file spendendo, nella prova, meno di quanto 
avrei speso nella compressione (in termini di tempo)
comunque tks :-)
Pinolo

 avrei speso nella compressione (in termini di tempo)
Anche in questo caso, a meno di approssimazioni notevoli, non puoi
prescindere dall'algoritmo utilizzato.
Ciao,
Nicola

 So di essere OT e di avere poche chance di risposta, ma comunque provo :-)
Supponiamo, per assurdo, che i file siano composti solo da lettere vocali 
e che il fattore di 'entropia' vada da 1 (max compressione) a 10 (min 
compressione).
Tu vuoi che un file tipo:
AAAAAEEEOOOOUUUUAAAAAIIII
abbia un fattore tendente a 1
ed un file tipo:
AIUOEEAEUIOUUAIAOAEIOAOEU
abbia un fattore tendente a 10?
In questo caso non è difficile....
-- 
Luc.

     only proved it correct, not tried it."
chi e` stato a dirlo?
ciao Anto
-- 
Antonio Cuni, 20 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 chi e` stato a dirlo?
Donald Knuth, nel 1977
