Instructions
Objective
Write a program to implement encoder in c++
Requirements and Specifications
To complete C++ assignment, you will create a multithreaded Shannon-Fano-Elias encoder (https://en.wikipedia.org/wiki/Shannon–Fano–Elias_coding).
To determine the codes for the symbols using the Shannon-Fano-Elias encoder, you must execute the following steps:
- 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).
Given the symbols with their probabilities (sorted in decreasing order based on the probability value), you need to implement the Shannon-Fano-Elias encoding algorithm based on the following steps:
- 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:
- A string representing the symbols. A single character represents each symbol, and a single white space separates the symbols.
- A list of double values representing the probabilities of the symbols
The symbols from the input are sorted (in decreasing order) based on their probabilities.
Given the previous format, the following file represents a valid input file:
A B C D E
0.3 0.25 0.2 0.15 0.1
- Create n POSIX threads (where n is the number of symbols to encode). Each child thread executes the following tasks:
Receives the probabilities of the symbols from the main thread.
Implements the Shannon-Fano-Elias encoding algorithm to determine the code for the assigned symbol.
Stores the code on a memory location accessible by the main thread.
- Print the Shannon-Fano-Elias codes for the symbols from the input file. Given the previous input, the expected output is:
SHANNON-FANO-ELIAS Codes:
Symbol A, Code: 001
Symbol B, Code: 011
Symbol C, Code: 1010
Symbol D, Code: 1101
Symbol E, Code: 11110
NOTES:
- 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;
}
Similar Samples
At ProgrammingHomeworkHelp.com, our samples showcase the high-quality solutions provided by our expert programmers. Each example demonstrates our commitment to accuracy, efficiency, and clarity, ensuring you receive top-notch assistance for your programming assignments. Explore our samples to see the excellence we deliver in every project.
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++
C++