Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 7 of 7

Thread: Huffman Algorithm Help

  1. #1
    Junior Member
    Join Date
    Feb 2013
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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!

    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!
    Last edited by Norm; February 19th, 2013 at 04:47 PM. Reason: Changed /java to /code


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,719
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default Re: Huffman Algorithm Help

    Can you explain what the problem is?
    Post any error messages
    or the program's output and add some comments describing what's wrong.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Feb 2013
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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!

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,719
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Feb 2013
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Huffman Algorithm Help

    The code is to implement huffmans algorithm for compressing Strings, but that is all that is on the exam paper

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,719
    Thanks
    45
    Thanked 1,974 Times in 1,948 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Huffman Algorithm Help

    Quote Originally Posted by Chewybakas View Post
    ...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:
    .
    .
    .
                    //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

Similar Threads

  1. (HELP!! )Compressing File using Huffman Algorithm
    By alihasyim in forum What's Wrong With My Code?
    Replies: 0
    Last Post: May 6th, 2012, 09:22 AM
  2. Need help with Huffman coding, please?
    By knguye in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 12th, 2012, 07:36 AM
  3. Huffman tree help!
    By rmendoza in forum Algorithms & Recursion
    Replies: 1
    Last Post: March 3rd, 2012, 05:36 PM
  4. Help Huffman Coding>>
    By cool_97 in forum What's Wrong With My Code?
    Replies: 35
    Last Post: July 23rd, 2011, 04:27 PM
  5. Huffman Tree
    By Aberforth in forum Java Theory & Questions
    Replies: 2
    Last Post: November 9th, 2010, 04:49 AM

Tags for this Thread