CSCI 2110 - Data Structures and Algorithms - Assignment No.4

• 作业标题：CSCI 2110 - Data Structures and Algorithms - Assignment No.4
• 课程名称：Dalhouse University CSCI 2110 Data Structures and Algorithms
• 完成周期：1天

描述

This assignment in on the Huffman coding algorithm using the Binary Tree Data Structure that we
discussed in the lectures. It would be good to review Module 5: Binary Trees before you start the
assignment.

You will need the following files to complete this assignment. Download them.
BinaryTree.java (Generic Binary Tree Class)
LettersProbability.txt (Text file containing letters and their probabilities)
Problem Summary:

Your program do the following:

1. Read the LettersProbability.txt file.
2. Build the Huffman tree and derive the Huffman code for each symbol (letter).
3. Prompt the user to enter a line of text. Read the line and encode it as a String of 1’s and 0’s using
   the Huffman codes.
4. Decode the String of 1’s and 0’s and display the decoded text. If your program is correct, the
   decoded line that is displayed will be identical to the line of text entered by the user.

Heres’ a sample dialog:

Huffman Coding
Enter the name of the file with letters and probability: LettersProbability.txt
Building the Huffman tree ….
Huffman coding completed.
Enter a line (uppercase letters only): THIS IS COOL
Here’s the encoded line: 0100010010010100000 0001011001 101010100001000011010100
The decoded line is: THIS IS COOL

Note 1: The above codes are not the actual codes that you will derive. They are just for demonstration only.
Your codes will be different.

Note 2: You will be encoding only uppercase letters. Keep the spaces as they are in the input. The spaces
are not encoded.

Problem in Detail:

You will write a class that builds the Huffman tree given a list of symbols-probability pairs and provides
methods to encode and decode text according to the Huffman coding algorithm. Call your class file
Huffman.java. You can design as many methods as you find appropriate within the program to make it
modular.

Step 1: Read the LettersProbability.txt file. The file contains the uppercase letters of the English alphabet
and their probabilities arranged in increasing order of probability. For example, the first few lines of the
text file are as follows:

Z 0.0007
J 0.0010
Q 0.0011
X 0.0017
etc.

If you add up all the probabilities, you will see that they add up to 1.

Step 2: You will need to keep track of letters and their relative probabilities in order to build your Huffman
tree. To do this, you will likely find it useful to create a separate class called Pair.java:

public class Pair implements Comparable<Pair>{
// declare all required fields
private char value;
private double prob;
//constructor
//getters
//setters
//toString
/**
The compareTo method overrides the compareTo method of the
Comparable interface.
*/
@Override
public int compareTo(Pair p){
    return Double.compare(this.getProb(), p.getProb());
    }
}

As you read each line of the LettersProbability.txt file, you will create a BinaryTree object
for each letter-probability pair that you read.

Step 3: Next, you will build a Huffman tree. To build a Huffman tree you will require two queues, Queue S
and Queue T, of type BinaryTree. You may use structures from the Java Standard Libraries or you
may choose to trivially implement your queues using ArrayLists (appending new elements and removing
at index 0). Both options are acceptable.

。。。