COP 5536程序写作、辅导C/C++编程设

” COP 5536程序写作、辅导C/C++编程设COP 5536 Fall 2020Programming ProjectDue Date: Nov 27th 2020, 11:55 pm ESTIn computer science and information theory, a Huffman code is a particular type of optimal prefix code that iscommonly used for lossless data compression. In this project, you will implement the Huffman encoder anddecoder with the following details.1. Huffman CodingThe first step in this project is to develop a program that generates Huffman codes. The algorithm for this wasdiscussed in Lecture 7. For this project, you need to evaluate which of the following priority queue structuresgives best performance: Binary Heap, 4-way cache optimized heap (lecture 10 slides 23 and 24), and PairingHeap (lecture 15). Write code to generate Huffman trees using these three data structures and then measurerun time using input data of sample_input_large.txt. Use the following code as reference (this is in C++, use asimilar approach if you are using some other programming language):clock_t start_time;// binary heapstart_time = clock();for(int i = 0; i 10; i++){ //run 10 times on given data setbuild_tree_using_binary_heap(freq_table);} cout Time Using binary heap (microsecond): (clock() – start_time)/10 endl;// 4-way heapstart_time = clock();for(int i = 0; i 10; i++){ //run 10 times on given data setbuild_tree_using_4way_heap(freq_table);} cout Time using 4-way heap (microsecond): (clock() – start_time)/10 endl;// pairing heapstart_time = clock();for(int i = 0; i 10; i++){ //run 10 times on given data setbuild_tree_using_pairing_heap(freq_table);}cout Time using pairing heap (microsecond): (clock() – start_time)/10 endl;Once you have determined which data structure gives the best performance, finalize your Huffman codeprogram using That data structure. The finalized Huffman code program will take as input a frequency table andoutput a code table. Include the timings and conclusions in your report. Once the Huffman code program isfinalized, you should proceed to write the encoder and decoder.2. EncoderThe Encoder reads an input file that is to be compressed and generates two output files the compressedversion of the input file and the Code table. Your encoder can follow this diagram:Input formatInput file name will be given as a Command line argument. This file can have up to 100,000,000 lines and eachline will contain an integer in the range of 0 to 999,999. Consider the following input for the rest of the document:input_fileBuilding frequency tableFirst step Towards Huffman encoding is to build the frequency table for each value in input. As values will bewithin 0 to 999999, an array can be used for storing frequency for each value. Frequency mapping for the giveninput file is:0 == 42245 == 4999999 == 234 == 3446 == 22 == 1build Huffman tree and codetableinput_file freq_tablecode_tableEncoded.binencodedatabuildfreqtableEncodercode_table.txtBuild Huffman tree and code tableUse the data structure with best timing from section 1 to build the Huffman code table. For the sample inputgiven, one possible Huffman tree and corresponding code table mapping is given below. The code table can bebuilt from the Huffman tree by doing a traversal of the tree.2 == 000999999 == 0010 == 012245 == 10446 == 11034 == 111Huffman tree code tableEncode dataOnce the code table is built, it can be used to encode the original input file by replacing each input value by itscode. Please note that the values are not ASCII characters, rather binary values. You can use ios::binary flagin C++, or OutputStream in Java.0110010011001011010111110111110111001000Output formatEncoder program has two output files. One is encoded message in binary format. It must be saved asencoded.bin. As mentioned in Encode Data phase, output encoded.bin for given data will be:encoded.bin0110010011001011010111110111110111001000Second output is the code table. Each line in this output file will contain value of a leaf node of Huffman tree,and its code Separated by a space. It must be saved as code_table.txt.code_table.txt2 000999999 0010 012245 10446 11034 111Note: Both encoded.bin and code_table.txt are NOT unique. They will not be used for grading directly.However, the size of encoded.bin is unique, so this size will be used for grading purpose. code_table.txtwill be used by your decoder program to decompress the encoded file.3. DecoderThe decoder reads two input files – encoded message and code table. The decoder first constructs the decodetree using the code table. Then the decoded message can be generated from the encoded message using thedecode tree. Your report should include a description of the algorithm used to construct the decode tree fromthe code table together with the complexity of this algorithm.Input formatThe decoder takes two input files – encoded message and code table. File names will be given as command linearguments. The format of these files is the same as the output format of the encoder, so that the output filesof the encoder program can be directly used by the decoder program. Note that the input encoded messagewill be in Binary format, not ASCII characters. You can use ios::binary flag for C++ or InputStream for Java.Output formatOutput of Decoder program is the decoded message. It should be saved as decoded.txt. The format of this fileis same as the input format for the encoder. For any sample input, the following scenario should be true:input_file Decoded.txt4. Files provided in elearningsample1/..i. sample_input_small.txtii. encoded.biniii. code_table.txt iv.decoded.txt;inputs/outputs mentioned in this documentsample2/.. ;large inputs/outputs seti. sample_input_large.txtii. Encoded.biniii. code_table.txt iv.decoded.txt;use this file for performance measurementCOP5536_FA20_Project.pdf ;this file5. Run environmentYour code must be able to run in the linux environment. You can test your program either on CISEstorm.cise.ufl.edu or thunder.cise.ufl.edu server (for which you need to login using your CISE account). Writea Makefile so that we can build your code using following command at terminal:$ makeThis command should produce two binary files: encoder and decoder.As mentioned before, encoder should take one input file. We will run it using following command:$ ./encoder input_file_name [For C++]$ java encoder input_file_name [For Java]Running encoder program must produce the output files with exact name encoded.bin and code_table.txt.On the other hand, decoder will take two input files. We will run it using following command:$ ./decoder encoded_file_name code_table_file_name [For C++]$ java decoder encoded_file_name code_table_file_name [For Java]Running decoder program must produce output file with exact name decoded.txt. Anyviolation of these rules will incur 25% penalty.6. SubmissionYour submission must contain the following files:1. Makefile: To build your program.2. Your Source codes. Do not use any subdirectory.3. Report.pdf:a. Should be in pdf format.b. Should contain your name and UFID.c. Present function prototypes and structure of your program.d. Include performance measurement results and explanation.e. Include what decoding algorithm you used and its complexity.To submit, compress all your files together into LastName_FirstName.zip and upload to elearning. Please do notsubmit Directly to a TA. All email submissions will be ignored without further notification. Please note that thedue date is a hard Deadline. No late submission will be allowed.7.Grading Policy1. Report: 30%2. Performance Analysis: 10%3. Correct implementation and execution: 60% Correctness will be tested by:a. For encoder only: Size of encoded messageb. For decoder only: Correctness of decoded messagec. For Both encoder and decoder: Input message = encoder = decoder = output message. Outputmessage should be same as input message8. Others For C++ and Java, do not use any standard library container other than vector. You must implement allthree types of priority queue by yourself. Again, go through the Run Environment section and make sure your program does exactly as required.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“