Results 1 to 2 of 2
  1. #1
    Chewybakas is offline Member
    Join Date
    Feb 2013
    Rep Power

    Default 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.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
               { //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:
                    //create a new Tree 
                    //set the cumulative frequency of that Tree
                    //insert the letter as the root node 
                    //add the Tree into the PQ
                //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)
                 { //
                     { //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
                          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 no idea how to approach the problem, the aim is to implement the algorithm filling in code where it says to!

  2. #2
    AndrewM16921 is offline Senior Member
    Join Date
    Jan 2009
    CA, USA
    Rep Power

    Default 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 A-F, with the frequencies:

    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.

    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

  1. Huffman coding algorithm question?
    By knguye88 in forum New To Java
    Replies: 1
    Last Post: 03-12-2012, 09:06 AM
  2. Help: traverse Huffman tree
    By Reploids in forum New To Java
    Replies: 0
    Last Post: 05-24-2011, 10:02 AM
  3. Help: traversing huffman tree
    By Reploids in forum New To Java
    Replies: 0
    Last Post: 05-24-2011, 09:42 AM
  4. huffman coding in java
    By warlock in forum New To Java
    Replies: 2
    Last Post: 03-12-2011, 12:59 PM
  5. BufferedInputStream with Huffman Compression
    By Msnforum in forum New To Java
    Replies: 0
    Last Post: 11-03-2009, 09:04 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts