Newsgroup: it.comp.programmare
Titolo: Esistono algoritmi di compressione lossless non-huffman?

Ciao,
per comprimere i dati e i programmi si usano degli
algoritmi di compressione (Lempel-Ziv per esempio)
che "ricodificano" i file rimuovendo la ridondanza,
esattamente come fa l'algoritmo di Huffman; cioč
(correggetemi se sbaglio) semplici miglioramenti
dell'algoritmo di Huffman che non apportano nessuna
novitŕ "concettuale" di rilievo e che quindi hanno
gli stessi limiti prestazionali dell'Huffman stesso.
Ora, mi interesserebbe sapere se esiste un algoritmo
di compressione lossless come l'Huffman (quindi
adatto per comprimere files che *devono* restare
identici prima e dopo la compressione) che NON
siano basati sul concetto di eliminazione della
ridondanza, cioč che non partono dall'algoritmo di
Huffman ma si basano su altri principi/presupposti...
Voi ne conoscete? Conoscete qualche sito in cui
cercare info? Finora in rete ho trovato solo algoritmi
simil-Huffman...

 simil-Huffman...
Provato con CiteSeer? 
http://citeseer.nj.nec.com/cs
-- 
Roberto Lupi

 preservare.
Non è detto. Voglio dire che _per ora_ l'unico modo che
si conosce per comprimere è eliminare la ridondanza, ma
non si può escludere che esistano altri metodi che con
la ridondanza non hanno nulla a che fare... io cercavo
appunto (se c'è) uno di questi metodi "alternativi".

 appunto (se c'è) uno di questi metodi "alternativi".
Non sono un esperto ma onestamente non mi viene in mente cos'altro si
possa togliere a parte i dati ridondanti per risparmiare bit. Come
diceva Roberto compressione = (o quasi) eliminazione dei dati
ridondanti. Per definizione ciò che non è ridondante è un informazione
utile, quindi la sua eliminazione impedirebbe di tornare esattamente ai
dati iniziali.
Mi sbaglio ?
--  
Ciao
Wezzy

 Mi sbaglio ?
Non lo so... forse sě, forse no.
Forse č possibile fare di meglio.
Come non so, ma forse sě.

Huffman ma si basano su altri principi/presupposti...
Lempel-Ziv è esattamente uno di questi (loss-less).  L'eliminazione
della ridondanza è l'elemento chiave per la compressione dei dati.
Non troverai mai un algoritmo di compressione che prescinda da ciò: la
compressione dati ha senso d'esistere *PROPRIO* perché esiste la
ridondanza.

si conosce per comprimere è eliminare la ridondanza
Ti sbagli: come già detto, una tecnica loss-less di compressione
server PROPRIO a ridurre la ridondanza.

byte di 8 bit arriva massimo all'87,2% di compressine (8:1). 
Ovviamente è 1-1/8 = 0.875, quindi 87.5%

, 
massim...@hotmail.com
 says...

Forse è il caso di definire "ridondanza" prima di continuare. Per come 
la vedo io, una sequenza priva di ridondanza è una sequenza di simboli 
elementari equiprobabili.
Un tale sequenza non può essere compressa, è facile dimostrarlo per 
assurdo: se ciò avvenisse i simboli che la compongono non sarebbero 
equiprobabili il che nega l'ipotesi. Q.E.D.
(Correggetemi se sbaglio, l'ora è tarda e la concentrazione latita)
-- 
Roberto Lupi

Uno è questo:
huffyuv
è un codec lossless opensource.. lo puoi usare senza problemi.. un
sito in cui trovarlo credo sia questo:
http://www.divx-digest.com/software/huffyuv.html
Ciao Cris

 elementari equiprobabili.
Come "definizione" questa e` peculiare assai!  Se mai, puoi _dimostrare_
il tuo asserto dopo avere dato una definizione di ridondanza basata
sulla teoria dell'informazione (fondata da Shannon).
Supponiamo di avere una FONTE (o 'sorgente') di messaggi che emette
messaggi: i possibili messaggi sono elementi di un insieme finito (per
semplicita`; notare che, ponendo un limite superiore, ad esempio il
fattoriale del numero di particelle elementari nell'universo, alla
dimensione/complessita` degli apparati di elaborazione, i messaggi
digitali possono sempre essere considerati come elementi di un insieme
finito -- quindi, rimuovere questa ipotesi semplificativa non e`
strettamente necessario ai fini pratici).
La fonte emette ciascun messaggio Mi con una probabilita` Pi (con
le solite regole della teoria della probabilita`: 0<Pi<1, e la somma
dei Pi per tutti i possibili i e` esattamente 1).
Seguendo Shannon, definiamo "quantita` di informazione" in un
messaggio Mi il -log(Pi) in una qualche base che ci faccia comodo
(si usa normalmente base 2, cosi` esprimendo la quantita` di
informazione in quello che Shannon defini` come unita` di misura
"bit" -- ma ovviamente usare base e, ottenendo come unita` di
misura il "nit", o qualsiasi altra base fissa, e` solo questione
di un fattore moltiplicativo, e totalmente indifferente qui).
Con questa definizione, quando la fonte emette un messaggio che
era molto probabile che emettesse ci da` poca informazione; al
contrario, riceviamo molta informazione se veniamo "sorpresi", cioe`
se la fonte emette un messaggio che, a priori, era poco probabile.
Il dibattito filosofico ed epistemologico su questo concetto di
"informazione" e` interminabile, ma qui notiamo solo che c'e` una
certa corrispondenza con l'uso comune/intuitivo del termine: se
ricevo un messaggio che mi aspettavo pienamente non ho imparato
molto di nuovo, mentre se il messaggio mi stupisce (quindi la sua
probabilita` a priori era bassa) ho "imparato" di piu` -- "ho
ricevuto piu` informazione", dunque, non e` un modo assurdo di
porre la problematica.
Quanta informazione mi aspetto di ricevere da un messaggio di
questa fonte?  La definizione di "valore atteso" della teoria
delle probabilita` chiaramente si applica: il valore atteso della
informazione che ricevero` e` la somma pesata (secondo i valori
delle probabilita` di ciascun messaggio) della quantita` di
informazione portata da ciascun messaggio.  Quindi, con la detta
definizione, la somma di Pi * -log(Pi) per tutti i possibili i.
Se ciascun messaggio della fonte e` espresso ("codificato") come
una sequenza di bit Si, allora posso esaminare anche il valore
atteso della LUNGHEZZA (in bit) dei messaggi: e` la somma di
Pi * len(Si), ovviamente.
Infine, posso definire la fonte (inclusa la codifica) come "non
ridondante" se e solo se:
    sommatoria di Pi * len(Si) <= sommatoria di Pi * -log(Pi)
I teoremi interessanti qui sono: non esiste alcuna codifica per
cui valga il segno di < ; _esiste_ (asintoticamente!) almeno una
codifica per cui vale il segno di =.  Questo "asintoticamente"
si riferisce al fatto che in generale, per trovare una codifica
ottimale, devo potere "accorpare" sequenze (in generale, sequenze
lunghe a piacere, da cui l'uso di "asintotico") di messaggi della
fonte in una singola codifica.
Ad es, se la fonte emette due soli possibili messaggi M0 e M1
con probabilita` rispettivamente 0.75 e 0.25, visto che non posso
codificare UN messaggio in meno di UN bit, non posso (senza poter
accorpare sequenze di messaggi) avere come valore atteso della
lunghezza in bit del messaggio quello 0.81127812... che e` il
valore atteso della quantita` d'informazione della fonte; e`
infatti chiaro che non posso scendere sotto 1.0 senza accorpare.
In generale questo "dettaglio" dell'accorpamento ha importanza
solo per fonti con relativamente pochi messaggi diversi (o piu`
precisamente, con quantita` attesa d'informazione piccola) e in
pratica possiamo ignorarlo quando parliamo di "compressione di
file", visto che i possibili diversi file da coprimere (o piu`
precisamente la quantita` attesa d'informazione per file) sono
in numero sufficientemente elevato da non causare problemi in
quest'ambito.
E dunque, se ricevo messaggi dalla fonte con una codifica tale
che la sommatoria di Pi*len(Si) sia maggiore della sommatoria
di Pi * -log(Pi) posso dire di avere "ridondanza", _E_ posso in
teoria trovare una transcodifica (cambiamento di codifica dei
messaggi) senza ridondanza (o almeno con ridondanza minore) e
quindi con una lunghezza attesa minore per i messaggi.  Questo
processo e` detto anche "compressione".  Ovviamente, dunque, la
compressione altro non puo` essere che eliminare ridondanza.
Cio` detto, non e` minimamente necessario che la ridondanza si
elimini con ragionamenti in termini di "simboli elementari".
Nulla osta, in teoria, ad assegnare semplicemente una data
stringa di bit (ciascuna di diversa lunghezza) ad ogni possibile
messaggio (visto che abbiamo detto che i messaggi sono elementi
di un insieme finito...); nulla impone che queste stringhe di
bit siano "sequenze di simboli elementari equiprobabili".  La
teoria delle codifiche che SONO limitate ad essere sequenze di
questo tipo porta a sottoproblemi interessanti, tipo quello
relativo a come i messaggi vengono _delimitati_, ma personalmente
non la tirerei in gioco parlando delle basi astratte dei concetti
di informazione, ridondanza, e compressione.
Alex

 
http://www.divx-digest.com/software/huffyuv.html
Ehm huffyuv sta per HUFFMAN-YUV :-)
č un codec huffman :-)

 sulla teoria dell'informazione (fondata da Shannon).
Hai perfettamente ragione e ti ringrazio per aver chiarito la questione.
Ho dato quella descrizione di sequenza priva di ridondanza guidato 
dall'abitudine piu' che dalla memoria delle basi di teoria 
dell'informazione. Sto preparando un paper (tesina) per l'universita'[1] 
su un particolare approccio alla compressione e, nell'ambito di tale 
lavoro, quella descrizione ha senso.
Per chiarire, abbiamo affrontato il problema della compressione 
utilizzando alcuni strumenti forniti dall'intelligenza artificiale 
(algoritmi genetici e kernel machines). Trasformiamo cosi' l'atto di 
comprimere nell'atto di costruire un programma in grado di generare la 
sequenza originale.
In tale ambito, si puo' parlare di simboli elementari in 
contrapposizione a simboli compositi o ricorsivi - perche' la 
rappresentazione utilizzata per i cromosomi equivale ad un linguaggio di 
programmazione (basato su una versione limitata -nello spazio e tempo 
d'esecuzione- del lambda-calcolo) che supporti la composizione e la 
ricorsione (funzioni di ordine superiore e combinatori Y).
Una kernel machine (SVM non lineare) e' impiegate per costruire cio' che 
chiamiamo simboli elementari, semplici sequenze dati, che costituiscono 
la "base" del nostro segnale i cui elementi vengono combinati in modo 
non lineare dagli individui (programmi) selezionati dall'algoritmo 
genetico.
Questa tecnica sfrutta le interdipendenze nel segnale in modo differente 
rispetto ai classici algoritmi di compressione, perche' cerca di 
costruire una definizione implicita del segnale (eg. puo' comprimere una 
la sequenza di numeri naturali ordinati di lunghezza N in una 
rappresentazione equivalente a: f(0) = 1; f(x) = f(x-1)+1; 0 < x < N).
-- 
Roberto Lupi
[1] Ho commesso l'errore di lasciar perdere gli studi un paio d'anni fa 
e sto cercando di rimediare.

Me ne sono reso conto quando ho premuto il tasto post...:))
heheh figura dimmerda..:)
speravo glissassi..:Ppp