1. Member 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);

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 += binaryValue+" "; //add to the string of binary
}

System.out.println(binaryString);    //print out the binary

int[] array = new int;      //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!  Reply With Quote

2. Senior 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 A-F, with the frequencies:
A=25%
B=10%
C=10%
D=15%
E=35%
F=5% 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.  Reply With Quote
huffman, java 