# CHALLENGING: Huffman coding

• 03-29-2011, 09:05 PM
CHALLENGING: Huffman coding
Hi, am working on a huffman coding and having problem assembling my tree, here is how huffman coding works:

1. Initialization: Put all symbols on a list sorted according to their frequency counts.

2. Repeat until the list has only one symbol left:
(1) From the list pick two symbols with the lowest frequency counts. Form a Huffman subtree that has these two symbols as child nodes and create a parent node.

(2) Assign the sum of the children’s frequency counts to the parent and insert it into the list such that the order is maintained.

(3) Delete the children from the list.

3. Assign a codeword for each leaf based on the path from the root.

http://www.imagebam.com/image/ba8321125693020
(ImageBam - Fast, Free Image Hosting and Photo Sharing)
Coding Tree for “HELLO” using the Huffman Algorithm.

My program already builds the small nodes (Parent child) but i can't find any solution for how to assemble them in the whole tree

Main code:
Quote:

/**
*
*/

import java.util.*;

public class Huffman {

public static void main (String args[])
{
System.out.print("Enter string: ");
Scanner input = new Scanner (System.in);
String completeData = input.nextLine().toUpperCase();

//used to store the objects -> each character and its frequency
Vector<HuffmanObject> myData = new Vector<HuffmanObject>();

int frequency; //used to store frequency for each character
String temp; //used to temporarily store each character one by one

//i iterates for each character
for (int i=0; i<completeData.length(); i++)
{
temp = Character.toString(completeData.charAt(i)); //temp is holding the actual character

//searching for temp in myData
//j iterates for searching inside the data
for (int j=0; j<=myData.size(); j++)
{
if (containsValue(myData, temp)>0) //if character already read before
{
//just incrementing frequency for that character by 1
frequency=myData.get(containsValue(myData, temp)).getFreq();
myData.get(containsValue(myData, temp)).setFreq( frequency +1 );
break;
}

if (containsValue(myData, temp)<0) //if character was not read before
{
myData.add( new HuffmanObject(temp, 1) ); //adding character to myData with frequency 1
}
}

}//end for -> processing of string -> Array fill complete

String name = "P"; //used to build the parent node's name, e.g. P1, P2,...
int freq, freq1, freq2 = 0; //used to build parent's frequency

int parentCount=1; //used to define parent name count

//parentArray used to monitor which parent has which child
Vector<ParentChild> parentArray = new Vector<ParentChild>();

int lastPosition=0; //monitor last index used of Vector data rather than typing myData.size() each time

//Building the tree
while (parentArray.size()!=1) //should end when there is only 1 parent left in the vector
{
myData = sort(myData); //sorting descending

//get last 2 object's frequencies
lastPosition = myData.size();
freq1 = myData.get(lastPosition-1).getFreq();
freq2 = myData.get(lastPosition-2).getFreq();

//combine into parent frequency
freq = freq1 + freq2;

//building parent name
name = name+parentCount;

//adding parent object to parentArray
parentArray.add(new ParentChild( myData.get(lastPosition-2)/*Code is zero*/, myData.get(lastPosition-1)/*Code is one*/ ));

//removing used huffman objects
myData.remove(lastPosition-1);
myData.remove(lastPosition-2);

//adding parent node to myArray
parentCount++;

}//end while -> tree builded

System.out.print("Tree complete");

/*SUMMARY:
*
* myArray holds the last ultimate parent node
* myParentArray holds details of what child is found under which parent
*
**/

}//end main

//sort decending
public static Vector<HuffmanObject> sort(Vector<HuffmanObject> array)
{
HuffmanObject temp;

for(int i=0; i<array.size();i++)
{
for(int j=i+1; j<array.size();j++)
{
if(array.get(i).getFreq()<array.get(j).getFreq())
{
temp=array.get(i);

array.insertElementAt(array.get(j), i);
array.insertElementAt(temp, j);
}
}
}

return array;
}

public static int containsValue (Vector<HuffmanObject> dict, String s)
{
int result=-1;
for (int i=0; i<dict.size(); i++)
{
if ( (dict.get(i).getName() ).equals(s))
{
result = i;
}
}

return result;
}

/*
public static HuffmanObject[] removeLastTwo(HuffmanObject[] array)
{
HuffmanObject[] arrayNew = new HuffmanObject[array.length-2];

for (int i=0; i<arrayNew.length; i++)
{
arrayNew[i] = array[i];
}

return arrayNew;
}*/
}//end class

Huffman Object
Quote:

/**
*
*/
public class HuffmanObject {

private static String name;
private static int freq;

public HuffmanObject(String name, int freq)
{
this.name = name;
this.freq = freq;
}

public static String getName() {
return name;
}

public static void setName(String name) {
HuffmanObject.name = name;
}

public static int getFreq() {
return freq;
}

public static void setFreq(int freq) {
HuffmanObject.freq = freq;
}
}

ParentChild object
Quote:

/**
*
*/

//A ParentChild object has 2 attributes: parent & child which on their own have 2 attributes, normal HuffmanObjects

public class ParentChild {

private HuffmanObject zero;
private HuffmanObject one;

public ParentChild (HuffmanObject p, HuffmanObject c)
{
this.zero = p;
this.one = c;
}

public HuffmanObject getParent() {
return zero;
}

public void setParent(HuffmanObject parent) {
this.zero = parent;
}

public HuffmanObject getChild() {
return one;
}

public void setChild(HuffmanObject child) {
this.one = child;
}
}