## 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++