Newsgroup: it.comp.lang.pascal
Titolo: zippare?

salve,
vorrei kiedere 2 cose:
- Cosa significa (a livello strutturale del file) zippare?
- E' difficile creare un prog. in pascal ke lo faccia?
grazie
--
DArK
===============================
         ThE DArKneSS Is JuST DArK
===============================

 ha scritto nel messaggio
news:Gqx%8.25086$GV2.6...@twister2.libero.it...


io conosco l'algoritmo di huffman..
allora.
pensa ad un file come un testo di italiano.
noterai che certe lettere appaiono più frequentemente
di altre (per esempio una "E" appare di più di una "Z" no?)
bene. il tutto si basa sul calcolo delle frequenze dei "simboli"
del tuo testo. Un carattere in termini di bit occupa sempre otto
byte giusto (spero di nn sbagliare almeno qui, vado 1 po' ad intuito)?
Ok. metti che in binario la lettera A sia 00000000 (otto zeri). vedi che
occupa tanto? il concetto di compressione sta nel fatto di riuscire a
rappresentare lo stesso simbolo con meno bit.. (facile a dirsi).
l'algoritmo di huffman si basa sulla creazione di alberi binari creati
in base alle frequenze.
ma come creare gli alberi binari? qui di seguito ti spiego come,
anzi lo fa carlo landini (non so chi sia, ho trovato questa ottima
spiegazioni
un paio d'anni fa)
Il problema principale dell'algoritmo è come costruire l'albero, da
costruire
"al contrario" cioè dalle foglie alla radice.. poi non è che sia
impossibile, ma
se riesci ti senti "potente" :-) . A noi pensa che lo fanno fare a scuola!
Se vuoi ho i sorgenti per C++ e Visual Basic.. però pascal mi manca!
Se lo fai e mi permetti, ti faccio una sezione sul mio sito!
Bye Cereal
----------------------------------------------------------------------------
ALGORITMO DI HUFFMAN                 Carlo Landini - 
lan...@ala.it
NB: impostare un carattere equispaziato per leggere meglio le tabelle
(Courier, Fixedsys etc)
Si costruisce una tabella in cui ad ogni simbolo del messaggio originale si
associa la sua frequenza, cioe' il numero di volte in cui questo simbolo
appare nel messaggio da spedire. La tabella si usa piu' facilmente se e'
ordinata secondo la frequenza. Esempio: voglio spedire la frase "SOPRA LA
PANCA LA CAPRA CAMPA, SOTTO LA PANCA LA CAPRA CREPA". Ottengo questa tabella
di frequenze: (sp e' lo spazio, vr e la virgola)
A 16
sp 11
P 7
C 6
L 4
R 4
O 3
N 2
S 2
T 2
E 1
vr 1
M 1
Si considerano i due simboli meno frequenti (vr e M) e si raggruppano in un
unico simbolo del quale si introduce in tabella la SOMMA delle due
frequenze. Si associa un bit zero al primo simbolo considerato, un bit 1 al
secondo e si riordina la tabella delle frequenze. Abbiamo quindi:
codici        tabella
Huff          frequenze
A             A     16
sp            sp    11
P             P     7
C             C     6
L             L     4
R             R     4
O             O     3
N             N     2
S             S     2
T             T     2
E            (vr-M  2)
vr  (0)       E     1
M   (1)
Nota: fra parentesi i bit aggiunti a questo passaggio e il nuovo simbolo
Si considerano ancora i due simboli meno frequenti, in questo caso vrM di
freq 2 ed E di freq 1. Si raggruppano in un unico gruppo di freq 3,
aggiungendo il bit 0 a tutti i simboli del primo gruppo (vr e M), e un bit 1
a tutti i simboli del secondo gruppo (la E). Si ottiene:
codici        tabella
Huff          frequenze
A             A      16
sp            sp     11
P             P      7
C             C      6
L             L      4
R             R      4
O             O      3
N            (vrM-E  3)
S             N      2
T             S      2
E   (1)       T      2
vr  (0)0
M   (0)1
Ora i gruppi da considerare sono S e T:
A             A      16
sp            sp     11
P             P      7
C             C      6
L             L      4
R             R      4
O            (S-T    4)
N             O      3
S   (0)       vrME   3
T   (1)       N      2
E   1
vr  00
M   01
e cosi' via fino ad ottenere un gruppo solo:
A             A       16
sp            sp      11
P             P       7
C             C       6
L            (vrME-N  5)
R             L       4
O             R       4
N   (1)       ST      4
S   0         O       3
T   1
E   (0)1
vr  (0)00
M   (0)01
A             A       16
sp            sp      11
P             P       7
C            (ST-O    7)
L             C       6
R             vrMEN   5
O   (1)       L       4
N   1         R       4
S   (0)0
T   (0)1
E   01
vr  000
M   001
A             A       16
sp            sp      11
P            (L-R     8)
C             P       7
L   (0)       STO     7
R   (1)       C       6
O   1         vrMEN   5
N   1
S   00
T   01
E   01
vr  000
M   001
A             A        16
sp            sp       11
P            (C-vrMEN  11)
C   (0)       LR        8
L   0         P         7
R   1         STO       7
O   1
N   (1)1
S   00
T   01
E   (1)01
vr  (1)000
M   (1)001
A             A        16
sp           (P-STO    14)
P   (0)       sp       11
C   0         CvrMEN   11
L   0         LR        8
R   1
O   (1)1
N   11
S   (1)00
T   (1)01
E   101
vr  1000
M   1001
A            (CvrMEN-LR  19)
sp            A          16
P   0         PSTO       14
C   (0)0      sp         11
L   (1)0
R   (1)1
O   11
N   (0)11
S   100
T   101
E   (0)101
vr  (0)1000
M   (0)1001
A            (PSTO-sp    25)
sp  (1)       CvrMEN-LR  19
P   (0)0      A          16
C   00
L   10
R   11
O   (0)11
N   011
S   (0)100
T   (0)101
E   0101
vr  01000
M   01001
A   (1)      (CvrMENLR-A 35)
sp  1         PSTOsp     25
P   00
C   (0)00
L   (0)10
R   (0)11
O   011
N   (0)011
S   0100
T   0101
E   (0)0101
vr  (0)01000
M   (0)01001
A   (0)1      (CvrMENLRA-PSTOsp  60)
sp  (1)1
P   (1)00
C   (0)000
L   (0)010
R   (0)011
O   (1)011
N   (0)0011
S   (1)0100
T   (1)0101
E   (0)00101
vr  (0)001000
M   (0)001001
Fine del procedimento, il codice di Huffman e'
A   01
sp  11
P   100
C   0000
L   0010
R   0011
O   1011
N   00011
S   10100
T   10101
E   000101
vr  0001000
M   0001001
Si notano alcune cose importanti:
- i simboli piu' frequenti si codificano con sequenze di bit piu' corte, con
evidente risparmio di spazio.
- la frequenza totale dell'ultimo gruppo trovato e' 60, uguale alla somma
delle frequenze iniziali (ovvio, ma serve per verifica)
- il codice generato non e' l'unico che si poteva generare, infatto ad ogni
passaggio la scelta di associare ai due gruppi 0 e 1 oppure 1 e 0 non fa
cambiare la lunghezza finale dei simboli
- la lunghezza media del codice generato si calcola moltiplicando le
frequenze per le lunghezze generate, sommando il tutto e dividendo per la
frequenza totale
sorg    Huffman    lunghezza    frequenza     calcolo
A       01           2             16        16x2 = 32
sp      11           2             11        11x2 = 22
P       100          3             7          7x3 = 21
C       0000         4             6          6x4 = 24
L       0010         4             4          4x4 = 16
R       0011         4             4          4x4 = 16
O       1011         4             3          4x3 = 12
N       00011        5             2          5x2 = 10
S       10100        5             2          5x2 = 10
T       10101        5             2          5x2 = 10
E       000101       6             1          6x1 =  6
vr      0001000      7             1          7x1 =  7
M       0001001      7             1          7x1 =  7
                                                  -------
                                               tot 193 / 60 =
                                     bit per simbolo    3.216
La frase di partenza deve essere codificata sostituendo ad ogni simbolo la
sequenza di bit di Huffman, poi impacchettata a byte e memorizzata. Si
ottengono 193 bit, cioe' 17 byte invece dei 60 di partenza.
Huffman e' molto piu' efficace su distribuzioni di frequenza molto
disomogenee, cioe' con pochi simboli a frequenza alta e tanti simboli a
frequenza bassa. Se la distribuzione e' troppo omogenea puo' diventare
addirittura piu' lungo dell'originale.
Importante memorizzare insieme al messaggio codificato anche la tabella di
conversione!

 - E' difficile creare un prog. in pascal ke lo faccia?
Se hai dimestichezza con alberi, liste, tabelle hash e dizionari, non
avrai molta difficolta', tuttavia se devi tirare su delle applicazioni
in breve tempo, allora puoi ricorrere a librerie gia' scritte, tra cui
un comodo add-on a riga di comando per lo stesso WinZip.

 - E' difficile creare un prog. in pascal ke lo faccia?
Mmmmmmmmmmm niente è difficile, soltanto complicato o lungo.
E poi lo si può fare in Pascal come in VB come in assembly (ma io non lo
farei mai in assembly).
L'algoritmo più diffuso è quello di Huffman, ma ce ne sono anche altri.
Googla un po' e vedi che trovi tutto quello che vuoi.
--
"La matematica è l'alfabeto con il quale DIO ha scritto l'Universo"
(G. Galilei)

L'algoritmo più diffuso è quello di Huffman, ma ce ne sono anche altri.
A dire il vero sia lo ZIP che il RAR che ACE e anche gli altri usano
tutti Huffman ma ottimizato in modo diverso...
Il Razziatore,
The Only Good Windows is an uninstalled Windows
-----------------------------------------------
E-MAILs : IlRazziat...@NOSPAMnetscape.net
WEB     : 
http://www.razziatore.dns2go.com/
ICQ     : 67552596

 tutti Huffman ma ottimizato in modo diverso...
Si č vero, ma ad esempio ARJ usa un vocabolario interno, di dimensione
variabile. Quindi non sempre si usa Huffman.
--
"La matematica č l'alfabeto con il quale DIO ha scritto l'Universo"
(G. Galilei)

 tutti Huffman ma ottimizato in modo diverso...
Anche, ma non solo.  Di certo non e' l'algoritmo piu' utilizzato da
questi compressori.  Usano prevalentemente il Lempel-Ziv, ottimizzato
in modo diverso.
Lo puoi notare guardando le percentuali di compressione (Huffman
supera scarsamente, nella media dei casi, il 50-60%).

) un prog
Pascal per la compressione con LHArc, in sostanza Lempel-Ziv +
Huffman.
Omega e' omega e basta
ma per le cose buone ci sia sempre posto.