Newsgroup: it.comp.lang.c
Titolo: Domanda su codifica di Huffman

Salve a tutti,
ho un problema sulla codifica di huffman.
Ho realizzato l'albero binario e sono riuscito a dare ai singoli
percorsi radice->foglia la codifica di huffman.
Per comodita' di stampa ho creato un array di 256 puntatori , uno per
ogni carattere.
Ad ogni puntatore e' collegata una lista dinamica che contiene la
codifica della lettera.
Es: la lettera A la trovo in vettore[65] che punta ad una lista dove
ogni blocco contiene un intero (0 o 1) e un puntatore all'elemento
successivo e cosi' codifico la lettera.
A questo punto vorrei salvare su file il messaggio codificato in 0 e
1.Ma come faccio?Con le funzioni del C posso scrivere un int alla
volta e non il singolo bit 0 1 di una codifica di huffman.
Se scrivo gli int, il file di uscita e' piu' grande di quello di
ingresso e addio compressione...
Che cosa si una in questi casi?
Naturalmente poi devo anche poter aprire il file e leggere i bit per
ricostruire il messaggio originale.
Grazie in anticipo per gli aiuti.
fabio.

 Che cosa si una in questi casi?
Ovviamente si impacchettano i dati. Lascia perdere gli int o
gli short perche' ritrovi il problema della endianness. Usa,
per esempio, un vettore di unsigned char (anche di un solo
elemento, volendo).
Scrivi i bit con le operazioni bitwise all'interno del byte
e tieni traccia di quanti bit rimangono. Ogni volta che il
byte si riempie, lo scrivi su disco e riazzeri i contatori.
Attento a gestire il caso (nemmeno troppo complesso) di un
simbolo codificato che va messo a cavallo di due byte.
Saluti,
Marco
-- 
To email me, remove the no_ and _spam from my address.

 ricostruire il messaggio originale.
Devi utilizzare gli operatori bit-a-bit (bitwise operators).
Utilizzando la tua struttura dati...
ad esempio se 'a' e' 0, 'b' e' 10 e 'c' e' 11 e vuoi scrivere la stringa
"babac" puoi fare:
unsigned char byte = 0;
int byte_pos = BYTE_SIZE-1;               /* msb in byte */
for each letter in the string
      for each bit in current letter
            if byte_pos < 0
                  Write_Byte_To_Disk(byte);
                  byte = 0;
                  byte_pos = BYTE_SIZE-1;
            byte |= current_bit << byte_pos;
            --byte_pos;
Write_Byte_To_Disk(byte);
Questo algoritmo e' trivial nel senso che scrive un byte alla volta su
disco, ovviamente ti conviene mettere insieme un pochino piu' bytes!
Allora: "babac"
inziamo con la lettera 'b' (10):
byte = 0
byte_pos = 7;
Il for interno preleva il bit 1:
byte diventa 10000000
byte pos diventa 6
Il for interno preleva il bit 0:
byte pos diventa 5
Il for ESTERNO preleva la lettra 'a' (0):
byte pos diventa 4
Il for ESTERNO preleva la lettera 'b' (10):
Il for interno preleva il bit 1:
byte diventa 10010000
byte pos diventa 3
Il for interno preleva il bit 0:
byte pos diventa 2
Il for ESTERNO preleva la lettra 'a' (0):
byte pos diventa 1
Il for ESTERNO preleva la lettera 'c' (11):
Il for interno preleva il bit 1:
byte diventa 10010010
byte pos diventa 0
Il for interno preleva il bit 1:
byte diventa 10010011
byte pos diventa -1
I due for finiscono e fuori dai for c'e' una chiamata a
Write_Byte_To_Disk() che scrive il byte su disco.
Abbiamo scritto 10010011
Se ci fosse stata un'altra lettera il byte sarebbe stato scritto su
disco dall'if interno ai due for, questo avrebbe ripristinato il byte a
0 e bytepos a 7 e si sarebbe rincominciato a riempire il byte (che poi
quando finiva si scriveva su disco).
Ovviamente se la stringa fosse stata "babacb" avresti scritto un byte e
poi ne avresti scritto uno di cui pero' avresti utilizzato solo i primi
due bit (msb).
Questo dovrebbe farti capire quanto siamo importante un header di
dimensione fissa o calcolabile da alcuni bytes fissi nell'header che dia
informazioni utili per poter decifrare il sucessivo contenuto (devi
anche salvare il codici di huffman che hai prodotto ovviamente).
Ok, l'algoritmo e' in pseudocodice ed e' scritto al volo. Sono sicuro
che cosi' come e' non funzioni, ma l'idea dovrebbe avertela trasmessa.
Ora dovresti essere in grado di scrivertene uno tu piu' completo, piu'
performante e funzionante.
Per concludere "la tua lista di bits" rende piuttosto semplice
l'algoritmo in quanto metti un bit per volta nel byte, ma la lista non
e' molto performante. Un domani potresti considerare una alternativa...
HTH,
Tommaso
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 simbolo codificato che va messo a cavallo di due byte.
Il fatto che lui memorizzi i singoli bits come elementi di una lista
rende questo caso banale.
Nel senso che non si deve piu' preoccupare di questa cosa ma deve solo
pensare di scrivere un bit alla volta.
Se invece salvasse, ad esempio, i bits in strutture tipo:
struct
usnigned long long bits
int numero_di_bits_usati
allora ovviamente se il numero di bits usati e' 5 e nel byte in corso
rimangono solo 3 bytes disponibili allora bisogna considerare il caso
che tu hai menzionato (specilmente se normalmente vuoi mettere i bits
nel byte in una botta sola invece che un bit alla volta).


 volta e non il singolo bit 0 1 di una codifica di huffman.
Io non avrei utilizzato il tuo metodo di memorizzazione del path binario
per raggiungere le foglie, avrei piů che altro impacchettato i bit in un
unsigned long, memorizzando anche il numero di bit (difatti, nei programmi
che ho scritto e che utilizzavano la codifica di huffman, ho fatto cosě).
L'output lo scrivi byte per byte, accodando i codici a lunghezza variabile
l'uno dopo l'altro.
Mi spiego: la codifica di Huffman per ABRACADABRA č, per esempio:
A 0
B 10
R 110
C 1110
D 1111
Io li memorizzerei come:
carattere --- codice (unsigned long a 32 bit) ----- numero bit
A             00000000000000000000000000000000       1
B             10000000000000000000000000000000       2
R             11000000000000000000000000000000       3 
C             11100000000000000000000000000000       4
D             11110000000000000000000000000000       4
La compressione si realizza accodando i codici secondo il numero di bit:
ABRACADABRA=A(0)+B(10)+R(110)+A(0)+C(1110)+A(0)+D(1111)+A(0)+B(10)+R(110)+A(0)
I byte vengono scritti bufferizzati un byte alla volta, quindi 8 bit alla
volta:
01011001110011110101100(0)
^^^^^^^^!!!!!!!!^^^^^^^ ^
1^ byte 2^ byte 3^ byte
L'ultimo bit a zero serve a riempire il byte.
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it