Java辅导 | Com S 228 Summer 2019 Homework 3

本次为Summer的CS辅导Java实现基于二叉树的算法压缩

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:

Character

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:

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:

^a^^!^dc^rb

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.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{

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

character code ————————-

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

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

character code ————————-

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:

STATISTICS:
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.