I am given a driver class called Asg7.java which will print the output values. I
ID: 3695944 • Letter: I
Question
I am given a driver class called Asg7.java which will print the output values. I need to create a Huffman Tree, so I will need to use the four methods with descriptions below to complete it. Please create the methods that are necessary to match the driver class. Thank you.
1. HuffmanTree(char[] a, int[] f) This is a constructor that builds a Huffman tree based on a and f, where a is an array of characters to be encoded and f is an array of frequencies corresponding to the characters in a. For example, if a[3] = ’D’ and f[3] = 43, that means the frequency of ’D’ is 43. Note: You are not going to build a random Huffman tree. Instead, you will build a rightheavy tree, which means, whenever you try to combine two sub-Huffman trees to form a new tree, the left-child of the new root always points to the node with higher frequency. In such a way, the right-child intends to have more nodes. As the result, this strategy will build a tree with the right side heavier than the left side.
2. public void printCodeWords() This method prints out all codewords in the Huffman tree. The order of printing the codewords doesn’t matter, but they are required to be printed in the following format: Huffman Codes: 000:E[69](127) 0010:H[72](61) 0011:S[82](63) ..... The list indicates that 000 is the Huffman code for E, [69] indicates the ASCII value of character E, and (127) is the frequency; same to characters H and S.
3. public String encodeToStr(String text) This method will return a 0-1 String using the Huffman code. For example, if the argument is "EHS" and we are using the same codes for this assignment to code it, the method should return "00000100011".
4. public String decodeFromStr(String codeString) The reverse of the function above. Using the same tree with the argument "00000100011", the method will return "EHS". /** * You should not modify this program. You should develop your own * HuffmanTree.java and put it in the package, myUtil.
/**
* You should not modify this program. You should develop your own
* HuffmanTree.java and put it in the package, myUtil.
*
* @author cli2
*
*/
import myUtil.HuffmanTree;
public class Asg7 {
// this example is extended from Corman's book
static public void CormanFrequency() {
int[] f = {82,15,29,43,127,22,20,61,70,5,8,40,24,67,75,19,4,60,63,91,28,10,23,2,21,1,123};
char[] a = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',' '};
HuffmanTree ht = new HuffmanTree(a, f); // Construct a Huffman Tree based on a and f
ht.printCodeWords();
System.out.printf("%nCode: %s%n", ht.encodeToStr("HUFFMAN ENCODING IS VERY USEFUL"));
System.out.printf("%nText: %s%n", ht.decodeFromStr("00100111011110011110011111011001000010000100001111101011010100110001101100101001001101010111110000110110111010011111010101010110"));
System.out.printf("%nText: %s%n", ht.decodeFromStr("0111101101101111011101110101011011001101100101110001011011101010010011010111100011101000"));
System.out.printf("%nText: %s%n", ht.decodeFromStr("11100010100100110101001001101011100010000010101101100001111100101100001100111001110110100011111000010001110"));
}
public static void main(String[] args) {
CormanFrequency();
}
}
Explanation / Answer
/****************************************************************************** * Compilation: javac Huffman.java * Execution: java Huffman - < input.txt (compress) * Execution: java Huffman + < input.txt (expand) * Dependencies: BinaryIn.java BinaryOut.java * Data files: http://algs4.cs.princeton.edu/55compression/abra.txt * http://algs4.cs.princeton.edu/55compression/tinytinyTale.txt * * Compress or expand a binary input stream using the Huffman algorithm. * * % java Huffman - < abra.txt | java BinaryDump 60 * 010100000100101000100010010000110100001101010100101010000100 * 000000000000000000000000000110001111100101101000111110010100 * 120 bits * * % java Huffman - < abra.txt | java Huffman + * ABRACADABRA! * ******************************************************************************/ /** * The <tt>Huffman</tt> class provides static methods for compressing * and expanding a binary input using Huffman codes over the 8-bit extended * ASCII alphabet. * <p> * For additional documentation, * see <a href="http://algs4.cs.princeton.edu/55compress">Section 5.5</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Huffman { // alphabet size of extended ASCII private static final int R = 256; // Do not instantiate. private Huffman() { } // Huffman trie node private static class Node implements Comparable<Node> { private final char ch; private final int freq; private final Node left, right; Node(char ch, int freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } // is the node a leaf node? private boolean isLeaf() { assert ((left == null) && (right == null)) || ((left != null) && (right != null)); return (left == null) && (right == null); } // compare, based on frequency public int compareTo(Node that) { return this.freq - that.freq; } } /** * Reads a sequence of 8-bit bytes from standard input; compresses them * using Huffman codes with an 8-bit alphabet; and writes the results * to standard output. */ public static void compress() { // read the input String s = BinaryStdIn.readString(); char[] input = s.toCharArray(); // tabulate frequency counts int[] freq = new int[R]; for (int i = 0; i < input.length; i++) freq[input[i]]++; // build Huffman trie Node root = buildTrie(freq); // build code table String[] st = new String[R]; buildCode(st, root, ""); // print trie for decoder writeTrie(root); // print number of bytes in original uncompressed message BinaryStdOut.write(input.length); // use Huffman code to encode input for (int i = 0; i < input.length; i++) { String code = st[input[i]]; for (int j = 0; j < code.length(); j++) { if (code.charAt(j) == '0') { BinaryStdOut.write(false); } else if (code.charAt(j) == '1') { BinaryStdOut.write(true); } else throw new IllegalStateException("Illegal state"); } } // close output stream BinaryStdOut.close(); } // build the Huffman trie given frequencies private static Node buildTrie(int[] freq) { // initialze priority queue with singleton trees MinPQ<Node> pq = new MinPQ<Node>(); for (char i = 0; i < R; i++) if (freq[i] > 0) pq.insert(new Node(i, freq[i], null, null)); // special case in case there is only one character with a nonzero frequency if (pq.size() == 1) { if (freq[''] == 0) pq.insert(new Node('', 0, null, null)); else pq.insert(new Node('', 0, null, null)); } // merge two smallest trees while (pq.size() > 1) { Node left = pq.delMin(); Node right = pq.delMin(); Node parent = new Node('', left.freq + right.freq, left, right); pq.insert(parent); } return pq.delMin(); } // write bitstring-encoded trie to standard output private static void writeTrie(Node x) { if (x.isLeaf()) { BinaryStdOut.write(true); BinaryStdOut.write(x.ch, 8); return; } BinaryStdOut.write(false); writeTrie(x.left); writeTrie(x.right); } // make a lookup table from symbols and their encodings private static void buildCode(String[] st, Node x, String s) { if (!x.isLeaf()) { buildCode(st, x.left, s + '0'); buildCode(st, x.right, s + '1'); } else { st[x.ch] = s; } } /** * Reads a sequence of bits that represents a Huffman-compressed message from * standard input; expands them; and writes the results to standard output. */ public static void expand() { // read in Huffman trie from input stream Node root = readTrie(); // number of bytes to write int length = BinaryStdIn.readInt(); // decode using the Huffman trie for (int i = 0; i < length; i++) { Node x = root; while (!x.isLeaf()) { boolean bit = BinaryStdIn.readBoolean(); if (bit) x = x.right; else x = x.left; } BinaryStdOut.write(x.ch, 8); } BinaryStdOut.close(); } private static Node readTrie() { boolean isLeaf = BinaryStdIn.readBoolean(); if (isLeaf) { return new Node(BinaryStdIn.readChar(), -1, null, null); } else { return new Node('', -1, readTrie(), readTrie()); } } /** * Sample client that calls <tt>compress()</tt> if the command-line * argument is "-" an <tt>expand()</tt> if it is "+". */ public static void main(String[] args) { if (args[0].equals("-")) compress(); else if (args[0].equals("+")) expand(); else throw new IllegalArgumentException("Illegal command line argument"); } }
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.