Results 1 to 2 of 2
Thread: Huffman Algorithm Help
 02202013, 12:15 AM #1Member
 Join Date
 Feb 2013
 Posts
 1
 Rep Power
 0
Huffman Algorithm Help
This question appeared in a previous year exam paper and I have this exam on Friday and was wondering if anyone help me with one of the questions as I have no idea what to do!
Java Code:import java.util.*; public class Huffman{ public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Enter your sentence: "); String sentence = in.nextLine(); String binaryString=""; //this stores the string of binary code for(int i=0; i < sentence.length(); i++) { int decimalValue = (int)sentence.charAt(i); //convert to decimal String binaryValue = Integer.toBinaryString(decimalValue); //convert to binary for(int j=7;j>binaryValue.length();j) { binaryString+="0"; //this loop adds in those pesky leading zeroes } binaryString += binaryValue+" "; //add to the string of binary } System.out.println(binaryString); //print out the binary int[] array = new int[256]; //an array to store all the frequencies for(int i=0; i < sentence.length(); i++) { //go through the sentence array[(int)sentence.charAt(i)]++; //increment the appropriate frequencies } PriorityQueue < Tree > PQ = new PriorityQueue < Tree >() ; //make a priority queue to hold the forest of trees for(int i=0; i<array.length; i++) { //go through frequency array if(array[i]>0) { //print out nonzero frequencies  cast to a char System.out.println("'"+(char)i+"' appeared "+array[i]+((array[i] == 1) ? " time" : " times")); //FILL THIS IN: //MAKE THE FOREST OF TREES AND ADD THEM TO THE PQ //create a new Tree //set the cumulative frequency of that Tree //insert the letter as the root node //add the Tree into the PQ } } while(PQ.size()>1) { //FILL THIS IN: //IMPLEMENT THE HUFFMAN ALGORITHM //when you're making the new combined tree, don't forget to assign a default root node (or else you'll get a null pointer exception) //if you like, to check if everything is working so far, try printing out the letter of the roots of the two trees you're combining } Tree HuffmanTree = PQ.poll(); //now there's only one tree left  get its codes //FILL THIS IN: //get all the codes for the letters and print them out //call the getCode() method on the HuffmanTree Tree object for each letter in the sentence //print out all the info } public class Tree implements Comparable<Tree> { public Node root; // first node of tree public int frequency=0; public Tree() // constructor { root = null; } public int compareTo(Tree object) { // if(frequencyobject.frequency>0) { //compare the cumulative frequencies of the tree return 1; } else if(frequencyobject.frequency<0) { return 1; //return 1 or 1 depending on whether these frequencies are bigger or smaller } else { return 0; //return 0 if they're the same } } String path="error"; public String getCode(char letter) { //FILL THIS IN: //How do you get the code for the letter? Maybe try a traversal of the tree //Track the path along the way and store the current path when you arrive at the right letter return path; //return the path that results } } class Node { public char letter; //stores letter public Node leftChild; // this node's left child public Node rightChild; // this node's right child } // end class Node }
 02212013, 06:12 AM #2Senior Member
 Join Date
 Jan 2009
 Location
 CA, USA
 Posts
 271
 Rep Power
 12
Re: Huffman Algorithm Help
The code is a little difficult to read, but I will try to explain the Huffman algorithm as I remember it. I'll use an example where we would attempt to optimize the Huffman code for the letters AF, with the frequencies:
A=25%
B=10%
C=10%
D=15%
E=35%
F=5%
So, we start with 6 root nodes.
The smallest two frequencies are F (5) and either B or C (10). We'll take the first occurence, B.
So, we combine B and F.
The next smallest are 10 (C) and 15 (D)
So, we combine them.
The next smallest are 25 and 15.
We'll use the second 25 because it will make drawing the graph easier.
Next up is 25 (A) and 35 (E).
Combine them.
Finally, combine the 60 and 40 to get the 100%.
This tree happens to be a heap. A heap is a tree where every node’s parent’s value is greater than the node’s value. This is important when a computer is creating this tree; but, from a human perspective it makes little difference.
Now, write a 0 on every left edge and a 1 on every right edge.
Notice that all of the letters are in leaf nodes. So, to obtain the code for any of the letters simply trace the root from the root down to the letter's node and write the edge's label as you go. For example, to get the code for E you would follow the root to the left (0) then to the right (1), so the code for E is 01.
A=00
B=110
C=100
D=101
E=01
F=111
Notice that the two most frequently used characters in this list have the shortest codes, and the least frequently used characters have the longest codes. Therefore, the average transmission of characters will tend to be shorter.
There is another important property that a Huffman Code has. It's called the "Prefix Property." To put it simply, no code is a prefix of another code. To understand why this is you can take another look at the tree. The only way a code can be a prefix is if it is an ancestor of that node. However, by definition every character is a leaf node so it cannot be the ancestor of any other character. This property is useful when decoding messages because when you encounter a string of 0s and 1s you know that when you find a letter it isn't part of another letter and can just continue on your way.
Hopefully this will help you figure out what you need to do for your program.
Similar Threads

Huffman coding algorithm question?
By knguye88 in forum New To JavaReplies: 1Last Post: 03122012, 09:06 AM 
Help: traverse Huffman tree
By Reploids in forum New To JavaReplies: 0Last Post: 05242011, 10:02 AM 
Help: traversing huffman tree
By Reploids in forum New To JavaReplies: 0Last Post: 05242011, 09:42 AM 
huffman coding in java
By warlock in forum New To JavaReplies: 2Last Post: 03122011, 12:59 PM 
BufferedInputStream with Huffman Compression
By Msnforum in forum New To JavaReplies: 0Last Post: 11032009, 09:04 PM
Bookmarks