---
tags: 2023DS
---
# 2023 Data Structure - Homework 5
## Huffman Coding
* Deadline: 6/2 - 14:00
* Upload your homework to **moodle** platform.
* Please consult with TA if you have any questions.
* FB or email
## Problem
After learning Chapter 5, you should learn **Huffman Coding** to compress data to reduce memory usage and speed up data transmission.

Please review Chapter 5 slide - p.127.

Now, Given a set of a characters and a string, please use Huffman Coding to create the Huffman codes and encode the string.
## Input Description
First $n$ lines contain a set of $n$ characters including their frequencies. Then, seperated by a blank, the following one line is a string that consists of the characters in the set.
### Sample Input
* ```samp.in``` / ```sampin.txt```

A 15
B 7
C 6
D 6
E 5

BDCEA

* ```test.in``` / ```testin.txt```

A 1
B 11
C 6
D 4
E 17
F 15
G 15

FFGBCDAAE

## Output Description
Please implement Huffman Coding, and show your Huffman codes and the encoded string.
### Sample Output
Here shows the output format
* ```samp.out``` / ```sampout.txt```

A 0
B 100
C 101
D 110
E 111

1001101011110

test output filename: ```test.out``` / ```testout.txt```
## Restriction
**C++ STL containers**, such as ```<stack>```, ```<vector>```... , **are forbidden** for this homework.
## Note
Compress all the files (including your report and source code files), and name the compressed file as ```A1105500_hw5.zip(or .rar)``` using your student ID. Then upload the compressed file to the **moodle** platform.

For this homework, TA doesn't provide test case files, please create the input files by yourself. **But, also, you should submit your output files.**

The file structure should be like following forms:

|-A1105500_hw5.zip (.rar)
| |-main.cpp
| |-xxx.h
| |-xxx.cpp
| |-Report.pdf
| |-(And other files...)

or

|-A1105500_hw5.zip (.rar)
| |-A1105500 (Folder)
| | |-main.cpp
| | |-xxx.h
| | |-xxx.cpp
| | |-Report.pdf
| | |-(And other files...)

**Don't cheating**, or you will get 0 for this homework. If you can’t finish this homework before deadline, just hand in your unfinished code and report.

**Be honest with yourself.**
## Score
* Source code: 80% + 5%
* Bonus: Design a ```HuffmanTree``` class.
* test files:
* ```samp.out``` / ```sampout.txt```: 5%
* ```test.out``` / ```testout.txt```: 5%
* **TA will use a program to read your output file, and try to decode the original string, which occurs in input file.**
* So, for your output file, **Please output the correct format.**
* Report: 10% + 5%
* Please describe your implementation of Huffman Coding.
* If you design a ```HuffmanTree``` class, please also describe your consideration. (Bonus 5%)
* Just write 1 ~ 4 pages
## Hint
### About Huffman Tree...
#### Implementation
This homework may be a little to use ```class``` to build a Huffman tree, so **you don't need to design a class like ```HuffmanTree``` to finish this homework.**

For example, you can just use C ```struct``` to finish it.

#include <iostream>
...

struct HuffmanNode {
	char ch;
	int freq;
	HuffmanNode *left;
	HuffmanNode *right;
};

int main(void) {
	// Create some Huffman trees.
	//...
	
	return 0;
}

#### Huffman Coding has many different combinations.
[When implementing Huffman Coding...](https://en.wikipedia.org/wiki/Huffman_coding#/media/File:HuffmanCodeAlg.png)
* You should notice that **Huffman Coding doesn't describe two nodes' order!**
* Changing left node and right node is accepted.
* But, **it must be decoded to original data after encoding.**
### Create Huffman Code can be ideal
* Because our two test cases contain **consecutive characters (A-E, A-G)**, you can record the Huffman Codes like the following way.

#include <string>

string huffman_code[10];

huffman_code[ch - 'A'] = ch_code;

### Useful function
You may need to sort an array, and the header ```<algorithm>``` provides a function ```sort()```.

Here shows some examples.
* General usage

	#include <algorithm>
	
	int main(void) {
		int array[100];
		// Given array some values...
		sort(array, array + 100);
		// print the contents of array...
		return 0;
	}

* Compare function (Notice the difference between this and the previous example.)

	#include <algorithm>
	
	bool cmp(int a, int b) {
		return a > b;
	}

	int main(void) {
		int array[100];
		// Given array some values...
		sort(array, array + 100, cmp);
		// print the contents of array...
		return 0;
	}

* ? ? ?

	#include <algorithm>
	
	int main(void) {
		int array[100];

		// Given array some values...
		sort(array, array + 100, [&](int a, int b){
			return a > b;
		});
		// print the contents of array...
		return 0;
	}

* If you use the this way, please remember to write down what it is in your report.