首页 » CS辅导 » Java辅导 | Com S 228 Summer 2019 Homework 3

Java辅导 | Com S 228 Summer 2019 Homework 3


Com S 228 Summer 2019
Homework 3: Decoding a Compressed Message (100 pts) Due at 11:59 pm
Sunday, July 14

1. Problem Description

The goal of this exercise is to read a message compressed with a simple binary-tree-based algorithm. The program should ask for a single filename at the start, decode the message in the file and print it out to the console. The name of the compressed message file will end in .msg, e.g. “twocities.msg”. The message file consists of two lines: the first one contains the encoding scheme, and the second line contains the compressed string.

2. Encoding

The compression algorithm is based on a binary tree. Starting at the root, an edge to a left child always represens a 0, and an edge to a right child always represents a 1. Internal nodes are empty, while leaf nodes contain message characters. The encoding of a leaf character is the sequence of bits along the path from the root to the leaf.

The tree on the left encodes these characters:



a ! d c r b


With the above encoding, the message:


translates to


which is decoded as:


Note that with this binary-tree encoding, we can infer the breaks between characters automatically! That is because no character code can be the start of another character code. For example, if you have the code 111, you cannot have the codes 1 and 11, as they would be internal nodes.

Another note is that the compression algorithm selects the binary tree to encode more frequently occurring characters with fewer bits.

The following steps decode the bit string:

Start at root
Repeat until at leaf
     Scan one bit character
     Go to left child if at 0; else go to right child
Print leaf payload

3. Input/Output Format

The message file consists of two lines: the first one contains the encoding scheme, and the second line contains the compressed string. For ease of development and to make the message file human-readable, each bit is represented as a the character ‘0’ or ‘1’, rather than as an actual bit from a binary file.

The encoding tree can be represented as a string. For example, the tree from section 3 can be represented as:


where ^ indicates an internal node. The above code represents a preorder traversal of the tree.

The badcard! message is encoded in the following file (“badcard.msg”): ^a^^!^dc^rb


There are four test files in project3_Test_Files.zip. Note the encoding tree representations may include a space character and a newline character, thereby breaking the tree representation into two lines!

4. Task

4.1. Read in the first line of the file and construct an encoding tree. The tree should be in a class EncodingTree with the following members:
public class EncodingTree{

     public char codedChar;
     public EncodingTree left;
     public EncodingTree right;
     //Constructor building the encoding tree from a file
     public EncodingTree(String msgFileName);
     //method to print characters together with their codes
     public static void printCodes(EncodingTree root);

printCodes() does a preorder traversal and prints all the characters and their bit codes:

character code ————————-

   c       1011
   r       110
   b       111

4.2. Write a method public void decode(String msgFileName) to decode the message. It would print the decoded message to the console:

The quick brown fox jumped over the lazy dog.

The overall output of the program should be the output of printCodes() followed by the output of decode():

character code ————————-

   c       1011
   r       110
   b       111
The quick brown fox jumped over the lazy dog.

5. Submission

Write your classes in the cs228.hw3 package. Turn in the zip file, not your class files. Please follow the guideline posted under Documents & Links on Canvas.

Include the Javadoc tag @author in each class source file. Your zip file should be named Firstname_Lastname_HW3.zip.

6. Extra credit (10%)

Print the following statistics after the rest of the program output:

Average bits per char: 6.8 Number of characters: 17 Space savings: 31.12%

The space savings calculation assumes that an uncompressed character is encoded with 8 bits. It is defined as (1 – compressed_bits/uncompressed_bits)*100.

Name your file Firstname_Lastname_HW3_extra.zip if you completed the work for extra credit.


本网站支持 Alipay WeChatPay PayPal等支付方式

E-mail: vipdue@outlook.com  微信号:vipnxx