Huffman encoding in C

Question

I am trying to write a module which assigns huffman encoded words to the input symbols, but the given codes differ from what they should look like.

For example, if I run it with following symbol probabilities:

(1st column: probabilities; 2nd column: my huffman codes; 3rd column: correct huffman codes)

0,25 --> 01 --> 10

0,15 --> 101 --> 111

0,15 --> 110 --> 110

0,1 --> 1111 --> 010

0,1 --> 000 --> 001

0,05 --> 0010 --> 0110

0,05 --> 0011 --> 0001

0,05 --> 1000 --> 0000

0,05 --> 1001 --> 01111

0,05 --> 1110 --> 01110

I think the problem might be caused in my function for generating huffman codes, since strcat() function's behaviour was initially not good for my idea, so I combined it with strcat(). Not sure if it is good that way tho.

I am providing you with two functions responsible for codes assign, build_huffman_tree() and generate_huffman_tree(), hopefully you can help me out with this, and point out where the problem could be.

Generate guffman tree:

void generate_huffman_tree(node *n, char *code){
if(n->left== NULL && n->right== NULL){
    SYMBOLS[code_counter] = n->symbol; // this 3 lines just store current code, not important
    CODES[code_counter] = strdup(code);
    code_counter += 1;
}
if(n->left!= NULL){
    char temp[100];
    strcpy(temp, code);
    strcat(temp, "0");
    generate_huffman_tree(n->left, temp);
}
if(n->right!= NULL){
    char temp[100];
    strcpy(temp, code);
    strcat(temp, "1");
    generate_huffman_tree(n->right, temp);
}

Build Huffman tree:

node *build_huffman_tree(double *probabilities){

int num_of_nodes = NUM_SYMBOLS;
int num = NUM_SYMBOLS;

// 1) Initialization: Create new node for every probability
node *leafs = (node*) malloc(num_of_nodes*sizeof(node));
int i;
for(i=0; i<num_of_nodes; i+=1){
    node c;
    c.probability= *(probability+ i);
    c.symbol= *(SYMBOLS + i);
    c.left= NULL;
    c.right= NULL;
    *(leafs+i) = c;
}

node *root= (node*) malloc(sizeof(node)); // Root node which will be returned

while(num_of_nodes> 1){

    // 2) Find 2 nodes with lowest probabilities
    node *min_n1= (node*)malloc(sizeof(node));
    node *min_n2 = (node*)malloc(sizeof(node));

    *min_n1 = *find_min_node(leafs, num, min_n1);
    leafs = remove_node(leafs, min_n1, num); 
    num -= 1;

    *min_n2= *find_min_node(leafs, num, min_n2);
    leafs = remove_node(leafs, min_n2, num);
    num -= 1;

    // 3) Create parent node, and assign 2 min nodes as its children
            // add parent node to leafs, while its children have been removed from leafs
    node *new_node = (node*) malloc(sizeof(node));
    new_node->probabilty= min_n1->probability + min_n2->probability;
    new_node->left= min_n1;
    new_node->right= min_n2;

    leafs = add_node(leafs, new_node, num);
    num += 1;

    num_of_nodes -= 1;

    root = new_node;
}

return root;

I have tested functions for finding 2 min nodes, removing and adding nodes to leafs structure, and it is proven to work fine, so I guess the problem should be something about this here.

Answer 1

This code below is an implementation of Mark Allen Weiss's Algorithm. Give it a try!

It offers routines similar to yours, in addition to a function that displays the result according to the previously constituted codes for each letter.

The compiler used is MinGW 2.95 (C-Free 4.0).

Prerequisites:

An input file with a text (any, but remember, it deals with alphabet characters only, no punctuation, no space, no numbers). The constant IN_PATH is the one you should modify to point at the right location of your text file to run the program successfully.

The image shows a sample text, the letters proportions and the result of huffman code interpretation (letters separated by one space).

Good luck!

//*******************************************************************
// File:            HuffmanEncoding - Tree.c
// Author(s):       Mohamed Ennahdi El Idrissi
// Date:            14-Aug-2012
// 
// Input Files:     in.txt
// Output Files:    out.txt
// Description:     CSC 2302 - <Data Structures>
//                             <Struct, Array, File I/O, Recursion, Pointers, Binary Tree>
//                  This program covers the Huffman Encoding concept.
//                  We first read a file, from we which we count the number of characters, and then reckon the frequency
//                  of each letter individually. Each letter's frequency is stored in a node with its respective character.
//                  This node is stored in an array of 26 elements (element 0 -> 'A', element 1 -> 'B'...element 25 -> 'Z').
//                  Each element is a pointer, and each pointer is supposed to be a root of a tree (sub tree).
//                  After processing all characters of the text (read from a file), we end up with an array with
//                  25 NULL elements. The only element that is not NULL is the root of the tree that gathers the different
//                  nodes of each letter.
//                  Deducing the encoding of each letter if performed with intermediary of the prefix traversal.
//                  To summarize, the pseudo-code is:
//                      - Initialize the letters array
//                      - Read file
//                          - Increment each letter frequency + compute the number of characters in the file
//                          - Store in the array's node the frequency of each letter
//                      - Compute the number (N) of involved characters (Sometimes, texts don't include all letters. In our case 'Q' and 'Z' are absent).
//                      - Loop N times
//                          - find Minimum and second minimum
//                          - create a new node, its left child contains the minimum and the right child contains the second minimum
//                          - minimum position points on the new node, and the second minimum's array position points on NULL
//                      - Browse the array till the unique non NULL element is encountered
//                          - invoke prefix traversal function
//                              - build the encoding of each character
//                              - display the letter and its characteristics when found.
//                      - Finally, read the output file to interpret its content
//                          - if root contains a character (A - Z), display character
//                          - else, if the current character is '0', browse the left leaf
//                          - else, if the current character is '1', browse the right leaf
//                          
//*******************************************************************
#include <stdio.h>

#define NBR_OF_LETTERS 26

#define LEFT 'L'
#define RIGHT 'R'

#define CODE_SIZE 128

#define TYPED_ALLOC(type) (type *) malloc( sizeof(type) )
#define BYTE_SIZE 8

#define IN_PATH "./files/in.txt"
#define OUT_PATH "./files/out.txt"

typedef struct tree_node_s {
    float frequency;
    char c;
    char code[CODE_SIZE];
    struct tree_node_s *left;
    struct tree_node_s *right;
} tree_node_t;

tree_node_t *arr[NBR_OF_LETTERS], *letters[NBR_OF_LETTERS];


void findMinAndSecondMin(tree_node_t **, float *, int *, float *, int *);
void printTree(tree_node_t *);
void interpret(char *, int *, tree_node_t *);
void printTree(tree_node_t *);
void encode(tree_node_t *, tree_node_t **, char, short, char*);

/*
 *
 */
int main() {
    char str[CODE_SIZE];
    int fileReadingVerdict;
    int i, j, k, index, n;
    float min, secondMin;
    int minIndex, secondMinIndex;
    int numberOfCharacters = 0;
    tree_node_t *tree;
    FILE *in = fopen(IN_PATH, "r");
    FILE *out;
    if ( in == NULL ) {
        printf("\nFile not found");
        return 0;
    } else {
        /*
         *  Begin: Array Initialization
         */
        for (i = 'A'; i <= 'Z'; i++) {
            index = i - 'A';
            arr[index] = NULL;
        }
        /*
         *  End:    Array Initialization
         */
        numberOfCharacters = 0;
        fileReadingVerdict = fgets(str, CODE_SIZE, in) != NULL;
        while(!feof(in) || fileReadingVerdict) {
            n = strlen(str);
            printf("\n%s", str);
            for (i = 0; i < n ; i ++ ) {
                str[i] = toupper(str[i]);
                if (str[i] >= 'A' && str[i] <= 'Z') {
                    numberOfCharacters ++;
                    index = str[i] - 'A';
                    if (arr[index] == NULL) {
                        arr[index] = TYPED_ALLOC(tree_node_t);// malloc(sizeof(tree_node_t));
                        arr[index]->c = str[i];
                        arr[index]->frequency = 1;
                        arr[index]->left = arr[index]->right = NULL;
                    } else {
                        arr[index]->frequency += 1;
                    }
                }
            }
            if (fileReadingVerdict) {
                fileReadingVerdict = fgets(str, CODE_SIZE, in) != NULL;
            }
        }
    }   
    fclose(in);

    for ( i = 0, n = 0 ; i < NBR_OF_LETTERS ; i ++ ) {
        letters[i] = arr[i];
        if (arr[i] != NULL) {
            arr[i]->frequency /= numberOfCharacters;    // Computing the frequency.
            n ++;                                       // n is the number of involved letters which is going to be consumed in the do while loop's condition
        }
    }

    j = 1;
    do {
        findMinAndSecondMin(arr, &min, &minIndex, &secondMin, &secondMinIndex);

        if (minIndex != -1 && secondMinIndex != -1 && minIndex != secondMinIndex) {
            tree_node_t *temp;
            tree = TYPED_ALLOC(tree_node_t);// malloc(sizeof(tree_node_t));
            tree->frequency = arr[minIndex]->frequency + arr[secondMinIndex]->frequency;
            tree->c = j;
            tree->left = arr[minIndex];
            temp = TYPED_ALLOC(tree_node_t);// malloc(sizeof(tree_node_t));
            temp->c = arr[secondMinIndex]->c;
            temp->frequency = arr[secondMinIndex]->frequency;
            temp->left = arr[secondMinIndex]->left;
            temp->right = arr[secondMinIndex]->right;
            tree->right = temp;

            arr[minIndex] = tree;

            arr[secondMinIndex] = NULL;
        } 
        j ++;
    } while( j < n );

    for ( i = 0 ; i < NBR_OF_LETTERS ; i ++ ) {
        if (arr[i] != NULL)  {
            char code[CODE_SIZE];
            strcpy(code, "");
            encode(tree = arr[i], letters, 0, 0, code);
            puts("\nSuccessful encoding");
            printTree(arr[i]);
            break;
        }
    }
    in = fopen(IN_PATH, "r");
    out = fopen(OUT_PATH, "w");
    fileReadingVerdict = fgets(str, CODE_SIZE, in) != NULL;
    while(!feof(in) || fileReadingVerdict) {
        n = strlen(str);
        for (i = 0; i < n ; i ++ ) {
            str[i] = toupper(str[i]);
            if (str[i] >= 'A' && str[i] <= 'Z') {
                index = str[i] - 'A';
                fputs(letters[index]->code, out);
            }
        }
        if (fileReadingVerdict) {
            fileReadingVerdict = fgets(str, CODE_SIZE, in) != NULL;
        }
    }

    fclose(in);
    fclose(out);

    printf("\nFile size (only letters) of the input file:   %d bits", numberOfCharacters * BYTE_SIZE);

    out = fopen(OUT_PATH, "r");
    fileReadingVerdict = fgets(str, CODE_SIZE, out) != NULL;
    numberOfCharacters = 0;
    while(!feof(out) || fileReadingVerdict) {
        numberOfCharacters += strlen(str);
        if (fileReadingVerdict) {
            fileReadingVerdict = fgets(str, CODE_SIZE, out) != NULL;
        }
    }
    fclose(out);    

    printf("\nFile size of the output file: %d bits", numberOfCharacters);

    printf("\nInterpreting output file:\n");
    out = fopen(OUT_PATH, "r");
    fileReadingVerdict = fgets(str, CODE_SIZE, out) != NULL;
    while(!feof(out) || fileReadingVerdict) {
        n = strlen(str);
        i = 0 ;
        while(i < n) {
            interpret(str, &i, tree);
        }
        if (fileReadingVerdict) {
            fileReadingVerdict = fgets(str, CODE_SIZE, out) != NULL;
        }
    }
    fclose(out);

    puts("\n");
    return 0;
}
/*
 *
 */
void encode(tree_node_t *node, tree_node_t **letters, char direction, short level, char* code) {
    int n;
    if ( node != NULL ) {
        if ((n = strlen(code)) < level) {
            if (direction == RIGHT) {
                strcat(code, "1");
            } else {
                if (direction == LEFT) {
                    strcat(code, "0");
                }
            }
        } else {
            if (n >= level) {
                code[n - (n - level) - 1] = 0;
                if (direction == RIGHT) {
                    strcat(code, "1");
                } else {
                    if (direction == LEFT) {
                        strcat(code, "0");
                    }
                }   
            }
        }
        if (node->c >= 'A' && node->c <= 'Z') {
            strcpy(node->code, code);
            strcpy(letters[node->c - 'A']->code, code);
        }
        encode(node->left, letters, LEFT, level + 1, code);
        encode(node->right, letters, RIGHT, level + 1, code);
    }
}

void printTree(tree_node_t *node) {
    int n;
    if ( node != NULL ) {
        if (node->c >= 'A' && node->c <= 'Z') {
            printf("\t%c - frequency: %.10f\tencoding: %s\n", node->c, node->frequency, node->code);
        }
        printTree(node->left);
        printTree(node->right);
    }
}

/*
 *  Begin:  Minimum and second minimum
 */
void findMinAndSecondMin(tree_node_t *arr[], float *min, int *minIndex, float *secondMin, int *secondMinIndex) {
    int i, k;
    k = 0;
    *minIndex = -1;
    /*
     * Skipping all the NULL elements.
     */     
    while (k < NBR_OF_LETTERS && arr[k] == NULL) k++;

    *minIndex = k;
    *min = arr[k]->frequency;

    for ( i = k ; i < NBR_OF_LETTERS; i ++ ) {
        if ( arr[i] != NULL && arr[i]->frequency < *min ) {
            *min = arr[i]->frequency;
            *minIndex = i;
        }
    }

    k = 0;
    *secondMinIndex = -1;
    /*
     * Skipping all the NULL elements.
     */         
    while ((k < NBR_OF_LETTERS && arr[k] == NULL) || (k == *minIndex && arr[k] != NULL)) k++;

    *secondMin = arr[k]->frequency;
    *secondMinIndex = k;

    if (k == *minIndex) k ++;

    for ( i = k ; i < NBR_OF_LETTERS; i ++ ) {
        if ( arr[i] != NULL && arr[i]->frequency < *secondMin && i != *minIndex ) {
            *secondMin = arr[i]->frequency;
            *secondMinIndex = i;
        }
    }
    /*
     *  End:    Minimum and second minimum
     */
}

void interpret(char *str, int *index, tree_node_t *tree) {
    int n = strlen(str);
    if (tree->c >= 'A' && tree->c <= 'Z') {
        printf("%c ", tree->c);
        return ;
    } else {
        if ( *index < n ) {
            if (str[*index] == '0') {
                (*index) ++;
                interpret(str, index, tree->left);
            } else {
                if (str[*index] == '1') {
                    (*index) ++;
                    interpret(str, index, tree->right);
                }
            }
        }
    }
}

Answer 2

I didn't look at your source code, but there's nothing wrong with the Huffman code you generated. There is also nothing wrong with what you are calling "correct huffman codes". There is more than one valid Huffman code possible with that set of probabilities. If you take the sum of the probabilities times the bit lengths for both Huffman codes, you will find that those sums are exactly the same. Both Huffman codes are optimal, even though they're different.

The way this happens is that when you look for the two lowest frequencies, there is more than one choice. Depending on which choice you make, you will get a different tree.