problem in saving Huffman Code?

Question

I want to save Huffman codes into a file. How can I do this? I am saving Huffman codes into a string but size of generated file is bigger than Original file.

Huffman coding results in variable bit-length codes. If you don't pack the codes together on output, so a 5-bit code only takes five bits, you won't get compression. You need to create a byte buffer that you can fill n-bits at a time, where n is not a multiple of 8. — antlersoft
I dont't understand the "You need to create a byte buffer that you can fill n-bits at a time, where n is not a multiple of 8 " ????? How can do it? — zahratTZ
You will have to set the bits manually, either by encoding your data into another datatype like an int or using another library for a bitset. — Maynza
static huffman algorithm, I suppose. for the dynamic huffman algorithm, you don't need to store anything :) — ShinTakezou
@antlersoft What if the encoded data does not result into an overall bit-count that isn't multiple of 8? One can't simply append 0-Bits to the end of the file to complete the last byte... the dummy-zeros would be decoded as well when reading the compressed file... — Silicomancer

6502 6502 · Accepted Answer · 2011-07-07T19:44:32

A very simple approach is to write one bit at a time with something like the following:

unsigned char acc; // Accumulator of bit waiting to be written
int bitcount;      // How many bits are aready present in the accumulator

// write a single bit (0/1)
void writebit(int bit)
{
    acc |= (bit << bitcount);
    if (++bitcount == 8)
    {
        writebyte(acc);
        acc = 0;
        bitcount = 0;
    }
}

to read back a sigle bit the procedure is symmetrical

unsigned char acc;   // bits waiting to be extracted
int bitcount;        // how many bits are still available in acc

int readbit()
{
   if (bitcount == 0)
   {
       bitcount = 8;
       acc = readbyte();
   }
   --bitcount;
   return (acc >> (7 - bitcount)) & 1;
}

of course this is just the simplest approach, but I'd wait before worrying about code speed until you are first able to save and load correctly your encoded data.

Example:

Suppose you have the following Huffman coded symbols

A - 0
B - 10
C - 110
D - 111

and that you want to encode the sequence

A B A A C D A D B B

then you would call in order

writebit(0);                           // A
writebit(1); writebit(0);              // B
writebit(0);                           // A
writebit(0);                           // A
writebit(1); writebit(1); writebit(0); // C
writebit(1); writebit(1); writebit(1); // D
writebit(0);                           // A
writebit(1); writebit(0);              // B
writebit(1); writebit(0);              // B

The actual bytes written would therefore be

(01100010) = 0x62
(01010111) = 0x57

(Note that the code shown starts from the least significant bit, i.e. you should read the bit sequences inside the parenthesis from right to left if you want to recognize the symbols).

problem in saving Huffman Code?

3 Answers

Example: