?
Solved

Huffman (de)compression implementation

Posted on 2003-03-25
8
Medium Priority
?
211 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

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…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
Suggested Courses
Course of the Month9 days, 4 hours left to enroll

764 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