Shanno - Fano Code

/*
The Shannon-Fano Algorithm

This is a basic information theoretic algorithm. A simple example will be used to illustrate the algorithm:


Symbol A B C D E
----------------------------------
Count 15 7 6 6 5

Encoding for the Shannon-Fano Algorithm:


A top-down approach
1. Sort symbols according to their frequencies/probabilities, e.g., ABCDE.

2. Recursively divide into two parts, each with approx. same number of counts.




Symbol Count log(1/p) Code Subtotal (# of bits)
------ ----- -------- --------- --------------------
A 15 1.38 00 30
B 7 2.48 01 14
C 6 2.70 10 12
D 6 2.70 110 18
E 5 2.96 111 15
TOTAL (# of bits): 89

*/

#include< stdio.h>
#include< conio.h>
#include< string.h>
struct node
{
char sym[10];
float pro;
int arr[20];
int top;
}s[20];

typedef struct node node;

void prints(int l,int h,node s[])
{
int i;
for(i=l;i< =h;i++)
{
printf("\n%s\t%f",s[i].sym,s[i].pro);
}
}

void shannon(int l,int h,node s[])
{
float pack1=0,pack2=0,diff1=0,diff2=0;
int i,d,k,j;
if((l+1)==h || l==h || l>h)
{
if(l==h || l>h)
return;
s[h].arr[++(s[h].top)]=0;
s[l].arr[++(s[l].top)]=1;
return;
}
else
{
for(i=l;i< =h-1;i++)
pack1=pack1+s[i].pro;
pack2=pack2+s[h].pro;
diff1=pack1-pack2;
if(diff1< 0)
diff1=diff1*-1;
j=2;
while(j!=h-l+1)
{
k=h-j;
pack1=pack2=0;
for(i=l;i< =k;i++)
pack1=pack1+s[i].pro;
for(i=h;i>k;i--)
pack2=pack2+s[i].pro;
diff2=pack1-pack2;
if(diff2< 0)
diff2=diff2*-1;
if(diff2>=diff1)
break;
diff1=diff2;
j++;
}
k++;
for(i=l;i< =k;i++)
s[i].arr[++(s[i].top)]=1;
for(i=k+1;i< =h;i++)
s[i].arr[++(s[i].top)]=0;
shannon(l,k,s);
shannon(k+1,h,s);
}
}

void main()
{
int n,i,j;
float x,total=0;
char ch[10];
node temp;
clrscr();
printf("Enter How Many Symbols Do You Want To Enter\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("Enter symbol %d ---> ",i+1);
scanf("%s",ch);
strcpy(s[i].sym,ch);
}
for(i=0;i< n;i++)
{
printf("\n\tEnter probability for %s ---> ",s[i].sym);
scanf("%f",&x);
s[i].pro=x;
total=total+s[i].pro;
if(total>1)
{
printf("\t\tThis probability is not possible.Enter new probability");
total=total-s[i].pro;
i--;
}
}
s[i].pro=1-total;
for(j=1;j< =n-1;j++)
{
for(i=0;i< n-1;i++)
{
if((s[i].pro)>(s[i+1].pro))
{
temp.pro=s[i].pro;
strcpy(temp.sym,s[i].sym);
s[i].pro=s[i+1].pro;
strcpy(s[i].sym,s[i+1].sym);
s[i+1].pro=temp.pro;
strcpy(s[i+1].sym,temp.sym);
}
}
}
for(i=0;i< n;i++)
s[i].top=-1;

shannon(0,n-1,s);
printf("---------------------------------------------------------------");
printf("\n\n\n\tSymbol\tProbability\tCode");
for(i=n-1;i>=0;i--)
{
printf("\n\t%s\t%f\t",s[i].sym,s[i].pro);
for(j=0;j< =s[i].top;j++)
printf("%d",s[i].arr[j]);
}
printf("\n---------------------------------------------------------------");
getch();
}

/********************* OUTPUT **************************

Enter How Many Symbols Do You Want To Enter : 6
Enter symbol 1 ---> a
Enter symbol 2 ---> b
Enter symbol 3 ---> c
Enter symbol 4 ---> d
Enter symbol 5 ---> e
Enter symbol 6 ---> f

Enter probability for a ---> 0.3

Enter probability for b ---> 0.25

Enter probability for c ---> 0.20

Enter probability for d ---> 0.12

Enter probability for e ---> 0.08

Enter probability for f ---> 0.05


---------------------------------------------------------------
Symbol Probability Code
a 0.300000 00
b 0.250000 01
c 0.200000 10
d 0.120000 110
e 0.080000 1110
f 0.050000 1111
---------------------------------------------------------------
*/