SHANNON FANO
In the field of data compression, Shannon–Fano coding, named after Claude Shannon and Robert Fano, is a technique for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). It is suboptimal in the sense that it does not achieve the lowest possible expected code word length like Huffman coding.
In Shannon–Fano coding, the symbols are arranged in order from most probable to least probable, and then divided into two sets whose total probabilities are as close as possible to being equal. All symbols then have the first digits of their codes assigned; symbols in the first set receive "0" and symbols in the second set receive "1". As long as any sets with more than one member remain, the same process is repeated on those sets, to determine successive digits of their codes. When a set has been reduced to one symbol this means the symbol's code is complete and will not form the prefix of any other symbol's code.
Code:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
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);
}
}
int main()
{
int n,i,j;
float x,total=0,entropy=0, avgcode=0,efficiency;
char ch[10];
node temp;
printf("Enter How Many Symbols You Want To Enter\t: ");
scanf("%d",&n);
printf("\n\t\t\t\t\tSymbol\tProbability");
for(i=0;i< n;i++)
{
printf("\nEnter symbol and probability for %d ---> ",i+1);
scanf("%s%f",ch,&x);
strcpy(s[i].sym,ch);
s[i].pro=x;
total=total+s[i].pro;
entropy=entropy+(s[i].pro*log2 (1/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);
system("CLS");
printf("----------------------------SHANNON-FANO CODING------------------------");
printf("\n\n\n\t\tSymbol\tProbability\tCodeword\tCodeword length\n");
for(i=n-1;i>=0;i--)
{
printf("\n\t\t %s\t %.2f\t\t",s[i].sym,s[i].pro);
for(j=0;j<=s[i].top;j++)
printf("%d",s[i].arr[j]);
printf("\t\t%d",j);
avgcode=avgcode+(s[i].pro*j);
}
efficiency=(entropy/avgcode)*100;
printf("\n-----------------------------------------------------------------------");
printf("\nEntropy of this code is:\t\t%.2f bits",entropy);
printf("\nAverage Code Length of this code is:\t%.2f bits",avgcode);
printf("\nEfficiency of this code is:\t\t%.2f Percent",efficiency);
getch();
return 0;
}
Output:
Comments
Post a Comment