I need help completing this assignment. HuffmanCoding Direction below: Building

Question

I need help completing this assignment.

HuffmanCoding

Direction below:

Building a binary tree, where the “data” is a count of the frequency of each character.

public class HuffmanNode implements Comparable      

public int frequency;    

public char character;    

public HuffmanNode left;    

public HuffmanNode right;

The Huffman Node class will also need a boolean isLeaf() method, plus a static method to actually provide a count of the characters in an input file, and place those counts into a Map, with character as the unique key mapped into the integer counts of that character:

public static Map getCounts(FileInputStream input)

Your Huffman Tree class must have the following defined:

public HuffmanTree(Map counts) // Constructor     

public StringBuilder compress(InputStream inputFile) // inputFile is a text file

public StringBuilder decompress(StringBuilder inputString) //inputString 1’s & 0’s

public String printSideways()

The compress method returns a string of 1’s and 0’s (bits) as per the description below. The decompress method can take that string of 1’s and 0’s, use the Huffman tree structure and recreate the text file from those bits. Finally, the printSideways in this case we build a string to return into a graphical text area. You should actually use the String Builder class, as it is mutable.  

You must comment out all System.out calls before submitting your work. The client program (HuffmanGUI.java) is provided, and you need to meet these specifications listed above.

The steps involved in Huffman coding a given text source file into a destination compressed file are the following:

1.Examine the source file's contents and count the number of occurrences of each character.

2.Place each character and its frequency (count of occurrences) into a sorted "priority" queue.

3.Convert the contents of this priority queue into a binary tree with a particular structure.

4.Traverse the tree to discover the binary encodings of each character.

5.Re-examine the source file's contents, and for each character, output the encoded binary version of that character to the destination file.

Explanation / Answer

import java.util.*;

abstract class HuffmanTree implements Comparable<HuffmanTree> {
    public final int frequency; // the frequency of this tree
    public HuffmanTree(int freq) { frequency = freq; }

    // compares on the frequency
    public int compareTo(HuffmanTree tree) {
        return frequency - tree.frequency;
    }
}

class HuffmanLeaf extends HuffmanTree {
    public final char value; // the character this leaf represents

    public HuffmanLeaf(int freq, char val) {
        super(freq);
        value = val;
    }
}

class HuffmanNode extends HuffmanTree {
    public final HuffmanTree left, right; // subtrees

    public HuffmanNode(HuffmanTree l, HuffmanTree r) {
        super(l.frequency + r.frequency);
        left = l;
        right = r;
    }
}

public class HuffmanCode {

// input is an array of frequencies, indexed by character code
    public static HuffmanTree buildTree(int[] charFreqs) {
        PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
        // initially, we have a forest of leaves
        // one for each non-empty character
        for (int i = 0; i < charFreqs.length; i++)
            if (charFreqs[i] > 0)
                trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));

        assert trees.size() > 0;
        // loop until there is only one tree left
        while (trees.size() > 1) {
            // two trees with least frequency
            HuffmanTree a = trees.poll();
            HuffmanTree b = trees.poll();

            // put into new node and re-insert into queue
            trees.offer(new HuffmanNode(a, b));
        }
        return trees.poll();
    }

    public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
        assert tree != null;
        if (tree instanceof HuffmanLeaf) {
            HuffmanLeaf leaf = (HuffmanLeaf)tree;

            // print out character, frequency, and code for this leaf (which is just the prefix)
            System.out.println(leaf.value + " " + leaf.frequency + " " + prefix);

        } else if (tree instanceof HuffmanNode) {
            HuffmanNode node = (HuffmanNode)tree;

// traverse left
          prefix.append('0');
            printCodes(node.left, prefix);
            prefix.deleteCharAt(prefix.length()-1);

            // traverse right
            prefix.append('1');
            printCodes(node.right, prefix);
            prefix.deleteCharAt(prefix.length()-1);
        }
    }
  public static void main(String[] args) {
        String test = "this is an example for huffman encoding";

        // we will assume that all our characters will have
        // code less than 256, for simplicity
        int[] charFreqs = new int[256];
        // read each character and record the frequencies
        for (char c : test.toCharArray())
            charFreqs[c]++;

  // build tree
        HuffmanTree tree = buildTree(charFreqs);

        // print out results
System.out.println("SYMBOL WEIGHT HUFFMAN CODE");
        printCodes(tree, new StringBuffer());
}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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