Java代写 | Computer Science 228 Decoding an Archived Message

本次Java代写是完成一个基于二叉搜索树存档消息算法的解码/解压缩程序

Computer Science 228, Summer 2020
Homework 3: Decoding an Archived Message (100 pts)
2. Encoding
The archival algorithm uses a binary tree. An edge to a left child always represents a 0, and an
edge to a right child always represents a 1. Non-leaf nodes have no payload, while leaf nodes
are labeled with characters from the message. Characters are encoded by the sequence of bits
along a path from the root to a particular leaf.
The tree on the left encodes these characters:
Character Encoding
a 0
! 100
d 1010
c 1011
r 110
b 111
With the above encoding, the bit string:
10100101010110110111100 is parsed as
1010|0|1010|1011|0|110|111|100
which is decoded as:
dadcarb!
With this encoding, we can automatically infer where one character ends and another begins.
That is because no character code can be the start of another character code. For example, if
you have a character with the code 111, you cannot have the codes 1 and 11, as they would
be internal nodes.
The following steps decode one character from the bit string:
Start at root
Repeat until at leaf
Scan one bit character
Go to left child if 0; else go to right child
Print leaf payload
3. Input/Output Format
The archive file consists of two lines: the first line contains the encoding scheme, and the
second line contains the compressed string. For ease of development and to make the
archive 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 scheme 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 dadcarb! message is encoded in the following file (“dadcarb.arch”):
^a^^!^dc^rb
10100101010110110111100
There are four test files in project3_Test_Files.zip. Note the encoding scheme
representations may include a space character and a newline character, thereby breaking
the tree string into two lines!
4. Task
4.1. Read n the first line of the file and construct the character tree. The tree should be in a
class MsgTree with the following members:
public class MsgTree{
public char payloadChar;
public MsgTree left;
public MsgTree right;
//Need static char idx in the tree string for recursive solution
private static int staticCharIdx = 0;
//Constructor building the tree from a string
public MsgTree(String encodingString){}
//Constructor for a single node with null children
public MsgTree(char payloadChar){}
//method to print characters and their binary codes
public static void printCodes(MsgTree root, String code){}
}
When building the tree, try a recursive solution where staticCharIdx tracks the location
within the tree string. You can pass the same tree string during recursive calls, and update
the staticCharIdx to point to the next character to be read.
If you decide to implement an iterative solution, you will receive 30% bonus points, as it is
considerably more difficult. In that case, you cannot get the 5% bonus for printing statistics.
printCodes() does a recursive preorder traversal and prints all the characters and
their bit codes:
character code
————————-
c 1011
r 110
b 111
You are allowed to print the header of the table (character, code, —-) in main().
4.2. Write a method public void decode(MsgTree codes, String msg) to
decode the message. It would print the decoded message to the console:
MESSAGE:
The quick brown fox jumped over the lazy dog.
You are allowed to print “MESSAGE:” in main().
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