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.

Here is my HuffTree class:

import java.io.PrintStream;
import java.io.Serializable;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
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)
{
  
  
/*
try
{
input = new Scanner(new FileInputStream("huff.txt"));
}
  
catch(FileNotFoundException e)
{
System.out.println("File data.txt was not found ");
System.out.println("or could not be opened. ");
System.exit(0);
}*/

}

}

Explanation / Answer

//Modified code as per requirements.

import java.io.PrintStream;
import java.io.Serializable;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
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;
      Scanner input;
      double freq[]=new double[256];

    
      try
      {
        int i=0;
        hf=new HuffmanTree();
        HuffmanTree.HuffData hd[]=new HuffmanTree.HuffData[256];
        input = new Scanner(new FileInputStream("huff.txt"));
         while(input.hasNext())
         {
            freq[input.nextChar()]++;
         }
         for(int i=0;i<256;i++)
            hd[i]=new HuffData(freq[i],i);
        hf.buildTree(hd);
        hf.printCode(System.out);
      }
    
      catch(FileNotFoundException e)
      {
         System.out.println("File data.txt was not found ");
         System.out.println("or could not be opened. ");
         System.exit(0);
      }

    }

}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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