1
Student Name: __________________
Class and Section __________________
Total Points (20 pts) __________________
Due: October 27, 2010 before the class
Project: Huffman Tree
CSCI 2410 Data Structures and Algorithms
Armstrong Atlantic State University
Problem Description:
The text presented Huffman tree and you learned how to create a Huffman tree
and how to encode a text using a Huffman tree. Write a program that prompts the
What should you do?
1. You should run the following program to encode a file (e.g., Welcome.java) to
create two files (e.g., Welcome.java.new and Welcome.java.counts).
(Delete this program when you print out this project to save paper.)
Scanner input = new Scanner(System.in);
System.out.print(“Enter a filename: “);
String filename = input.nextLine();
public static void storeCounts(String filename, long numberOfCharacters, int[]
counts) throws IOException {
ObjectOutputStream output = new ObjectOutputStream(
new FileOutputStream(filename + “.counts”));
output.writeLong(numberOfCharacters);
output.writeObject(counts);
output.close();
}
public static void encode(String filename, String[] codes) throws IOException {
BufferedInputStream fileInput = new BufferedInputStream(
new FileInputStream(new File(filename)));
BitOutputStream output = new BitOutputStream(new File(filename + “.new”));
3
if (root.left != null) {
root.left.code = root.code + “0”;
assignCode(root.left, codes);
while (heap.getSize() > 1) {
Tree t1 = heap.remove();
Tree t2 = heap.remove();
heap.add(new Tree(t1, t2));
}
return heap.remove();
}
4
public int compareTo(Tree o) {
// Purposely reverse the order so the smallest one will be removed first from
the heap
if (root.weight < o.root.weight)
return 1;
else if (root.weight == o.root.weight)
5
while (currentIndex > 0) {
int parentIndex = (currentIndex – 1) / 2;
// Swap if the current object is greater than its parent
if (list.get(currentIndex).compareTo(
list.get(parentIndex)) > 0) {
E temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
}
}
}
}
else
break; // The tree is a heap
}
return removedObject;
}
/** Get the number of nodes in the tree */
public int getSize() {
return list.size();
}
}
7
for (int i = 0; i < bitString.length(); i++)
writeBit(bitString.charAt(i));
}
2. In your program, you need to read the Huffman codes from the .counts file,
create a Huffman tree from the codes, and then use the Huffman tree to decode
the .new file to generate the new target file.
Submit the following items:
1. Compile and Submit to LiveLab (you must submit the program regardless whether it
complete or incomplete, correct or incorrect)
2. Fill in self-evaluation:
1. Can your program read codes from the file? _______________
2. Can your program build a Huffman tree from the codes? _______________
3. Can your program read the input file and decode it using the Huffman tree?
_______________
4. Can your program handle very large files (e.g., 1GB)? _______________