Huffman Code in C/C++ with String as Node

Hi everyone,

I have copied someone's code and modified. But Since, the author has put the code as open source, I have done that for my friend.

Here it goes, Huffman code in C/C++

Source Code:

#include<conio.h>
#include<string.h>
#include<math.h>
#include<iostream.h>
#include<stdlib.h>

#define ARRAY_SIZE 20
#define MAX_NAME_LEN 25

int g,h,p,y,n;
char m[ARRAY_SIZE],b[ARRAY_SIZE][2],re;

int alpha = 65;

char name[ARRAY_SIZE][MAX_NAME_LEN];
int i=0,j=0,k=0;

/*
Perfoming operations
*/

//Tree Structure
struct tree
{
char a[20];
int s;
struct tree *left,*right;
}*root=NULL,*tt[20]={NULL},*temp,*temp2,*t2,*ri,*le;


// Queur Structure
struct pqu
{
int info;
char a[20];
struct pqu *ptr;
}*front=NULL,*t,*par,*t1,*p1,*p2;

// Pointer to queue
struct pqu* fp(int info)
{
struct pqu *p=NULL;
for(t1=front;t1->info<info&&t1!=NULL;t1=t1->ptr)
{
p=t1;
}
return (p);

}

//PUSH operation
void enqu(char a[20],int p)
{
t=(struct pqu*)malloc(sizeof(struct pqu));
strcpy(t->a,a);
t->info=p;
t->ptr=NULL;
if(front==NULL)
{
front=t;
}
else
{
par=fp(p);
if(par==NULL)
{
t->ptr=front;
front=t;
}
else
{
t->ptr=par->ptr;
par->ptr=t;
}
}
}

// POP operation
struct pqu* dequ()
{
t1=front;
front=front->ptr;
return t1;
}

//Get Info of a leaf
void info(char c[2])
{
int m=0,i;
temp2=root;
while(strcmp(c,temp2->a)!=0)
{
t2=temp2->left;
for(i=0;i<strlen(t2->a);i++)
{
if(t2->a[i]==c[0])
{
temp2=temp2->left;
m=1;
cout<<”0&”;
break;
}
}
if(m!=1)
{
temp2=temp2->right;
cout<<&”1&”;
}
m=0;
}
}

// Insert Operation
void insert()
{
char a1[20],b1[20],v1[20];
int i,j,z=0,l;
while(front!=NULL)
{
p1=dequ();
strcpy(a1,p1->a);
l=p1->info;
p2=dequ();
if(p2==NULL)
break;
strcpy(b1,p2->a);
strcpy(v1,a1);
temp=(struct tree*)malloc(sizeof(struct tree));
strcpy(temp->a,strcat(v1,b1));
temp->s=l+p2->info;
temp->left=NULL;
temp->right=NULL;
temp2=temp;
root=temp;
for(i=0;i<z;)
{
if(strcmp(tt[i]->a,a1)==0)
{
temp->left=tt[i];
for(l=i;l<z;l++)
{
tt[l]=tt[l+1];
}
i=0;
continue;
}
else if(strcmp(tt[i]->a,b1)==0)
{
temp->right=tt[i];
for(l=i;l<z;l++)
{
tt[l]=tt[l+1];
}
i=0;
continue;
}
i++;
}
if(temp->left==NULL)
{
le=(struct tree*)malloc(sizeof(struct tree));
strcpy(le->a,a1);
le->left=NULL;
le->right=NULL;
temp2->left=le;
}
if(temp->right==NULL)
{
ri=(struct tree*)malloc(sizeof(struct tree));
strcpy(ri->a,b1);
ri->left=NULL;
ri->right=NULL;
temp2->right=ri;
}
if(front!=NULL)
enqu(temp2->a,temp2->s);
tt[z++]=temp2;
}
}

//Display Tree
void disp(struct tree *rt)
{
if(rt!=NULL)
{
disp(rt->left);
//cout<<””<<rt->a;disp(rt->right);
}
}

//Display Name
void displayname(int idx)
{
cout<<name[idx]<<”: ”;
}

/*
End of operations
*/


//Main Method

int main()
{
while(1)
{
//Clear Screen
clrscr();

cout<<”Enter the total no of leafs : ”;
cin>>n;


for(i=0;i<n;i++,alpha++)
{
cout<<”Enter Name: ”;
cin>>name[i];

//itoa(alpha,m,10);
//strcpy(m,(char*)alpha[i]);
*m=(char)alpha; //Assigning Local Values
strcpy(b[i],m);

cout<<”Enter frequency for ”<<name[i]<<” : ”;
cin>>g;

//Enque to the list
enqu(m,g);

} //Repeat till all the leafs data entered

insert(); // Form the tree
disp(root); // Display the codeword of leaf from root


for(i=0;i<n;i++)
{
displayname(i);
info(b[i]);
cout<<”n”;
}

cout<<”nDo You Want To Continue Y or N: ”;
cin>>re;
clrscr();
if(re=='y'||re=='Y')
continue;
else
break; //exit(0);
}

return 0;
}//end of while

Output:

I am also making this as an open source code. Anyone can edit, share, re-distribute the code.

For further queries, please mail to psrdotcom@gmail.com

My first Matlab Program, Encode and Decode image using Huffman Coding

For the academic purpose i had written a small program in Matlab.

I have tried encoding and decoding the image by using Huffman coding.

Huffman code generally used for data encoding but i tried Huffman coding on small image.

Preconditions:

1. You need to create a small image, in my code i am using PSR.jpg
2. It will work well only with small images

Matlab Code:

%Huffman Coding on image by Suresh Raju Pilli

%clearing all variableas and screen
clear all;
close all;
clc;

%Reading image
a=imread('psr.JPG');
figure,imshow(a)

%converting an image to grayscale
I=rgb2gray(a);

%size of the image
[m,n]=size(I);
Totalcount=m*n;

%variables using to find the probability
cnt=1;
sigma=0;

%computing the cumulative probability.
for i=0:255
k=I==i;
count(cnt)=sum(k(:))

%pro array is having the probabilities
pro(cnt)=count(cnt)/Totalcount;
sigma=sigma+pro(cnt);
cumpro(cnt)=sigma;
cnt=cnt+1;
end;


%Symbols for an image
symbols = [0:255];

%Huffman code Dictionary
dict = huffmandict(symbols,pro);

%function which converts array to vector
vec_size = 1;
for p = 1:m
for q = 1:n
newvec(vec_size) = I(p,q);
vec_size = vec_size+1;
end
end

%Huffman Encodig
hcode = huffmanenco(newvec,dict);

%Huffman Decoding
dhsig1 = huffmandeco(hcode,dict);

%convertign dhsig1 double to dhsig uint8
dhsig = uint8(dhsig1);

%vector to array conversion
dec_row=sqrt(length(dhsig));
dec_col=dec_row;

%variables using to convert vector 2 array
arr_row = 1;
arr_col = 1;
vec_si = 1;

for x = 1:m
for y = 1:n
back(x,y)=dhsig(vec_si);
arr_col = arr_col+1;
vec_si = vec_si + 1;
end
arr_row = arr_row+1;
end


%converting image from grayscale to rgb
[deco, map] = gray2ind(back,256);
RGB = ind2rgb(deco,map);
imwrite(RGB,'decoded.JPG');

%end of the huffman coding

Postcondition:

1. Check the original image and decoded image
2. Analyze the compression ratio.

You can easily understand the code. Its not at all difficult.

Please send your feedback and comments to psrdotcom@gmail.com