# Huffman Algorithm Help

• February 19th, 2013, 04:45 PM
Chewybakas
Huffman Algorithm Help
I have been staring at this previous years exam question for hours now and I just can't get it working correctly. If anyone can help it would be greatly appreciated as I have an exam on Friday!

Code java:

```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 non-zero 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(frequency-object.frequency>0) { //compare the cumulative frequencies of the tree return 1; } else if(frequency-object.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     }```

I have included the entire problem! Help with any part would be greatly appreciated!
• February 19th, 2013, 04:49 PM
Norm
Re: Huffman Algorithm Help
Can you explain what the problem is?
Post any error messages
• February 19th, 2013, 04:55 PM
Chewybakas
Re: Huffman Algorithm Help
Its an exam question which I have no idea how to approach! For example if the user inputs the string "The" the program will output 1010100 1101000 1100101
and 'T' appeared 1 time 'e' appeared 1 time 'h' appeared 1 time Which is fine. But the question wants me to get the huffman codes and print them out, for each letter filling in the areas of the code commented out! Which I have no idea how to do!
• February 19th, 2013, 05:00 PM
Norm
Re: Huffman Algorithm Help
Do you have the algorithm that the code is supposed to implement? You need that before you can write any code.
• February 19th, 2013, 05:04 PM
Chewybakas
Re: Huffman Algorithm Help
The code is to implement huffmans algorithm for compressing Strings, but that is all that is on the exam paper
• February 19th, 2013, 05:34 PM
Norm
Re: Huffman Algorithm Help
Do you have the algorithm that the code is supposed to implement? You need that before you can write any code.
• February 20th, 2013, 09:40 AM
Zaphod_b
Re: Huffman Algorithm Help
Quote:

Originally Posted by Chewybakas
...I have no idea how to do.

The exam is from a course on algorithms or data structures or some such thing. The specific assignment is expressed as comments in the code:
Code java:

```. . . //FILL THIS IN: //<--- This is line 47 of the code you posted   //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 . . . //FILL THIS IN: // <--- Line 66   //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 . . . //FILL THIS IN: <--- Line 78   //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```

If a person has taken the course and doesn't have a clue as to where to start the "FILL THIS IN" stuff, well, maybe it is time to go back through class notes or textbook or whatever other material was presented. Maybe students were even given references to additional material for individual study.

If a person has not taken the course and has no clue as to how to do Huffman coding, one might get a textbook on algorithms or find something on-line that would help. For example, the Fourth Edition of the excellent and ubiquitous "Algorithms" book by Sedgewick even uses Java for its example code. A lot of the program material is available (legally and free) here: Algirithms, 4th Edition

Anyhow...

Just having some Java code that implements and illustrates some of the material might not be enough to finish the exam and/or pass the course, but I think it might be a starting point for study...

Cheers!

Z