information theory

The test file “[login to view URL]” is the script from the movie “Monty Python and the Holy Grail.” It has been modified so that it contains only 30 different characters: lowercase a-z (ascii 9710-12210), “space (sp)” (ascii 3210), “line feed (lf)” (ascii 1010) “carriage return (cr)” (ascii 1310), and “end of text (etx)” (ascii 0310). All uppercase, punctuation, and numerals have been removed. The file is in “.txt” format, and contains 61,392 characters. It has also been compressed using zip. First, unzip the file, and note the size of the zipped file vs. the unzipped .txt file. Write the following programs: 1. Write a program to calculate the 30 letter probabilities directly from the file. 2. Write a program to construct a binary Huffman code based on these probabilities. 3. Print out a neat, concise table of your Huffman code, showing the character, probability, Huffman code representation, and code length for each character. 4. Write a program to Huffman encode the data, so that the output file is a sequence of ones and zeros. Then group the output bits symbols into groups of 8 bits (i.e. bytes) so that the final output file is a sequence of 8-bit ascii characters. 5. Have your program calculate the final length, in bits, of the compressed output file. Also have your program calculate the entropy of the source, based on your derived probability values, (assuming that source symbols are independent, which is not really true). 6. Have your program calculate the ratio of output bits per input character. This is Lavg for this compression scheme. 7. Compare Lavg to the calculated entropy of the source. Explain the differences you see. 8. Write a program to decode your encoded data. Confirm that it perfectly reconstructs the original file. Turn in your source code, your Huffman table, evidence that the programs work, and a summary of all calculated values. Include a write-up (1 page max) discussing your results. In particular, discuss the relationship between the (approximate) entropy of the source and the average length of the code. RULES: 1. Do not use library functions for Huffman coding, but feel free to use libraries for opening files, reading in its contents, and for any data structure you may need. 2. Plagiarism: Huffman coding is used fairly extensively in undergraduate programming assignments. As such, there are many resources online (e.g. [login to view URL])which do exactly what the assignment asks of you. You are free to refer to as many resources as you want (and cite them), but do NOT copy paste content from those resources, or from other students. Do NOT use tricks like renaming variables, shuffling the order of functions in the code etc. as this counts as plagiarism. Write your OWN code and submit it. That said, here are some hints (more on this during the live session): * Note that the file contains both carriage return and line feed characters. Depending on your prog. language and library, these may be stripped from the file during the processs of reading it into a string/array. Be careful, do not let this happen as this is incorrect. Total number of characters read in from the file MUST be 61392. Treat the \r and \n characters as it is. * The main idea is to replicate exactly what you're doing on pen and paper while performing Huffman coding. There are a few extra steps (such as calculating character probabilities) that you need to take care of. Once that's done, try to replicate whatever your method is on pen & paper. * You will need some data structures. Arrays/lists/arraylists can suffice (not the best tool for the job), but there are more efficient/convenient ones like dictionaries (hash maps), priority queues etc. To implement the nodes/leaves in a tree, you can use object oriented programming, or just store the binary tree in array form.