Assignment 15 Huffman Code

Sample Test and Output

enter a sentence: aaaaaaaaaabbbbbcccdeeffffgggggggghhhhhhhhhhhh F 4 000 B 5 001 A 10 01 H 12 10 C 3 1100 D 1 11010 E 2 11011 G 8 111 the sorted Huffman code list: (not in starter, must be completed by you) H 12 10 A 10 01 G 8 111 B 5 001 F 4 000 C 3 1100 E 2 11011 D 1 11010 +-- 8G111 +-- 14*11 | | +-- 2E11011 | | +-- 3*1101 | | | +-- 1D11010 | +-- 6*110 | +-- 3C1100 +-- 26*1 | +-- 12H10 +-- 45* | +-- 10A01 +-- 19*0 | +-- 5B001 +-- 9*00 +-- 4F000 

Convention: 4F000: frequency 4, letter F, code 000

Another example test run:

Enter a text string: the ai is hot, iot is not, iota is [1]->e [1]->n [2]->a [2]->h [3]->s [4]->o [5]->t [6]->i +-- 1n1 +-- 2_ +-- 1e0 +-- 1n11 +-- 2_1 | +-- 1e10 +-- 4_ +-- 2h0 +-- 3s1 +-- 5_ +-- 2a0 +-- 4o1 +-- 8_ | +-- 1n011 | +-- 2_01 | | +-- 1e010 +-- 4_0 +-- 2h00 +-- 3s11 +-- 5_1 | +-- 2a10 +-- 10_ +-- 5t0 +-- 4o11 +-- 8_1 | | +-- 1n1011 | | +-- 2_101 | | | +-- 1e1010 | +-- 4_10 | +-- 2h100 +-- 14_ +-- 6i0 +-- 4o111 +-- 8_11 | | +-- 1n11011 | | +-- 2_1101 | | | +-- 1e11010 | +-- 4_110 | +-- 2h1100 +-- 14_1 | +-- 6i10 +-- 24_ | +-- 3s011 | +-- 5_01 | | +-- 2a010 +-- 10_0 +-- 5t00 t 5 00 a 2 010 s 3 011 i 6 10 h 2 1100 e 1 11010 n 1 11011 o 4 111 

Starter: in class github

Submit:

Do a map data structure to capture the requency of characters entered. Do NOT use an array/vector of all 26 characters.

Use this Test Pattern

aaaaaaaaaabbbbbcccdeeffffgggggggghhhhhhhhhhhh for your submitted test.

Do not convert to upper case!

huffman.cpp

validation (15 points)

Illustration with trace mode for the Huffman tree build up step by step (15 points)

Starter:

#include

using namespace std;

bool TRACE=true;

class Node {

public:

int freq;

char val;

string code;

Node *left, *right;

Node():left(nullptr), right(nullptr), freq(0), val('_'){} };

class Huffman {

class cmp {

public: bool operator() (const Node* a, const Node* b) const

{ return a->freq > b->freq; } };

Node* root=nullptr;

priority_queue, cmp> Q;

vector list;

public:

Huffman(){}

void add( int freq, char val ) {

Node* node = new Node();

node->freq = freq;

node->val =val;

Q.push(node);

}

void build() {

while (Q.size() > 1) {

Node* first = Q.top(); Q.pop();

Node* second = Q.top(); Q.pop();

Node* tmp = new Node();

tmp->val = '_';

tmp->freq = first->freq + second->freq;

tmp->left = first;

tmp->right = second;

if(TRACE) { root=tmp; draw(); }

Q.push(tmp);

}

root=Q.top();

}

void show() {

if(!root) return;

show(root, "");

}

void show(Node* node, string coding) {

if (!node) return;

if (node->val != '_') {

Node tmp;

tmp.val = node->val;

tmp.freq = node->freq;

node->code = tmp.code = coding;

list.push_back(tmp);

cout << node->val <<" " << node->freq <<" "<< tmp.code << endl;

return;

}

show(node->left, coding + "0");

show(node->right, coding + "1");

}

void draw() const {

if(!root) return;

cout << endl;

draw(root, " ", " ", "");

cout << endl;

}

void draw(Node* treePtr, string lpad, string rpad, string coding) const {

string pad = lpad.substr(0, lpad.size() - 1);

if (treePtr == nullptr) return;

draw(treePtr->right, rpad + " |", rpad + " ", coding + "1");

cout << pad << "+--" << setw(3) << treePtr->freq << treePtr->val << coding << endl;

draw(treePtr->left, lpad + " ", lpad + " |", coding + "0");

}

};

int main () {

string input;

cout << "Enter a text string: "; // the ai is hot, iot is not, iota is

// getline(cin, input);

map freq = { {'A', 2}, {'E', 1}, {'H', 2}, {'I', 6},

{'N', 1}, {'O', 4}, {'S', 3}, {'T', 5} };

// Instead you can process the input words here

Huffman H;

multimap> Occur;

for (auto ch:freq) {

Occur.insert(pair(ch.second, ch.first));

H.add( ch.second, ch.first ); }

for (auto i:Occur)

cout << "[" << i.first << "]->" << i.second << endl;

H.build();

H.show();

return 0;

}