I need help with building the program since Huffman's algorithm is not clear. I would appreciate if a pseudo code for encoding and decoding the algorithm is provided, as well as the program for both of them since it deals with English text instead of characters. I'd appreciate it if it was in C++, or Java.
Please see the C++ program for huffman coding below and huffman coding is easy to understand, go through the example for huffman coding in Geekforgeeks.
// C++ program for Huffman Coding
#include <iostream>
#include <cstdlib>
using namespace std;
// This constant can be avoided by explicitly
// calculating height of Huffman Tree
#define MAX_TREE_HT 100
// A Huffman tree node
struct MinHeapNode {
// One of the input characters
char data;
// Frequency of the character
unsigned freq;
// Left and right child of this node
struct MinHeapNode *left, *right;
};
// A Min Heap: Collection of
// min-heap (or Huffman tree) nodes
struct MinHeap {
// Current size of min heap
unsigned size;
// capacity of min heap
unsigned capacity;
// Attay of minheap node pointers
struct MinHeapNode** array;
};
// A utility function allocate a new
// min heap node with given character
// and frequency of the character
struct MinHeapNode* newNode(char data, unsigned freq)
{
struct MinHeapNode* temp
= (struct
MinHeapNode*)malloc
(sizeof(struct MinHeapNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
// A utility function to create
// a min heap of given capacity
struct MinHeap* createMinHeap(unsigned capacity)
{
struct MinHeap* minHeap
= (struct
MinHeap*)malloc(sizeof(struct MinHeap));
// current size is 0
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array
= (struct
MinHeapNode**)malloc(minHeap->
capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
// A utility function to
// swap two min heap nodes
void swapMinHeapNode(struct MinHeapNode** a,
struct MinHeapNode** b)
{
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
// The standard minHeapify function.
void minHeapify(struct MinHeap* minHeap, int idx)
{
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size &&
minHeap->array[left]->
freq < minHeap->array[smallest]->freq)
smallest = left;
if (right < minHeap->size &&
minHeap->array[right]->
freq < minHeap->array[smallest]->freq)
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->array[smallest],
&minHeap->array[idx]);
minHeapify(minHeap,
smallest);
}
}
// A utility function to check
// if size of heap is 1 or not
int isSizeOne(struct MinHeap* minHeap)
{
return (minHeap->size == 1);
}
// A standard function to extract
// minimum value node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
struct MinHeapNode* temp =
minHeap->array[0];
minHeap->array[0]
=
minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
// A utility function to insert
// a new node to Min Heap
void insertMinHeap(struct MinHeap* minHeap,
struct MinHeapNode* minHeapNode)
{
++minHeap->size;
int i = minHeap->size - 1;
while (i && minHeapNode->freq <
minHeap->array[(i - 1) / 2]->freq) {
minHeap->array[i] =
minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}
// A standard function to build min heap
void buildMinHeap(struct MinHeap* minHeap)
{
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap,
i);
}
// A utility function to print an array of size n
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
cout<<
arr[i];
cout<<"\n";
}
// Utility function to check if this node is leaf
int isLeaf(struct MinHeapNode* root)
{
return !(root->left) &&
!(root->right);
}
// Creates a min heap of capacity
// equal to size and inserts all character of
// data[] in min heap. Initially size of
// min heap is equal to capacity
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int
size)
{
struct MinHeap* minHeap =
createMinHeap(size);
for (int i = 0; i < size; ++i)
minHeap->array[i] =
newNode(data[i], freq[i]);
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
// The main function that builds Huffman tree
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int
size)
{
struct MinHeapNode *left, *right, *top;
// Step 1: Create a min heap of capacity
// equal to size. Initially, there are
// modes equal to size.
struct MinHeap* minHeap =
createAndBuildMinHeap(data, freq, size);
// Iterate while size of heap doesn't become
1
while (!isSizeOne(minHeap)) {
// Step 2: Extract the
two minimum
// freq items from min
heap
left =
extractMin(minHeap);
right =
extractMin(minHeap);
// Step 3: Create a new
internal
// node with frequency
equal to the
// sum of the two nodes
frequencies.
// Make the two
extracted node as
// left and right
children of this new node.
// Add this node to the
min heap
// '$' is a special
value for internal nodes, not used
top = newNode('$',
left->freq + right->freq);
top->left =
left;
top->right =
right;
insertMinHeap(minHeap,
top);
}
// Step 4: The remaining node is the
// root node and the tree is complete.
return extractMin(minHeap);
}
// Prints huffman codes from the root of Huffman Tree.
// It uses arr[] to store codes
void printCodes(struct MinHeapNode* root, int arr[], int top)
{
// Assign 0 to left edge and recur
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
// Assign 1 to right edge and recur
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
// If this is a leaf node, then
// it contains one of the input
// characters, print the character
// and its code from arr[]
if (isLeaf(root)) {
cout<<
root->data <<": ";
printArr(arr,
top);
}
}
// The main function that builds a
// Huffman Tree and print codes by traversing
// the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{
// Construct Huffman Tree
struct MinHeapNode* root
= buildHuffmanTree(data,
freq, size);
// Print Huffman codes using
// the Huffman tree built above
int arr[MAX_TREE_HT], top = 0;
printCodes(root, arr, top);
}
// Driver program to test above functions
int main()
{
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f'
};
int freq[] = { 5, 9, 12, 13, 16, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
I need help with building the program since Huffman's algorithm is not clear. I would appreciate...
For this assignment, you will write a program to work with Huffman encoding. Huffman code is an optimal prefix code, which means no code is the prefix of another code. Most of the code is included. You will need to extend the code to complete three additional methods. In particular, code to actually build the Huffman tree is provided. It uses a data file containing the frequency of occurrence of characters. You will write the following three methods in the...
In C++ Having heard you have gotten really good at programming, your friend has come to ask for your help with a simple task. She would like you to implement a program to encrypt the messages she exchanges with her friends. The idea is very simple. Every letter of the alphabet will be substituted with some other letter according to a given key pattern like the one below. "abcdefghijklmnopqrstuvwxyz" "doxrhvauspntbcmqlfgwijezky" // key pattern For example, every 'a' will become a...
cs55(java) please Part 1: You are a programming intern at the student transfer counselor's office. Having heard you are taking CS 55, your boss has come to ask for your help with a task. Students often come to ask her whether their GPA is good enough to transfer to some college to study some major and she has to look up the GPA requirements for a school and its majors in a spreadsheet to answer their question. She would like...
You will construct a Huffman tree based on the given frequencies of 26 English alphabets in upper case plus the space character. An internal tree node class in HuffmanTree with necessary information is required. • You will not randomly switch left and right children when merger two trees. Instead, you will build a right-heavy tree according to the following strategies to select the right child. (1) The tree that is taller will be the right child, i.e., the height is...
Do this using the C language. show me the code being executed and also copy and paste the code so i can try it out for myseld Instructions A cipher is mirrored algorithm that allow phrases or messages to be obfuscated (ie. "scrambled"). Ciphers were an early form of security used to send hidden messages from one party to another. The most famous and classic example of a cipher is the Caesar Cipher. This cypher worked by shifting each letter...
I need help implementing the following code without using filehandling and only getchar(); this is the prompt "The input for your program will be a text file containing a large amount of English. Typically, an English sentence ends with a period (aka, dot). Many years ago, when people used mechanical typewriters, the proper form was to place one space between words in a sentence, but two spaces after the period at the end of the sentence. This rule is no...
I need help in C++ implementing binary search tree. I have the .h file for the binary search tree class. I have 4 classic texts, and 2 different dictionaries. Classic Texts: Alice In Wonderland.txt A Tale of Two Cities.txt Pride And Prejudice.txt War and Peace.txt 2 different dictionaries: Dictionary.txt Dictionary-brit.txt The data structures from the standard template library can not be used.The main program should open the text file, read in the words, remove the punctuation and change all the...
i need help with a mips program to to covert roman numerals to real numbers Lab 4: Roman Numeral Conversion Part A: Due Sunday, 19 May 2019, 11:59 PM Due Friday, 24 May 2019, 11:59 PM Part B: Minimum Submission Requirements Ensure that your Lab4 folder contains the following files (note the capitalization convention): o Diagram.pdf o Lab4. asm O README.txt Commit and push your repository Lab Objective In this lab, you will develop a more detailed understanding of how...
C++ please Programming Assignment #6 Help Me Find The Secret Message Description: This assignment will require that you read in an encrypted message from a file, decode the message, and then output the message to a file. The encryption method being used on the file is called a shift cipher (Info Here). I will provide you with a sample encrypted message, the offset, and the decrypted message for testing. For this project I will provide you main.cpp, ShiftCipher.h, and ShiftCipher.cpp....
Hello I need help with this program. Should programmed in C! Program 2: Sorting with Pointers Sometimes we're given an array of data that we need to be able to view in sorted order while leaving the original order unchanged. In such cases we could sort the data set, but then we would lose the information contained in the original order. We need a better solution. One solution might be to create a duplicate of the data set, perhaps make...