Newsgroup: it.hobby.enigmi
Titolo: Come si fa un compressore?

mi speigo, intendo un programma per "comprimere" i files non un compressore
inteso come aria compressa; se 1 carattere sono 8 bit e quindi 1 byte come è
possibile che un algoritmo di compressione possa ridurre lo spazio senza
perdita di informazioni? Qualcuno conosce il principio di base di questi
programmi?

 
Provo a spiegarti il concetto a grandi linee.
Si prende il file da comprimere.
Supponiamo che sia un file di testo per semplicita'.
Dal file estrai tutte le singole parole che lo compongono, conti 
ciascuna quante volte compare, e le metti in ordine per frequenza.
A questo punto alla parola che compare con maggior frequenza attribuisci 
   il numero 1, alla successiva il numero 2, etc...
Esempio.
File originale:
Questa e' la prima riga.
Questa e' la seconda riga.
Questa e' la terza riga.
Questa e' la quarta riga.
File compresso:
[dizionario]
1=Questa
2=e'
3=la
4=riga.
5=prima
6=seconda
7=terza
8=quarta
[file]
1 2 3 5 4
1 2 3 6 4
1 2 3 7 4
1 2 3 8 4
Ecco, questo grosso modo e' il concetto.
Poi in pratica la divisione in parole viene fatta con criteri piu' 
efficienti e il numero da assegnare in ordine di frequenza e' una 
sequenza binaria che va da un minimo di 2 o 3 bit per le parole piu' 
frequenti, fino a anche 32 bit per quelle che compaiono una volta sola.
Infatti la compressione e' piu' complessa della decopressione.
La compressione prevede la ricerca delle sequenze e delle loro 
frequenze, il che richiede complessi algoritmi;
mentre la decompressione agisce sul file gia' compresso che e' diviso in 
due parti: il dizionario e la sequenza di dati, e si tratta 
semplicemente di un lavoro di sostituzione.
Sperando di essere stato chiaro.
Eventualmente domani ti sapro' indicare in rete qualche documento in 
proposito: la rete e' piena e gli algoritmi di compressione sono quasi 
tutti pubblici.

Ludico.Net wrote:

Ricercando informazioni ridondanti e traducendole in una codifica più 
efficiente, che quindi occupa meno spazio.
Dato che un esempio val più di 1000 parole, ti spiego velocemente uno 
degli algoritmi di compressione più antiquato, ma semplice, ovvero il 
Run Lenght Encoding (RLE).
Tu sai che una immagine, ad esempio, è in realtà una "mappa" di byte: 
supponiamo ad esempio di avere una immagine codificata come bitmap a 
scala di grigi a 256 livelli, in cui quindi ogni "punto" dell'immagine è 
un byte che può assumere un valore da 0 a 255. L'immagine completa sarà, 
sempre per supposizione, 1024*1024 pixel, e quindi io avro' una mappa da 
1 Mb per descrivere completamente l'immagine. Pero' è immediato dedurre 
  che, essendo solo 255 i valori possibili per un byte, nel milione di 
punti che mi descrivono l'immagine io avro' sicuramente un sacco di 
punti con valore uguale. E' altamente probabile (anche se dipende, 
ovviamente, dalla natura delle immagini) che questi punti di valore 
uguale siano raggruppati in zone contigue: per fare un esempio pratico, 
si potrebbe pensare a delle lastre radiografiche: una larga parte dei 
punti sono neri, una parte significativa sono bianchi, e i valori 
intermedi sono concentrati nei "bordi" tra zone radioopache e zone 
radiotrasparenti.
Allora io cambio codifica e anzichè limitarmi a mettere un byte dietro 
l'altro metto una seguenza di coppie di byte, in cui il secondo è il 
valore della scala di grigi e il primo è il numero di byte per cui devo 
ripetere tale valore nella mappa.
Se cioè la prima "riga" della mia mappa originale era qualcosa del tipo
0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0...
la codifica RLE è:
10 0 1 1 1 2 1 1 5 0...
come vedi, ho "compresso" la stessa informazione utilizzando meno byte 
(10 anzichè 19).
l'RLE non è un algoritmo particolarmente efficiente e funziona bene solo 
in alcuni casi; è evidente che se ho larghe zone dell'immagine con molte 
variazioni di colore, in realtà è possibile anche che vada ad allargare 
le dimensioni totali della mia immagine. Pero' è un algoritmo 
"lossless", cioè senza perdita di informazione: algoritmi più 
performanti, invece, possono essere costruiti per sacrificare qualcosa.
Dalla considerazioni sulla natura del messaggio da comprimere, sulle 
esigenze di conservazione dell'informazione inalterata o meno, ecc. si 
andrà poi a decidere su qual'e' la giusta codifica (e cioè l'algoritmo) 
da usare per la compressione che si vuole realizzare.
Se ti interessa approfondire le basi teoriche, devi cercare un libro di 
"teoria dell'informazione", dove almeno siano riportati i concetti di 
entropia di un messaggio e della relativa codifica.
Ciao!
-- 
Fabrizio "Hermooz" Ermini

performanti, invece, possono essere costruiti per sacrificare qualcosa.
verissimo, ma non dimenitchiamo che ci sono anche algoritmi loseless
migliori dell'RLE. (quello descritto da Roberto Montaruli, ad esempio)
Saluti,
Natale Fietta

Ludico.Net ha scritto:

Banalizzando, più o meno si basa sullo stesso principio del linguaggio 
parlato; tu ad esempio quando guardi fuori dalla finestra dici "vedo tre 
gatti e due auto", non "vedo gatto gatto gatto, auto auto" (questo 
esempio l'ho letto anni fa su una rivista, e mi sembra parecchio 
azzeccato!   :)
m.


La maggior parte dei programmi si basa sul concetto che quanto più un
evento è raro, tanto più è l'informazione associata, quindi
assegnano agli eventi più frequenti una codifica più corta.
Per esempio immagina una sequenza di un migliaio di caratteri presi da
un alfabeto di 256 (quindi 8 bit per carattere). E poniamo che 745 di
loro siano 'A', mentre i 255 rimanenti caratteri siano ripetuti una
volta sola. Senza compressione la sequenza richiederebbe 8000 bit.
Ma se noi codificassimo la A con un singolo bit, poniamo 0, e gli altri
con una sequenza 9 bit ciascuno (ogni sequenza deve iniziare con 1 per
evitare ambiguità), la lunghezza totale sarà:
745*1 = 745 bit per le A.
9*255 = 2295 bit per le rimanenti lettere.
Totale: 3040 bit (se non ho sbagliato i conti)
Ovviamente ai 3040 bit ne vanno aggiunti altri per immagazzinare la
tabella delle corrispondenze (cioè una tabella che mi dica cha alla A
è associato il bit 0 etc.), e quindi più il file è grande e minore
sarà il peso in percentuale di detta tabella e di conseguenza sarà
migliore la compressione.
Ciao,
GB

 
Come detto da altri esistono vari metodi per comprimere un file, e'
importante sapere che diversi metodi vanno bene per diversi tipi di
files e che non puo' esistere un metodo che comprime qualsiasi file
(anche riducendolo di un solo byte). Per una introduzione ai vari metodi
di compressione ti consiglio di leggere la FAQ del newsgroup
comp.compression.research (e' in inglese ma abbastanza facile) che puoi
trovare in 
http://www.faqs.org/faqs/compression-faq/part1/preamble.html
La parte 2 e' quella che piu' ti interessa.
Ciao,
      Gorgo

    il numero 1, alla successiva il numero 2, etc...
quindi possiamo dire che il file deve avere una lunghezza "minima" per
poter usufruire della compressione senza che questa risulti in una
dimesione maggiore del file originale?

 Run Lenght Encoding (RLE).
è ancora usato? sotto quale nome? .zip .rar .ace ecc...

 dimesione maggiore del file originale?
Non e' questione di lunghezza del file, ma di "entropia", ovvero della 
suddivisione statistica della probabilita' dei vari simboli.
I vari algoritmi di compressione riducono l'entropia e tendono a dare 
uno spettro al rumor bianco... e questo e' ovvio, altrimenti applicando 
piu' volte l'algoritmo di compressione, arriveresti per assurdo a file 
di lunghezza uno!
La prova e' semplice: se zippi un file .JPG, .GIF, .PDF, che sono gia' 
compressi, non ottieni niente di significativo anzi spesso il file 
finale e' piu' grosso.
Max

 č ancora usato? sotto quale nome? .zip .rar .ace ecc...
E' usato per le immagini grafiche compresse con RLE.
E' un algoritmo che e' altamente efficiente nelle immagini grafiche fino
a 256 colori proprio perche' e' molto probabile la presenza di n bytes
consecutivi tutti uguali codificati con un solo byte.
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 č ancora usato? sotto quale nome? .zip .rar .ace ecc...
E' usato per le immagini grafiche compresse con RLE.
E' un algoritmo che e' altamente efficiente nelle immagini grafiche fino
a 256 colori proprio perche' e' molto probabile la presenza di n bytes
consecutivi tutti uguali.


 ciascuna quante volte compare, e le metti in ordine per frequenza.
mi è venuto un dubbio adesso, ma con la punteggiatura come
si fa? voglio dire mettere un numero per tutte le virgole finisco
con occupare + spazio; come vengono gestite le ricorrenze
molto frequenti ma di limitata dimesione (come una virgola o un
punto)?

 punto)?
Per quanto la dimensione sia limitata, sarà comunque pari almeno al
valore del simbolo più breve tra quelli componenti il messaggio (in
questo caso un char). E un buon algoritmo di compressione assegna a
tutti i componenti del messaggio di alta frequenza un simbolo di
lunghezza minima, quindi il problema non si pone...

consecutivi tutti uguali codificati con un solo byte.
L'ho visto applicare anche alle immagini 24 bit, separatamente ai
canali RGB. ma non vorrei andare troppo OT, mi pare questo sia
it.hobby.enigmi, non it.hobby.informatica ;-)
Saluti,
Natale Fietta

 un simbolo di lunghezza minima
si ma meno di un simbolo che gli assegna? assegnare
ad un carattere un altro carattere che utilità può avere?
Come funziona in pratica?


un carattere e' composto da 8 bit. Nulla vieta di usare meno
di 8 bit per esprimere caratteri che sono molto frequenti
(e piu' bit per quelli meno frequenti, tipo 4 bit per codificare una E e 10 bit
per codificare una X).
In effetti molti compressori si basano su due fasi di compressione:
nella prima si costruisce una specie di dizionario col testo stesso
(magari in una sliding window) e quindi il messaggio viene
codificato in funzione di se stesso con un output del tipo:
...ciao (4 caratteri che ho visto 12 caratteri fa) tu
(5 caratteri che ho visto 231 caratteri fa) ... (3 caratteri che ho visto 4
caratteri fa)....
poi questa codifica viene ulteriormente compressa basandosi sulle
frequenze relative non solo dei caratteri "in chiaro" ma anche
delle combinazioni (x caratteri visti y caratteri fa)
(quindi in totale ci saranno piu' di 256 possibili simboli, ma questo
non cambia il metodo generale successivo basato sulle frequenze).
Come ti hanno gia' scritto questa codifica basata sulle frequenze dei
simboli si basa spesso (ma c'e' anche la codifica aritmetica che e' un po'
diversa) sul fatto di esprimere i simboli piu' frequenti con meno bit e
quelli piu' frequenti con piu' bit. Un esempio di questo tipo di codifica
e' la Huffman. La cosa tricky di queste codifiche a numero di bit variabile
e' che non essendo tutti i codici di 8 bit devo anche avere un modo
per capire dove inizia e dove finisce un codice.
Cioe' se pongo A='10'; E='11';....; Z='1110'
e poi leggo 101110 non so se corrisponde a AEA oppure ad AZ.
Quello che si fa e' scegliere codici (l'algoritmo di Huffman lo fa
"automaticamente") tali che non abbiano parti comuni iniziali che possano
generare ambiguita'.
ciao,
g.

 di 8 bit per esprimere caratteri che sono molto frequenti
mi mancava questo, come faccio io a
scrivere un carattere con meno di 8 bit?



In un certo senso non si puo'... il "trucco" e' che non ti serve
scrivere un singolo carattere, ma una sequenza di caratteri
consecutivi.
Facciamo un semplice esempio: mettiamo di aver compresso una breve
parola ottenendo la seguente codifica per i vari caratteri (uso una
lettera per ogni bit)
aa  bbbb  cccc  dd  eeeee  fff  gggg
essi vengono "impacchettati" in questo modo per avere i soliti byte di
8 bit
aabbbbcc  ccddeeee  efffgggg
cosi' possiamo salvare il tutto in 3 byte complessivi.
Saluti,
Natale Fietta


SPETTACOLO!! Appena finisco di fare il MOD mi ci
voglio dedicare, sembra interessante dal mio punto
di vista (miope magari) :) grazie a tutti per le info

migliori dell'RLE. (quello descritto da Roberto Montaruli, ad esempio)
Ciao, Natale !!! E' la prima volta che ti leggo su questo NG... eri un
lurker incallito, o sono distratto io ? ;-)
Volevo solo aggiungere, anche se dovrebbe essere ovvio, che gli
algoritmi lossless (es. ZIP, RAR per uso generale, GIF per le immagini
ecc.) sono indispensabili se si vogliono comprimere files in cui anche
la minima perdita di informazione renderebbe "inutilizzabile" il file,
una volta decompresso. Esempio, un file EXE, ma anche un testo. Per le
immagini in cui è tollerabile una perdita di qualita', col vantaggio
di una maggiore compressione, si possono usare compressori "non
lossless", classico esempio il JPEG. Il bitmap rigenerato dal file
compresso non sarà ovviamente uguale all'originale ma più "grezzo":
finche' le dimensioni dell'immagine sono relativamente piccole la
differenza è inavvertibile, ma se la si ingrandisce la degradazione
qualitativa diventa prima o poi evidente.
Chiusa OT... anche se l'argomento puo' ben essere "enigmatico" per chi
non e' addetto ai lavori ! 
Robby
-
-------------------------------------------------------------
Per risposte private, togliere TUTTE le "x" dal mio address !
For private replies, remove ALL the "x" from my address !
-------------------------------------------------------------