UE CS 215 - CS 215 ­ Fundamentals of Programming II (6 pages)

Previewing pages 1, 2 of 6 page document View the full content.
View Full Document

CS 215 ­ Fundamentals of Programming II



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document
View Full Document

CS 215 ­ Fundamentals of Programming II

59 views


Pages:
6
School:
University of Evansville
Course:
Cs 215 - Fundamentals of Programming II
Fundamentals of Programming II Documents

Unformatted text preview:

CS 215 Fundamentals of Programming II Fall 2010 Project 7 30 points Out November 12 2010 Due November 29 2010 Monday after Thanksgiving but really should be completed before break This project is to build a Huffman coding tree and use it to encode and decode messages Huffman Codes As you should know characters are encoded in a computer in ASCII format The ASCII format assigns 8 bits to each character This makes it easy to determine where the bits for one character start and end in a text file Although ASCII is convenient it is also wasteful of space If we look at a file of English text we can see there are far fewer than 256 characters 256 is the maximum number of characters 8 bits can encode To save space it is possible to compress a text file by encoding each character with less than 8 bits The assignment of such an encoding can be done in various different ways One way is to design a Huffman code A Huffman code is a variable length encoding scheme i e the code for each character is not necessarily the same length and has the prefix property no sequence of bits that represents a character is a prefix of a longer sequence for some other character This allows the code to be represented using a binary tree called a codetree with the following properties Every node is either a leaf or has exactly 2 children Letters appear only at the leaves of the tree Each letter appears at most once in the codetree thus there is a unique root to leaf path encoding for each letter For example consider the following codetree root s n u i y The code for each letter is a string formed by appending a 0 when taking a left branch and a 1 for a right branch when traversing the root to leaf path In the codetree above the code for u is 010 left right left 11 11 2010 1 of 6 D Hwang the code for s is 00 and the code for n is 10 A message is encoded by appending the codes for letters in the message For example the code for the message sun is 0001010 which is formed by appending the codes for s u



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view CS 215 ­ Fundamentals of Programming II and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 215 ­ Fundamentals of Programming II and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?