?
Solved

Huffman (de)compression implementation

Posted on 2003-03-25
8
Medium Priority
?
212 Views
Last Modified: 2008-03-10
I have been using the Huffman implementation posted by a VB expert here: http://www.experts-exchange.com/Programming/Programming_Languages/Visual_Basic/Q_11088729.html in one of my projects.

The problem is, someone else is going to start helping me with this project, but he uses Linux. I've been searching high and low for a program written in C that can open one of the files created with the above mentioned function. Example here: http://12.233.221.111/test.huf So far I've had no luck finding a program that can uncompress this file in Linux.

I'm looking for source code that can uncompress the file mentioned above. Thank you very much in advance.
0
Comment
Question by:izaram
  • 3
  • 2
  • 2
  • +1
8 Comments
 
LVL 8

Expert Comment

by:akshayxx
ID: 8207283
on this page
http://www.cryogenius.com/huffman/
u'll find information and links to huffman code-decode source codes , and i had a look at the code and  i found it shud work on linux and all other unix
see if that can be useful for ur project
0
 

Author Comment

by:izaram
ID: 8207367
Thanks for the comment akshayxx. I should have noted that while I did find several source samples on the net that compiled fine with Linux, none of them were able to open the files I'm working on. The site you pointed me to is one such example.

As additional information for my question, the VB basic code linked to above checks if the first characters on the file are "H3". I assume it's a kind of file signature, but I haven't been able to find references to this "header" either.

Thanks again.
0
 

Author Comment

by:izaram
ID: 8214380
I've added the points I got today. :) BTW, just wanted to clarify that this is *not* homework. I just want to mention that since I've noticed a lot of the information online regarding Huffman compressing is geared toward students. I'm trying to build a db for DirectConnect and they use Huffman as the format to compress their filelists with.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:izaram
ID: 8216062
Ok, I think I'm talking to myself now, but I'll request to close this Q and open up a new one since I found code on the web that does this, but I have been unable to get it to work. Thank you.
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8216404
sorry but i have been busy , if u still have it unsolved , i can give another look, when i get time.. after all i have to give some time to the work that earns me my living
0
 
LVL 10

Expert Comment

by:substand
ID: 8217085
a full huffman implementation:

------- minheap.h ----
#ifndef _minheap_h
#define _minheap_h
#include "hufftree.h"

typedef struct MinHeapInfo *Heap;
typedef HuffTree ElementType;

Heap NewMinHeap();
ElementType DeleteMinHeap(Heap h);
void InsertMinHeap(ElementType x, Heap h);
int SizeMinHeap(Heap h);
int cmp(HuffTree t1, HuffTree t2);

#endif

---------minheap.c----------

#include<stdio.h>
#include "error.h"
#include "hufftree.h"
#include "minheap.h"

struct MinHeapInfo{int arraysize; int num; ElementType *array;};

Heap NewMinHeap(int arraysize)
{
 Heap h;
 h =(Heap)malloc(sizeof(struct MinHeapInfo));
 if(h == NULL)FatalError("Out of Storage!!");
 h->array =(HuffTree)malloc(arraysize * sizeof(ElementType));
 if(h->array == NULL)FatalError("Out of storage");
 h->arraysize = arraysize;
 h->num = 0;
 return h;
}

ElementType DeleteMinHeap(Heap h)
{
 int parent, child;
 ElementType x, last;
 
 if(h->num == 0)
 return NULL;
 x = h->array[1];
 last = h->array[h->num--];
 h->array[1] = last;
 parent = 1;
 child = 2 * parent;
 while(child <= h->num)
 {
  if(child + 1 <= h->num && cmp(h->array[child + 1], h->array[child]) < 0)
  child++;
  if(cmp(last, h->array[child]) > 0)
  h->array[parent] = h->array[child];
  else
  break;
  parent = child;
  child = 2 * parent;
 }
 h->array[parent] = last;
 return x;
}

void InsertMinHeap(ElementType x, Heap h)
{
 int child, parent;
 child = ++h->num;
 parent = child / 2;
 while(parent > 0 && cmp(h->array[parent], x) > 0)
 {
  h->array[child] = h->array[parent];
  child = parent;
  parent = child / 2;
 }
 h->array[child] = x;
}

int SizeMinHeap(Heap h)
{
 return h->num;
}

int cmp(HuffTree t1, HuffTree t2)
{
 if(CmprFreq(t1) > CmprFreq(t2))
 return 1;
 else if(CmprFreq(t1) < CmprFreq(t2))
 return -1;
 else
 return 0;
}

--------main.c---------------------
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include "error.h"
#include "hufftree.h"
#include "minheap.h"
#define SIZE 128

main()
{
 int freq[SIZE], i;
 char ch, filename[12];
 FILE *fp;
 Heap h = NewMinHeap(SIZE+1);
 HuffTree t;

 for (i = 0; i < SIZE; i++)
 freq[i] = 0;
 
printf("*****************************************************************\n");
printf("\t\tWelcome To File Compressor 1.0\t\t\n");

printf("*****************************************************************\n");
  printf ("\nENTER the filename to Commpress: ");
  scanf  ("%s", filename);

printf("\n*****************************************************************\n");
  fp = fopen (filename, "rt");
  if (fp == NULL) FatalError ("Cannot open file!");

  printf ("\nPress ENTER to view the input");
  getchar();getchar();
 while ((ch = tolower(fgetc (fp))) != EOF)
    freq[ch]++;
  fclose (fp);

printf("\n*****************************************************************\n");
  printf ("\n       Characters\t\t");
  printf ("\n       ----------\t\t");

  for (i = 0; i < SIZE; i++)
    if (freq[i] != 0)
    {
      switch (i)
      {
      case '\n': printf ("\nINPUTS:  nl \t\t");break;
      case ' ' : printf ("\nINPUTS:  sp \t\t");break;
      default  : printf ("\nINPUTS:  %c \t\t", i);break;
      }
      t = NewHuffTree(i, freq[i]);
      InsertMinHeap(t, h);
    }

printf("\n*****************************************************************\n");
 
  printf ("\n\npress ENTER to view the new Huffman codes!");
  getchar();
 
printf("\n*****************************************************************\n");
  while (SizeMinHeap (h) > 1)
  {
    t = JoinHuffTrees(DeleteMinHeap (h), DeleteMinHeap (h));
    InsertMinHeap (t, h);
  }
  OutputHuffCodes (DeleteMinHeap (h));
 
printf("\n*****************************************************************\n");
  return 0;
}

--------hufftree.h --------------
#ifndef _hufftree_h
#define _hufftree_h

typedef struct HuffNode *HuffTree;

HuffTree NewHuffTree(char ch, int freq);
HuffTree JoinHuffTrees(HuffTree t1, HuffTree t2);
void OutputHuffCodes(HuffTree t);
int CmprFreq(HuffTree t);

#endif

---------hufftree.c---------------
#include<stdio.h>
#include "hufftree.h"
#include "error.h"

int path[10];
int steps = 0;

struct HuffNode{char ch; int freq; HuffTree left, right;};
static void OutputHuffCodesRec(HuffTree t);

HuffTree NewHuffTree(char ch, int freq)
{
 HuffTree h;
 h =(HuffTree)malloc(sizeof(struct HuffNode));
 if(h == NULL)FatalError("Out of Memory!!");
 h->ch = ch;
 h->freq = freq;
 h->left = NULL;
 h->right = NULL;
 return h;
}

HuffTree JoinHuffTrees(HuffTree t1, HuffTree t2)
{
 HuffTree ht;
 ht = NewHuffTree(NULL, t1->freq + t2->freq);
 if(t1->freq <= t2->freq)
 {
  ht->left = t1;
  ht->right = t2;
 }
 else if(t1->freq >= t2->freq)
 {
  ht->left = t2;
  ht->right = t1;
 }
return ht;
}

void OutputHuffCodes (HuffTree t)
{
  printf ("\nCharacter\t\tHuffman Code\t\tFrequency\n");
  printf ("---------  \t\t------------\t\t---------\n");
  OutputHuffCodesRec (t);
}

static void OutputHuffCodesRec(HuffTree t)
{
  int i;
  if (t->ch != NULL)
  {
   switch (t->ch)
   {
    case '\n': printf ("\n nl \t\t  "); break;
    case ' ' : printf ("\n sp \t\t  "); break;
    default  : printf ("\n %c \t\t  ", t->ch);
   }
   printf("\t");
   for (i = 0; i < steps; i++)
   printf ("%d", path[i]);
   printf("\t\t\t%4d",t->freq);
    steps--;
   }
  else
 {
  path[steps++] = 0;
  OutputHuffCodesRec (t->left);
  path[steps++] = 1;
  OutputHuffCodesRec (t->right);
  steps--;
  }
}

int CmprFreq(HuffTree t)
{
 return t->freq;
}

-------- error.h---------------
#ifndef _error_h
#define _error_h
void FatalError(char msg[ ]);
void Error(char msg[ ]);
#endif

-------- nontest.c ----------
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include "error.h"
#include "hufftree.h"
#include "minheap.h"
#define SIZE 128

main()
{
 int freq[SIZE], i;
 char ch, filename[12];
 FILE *fp;
 Heap h = NewMinHeap(SIZE+1);
 HuffTree t;

 for (i = 0; i < SIZE; i++)
 freq[i] = 0;

printf("*****************************************************************\n");
printf("\t\tWelcome To File Compressor 1.0\t\t\n");

printf("*****************************************************************\n");
  printf ("\nENTER the filename to Commpress: ");
  scanf  ("%s", filename);

printf("\n*****************************************************************\n");
  fp = fopen (filename, "rt");
  if (fp == NULL) FatalError ("Cannot open file!");

  printf ("\nPress ENTER to view the input");
  getchar();getchar();
 while ((ch = tolower(fgetc (fp))) != EOF)
    freq[ch]++;
  fclose (fp);

printf("\n*****************************************************************\n");
  printf ("\n       Characters\t\t");
  printf ("\n       ----------\t\t");

  for (i = 0; i < SIZE; i++)
    if (freq[i] != 0)
    { getch();
      switch (i)
      {
      case '\n': printf ("\nINPUTS:  nl \t%d\t", freq[i]);break;
      case ' ' : printf ("\nINPUTS:  sp \t%d\t", freq[i]);break;
      default  : printf ("\nINPUTS:  %c \t%d\t", i, freq[i]);break;
      }
      if (freq[i]<60)
       {t = NewHuffTree(i, freq[i]);
      InsertMinHeap(t, h);}
    }

printf("\n*****************************************************************\n");

  printf ("\n\npress ENTER to view the new Huffman codes!");
  getchar();
printf("\n*****************************************************************\n");
  while (SizeMinHeap (h) > 1)
  {
    t = JoinHuffTrees(DeleteMinHeap (h), DeleteMinHeap (h));
    InsertMinHeap (t, h);
  }
  OutputHuffCodes(DeleteMinHeap (h));

printf("\n*****************************************************************\n");
  return 0;
}
/////////////////////////////////////////////////////////////
void FatalError(char msg[ ])
{  printf("\nFATAL ERROR: %s\n", msg);
   exit(1);
}

/////////////////////////////////////////////////////////////
#include<stdio.h>
#include "error.h"
#include "hufftree.h"
#include "minheap.h"

struct MinHeapInfo{int arraysize; int num; ElementType *array;};

Heap NewMinHeap(int arraysize)
{
 Heap h;
 h =(Heap)malloc(sizeof(struct MinHeapInfo));
 if(h == NULL)FatalError("Out of Storage!!");
 h->array =(HuffTree)malloc(arraysize * sizeof(ElementType));
 if(h->array == NULL)FatalError("Out of storage");
 h->arraysize = arraysize;
 h->num = 0;
 return h;
}

ElementType DeleteMinHeap(Heap h)
{
 int parent, child;
 ElementType x, last;

 if(h->num == 0)
 return NULL;
 x = h->array[1];
 last = h->array[h->num--];
 h->array[1] = last;
 parent = 1;
 child = 2 * parent;
 while(child <= h->num)
 {
  if(child + 1 <= h->num && cmp(h->array[child + 1], h->array[child]) < 0)
  child++;
  if(cmp(last, h->array[child]) > 0)
  h->array[parent] = h->array[child];
  else
  break;
  parent = child;
  child = 2 * parent;
 }
 h->array[parent] = last;
 return x;
}

void InsertMinHeap(ElementType x, Heap h)
{
 int child, parent;
 child = ++h->num;
 parent = child / 2;
 while(parent > 0 && cmp(h->array[parent], x) > 0)
 {
  h->array[child] = h->array[parent];
  child = parent;
  parent = child / 2;
 }
 h->array[child] = x;
}

int SizeMinHeap(Heap h)
{
 return h->num;
}

int cmp(HuffTree t1, HuffTree t2)
{
 if(CmprFreq(t1) > CmprFreq(t2))
 return 1;
 else if(CmprFreq(t1) < CmprFreq(t2))
 return -1;
 else
 return 0;
}
/////////////////////////////////////////////////////////////////
#include<stdio.h>
#include "hufftree.h"
#include "error.h"

int path[10];
int steps = 0;

struct HuffNode{char ch; int freq; HuffTree left, right;};
static void OutputHuffCodesRec(HuffTree t);

HuffTree NewHuffTree(char ch, int freq)
{
 HuffTree h;
 h =(HuffTree)malloc(sizeof(struct HuffNode));
 if(h == NULL)FatalError("Out of Memory!!");
 h->ch = ch;
 h->freq = freq;
 h->left = NULL;
 h->right = NULL;
 return h;
}

HuffTree JoinHuffTrees(HuffTree t1, HuffTree t2)
{
 HuffTree ht;
 ht = NewHuffTree(NULL, t1->freq + t2->freq);
 if(t1->freq <= t2->freq)
 {
  ht->left = t1;
  ht->right = t2;
 }
 else if(t1->freq >= t2->freq)
 {
  ht->left = t2;
  ht->right = t1;
 }
return ht;
}

void OutputHuffCodes (HuffTree t)
{
  printf ("\nCharacter\t\tHuffman Code\t\tFrequency\n");
  printf ("---------  \t\t------------\t\t---------\n");
  OutputHuffCodesRec (t);
}

static void OutputHuffCodesRec(HuffTree t)
{
  int i;

  if (t->ch != NULL)
  {getch();
   switch (t->ch)
   {
    case '\n': printf ("\n nl \t\t  "); break;
    case ' ' : printf ("\n sp \t\t  "); break;
    default  : printf ("\n %c \t\t  ", t->ch);
   }
   printf("\t");
   for (i = 0; i < steps; i++)
   printf ("%d", path[i]);
   printf("\t\t\t%4d",t->freq);
    steps--;
   }
  else
 {
  path[steps++] = 0;
  OutputHuffCodesRec (t->left);
  path[steps++] = 1;
  OutputHuffCodesRec (t->right);
  steps--;
  }
}

int CmprFreq(HuffTree t)
{
 return t->freq;
}
---------error.c--------------------------

#include <stdio.h>
#include <stdlib.h>   /*for prototype of exit*/
#include "error.h"

void FatalError(char msg[ ])
{  printf("\nFATAL ERROR: %s\n", msg);
   exit(1);
}

void Error(char msg[ ])
{  printf("\nERROR: %s\n", msg);
}



----------------------------------


hope that helps
0
 

Expert Comment

by:SpideyMod
ID: 8219833
A request for a refund has been made.  Experts you have 72 hours to object.

SpideyMod
Community Support Moderator @Experts Exchange
0
 

Accepted Solution

by:
SpideyMod earned 0 total points
ID: 8233798
PAQ'd and all 80 points refunded.

SpideyMod
Community Support Moderator @Experts Exchange
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
Suggested Courses

580 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question