JAVA: Write an application to test the HuffmanTree class. Your application will

Question

JAVA: Write an application to test the HuffmanTree class. Your application will need to read a text file
and build a frequency table for the characters occurring in that file. Once that table is built, create
a Huffman code tree and then a string consisting of '0' and '1' digit characters that represents
the code string for that file. Read that string back in and recreate the contents of the original file.

HuffMan Tree Class:

import java.io.*;
import java.util.*;

public class HuffmanTree implements Serializable
{
public static class HuffData implements Serializable
{
private double weight;
private Character symbol;

public HuffData(double weight, Character symbol)
{
this.weight = weight;
this.symbol = symbol;
}

public Character getSymbol() {return symbol;}
}
  
protected BinaryTree<HuffData> huffTree;
  
private static class CompareHuffmanTrees implements Comparator<BinaryTree<HuffData>> {

@Override
public int compare(BinaryTree<HuffData> treeLeft,BinaryTree<HuffData> treeRight)
{
double wLeft = treeLeft.getData().weight;
double wRight = treeRight.getData().weight;
return Double.compare(wLeft, wRight);
}
}

public void buildTree(HuffData[] symbols)
{
Queue<BinaryTree<HuffData>> theQueue = new PriorityQueue<BinaryTree<HuffData>>(symbols.length,new CompareHuffmanTrees());

for (HuffData nextSymbol : symbols) {
BinaryTree<HuffData> aBinaryTree =
new BinaryTree<HuffData>(nextSymbol, null, null);
theQueue.offer(aBinaryTree);
}

// Build the tree.
while (theQueue.size() > 1)
{
BinaryTree<HuffData> left = theQueue.poll();
BinaryTree<HuffData> right = theQueue.poll();
double wl = left.getData().weight;
double wr = right.getData().weight;
HuffData sum = new HuffData(wl + wr, null);
BinaryTree<HuffData> newTree = new BinaryTree<HuffData>(sum, left, right);
theQueue.offer(newTree);
}
huffTree = theQueue.poll();
}

private void printCode(PrintStream out, String code, BinaryTree<HuffData> tree)
{
HuffData theData = tree.getData();
if (theData.symbol != null)
{
if (theData.symbol.equals(' '))
{
out.println("space: " + code);
} else {
out.println(theData.symbol + ": " + code);
}
} else {
printCode(out, code + "0", tree.getLeftSubtree());
printCode(out, code + "1", tree.getRightSubtree());
}
}

public void printCode(PrintStream out) {
printCode(out, "", huffTree);
}
public String decode(String codedMessage)
{
StringBuilder result = new StringBuilder();
BinaryTree<HuffData> currentTree = huffTree;
for (int i = 0; i < codedMessage.length(); i++)
{
if (codedMessage.charAt(i) == '1')
{
currentTree = currentTree.getRightSubtree();
}
else
{
currentTree = currentTree.getLeftSubtree();
}
  
if (currentTree.isLeaf())
{
HuffData theData = currentTree.getData();
result.append(theData.symbol);
currentTree = huffTree;
}
}
return result.toString();
}
  
public static void main(String [] args)
{
HuffmanTree hf = new HuffmanTree();
  
double freq[]=new double[12];

try
{
  
HuffmanTree.HuffData hd[]=new HuffmanTree.HuffData[256];
Scanner input = new Scanner(new FileInputStream("huff.txt"));
while(input.hasNext())
{
System.out.println("pizza");
}
}
  
catch(FileNotFoundException e)
{
System.out.println("File huff.txt was not found ");
System.out.println("or could not be opened. ");
System.exit(0);
}
  
}

}

BINARY TREE CLASS:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.Serializable;

public class BinaryTree<E> implements Serializable {

protected static class Node<E> implements Serializable
{
public E data;
public Node<E> left;
public Node<E> right;

public Node(E data) {
this.data = data;
left = null;
right = null;
}

@Override
public String toString() {
return data.toString();
}
}

protected Node<E> root;

public BinaryTree() {
root = null;
}

protected BinaryTree(Node<E> root) {
this.root = root;
}

public BinaryTree(E data, BinaryTree<E> leftTree,
BinaryTree<E> rightTree) {
root = new Node<E>(data);
if (leftTree != null) {
root.left = leftTree.root;
} else {
root.left = null;
}
if (rightTree != null) {
root.right = rightTree.root;
} else {
root.right = null;
}
}

public BinaryTree<E> getLeftSubtree() {
if (root != null && root.left != null) {
return new BinaryTree<E>(root.left);
} else {
return null;
}
}

public BinaryTree<E> getRightSubtree() {
if (root != null && root.right != null) {
return new BinaryTree<E>(root.right);
} else {
return null;
}
}

public E getData() {
if (root != null) {
return root.data;
} else {
return null;
}
}

public boolean isLeaf() {
return (root == null || (root.left == null && root.right == null));
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
preOrderTraverse(root, 1, sb);
return sb.toString();
}

private void preOrderTraverse(Node<E> node, int depth,
StringBuilder sb) {
for (int i = 1; i < depth; i++) {
sb.append(" ");
}
if (node == null) {
sb.append("null ");
} else {
sb.append(node.toString());
sb.append(" ");
preOrderTraverse(node.left, depth + 1, sb);
preOrderTraverse(node.right, depth + 1, sb);
}
}

public static BinaryTree<String> readBinaryTree(BufferedReader bR)
throws IOException {
// Read a line and trim leading and trailing spaces.
String data = bR.readLine().trim();
if (data.equals("null")) {
return null;
} else {
BinaryTree<String> leftTree = readBinaryTree(bR);
BinaryTree<String> rightTree = readBinaryTree(bR);
return new BinaryTree<String>(data, leftTree, rightTree);
}
}

public String preorderToString() {
StringBuilder stb = new StringBuilder();
preorderToString(stb, root);
return stb.toString();
}

private void preorderToString(StringBuilder stb, Node<E> root) {
stb.append(root);
if (root.left != null) {
stb.append(" ");
preorderToString(stb, root.left);
}
if (root.right != null) {
stb.append(" ");
preorderToString(stb, root.right);
}
}

public String postorderToString() {
StringBuilder stb = new StringBuilder();
postorderToString(stb, root);
return stb.toString();
}

private void postorderToString(StringBuilder stb, Node<E> root) {
if (root.left != null) {
postorderToString(stb, root.left);
stb.append(" ");
}
if (root.right != null) {
postorderToString(stb, root.right);
stb.append(" ");
}
stb.append(root);
}

public String inorderToString() {
StringBuilder stb = new StringBuilder();
inorderToString(stb, root);
return stb.toString();
}

private void inorderToString(StringBuilder stb, Node<E> root) {
if (root.left != null) {
stb.append("(");
inorderToString(stb, root.left);
stb.append(") ");
}
stb.append(root);
if (root.right != null) {
stb.append(" (");
inorderToString(stb, root.right);
stb.append(")");
}
}
  
}

Explanation / Answer

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

import KW.CH06.HuffmanTree;
import KW.CH06.HuffmanTree.HuffData;

public class HuffmanTest {
  
private static final String INPUT_FILE = "test.txt";
private static final String INPUT_CODE_FILE = "code_table.txt";
private static String fileText;
public static void main(String[] args) {
  
HuffData[] freqTable = readFile(INPUT_FILE);
  
HuffmanTree tree = new HuffmanTree();
tree.buildTree(freqTable);
  
try {
tree.printCode(new PrintStream(INPUT_CODE_FILE));
} catch (FileNotFoundException e) {
e.printStackTrace();
System.out.println("Error writing to file.");
System.exit(1);
}
  
System.out.println("Original: " + fileText);
  
String encodedText = getEncoded(fileText);
  
System.out.println("Encoded: " + encodedText);
System.out.println("Decoded: " + tree.decode(encodedText));
}
  
public static HuffData[] readFile(String fileName) {
  
StringBuilder sb = new StringBuilder();
HashMap<Character, Integer> table = new HashMap<Character, Integer>();
  
try {
BufferedReader reader = new BufferedReader(new FileReader(fileName));
int next;
while ((next = reader.read()) != -1) {
sb.append((char) next);
Integer freq = table.get((char) next);
if (freq != null) {
table.put((char) next, freq + 1);
} else { // first occurrence
table.put((char) next, 1);
}
}
reader.close();
} catch (IOException e) {
e.printStackTrace();
System.out.println("Error reading from file.");
System.exit(1);
}
  
HuffData[] huffArray = new HuffData[table.size()];
int i = 0;
for (Map.Entry<Character, Integer> entry : table.entrySet()) {
huffArray[i] = new HuffData(entry.getValue().doubleValue(), entry.getKey());
i++;
}
fileText = sb.toString();
return huffArray;
}
  
public static String getEncoded(String text) {
HashMap<Character, String> codes = new HashMap<Character, String>();
  
try {
Scanner iStream = new Scanner(new FileInputStream(INPUT_CODE_FILE));
while (iStream.hasNext()) {
String nextStr = iStream.next();
char nextChar;
if (nextStr.startsWith("space")) {
nextChar = ' ';
} else {
nextChar = nextStr.charAt(0);
}
String code = iStream.next();
codes.put(nextChar, code);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
System.out.println("Error reading from file.");
System.exit(1);
}
  
StringBuilder sb = new StringBuilder();
for (int i = 0; i < text.length(); i ++) {
sb.append(codes.get(text.charAt(i)));
}
return sb.toString();
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.