Question
Construct a Huffman tree based on the given frequencies of 26 English alphabets in upper case plus the space character. You should design your own
Construct a Huffman tree based on the given frequencies of 26 English alphabets in upper case plus the space character. You should design your own HuffmanTree class and put it in myUtil package. You may use an inner class in HuffmanTree for the tree node that contains necessary information.
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 doesnt 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. * * @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(); }
}
This is the driver class Asg7, but I need help constructing a huffman tree and using those four methods described above. Thank you.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started