View Full Version : ALGORITMI DI COMPRESSIONE,QUESITO
3nigma666
19-03-2005, 13:06
Cosi a livello intuito ,ho provato a pensare in che modo agiscono gli algoritmi di compressione.. ditemi se ho intuito bene:
Tutti noi sappiamo ke un file è composto da una sequenza di 0 e 1 e proprio su questi va ad agire l algoritmo di compressione.Il modo su cui agisce a mio parere (spero di non dire castronate) è questo:
Se io ho un file ke ad esempio è descritto da questa sequenza di numeri:
0111111111000011111100
L'algoritmo di compressione ke fa? beh sostituisce ad esempio 3 sequenza consegutive di bit = 1 con un solo bit = 1(quindi 111 = 1) quindi il file di prima compresso risultera':
011100001100
Questo modello ke ho appena descritto pero mi suscita dei forti dubbi nel senso ke in questo modo io potrei ancora comprime il file presente raggrupando in un unico bit = 1 i primi 3 bit = 1 ottenendo:
0100001100
ottengo quindi un file "zippato" di un file "zippato" parlando in termini "windowsiani".Potrei teoricamente "zippare" file gia zippati fino ad ottenere un file lungo un solo bit (ad esempio se ho un file composto da soli 1 (e il numero di 1 presenti nel file deve ovviamente essere un multiplo di 3) ..questo è un 1 bel problema,perke non è possibile comprimere un file cosi tanto senza perdere informazioni,visto ke gli algoritmi di compressione di file sono notoriamente di tipo "unless"
Deduco quindi di essere davanti un vicolo cieco e ke la mia "tesi" è sbagliata anke perke se mi trovassi davanti ad un file di questo tipo:
1111001111
e lo comprimo otengo:
110011
Se vado poi a decomprimere per riotenere il file originale otterrei:
11111100111111
è ben visibile il fatto ke il file ottenuto non è assolutamente uguale a quello precedente.Quindi a mio avviso è corretto inserire una specie di bit di controllo
quindi ad esempio ogni volta ke incontro una sequenza di 111 la sostituisco non piu con un solo bit = 1 ma bensi con 10 dove lo 0 fa da separatore cosi il precedente ,se lo comprimo diventera' :
10100101
e quando lo vado a decomprimere pero ottengo lo stesso problema di prima ,ovverosia come faccio a sapere ke nella sequenza 101 lo 0 non è un "bit di controllo" ma è in realta uno zero vero? infatti dal file compresso se lo decomprimo potrei ottenere 3 versioni differenti di file originale:
1) 1111001111
2) 1110111001110111
3) 11111101111
quindi qua sorge il mio dubbio: come faccio a capire come interpretare il bit di controllo??
Avevo pensato magari ke i file compressi ,possiedano una specie di header dove vengono memorizzate le informazioni relative a tutti gli zeri presenti nel file,pero a mio avviso sembra un modo abb. laborioso e tedioso.
Qualcuno sa, o ha qualke idea??
end.is.forever
19-03-2005, 14:26
Al di la degli uni e gli zeri, la compressione senza perdita si basa sul fatto che la maggior parte dei linguaggi/protocolli hanno distribuzioni non omogenee di probabilità delle varie configurazioni di simboli.
Ad esempio se in un file di testo la 'A' si presenta più volte della 'B' si può decidere di scrivere un nuovo file di testo codificato in maniera diversa in modo che la lunghezza della stringa di bit che va a rappresentare 'A' sia più corta di quella che rappresenta 'B'.
Nei casi in cui c'e ridondanza nella rappresentazione dei simboli, o quando semplicemente alcuni simboli sono più probabili di altri (cioè danno meno "informazione") una rappresentazione senza ridondanza e con un modello statistico derivato dall'analisi del testo applicato al codice fornisce sempre una rappresentazione di minori dimensioni del testo totale.
Nel tuo caso l'errore sta nel fatto che il tuo modello di compressione no n prevede di rappresentare in maniera diversa due simboli di significato diverso
tu fai
1111001111 -> 110011
ma in questo modo la stringa finale contiene simboli uguali che rappresentano cose diverse a seconda del contesto, dato che per esempio il primo 1 rappresenta 11 mentre il secondo rappresenta solo 1.
Devi perforza rappresentare in maniera diversa le informazioni, per esempio considerare dei blocchi di tot bit e decidere una funzione biunivoca (mentre la tua non è biunivoca) che associ un blocco per esempio di 5 bit ad un altro blocco di 4 bit, e che venga applicata a tutti i blocchi di 5 bit del testo di partenza, altrimenti il testo finale non è scritto tutto nello stesso codice.
3nigma666
19-03-2005, 14:29
ok fondamentalmente ho capito il concetto,il mio problema è ke la funzione ke io avevo descritto,non era biettiva e di conseguenza il dominio della funzoine di partenza non er ail codominio della funzione diciamo inversa.. ok.. grazie mille
end.is.forever
19-03-2005, 14:37
Originariamente inviato da 3nigma666
Avevo pensato magari ke i file compressi ,possiedano una specie di header dove vengono memorizzate le informazioni relative a tutti gli zeri presenti nel file,pero a mio avviso sembra un modo abb. laborioso e tedioso.
Se facessi così otterresti un file molto più grande dell'originale dato che rappresenteresti nell'header per ogni sostituzione fatta con cosa va sostituita e nel contenuto avresti le informazioni sostituite codificate nel nuovo modo.
La cosa più semplice è stabilire analizzando il file un codice unico del tipo
001->01
010->10
011->11
100->00 (se queste 4 sono le uniche possibili configurazioni di 3 bit presenti nel testo)
che applichi a tutto il testo, per cui
001010011001100001100 -> 01101101000100
e aggiungi al file un header in cui metti la codifica rappresentata in qualche modo; se il file è lungo e contiene ripetizioni di simboli hai un guadagno in dimensioni.
Un algoritmo molto carino che si sviluppa facilmente agli inizi è la compressione/codifica di Huffman... E' un algoritmo che si utilizza praticamente in ogni compressore all'uscita del blocco principale di compressione su una parte dei dati compressi...
Prova a cercare qualcosa su internet (qualcosa che non sia un codice ovviamente)...
ha ragione cionci studiati Huffman
su wikipedia puoi farti un'idea in un paio di minuti
http://it.wikipedia.org/wiki/Codifica_di_Huffman
altrimenti prova sulle dispense di qualche corso di algoritmi e strutture dati
tra l'altro l'implementazione è abbastanza semplice, ne avevo scritta una ai tempi di algoritmi per esercitarmi e non ci avevo messo molto. la compressione era abbastanza buona
Ti consiglioanche di dare un'occhiata anche alla tecnica di Rice Coding ottima quando tratti valori interi. Molto semplicemente scommette che bastino "n" bit per rappresentare un qualsiasi numero. Restando costante la scommessa per tutto (o parte) il flusso, quando incontra un numero che provoca un overflow lo codifica in maniera particolare utilizzando i bit che gli sarebbero serviti per codificarlo normalmente piu' uno per delimitare tale overflow. :)
Dovrei avere da qualche parte l'algoritmo in pseudo-codice :)
Se ti serve fammi un fischio :)
Ciao!
Ziosilvio
20-03-2005, 09:30
Originariamente inviato da 3nigma666
ok fondamentalmente ho capito il concetto,il mio problema è ke la funzione ke io avevo descritto,non era biettiva e di conseguenza il dominio della funzoine di partenza non er ail codominio della funzione diciamo inversa.. ok.. grazie mille
Tieni a mente anche che nessuna trasformazione invertibile tra stringhe binarie è in grado di trasformare sempre una stringa binaria in una stringa binaria più corta.
3nigma666
20-03-2005, 09:39
ok raga ,ho capito finalmente..ho capito ke la mia idea di fondo non era del tutto errata,sbagliavo nel modo in cui sostituivo la ridondanza...e in piu mi avete illlustrato la presenza di diversi algoritmi ke andro a studiarmi molto volentieri.. ah... DUn se hai per caso tempo di postarmi lo pseudo codice mi faresti un favorone ,in quanto lo analizzerei molto volentieri..grazie a tutti .. :D
Un'algoritmo bellissimo è la compressione aritmetica, ma da quanto ho letto dal link sopra, è coperto da un brevetto IBM :mad:
lombardp
21-03-2005, 07:04
Originariamente inviato da 3nigma666
ottengo quindi un file "zippato" di un file "zippato" parlando in termini "windowsiani".Potrei teoricamente "zippare" file gia zippati fino ad ottenere un file lungo un solo bit (ad esempio se ho un file composto da soli 1 (e il numero di 1 presenti nel file deve ovviamente essere un multiplo di 3) ..questo è un 1 bel problema,perke non è possibile comprimere un file cosi tanto senza perdere informazioni,visto ke gli algoritmi di compressione di file sono notoriamente di tipo "unless"
Aggiungo solamente un dettaglio sul "file lungo un bit".
Un concetto molto interessante della teoria dell'informazione è questo: tu hai una sequenza di M bit che contiene una certa informazione. Questa informazione è misurabile, supponi che sia di N bit (con N<M). Anche se sembra ovvio, la sequenza M di bit non potrà mai essere compressa in una sequenza lunga meno di N bit, pena la perdita di informazione.
Quindi, la tua sequenza teoricamente (nella pratica è diverso) potrebbe diventare un file lungo un bit, se il contenuto informativo originario era effettivamente 1 bit. Per esempio: se usi una sequenza (lunga quanto vuoi) per comunicare un ON e un'altra sequenza per un OFF, puoi comprimere questo tipo di messaggi a 1 bit: 0 per OFF e 1 per ON. Perché il contenuto informativo che vuoi comunicare è effettivamente 1 bit.
3nigma666
21-03-2005, 22:36
uhmm .. quindi il limite "fisico" di compressione qual'è? dipende da caso a caso o c'è una equazione ke lo puo stabilire ... o bisogna parlare di statistica? altra cosa ... avete provato a zippare 2 3 volte un file zippato??se provate vedrete ke si ottiene un file piu lungo di quello di zippato una sola volta di qualke byte .. come mai?
Originariamente inviato da 3nigma666
uhmm .. quindi il limite "fisico" di compressione qual'è? dipende da caso a caso o c'è una equazione ke lo puo stabilire ... o bisogna parlare di statistica? altra cosa ... avete provato a zippare 2 3 volte un file zippato??se provate vedrete ke si ottiene un file piu lungo di quello di zippato una sola volta di qualke byte .. come mai?
Il limite fisico di compressione e' limitato dall'entropia dell'informazione ovvero dalla quantita' di informazione contenuta effettivamente nel flusso di bit. Ad esempio se in un canale di trasmissione vengono trasmessi solo i simboli A e B, sebbene su un alfabeto totale di piu' lettere, avro' bisogno di molte meno informazioni per codificare il messaggio.
In altre parole il limite della lunghezza del codice usato in una compressione lossless e' dimostrato essere limitato inferiormente dall'entropia della sorgente. Questo risultato e' dovuto a Shannon e al suo lavoro nella Teoria dell'informazione :)
Dato che hai richiesto l'equazione ho trovato questa definizione di entropia sulle dispense di un corso che ho seguito tempo fa:
H(S) = (Sommatoria al variare di i) di p_i log_2 (1/p_i) dove p_i e' la probabilita' che il valore i-esimo si presenti e log_2 (1/p_i) e' il minimo numero di bit necessario per codificare in modo riconoscibile il valore i-esimo
Per quanto riguarda l'algoritmino di Rice coding:
Algoritmo di Rice Coding (input n, parametro m)
q = n / (2^k);
[overflow] = NIL;
[terminatore] = “1”;
for(i = 0; i < q; i++) [overflow] = strcat([overflow], ”0”);
[num] = “m bit meno significativi di n”;
return [overflow][terminatore][num];
Ciao! :)
Originariamente inviato da 3nigma666
se provate vedrete ke si ottiene un file piu lungo di quello di zippato una sola volta di qualke byte .. come mai?
Perchè se non ci si guadagna il file viene inserito senza compressione...
lombardp
22-03-2005, 06:58
Originariamente inviato da 3nigma666
uhmm .. quindi il limite "fisico" di compressione qual'è? dipende da caso a caso o c'è una equazione ke lo puo stabilire ... o bisogna parlare di statistica?
Come ha egregiamente spiegato Dun, il limite fisico dipende dai dati, o meglio dall'informazione in essi contenuta.
Se hai un file di 1MB che contiene 1kB di informazione "vera", il limite fisico della compressione è 1kB.
altra cosa ... avete provato a zippare 2 3 volte un file zippato??se provate vedrete ke si ottiene un file piu lungo di quello di zippato una sola volta di qualke byte .. come mai?
Procedendo il discorso di prima, una volta compresso il file da 1MB a 1kB, non è possibile comprimere oltre. Infatti se zippi più volte il file, di fatto non ottieni nessuna altra compressione.
Originariamente inviato da lombardp
Procedendo il discorso di prima, una volta compresso il file da 1MB a 1kB, non è possibile comprimere oltre. Infatti se zippi più volte il file, di fatto non ottieni nessuna altra compressione.
Non sempre...solo se si raggiunge il limite minimo... Usando altri algoritmi è spesso possibile comprimere anche un file zip...ed a volte anche usando gli stessi algoritmi...come nel caso di Huffman...
3nigma666
22-03-2005, 09:25
l'equazione ke hai dato è molto utile perke cosi è possibile trovare un programma ke computa la funzione ke prende come un input un file, puo dare una stima della compressione massima su quel determinato file. tnks ..sto iniziando a buttare giu parecchie idee interessanti ... ;)
Originariamente inviato da cionci
come nel caso di Huffman...
intendi in generale o quando Huffman viene utilizzato su pacchetti di dati e non sull'intero flusso?
lombardp
22-03-2005, 13:27
Originariamente inviato da cionci
Non sempre...solo se si raggiunge il limite minimo... Usando altri algoritmi è spesso possibile comprimere anche un file zip...ed a volte anche usando gli stessi algoritmi...come nel caso di Huffman...
Si è chiaro, in fatti avevo usato il modo di dire "di fatto" per far capire che comprimere più dell'informazione non è proprio possibile.
Che poi l'efficienza dei vari formati/algoritmi sia più o meno vicina all'ideale, quello è un difetto del formato/algoritmo, non della teoria. Insomma si riesce a comprimere ulteriormente un file ZIP compresso, solo perché è sensibilmente lontano dalla compressione ideale.
Originariamente inviato da Angus
intendi in generale o quando Huffman viene utilizzato su pacchetti di dati e non sull'intero flusso?
In generale Huffman può essere applicato più volte...ovviamente dipende da quanto siamo lontani dal limite...
E' chiaro che dipende da quale flusso abbiamo in ingresso...
Originariamente inviato da cionci
In generale Huffman può essere applicato più volte...ovviamente dipende da quanto siamo lontani dal limite...
E' chiaro che dipende da quale flusso abbiamo in ingresso...
Riformulo:
ricordo (forse male) che il codice di Huffman è il linguaggio che garantisce la rappresentazione di un blocco di informazione col minimo possibile dei bit. La compressione tramite Huffman immagino quindi che sia un algoritmo che costruisca il codice di H. in base al flusso di informazione in ingresso e rappresenti quest'ultimo tramite il codice di H. appena costruito. Nella mia mente si affacciano due tesi:
1. Il codice di H. permette di raggiungere sempre, per flussi finiti di informazione, il limite inferiore imposto da Shannon.
2. Il codice di H. non può essere compresso.
Dove sbaglio?
Se Huffman fosse come dici tu allora sarebbe l'algoritmo di compressione perfetto... Ti posso dire che avendo fatto un compressore di Huffman, se si riapplica lo stesso algoritmo ad un flusso già compresso in un buona percentuale di casi (intendo tutti quelli che ho provato) il flusso viene ulteriormente compresso...
La compressione raggiunta con il solo algoritmo di Huffman è nettamente inferiore a qualsiasi compressore commerciale...ovviamente casi particolari a parte...
Nell'algoritmo di Huffman la lunghezza della codifica di un simbolo è proporzionale alla sua entropia...l'unica cosa che si può dire è questa...ma raramente la codifica di Huffman è quella ottima cioè quella in cui la lunghezza della codifica di un simbolo è uguale all'entropia...
Originariamente inviato da cionci
Se Huffman fosse come dici tu allora sarebbe l'algoritmo di compressione perfetto... Ti posso dire che avendo fatto un compressore di Huffman, se si riapplica lo stesso algoritmo ad un flusso già compresso in un buona percentuale di casi (intendo tutti quelli che ho provato) il flusso viene ulteriormente compresso...
La compressione raggiunta con il solo algoritmo di Huffman è nettamente inferiore a qualsiasi compressore commerciale...ovviamente casi particolari a parte...
Nell'algoritmo di Huffman la lunghezza della codifica di un simbolo è proporzionale alla sua entropia...l'unica cosa che si può dire è questa...ma raramente la codifica di Huffman è quella ottima cioè quella in cui la lunghezza della codifica di un simbolo è uguale all'entropia...
Il concetto di codifica proporzionale all'entropia mi piace, vedrò di indagare ulteriormente.
E' giunto il tempo che riapra il libro di algoritmi e mi diverta anch'io con Huffman.
Ti farò sapere ;-)
Il fatto che sia proporzionale è banale...visto che la lunghezza della codifica di un simbolo è proporzionale (con i dovuti arrotondamenti) alla frequenza del simbolo ;)
Originariamente inviato da cionci
Il fatto che sia proporzionale è banale...visto che la lunghezza della codifica di un simbolo è proporzionale (con i dovuti arrotondamenti) alla frequenza del simbolo ;)
Se così fosse credo che allora avrei avuto ragione, oppure ho capito male quello che dici.
Comunque ho approfittato di wikipedia (sono in ufficio e non ho il libro di algoritmi a portata di mano) e ho capito cosa ricordavo male: il codice di Huffman è il modo più efficiente di rappresentare simboli in stringhe binarie. Quindi non comprime in maniera ottimale l'informazione stessa ma la sua 'rappresentazione' senza cambiarne la semantica. Da qui credo che derivi il fatto che Huffman venga utilizzato spesso in uscita ad altri metodi di compressione, come hai giustamente detto qualche post fa.
Un esempio di quello che voglio dire:
L'informazione in ingresso è "0111111111111111111111111111111...10", cioè una stringa di n 1 delimitata da 0. Questa rappresentazione mediante i simboli {0, 1} non è migliorabile tramite Huffman o qualsiasi altro algoritmo di compressione che non alteri la semantica dei simboli.
Rilassando quest'ultimo vincolo però potrei utilizzare la seguente rappresentazione:
"0[n volte 1]0"
che rappresenta la stessa informazione mediante l'alfabeto {0, [, ], n, volte, 1}
adesso basta che sto sparando troppe idiozie... meglio che ritorni al lavoro...
Originariamente inviato da Angus
Se così fosse credo che allora avrei avuto ragione
Sì, ma renditi conto che questo algoritmo lavora su un carattere per volta l'informazione relativa alle ripetizioni e alle sequenze che in altra maniera potrebbe essere codificata in questo caso resta comunque non compressa...
Originariamente inviato da cionci
Sì, ma renditi conto che questo algoritmo lavora su un carattere per volta l'informazione relativa alle ripetizioni e alle sequenze che in altra maniera potrebbe essere codificata in questo caso resta comunque non compressa...
E' proprio quello che ho cercato di dire un post fa!
:mano: :ubriachi:
lombardp
23-03-2005, 00:13
Anche se esco un po' dal topic, vale la pena citare anche l'opposto degli algoritmi di compressione, cioè gli algoritmi di correzione d'errore.
Questi algoritmi fanno in pratica l'opposto, cioè introducono nel file opportune ridondanze in modo da poter correggere eventuali errori che si generano. Un esempio banale sarebbe includere nel solito file tre copie esatte dell'informazione, e con un voto di maggioranza escludere eventuali errori. Il file cresce di 3 volte, ma è più "robusto" ad eventuali errori. Ovviamente esistono codifiche di gran lunga più sofisticate, le cui basi matematiche raramente vengono affrontate in corsi universitari che non siano di matematica pura.
Originariamente inviato da lombardp
Ovviamente esistono codifiche di gran lunga più sofisticate, le cui basi matematiche raramente vengono affrontate in corsi universitari che non siano di matematica pura.
Curioso. Mi fai una citazione con riferimento a qualche pagina internet?
lombardp
23-03-2005, 09:36
Originariamente inviato da Angus
Curioso. Mi fai una citazione con riferimento a qualche pagina internet?
In effetti con quella frase mi volevo riferire a qualcosa di molto particolare, la codifica Reed-Solomon.
Sono ing. elettronico, non ho avuto la minima difficoltà a studiare, capire ed implementare la codifica di Hamming, ma quando ho provato con la Reed-Solomon ti confesso che non ci ho capito molto, almeno non abbastanza da implementarla. Da quello che ho capito si basa sulla teoria dei campi finiti di Galois, un argomento che almeno nei miei studi non è stato nemmeno nominato.
Per le pagine inserisci Reed-Solomon su Google e vai!
Originariamente inviato da lombardp
In effetti con quella frase mi volevo riferire a qualcosa di molto particolare, la codifica Reed-Solomon.
Sono ing. elettronico, non ho avuto la minima difficoltà a studiare, capire ed implementare la codifica di Hamming, ma quando ho provato con la Reed-Solomon ti confesso che non ci ho capito molto, almeno non abbastanza da implementarla. Da quello che ho capito si basa sulla teoria dei campi finiti di Galois, un argomento che almeno nei miei studi non è stato nemmeno nominato.
Per le pagine inserisci Reed-Solomon su Google e vai!
Neanch'io negli anni di ingegneria non ho mai sentito nominare l'argomento. Comunque grazie per la citazione, ho trovato qualcosa su google e mi sono immediatamente reso conto che è un algoritmo piuttosto complesso :mc:
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.