Newsgroup: it.comp.lang.c
Titolo: Bit vs Byte

Buonasera a tutti.
Esiste un modo di scrivere su disco un singolo bit alla volta?
Mi spiego meglio, se avessi bisogno di scrivere un byte alla volta (char per
esempio) dovrei fare:
fwrite( &c, sizeof(char),1,fp);
Ma se avessi bisogno di scrivere 2 bit solamente?
Mettiamo che io voglia rappresentare un carattere (per es.
A che č uguale a 11000001) con 01, e cosě per alcuni caratteri, in modo tale
che la sequenza ABC ad es. non sia composta da 24 bit ma solamente da 6.
ES:
- A = 01
- B = 11
- C = 10
ABC = 011110
6 bit contro 24. Una buona compressione! :-)
Grazie a tutti
Ciao
Paolo

 6 bit contro 24. Una buona compressione! :-)
Beh, questa e' una compressione molto semplice e poco potente in stile
huffman....
Quello che vuoi fare e' un esercizio di programmazione molto carino, ma i
livelli di compressione che otterrai saranno ridicoli se paragonati a quelli
che ottieni con zip o rar.
In fine, per un testo tipo
"abacaabcaabbcaabcbabcaabcaabbcaabcbabcaabcaabbcaabcbabcaabcaabbcaabcb"....
etc.. (piu' lungo altrimenti non conviene comprimere), insomma dove abbiamo
tre lettere (a,b e c) in cui 'a' ha maggiore frequenza, poi 'b' e poi meno
frequente di tutte 'c' allora converrebbe avere:
a -> 0
b -> 11
c -> 10
questo e' + o - quello che dice l'algoritmo di huffman.
una volta che implementi questo algoritmo magari vorrai aggiungerci qualche
altra caratteristica tipo RLE, etc... mettendone alcune insieme il programma
comprimera' un pochino meglio ma per fare qualche cosa di valido come zip e
rar ti consiglio vivamente di leggerti documentazioni su come questi formati
sono programmati.
Una utima cosa...
Se ad esempio un testo, una volta compresso, occupasse 5118 bits, ovvero 639
bytes e 6 bits, come faresti a scrivere solo i 6 bits? La risposta e'
semplice scrivi 640 bytes e per evitare che gli ultimi due bits a 0 vengano
ad esempio interpretati come due 'a' (ad esempio) ti serve un header
all'inizio del file compresso in cui scrivi il numero di caratteri
compressi, oppure il numero di bits utili, oppure ancora il numero di bits
utili nell'ultimo byte.
Se questa materia ti interessa ci sono libri e documenti interessanti a
riguardo.
Tommy

 6 bit contro 24. Una buona compressione! :-)
è una buona compressione solo se utilizzi file indicizzati che necessitano
di algoritmi di ordinamento
anche se è migliorabile
come ti è stato consigliato usa la teoria di huffman e varianti conseguenti
molte le trovi sul FTP universiatario milanese o torinese
mentre se si desidera definire file di indici pseudo criptati si possono
utilizzare sistemi di riduzione dei bit utilizzati per i caratteri
effettivamente utilizzati magari inserende delle funzioni di normalizzazione
delle stringhe
questa tecnica era utilizzata in passato per gestire file indice di indici
per dati ridondanti o files con dati non ordinati di grossissime dimensioni,
o estrazioni per stampe relazionali
la ricerca anagrafica per dati normalizzati era ovviamente più veloce e le
estrazioni risultanti occupavano molto meno spazio su disco e la ricerca
dicotomica in memoria era quasi immediata
è ovvio che non si legge ne si scrive un byte  alla volta (la dimensione è
definita dal S.O. e dal F.S. utilizzato
un cluster è l'unità fisica effettivamente letta o scritta alla volta
pertanto scendere la di sotto dell'unità minima fornita dal sistema non è ne
utile ne conveniente
sarebbe cosa saggia prevedere una dimensione definita sulla base del sistema
utilizzato  (da analizzare all'avvio) e utilizzare la valorizzazione dei bit
ed eventuale shift parametrizzando il tutto alla dimensione risultante
importantissimo è l'header del file sia la sua costituzione che la sua
lunghezza
se devi utilizzare tali file come insiemi ordinati ricordati di utilizzare
token a lunghezza fissa e normalizzazioni finite

Anno Domini Wed, 4 Feb 2004 23:38:12 +0000 (UTC), Tommy, nobilissimus apud
internautas, scripsit:
[CUT]
Potresti postare, se lo conosci, qualche buon link sia su huffman che su
standard di compressione più avanzata?
-- 
Poochie ©
Teoricamente la teoria è uguale alla pratica, ma in pratica non lo è...

 6 bit contro 24. Una buona compressione! :-)


 Poochie ©
questo e' un link sul file format dello zip: 
http://www.wotsit.org/
 ->
Archive Files -> 2nd page -> ZIP
Per il codice di huffman ti conviene usare google, questo e' quello che usai
a mio tempo, accompagnato da un paio di buoni libri di strutture dati ed
algoritmi.
Tommy

 Tommy
Grazie
Ciao
Paolo

 Ho scaricato i file.....ma non ho capito niente! :-)
non sono affatto facili ;-)
Tommy