Newsgroup: it.scienza.informatica
Titolo: Compressione files in "perdita"?

Tempo fa cercando di capire qualcosa sulla compressione digitale lessi un po` di materiale tra cui la documentazione (non approfondita) di come funziona l'algoritmo alla base del mitico WinZip (LZW e derivati).
E vi trovai scritto che, in teoria, con determinate sequenze di bit poteva succedere addirittura che il file compresso occupasse piu` spazio dell'originale!
Se non ricordo male cio` succedeva con sequenze casuali di bit che, per fortuna, non capitavano quasi mai nei tipici formati da comprimere.
Qualche giorno fa ho deciso di portarmi a casa su un dischetto il bookmark di Internet Explorer che ho sul PC aziendale e mi e` successa questa cosa curiosa:
  dimensione folder Bookmark non compresso = 71.2Kb
  dimensione files  Bookmark.zip           = 153Kb
Qualcuno mi sa spiegare cosa e` successo?
Il folder contiene solo sottofolder e files del tipo "Internet Shortcut" che mi aspetto siano piccolissimi files di testo con l'URL dell'indirizzo internet memorizzato. Quindi non riesco a motivarmi l'aumento di dimensione, qualcuno me lo sa spiegare?
Grazie
P.S. fra l'altro ricordo anche di aver letto che l'algoritmo in questione ha uno "switch intelligente" per evitare di produrre un file piu` grosso di quello ricevuto, accortosi di questa anomalia infatti si limita a tenere il file originale. Perche` non e` successo?
------------------------------------------
Posted via web GlobalNews
www.globalnews.it
------------------------------------------

 P.S. fra l'altro ricordo anche di aver letto che l'algoritmo in questione ha
uno "switch intelligente" per evitare di produrre un file piu` grosso di quello
ricevuto, accortosi di questa anomalia infatti si limita a
tenere il file originale. Perche` non e` successo?
Credo che tu abbia capito che il problema non e' la mancata compressione ma il
fatto che hai misurato due cose diverse (contenuto file in un caso, e contenuto
file + informazioni sui file nell'altro).
Il mio consiglio: archivia la tua gerarchia di folder in un file .zip salvando i
pathname completi (nota che le directory vuote non vengono comunque salvate) ma
specificando "compression: none". Poi comprimi il file .zip ottenuto. Alla fine
otterrai un file .zip che contiene un altro file .zip. Solo che quello esterno
serve per comprimere e quello interno serve per "archiviare". Dato che il tipo
di dati contenuti negli "internet shortcut" e' molto simile a quello gestito dal
formato .zip per i nomi dei file stessi, il primo passaggio (il file .zip
interno) fallo con compressione settata a "none". In teoria (ma andrebbe
verificato) il risultato della compressione finale e' migliore.
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

In teoria (ma andrebbe verificato) il risultato della compressione finale e' >migliore.
Eccome se lo e`...
Grazie, ora ho qualche dubbio in meno!


 Qui non ti seguo. Gli "internet shortcut" contengono gia` di loro informazione
compressa?
No. Contengono informazione principamente testuale ma non al 100% (possono
esserci alcuni byte 'binari'). Praticamente lo stesso genere di informazione che
il formato .zip usa nell'archivo. Ricorda che il .zip e' composto da due parti:
le informazioni dei file (eventualmente compresse) e quelle SUI file (non
compresse). Queste ultime non sono compresse e sono per buona parte (i nomi dei
file) testuali e per altra (minor) parte binarie. Proprio come gli shortcut di
windows.
In generale un file comprime meglio se e' "omogeneo" nel tipo di dati che
contiene perche' la ridondanza e' sempre dello stesso tipo e gli algoritmi di
predizione della ridondanza si basano sui byte precedenti per predire quelli
futuri. Per questo e' probabile che tu possa comprimere meglio, al secondo
passaggio (che ti serve per comprimere le informazioni SUI file), un file .zip
le cui informazione DEI file sono omogenee con quelle SUI file (ovvero nel
nostro caso non sono compresse).
Se non mi segui non importa.
L'importante e' che nel tuo caso specifico (tanti file piccoli) conviene
comprimere due volte (sia il primo passaggio sia meglio con o senza compressione
dipende da caso a caso e in questo dovrebbe essere meglio farlo senza. Ma e'
tutto da verificare).


Direi che sei davvero un ottimo insegnante.
A questo punto mi resta un solo dubbio. Perche` non vengono compresse anche le informazioni SUI file:
1. si ritiene che occupino parte irrilevante rispetto le informazioni DEI file e percio` si trascurano (quello in cui sono incappato io in effetti e` un caso raro: tantissime directory e tantissimi file di piccolissima dimensione)
2. troppo lavoro per il compressore che deve comunque mantenere nel file compresso le informazioni sulla struttura archiviata e quindi si limita ad ottimizzare quest'ultima (come mi hai fatto notare molto piu` efficiente della FAT del floppy) senza poi comprimerla (che poi come farebbe? Dovrebbe per forza fare due "passate" come abbiamo noi "a mano" giusto?).
Concludo con una domanda a questo punto inevitabile: dove posso trovare materiale informativo su come e` strutturata questa misteriosa informazione SUI file? Un qualsiasi manuale Unix in effetti spiega in dettaglio come e` composto questo "overhead" di byte necessario a gestire il file system ma di DOS/Windows non so nulla!
Ciao


 DOS/Windows non so nulla!
Facciamo un distinguo:
-) formato di archiviazione
-) file sistem
Per i formati di archiviazione (tipo .zip) bisogna cercare documentazione su
quel formato. Quella di un file zip da qualche parte e' documentata (prova il
sito di PkWare). Io avevo qualche info qualche cosa come 10 o 15 anni fa ma non
ho idea di dove sia (ammesso lo abbia ancora). In generale pero' ti serve solo
se devi scrivere un programma tipo WinZip. E a questo punto il problema grosso
non e' tanto il formato di archiving ma gli algoritmi di compressione (trovi
vari testi in merito in una buona libreria).
Un formato che quasi certamente e' piu' documentato e' il tar usato sotto unix.
Se hai accesso a una distribuzione linux dovresti poter accedere alle info di
qualche formato di archiviazione e anche di qualche formato di compressione
(vedi estensioni .z o simili).
Per i file system la cosa e' MOLTO diversa.
Per cominciare dipende molto da quale file sistem.
Per esempio il file system di Linux dovrebbe essere documentato.
Il vecchio file sistem FAT e' abbastanza ben documentato (cerca vecchi testi sul
DOS o i vecchi libri di P.Norton).
Il nuovo FAT32 non dovrebbe essere troppo diverso, ma alcune differenze ci sono.
Il file system HPFS (nato con OS2 e supportato dai vecchi NT) credo sia
documentato da IBM, ma mi domando se vale la pena.
Il file system NTFS in realtà ha due versioni che non sono del tutto
compatibili. So poco del suo funzionamento. Credo sia documentato da MS ma non
pubblicamente (per esempio dovrebbe esserlo se sei uno sviluppatore di file
system).
A proposito sappi che su NT (e Win2k e XP) il file system non e' una cosa
predefinita ma viene installato come una specie di device driver. O se
preferisci come se fosse un protocollo di rete. Esiste un apposito FSDK (File
System Developer Kit). Pero' occhio che stiamo parlando di cose da mal di testa
(e di portafoglio).
Ci sono poi i file system di supporti specifici (per esempio quelli usati sui CD
e sui DVD). Questi sono pubblicati dall'apposito comitato di standardizzazione.
Quindi si possono comperare i relativi documenti. Mi sono informato su quello
per i DVD Video (vedi il mio indirizzo e-mail) e il documento che lo descrive e'
acquistabile previa firma di una paccata di docmenti legali fra cui non
disclosure e altri vincoli di segretezza. Il costo del libercolo e' di 5.000$.
Per ora ho lasciato perdere!!!
In conclusione: a meno che tu non abbia un business serio che ti ripaga di
grossi investimenti in denaro e tempo, credo che tu possa arrivare a capire a
fondo solo il vecchio FAT16 (valido oggi solo per i floppy dei PC), forse il
FAT32, e i formati di Linux (che sono open per definizione).
