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

    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.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 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
    Location
    CA, USA
    Posts
    264
    Rep Power
    6

    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:
    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

  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
  •