In python 6. 75 points Program C Huffman Coding For this program you will implem
ID: 3906160 • Letter: I
Question
In python
6. 75 points Program C Huffman Coding For this program you will implement Huffman Coding. The program will take a file name as a command line argument, process it, and produce a prefix-free, variable length binary encoding that minimizes the average codeword lengtlh In addition, your program should output: the encoding, the average codeword length, the total number of bits in the original file (simply the total number of characters multiplied by 8), the total number of bits in the encoded file, and the compression ratio. Your output should resemble something like Character Codeword Frequency 111 17. 7848% 01111011100 0.0502% 1101010 1.0038% 011110110 0.2008% 0111100 0.7194% 1101011100010 0.0167% 1010111000 0.1004% 2 101011101 0.2175% 10101111010 0.0669% 10101111011 0.0669% 10101110010 0.0502% .. . [output truncated for length] Average Codeword Length: 4.386 bits Original Size (bits): 47816 Encoding Size (bits): 26219 Compression Ratio: 54.833% Name your test case files . input001.txt output001.txt input002.txt output002.txt respectivelyExplanation / Answer
#include <stdlib.h>
#include <minheap.h>
struct huffman_node {
char data;
unsigned int frequency;
struct huffman_node *left;
struct huffman_node *right;
};
typedef struct huffman_node huffman_node;
huffman_node *huffman_node_create(char data, unsigned int frequency)
{
huffman_node *node = malloc(sizeof(huffman_node));
if (node) {
node->data = data;
node->frequency = frequency;
node->left = NULL;
node->right = NULL;
}
return node;
}
void huffman_node_delete(huffman_node *node)
{
if (node) {
huffman_node_delete(node->left);
huffman_node_delete(node->right);
free(node);
}
}
unsigned int max(unsigned int a, unsigned int b)
{
return a > b ? a : b;
}
unsigned int huffman_node_height(const huffman_node *node)
{
unsigned int height = 0;
if (node->left || node->right) {
height = max(node->left ? huffman_node_height(node->left) : 0,
node->right ? huffman_node_height(node->right) : 0) + 1;
}
return height;
}
void huffman_node_print(const huffman_node *node, unsigned int indent)
{
unsigned int i;
for (i = 0; i < indent; i++) {
printf(" ");
}
printf("%c %u ", node->data, node->frequency);
if (node->left != NULL) {
huffman_node_print(node->left, indent + 1);
}
if (node->right != NULL) {
huffman_node_print(node->right, indent + 1);
}
}
typedef void huffmanfn(char, const unsigned int *, size_t);
void huffman_node_encodings(const huffman_node *node, unsigned int *arr,
unsigned int pos, huffmanfn fun)
{
if (node->left) {
arr[pos] = 0;
huffman_node_encodings(node->left, arr, pos + 1, fun);
}
if (node->right) {
arr[pos] = 1;
huffman_node_encodings(node->right, arr, pos + 1, fun);
}
if (!(node->left || node->right)) {
fun(node->data, arr, pos);
}
}
void huffman(const char *letters, const int *frequencies, size_t size, huffmanfn fun)
{
minheap *heap = minheap_create();
unsigned int i;
huffman_node *top;
unsigned int *arr;
/* Populate the heap */
for (i = 0; i < size; i++) {
minheap_add(heap, huffman_node_create(letters[i], frequencies[i]), frequencies[i]);
}
/* Build the tree */
while (minheap_get_count(heap) != 1) {
huffman_node *left = minheap_remove_min(heap);
huffman_node *right = minheap_remove_min(heap);
top = huffman_node_create('$', left->frequency + right->frequency);
top->left = left;
top->right = right;
minheap_add(heap, top, top->frequency);
}
top = minheap_remove_min(heap);
/* Generate the encodings */
arr = malloc(huffman_node_height(top) * sizeof(unsigned int));
huffman_node_encodings(top, arr, 0, fun);
/* Clean up */
huffman_node_delete(top);
free(arr);
minheap_delete(heap);
}
Example program:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void print(char letter, const unsigned int *arr, size_t len)
{
unsigned int i;
printf("%c: ", letter);
for (i = 0; i < len; i++) {
printf("%u", arr[i]);
}
putchar(' ');
}
int main(void)
{
char letters[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int frequencies[] = {45, 13, 12, 16, 9, 5};
const size_t size = sizeof(letters) / sizeof(letters[0]);
huffman(letters, frequencies, size, print);
return 0;
}
The output:
#include <stdlib.h>
#include <minheap.h>
struct huffman_node {
char data;
unsigned int frequency;
struct huffman_node *left;
struct huffman_node *right;
};
typedef struct huffman_node huffman_node;
huffman_node *huffman_node_create(char data, unsigned int frequency)
{
huffman_node *node = malloc(sizeof(huffman_node));
if (node) {
node->data = data;
node->frequency = frequency;
node->left = NULL;
node->right = NULL;
}
return node;
}
void huffman_node_delete(huffman_node *node)
{
if (node) {
huffman_node_delete(node->left);
huffman_node_delete(node->right);
free(node);
}
}
unsigned int max(unsigned int a, unsigned int b)
{
return a > b ? a : b;
}
unsigned int huffman_node_height(const huffman_node *node)
{
unsigned int height = 0;
if (node->left || node->right) {
height = max(node->left ? huffman_node_height(node->left) : 0,
node->right ? huffman_node_height(node->right) : 0) + 1;
}
return height;
}
void huffman_node_print(const huffman_node *node, unsigned int indent)
{
unsigned int i;
for (i = 0; i < indent; i++) {
printf(" ");
}
printf("%c %u ", node->data, node->frequency);
if (node->left != NULL) {
huffman_node_print(node->left, indent + 1);
}
if (node->right != NULL) {
huffman_node_print(node->right, indent + 1);
}
}
typedef void huffmanfn(char, const unsigned int *, size_t);
void huffman_node_encodings(const huffman_node *node, unsigned int *arr,
unsigned int pos, huffmanfn fun)
{
if (node->left) {
arr[pos] = 0;
huffman_node_encodings(node->left, arr, pos + 1, fun);
}
if (node->right) {
arr[pos] = 1;
huffman_node_encodings(node->right, arr, pos + 1, fun);
}
if (!(node->left || node->right)) {
fun(node->data, arr, pos);
}
}
void huffman(const char *letters, const int *frequencies, size_t size, huffmanfn fun)
{
minheap *heap = minheap_create();
unsigned int i;
huffman_node *top;
unsigned int *arr;
/* Populate the heap */
for (i = 0; i < size; i++) {
minheap_add(heap, huffman_node_create(letters[i], frequencies[i]), frequencies[i]);
}
/* Build the tree */
while (minheap_get_count(heap) != 1) {
huffman_node *left = minheap_remove_min(heap);
huffman_node *right = minheap_remove_min(heap);
top = huffman_node_create('$', left->frequency + right->frequency);
top->left = left;
top->right = right;
minheap_add(heap, top, top->frequency);
}
top = minheap_remove_min(heap);
/* Generate the encodings */
arr = malloc(huffman_node_height(top) * sizeof(unsigned int));
huffman_node_encodings(top, arr, 0, fun);
/* Clean up */
huffman_node_delete(top);
free(arr);
minheap_delete(heap);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.