Huffman Encoding, Saving codes and writing binary in C

Question

I have a problem with encoding a text file with Huffman. Let's say the line to encode is like the following:

AAAABBBCCAABBCCDFF

So the frequency table is like this :

A:6
B:5
C:4
D:1
F:2

So I build a tree, the struct is like this:

typedef struct node {
    struct node *left;
    struct node *right;
    unsigned char character;
    unsigned int flag; //needed for nodes with no value in Huffman-tree
    unsigned int occurences;
} node;

I know the codes should be:

A: 10
B: 11
C: 01
D: 000
F: 001

Now I want to get this codes from my tree, how can I do this easily?

Secondly, I want to save those codes so I can easily look the codes up and write them to a binary file.

How can I save those codes, and for writing, how can I write individual (or 2 or 3) bits to a binary file, because I know C wants bytes.

I want to write it like this (codes sorted by byte and last byte is only 7 bits)

10101010 11111101 01101011 11010100 0001001 (only 7 bits)

You can push the bits through a function where a static byte is built. When it has 8 bits, it is written to file. Similarly for reading it back, the function fetches 1 bit from a byte, when none remain, another byte is read from file. — Weather Vane
@fangio to have a more easy to check result, I often use a string to store bits as '0' or '1' ASCII value. Then you have just to cut the result string as 8 characters long and convert each to a byte before writing to a file. — J. Piquard

J. Piquard J. Piquard · Accepted Answer · 2016-10-18T16:53:38

Hereafter is an example to convert a bit-string-encoded to a serie of hexadecimal in a text file. The sBoolText string has been filled by '0' or '1' and has to be stuffed by completing '0' for the last byte.

In your case "AAAABBBCCAABBCCDFF" will encoded as 101010101111...001001 and generates a bit-string "101010101111...001001" stuffed with "0".

This is not exactly what you need, but you can use fputc() instead of fprintf().

void BoolToHexFile(FILE *foutText,char *sBoolText)
{
    int i,j,len,res;

    len = strlen(sBoolText);
    for(i=0;i<len;i+=8) {
        res = 0;
        // build one byte with 8bits as characters
        for(j=0;j<8;j++) {
            res *= 2;
            if (sBoolText[i+j]=='1') res++;
        }
        // add a NewLine every 16 bytes
        if ((i % 128) == 0) fprintf(foutText,"\n");
        // store the byte as 2 hexa-digits
        fprintf(foutText,"%02X ",res);
    }
}

Huffman Encoding, Saving codes and writing binary in C

1 Answers