Thread: huffman code

hello,

I wish to implement huffman code in C..I know the logic but stuck in implementing..i m finding it pretty difficult , I mean first sorting and counting frequency is ok but then building the tree is where I am totally stuck, and then again sorting?? Pls help if anyone can...

Thanks,
Edesign

Hi,

You are right, googling it, I got a few codes, even in that code I am facing problem in understanding sorting part, especially after base nodes are defined...

Code:

// huffman.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
#include <math.h>
#include <string.h>

#define         NUMBYTES                          256
#define         NUMBITS                            16
#define         INPUTFILENAME             "input.huf"
#define         OUTPUTFILENAME           "output.huf"
#define         TEMPFILENAME            "huffman.tmp"

typedef struct _HUFFNODE {
        char              byte;
        long              freq;
        struct _HUFFNODE *parent;
        struct _HUFFNODE *left;
        struct _HUFFNODE *right;
} HUFFNODE;

typedef struct _HUFFTAB {
        char              byte;
        char              numbits;
        long              freq;
        long              bits[NUMBITS];
} HUFFTAB;

FILE       *f;
long       fsize, numnodes, numbasenodes;
long       freq_tab[NUMBYTES];    // Frequency table
HUFFNODE  *nodelist[NUMBYTES];
HUFFNODE  *basenode[NUMBYTES];
HUFFNODE  *templist[NUMBYTES];
HUFFTAB    code_tab[NUMBYTES];

/////////////////////////////////
//  Return file size in bytes  //
/////////////////////////////////
long filesize(FILE *f)
{
  long pos, fsize;

  pos = ftell(f);
  fseek(f, 0L, SEEK_END);
  fsize = ftell(f);
  fseek(f, pos, SEEK_SET);

  return fsize;
}

/////////////////////////////////////////////////////////
//  Read input file to memory to speed up compression  //
/////////////////////////////////////////////////////////
char *huffman_readinputstream(char *inputstream)
{
  char *stream;

  f = fopen(inputstream, "r+b");
  assert(f != NULL);
  fsize = filesize(f);

  stream = (char *)calloc(fsize, sizeof(char));
  assert(stream != NULL);

  fread(stream, fsize, 1, f);
  fclose(f);

  return stream;
}


////////////////////////////
//  Make frequency table  //
////////////////////////////
void huffman_buildfreq(char *stream)
{
  long  k;

  for (k = 0; k < NUMBYTES; k++)
    freq_tab[k] = 0;

  for (k = 0; k < fsize; k++)
    freq_tab[stream[k]]++;
}

/////////////////////////////////////////////////////////
//  Sort node list table using straight insertion sort //
/////////////////////////////////////////////////////////
void huffman_sortnodelist(HUFFNODE *nodes[])
{
  HUFFNODE  *node;
  long       i, j, k;

  for (i = 0; i < numnodes-1; i++) {
    k = i;
    node = nodes[i];

    for (j = i+1; j < numnodes; j++)
	      if (nodes[j]->freq < node->freq) {     //Surprisingly breaks at this point in 2nd sort...
        k = j;
        node = nodes[j];
      }

    if (k != i) {
      node = nodes[i];
      nodes[i] = nodes[k];
      nodes[k] = node;
    }
  }
}

//////////////////////////
//  Build huffman tree  //
//////////////////////////
void huffman_buildtree(char *stream)
{
  HUFFNODE  *node;
  HUFFNODE  *node1, *node2;  // Two nodes with smallest frequency
  long       k, n;

  // Build frequency table
  huffman_buildfreq(stream);

  // Build base nodes
  numbasenodes = 0;
  for (k = 0; k < NUMBYTES; k++) {
    if (freq_tab[k] > 0) {

      node = (HUFFNODE *)calloc(1, sizeof(HUFFNODE));
      assert(node != NULL);

      node->byte = k;
      node->freq = freq_tab[k];
      node->parent = NULL;
      node->left = NULL;
      node->right = NULL;

      nodelist[numbasenodes] = node;
      basenode[numbasenodes] = node;
      templist[numbasenodes] = node;

      numbasenodes++;
    }
  }

  // Build huffman tree
  numnodes = numbasenodes;
  n = numnodes;
  while (--n > 0) {

    // Sort node list go get two nodes with minor frequency
    huffman_sortnodelist(nodelist);

    node1 = nodelist[0];
    node2 = nodelist[1];

    // Make new node and link nodes
    node = (HUFFNODE *)calloc(1, sizeof(HUFFNODE));

    node->byte = 'x';
    node->freq = node1->freq + node2->freq;
    node->left = node1;
    node->right = node2;
    node->parent = NULL;

    node1->parent = node;
    node2->parent = node;

    // Add new node and remove old two
    nodelist[0] = node;
    for (k = 1; k < n; k++)
      nodelist[k] = nodelist[k+1];
    nodelist[n] = NULL;

    templist[numnodes++] = node;

  }

  for (k = 0; k < numnodes; k++)
    nodelist[k] = templist[k];
}
////////////////////
//  Main program  //
////////////////////
int main()
{
  char   *stream;
  long    k;

  // Read input stream
  stream = huffman_readinputstream(INPUTFILENAME);

  // Build huffman tree
  huffman_buildtree(stream);

  return 0;
}

have just mentioned sort and tree build part

Code:

for (j = i+1; j < numnodes; j++)
	      if (nodes[j]->freq < node->freq)

after 1st sort, it always breaks at this point...I can't understand why..

Hello Sir,

Thanks for help..
I left it in between..thought I should start with simpler one...so started working on Run length coding..perhaps I can get back to huffman after I sharpen my poor programming skills...

Thanks,
Edesign