I am having trouble getting the desired output using shanno- fanno compression algorithm. I am unsure where the problem is. My output is not matching the desired output. Where am I making the mistake and why is my output different from the desired output.
my output =
Symbol A, Code: 001
Symbol B, Code: 000
Symbol C, Code: 0101
Symbol D, Code: 0100
Symbol E, Code: 0111
desired output =
Symbol A, Code: 001
Symbol B, Code: 011
Symbol C, Code: 101
Symbol D, Code: 1100
Symbol E, Code: 11110
#include <cstdlib>
#include <bits/stdc++.h>
#include <iostream>
#include <istream>
#include <fstream>
#include <vector>
#include <string>
#include <ctype.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct node {
// for storing symbol
char sym;
// for storing probability or frequency
float pro;
int arr[20];
int top;
} p[20];
typedef struct node node;
// function to find shannon code
void shannon(int l, int h, node p[])
{
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;
p[h].arr[++(p[h].top)] = 0;
p[l].arr[++(p[l].top)] = 1;
return;
}
else {
for (i = l; i <= h - 1; i++)
pack1 = pack1 + p[i].pro;
pack2 = pack2 + p[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 + p[i].pro;
for (i = h; i > k; i--)
pack2 = pack2 + p[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++)
p[i].arr[++(p[i].top)] = 0;
for (i = k + 1; i <= h; i++)
p[i].arr[++(p[i].top)] = 1;
// Invoke shannon function
shannon(l, k, p);
shannon(k + 1, h, p);
}
}
void display(int n, node p[])
{
int i, j;
for (i = 0 ; i < n; i++) {
cout << endl <<"Symbol " << p[i].sym << "," << " " <<"Code: ";
for (j = 0; j <= p[i].top; j++)
cout << p[i].arr[j];
}
}
int main() {
// store symbols from standard input pass by refrence to function //
int size = 20;
char symbol[size];
float integer[size];
float tot = 0;
node temp;
int n = 5;
for(int i = 0; i < n; i++){
cin >> symbol[i];
p[i].sym = symbol[i];
cout << p[i].sym << endl;
}
for(int i = 0; i < n ; i++) {
cin >> integer[i];
p[i].pro = integer[i];
cout << p[i].pro << endl;
}
// Find the shannon code
shannon(0, n, p);
// Display the codes
display(n, p);
return 0;
}