Java代写 | Com S 228 Fall 2020 Project 4: Decoding an Archived Message


Com S 228 Fall 2020
Project 4: Decoding an Archived Message

1. Problem Description
The objective of this exercise is to decode/unzip a message archived with a binary-tree-based
algorithm. The program should ask for a single filename at the start: “Please enter filename to
decode: “, decode the message in the file and print it out to the console. The name of the
compressed message file will end in .arch, e.g. “monalisa.arch”. The file consists of two or three
lines: the first one or two lines contain the encoding scheme, and the second or third line
contains the archived message.
2. Encoding
The archival algorithm uses a binary tree. The edges of the tree represent bits, and the leaf
nodes contain one character each. Internal nodes are empty. An edge to a left child always
represents a 0, and an edge to a right child always represents a 1. Characters are encoded by
the sequence of bits along a path from the root to a particular leaf. The below tree serves as an
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
which is decoded as:
With this encoding, we can automatically infer where one character ends and another
That is because no character code can be the start of another character code. For example,
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
Go to left child if 0; else go to right child
Print leaf payload
3. Input 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 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 2
can be represented as:
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”):
There are four test files in Note the encoding scheme representations
may include a space character and a newline character, thereby breaking the tree string into
two lines! The newline character needs to be parsed correctly if the encoding file has three
lines in total.
4. Task
4.1. Read in the first line (and possibly second line, if newline is part of the tree) of the
file and construct the character tree. Convert the line input into a MsgTree structure
using preorder traversal. 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 to 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){}


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: [email protected]  微信:itcsdx