Instructions
Requirements and Specifications
- Arrange the symbols according to decreasing probabilities.
- Calculate cumulative probability.
- Calculate modified cumulative distribution function.
- Find the length of the code.
- Generate the code word by finding the binary of Fbar(x) with respect to length l(x).
- Read the input from STDIN (the Moodle server will implement input redirection to send the information from a file to STDIN). The format of the input file is as follows:
- Create n POSIX threads (where n is the number of symbols to encode). Each child thread executes the following tasks:
- Print the Shannon-Fano-Elias codes for the symbols from the input file. Given the previous input, the expected output is:
- Not using multiple POSIX threads to implement your solution will translate into a penalty of 100%.
- You must use the output statement format based on the example above.
- You can safely assume that the input will always be valid.
Source Code
#include
using namespace std;
struct node {
string sym;
float pro;
int arr[20];
int top;
} p[20];
typedef struct node node;
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)] = 1;
for (i = k + 1; i <= h; i++)
p[i].arr[++(p[i].top)] = 0;
shannon(l, k, p);
shannon(k + 1, h, p);
}
}
void sortByProbability(int n, node p[])
{
int i, j;
node temp;
for (j = 1; j <= n - 1; j++) {
for (i = 0; i < n - 1; i++) {
if ((p[i].pro) > (p[i + 1].pro)) {
temp.pro = p[i].pro;
temp.sym = p[i].sym;
p[i].pro = p[i + 1].pro;
p[i].sym = p[i + 1].sym;
p[i + 1].pro = temp.pro;
p[i + 1].sym = temp.sym;
}
}
}
}
void display(int n, node p[])
{
int i, j;
cout << "\n\n\n\tSymbol\tProbability\tCode";
for (i = n - 1; i >= 0; i--) {
cout << "\n\t" << p[i].sym << "\t\t" << p[i].pro << "\t";
for (j = 0; j <= p[i].top; j++)
cout << p[i].arr[j];
}
}
// Driver code
int main()
{
int n, i, j;
float total = 0;
string ch;
node temp;
cout << "Enter number of symbols\t: ";
n = 5;
cout << n << endl;
for (i = 0; i < n; i++) {
cout << "Enter symbol " << i + 1 << " : ";
ch = (char)(65 + i);
cout << ch << endl;
p[i].sym += ch;
}
// Input probability of symbols
float x[] = { 0.3, 0.25, 0.2, 0.15, 0.1 };
for (i = 0; i < n; i++) {
cout << "\nEnter probability of " << p[i].sym << " : ";
cout << x[i] << endl;
p[i].pro = x[i];
total = total + p[i].pro;
// checking max probability
if (total > 1) {
cout << "Invalid. Enter new values";
total = total - p[i].pro;
i--;
}
}
p[i].pro = 1 - total;
sortByProbability(n, p);
for (i = 0; i < n; i++)
p[i].top = -1;
shannon(0, n - 1, p);
// Display the codes
display(n, p);
return 0;
}