ALGORITMI DI COMPRESSIONE,QUESITO

[3nigma666]

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]

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]

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]

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.

[cionci]

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)...

[recoil]

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

[Dun]

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]

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]

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 ..

[cionci]

Un'algoritmo bellissimo è la compressione aritmetica, ma da quanto ho letto dal link sopra, è coperto da un brevetto IBM

[lombardp]

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]

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?

[Dun]

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!

[cionci]

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]

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.

[cionci]

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]

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 ...

[Angus]

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]

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.

[cionci]

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...