代写Prefix Codes、代做C/C++语言、代写bit sequences、C/C++程序代做

日期：2018-12-18 09:04

Project 2

Assign 2018-11-28   Due 2018-12-17

Huffman encoding/decoding

Problem description: Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.

The variable-length codes assigned to input characters are Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not prefix of code assigned to any other character.

Steps to build Huffman Tree

The input is an array of unique characters along with their frequency of occurrences and the output is the Huffman Tree.

1. Create a leaf node for each unique character and build a min heap of all leaf nodes (The Min Heap is used as a priority queue. The value of the frequency field is used to compare two nodes in the min heap. Initially, the least frequent character is at the root.)

2. Extract two nodes with the minimum frequency from the min heap.

3. Create a new internal node with the frequency equal to the sum of the two nodes’ frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

4. Repeat steps 2 and 3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

Example:

Character   Frequency    Huffman Code

   a            5                1100

   b            9                1101

   c           12                100

   d           13                101

   e           16                111

   f           45                0

Submit:

1.File to submit: CS206_studentID_name(CN).h

2.The following class definition is included in your header file. You should complete the methods of the class in the .cpp file.

1.class huffmanTree;

2.// node for binary tree

3.class btnode{

4.public:

5.char data; // character

6.int frequency; // frequency

7.string code; // code for the node: if node is left child, code is 0. right child is 1.

8.btnode *lchild,*rchild;

9.};

10.

11.class huffmanTree{

12.private:

13.btnode *t; // t is root of the huffman tree

14.btnode **pq;//priority queue

15.int size_pq;

16.

17.public:

18.huffmanTree(int n);

19.void generate_leaf_node(int n, char *arr, int *frequency);

20.void insert_pq(btnode *tnode);// insert one node into priority queue

21.btnode* extractMin_pq();// extract mininmum weight node from priority queue

22.void display_pq();

23.void generate_huffmanTree(); // generate huffman tree

24.btnode* get_tree(); // get the huffman tree

25.void huffman_code(btnode *tnode,string code); //display huffman code of leaf nodes

26.

27.};

28.The description of the class huffmanTree is as follows:

a)The method “insert_pq(btnode *tnode)”is to insert one node into the priority queue “pq”.

Note: The min Heap is used as a priority queue. The priority queue “pq” should be a heap after one node is inserted.

b)The method “generate_leaf_node(int n, char *arr, int *frequency)” is to generate leaf nodes and they are inserted into the priority queue “pq” one by one.

c)The method “extractMin_pq()” is to extract the minimum frequency node from the priority queue “pq”.

Note: After removing the minimum, “pq” is still a min heap.

d)“display_pq()” is to output all elements of the priority queue “pq”.

e)“generate_huffmanTree()” is to generate the Huffman tree. “t” is the root of the tree.

f)“get_tree()” is to get the root “t” of the Huffman tree.

g)“huffman_code(btnode *tnode,string code)” is to output Huffman codes of all leaf nodes. You can use a recursion or stack to get the Huffman codes. Also, the function could be overloaded.

29.Score

a)The method “display_pq()” can output “character”, “frequency” of each node in priority queue “pq”. (10%)

b)After the method “insert_pq(btnode *tnode)” is implemented, “pq” must be a heap. (20%)

c)extractMin_pq() extracts the minimum frequency node from “pq”. And the priority queue “pq” is still a heap. (30%)

d)The Huffman tree should be generated by “generate_huffmanTree()” correctly. “t” is the root of the tree. (20%)

e)Get Huffman codes of all characters correctly. (20%)

30.The following file can be used to test your code.

int main(){

char arr1[] = { 'a', 'b', 'c', 'd', 'e', 'f' };

int freq1[] = { 5, 9, 12, 13, 16, 45 };

char arr2[] = { 's', 't', 'u', 'v', 'w', 'x'};

int freq2[] = { 5, 19, 12, 13, 16, 45 };

huffmanTree ht1(6),ht2(6);

ht1.generate_leaf_node(6, arr1, freq1);

cout << "the first test priority queue is "<<endl;

ht1.display_pq();

ht1.generate_huffmanTree();

btnode *t1 = ht1.get_tree();

cout << "the first test Huffman code is "<<endl;

string code1;

ht1.huffman_code(t1,code1);

// huffman_code could be overloaded

// ht1.huffman_code();

ht2.generate_leaf_node(6, arr2, freq2);

 cout << "the second test priority queue is "<<endl;

ht2.display_pq();

ht2.generate_huffmanTree();

btnode *t2 = ht2.get_tree();

cout << "the second test Huffman code is "<<endl;

string code2;

ht2.huffman_code(t2,code2);

// huffman_code could be overloaded

// ht2.huffman_code();

return 0;

}