Huffman coding Algorithm

Hello friends,

I am here with yet another algorithm question.

Suppose we have an input of characters. We want to encode the characters using Huffman Coding, so that we assign least number of bits to the character having the maximum occurrence in the input.

Please find the code below...

public class HuffmanCode {

static public class HashSet {
static public class EntrySet {
public char key;
public String code;
public int frequency = 1;
public EntrySet next;

public EntrySet(char key, EntrySet next) {
this.key = key;
this.next = next;
}

public static int getHashCodeForChar(char c) {
int result = 1;
result = 31 * c;
return result;

}

@Override
public int hashCode() {
return getHashCodeForChar(key);
}
}

public static class KeyNode {
KeyNode next;
char key;

public KeyNode(char key, KeyNode next) {
this.key = key;
this.next = next;
}
}

KeyNode keyList;
int keyCounter;
private int maxSize = 97;
private int size = 0;
private EntrySet[] set = new EntrySet[maxSize];

public boolean add(char data) {
EntrySet node = new EntrySet(data, null);
int index = calculateIndex(EntrySet.getHashCodeForChar(data));
EntrySet temp = set[index];
while (temp != null) {
if (data == temp.key) {
temp.frequency++;
return false;
}
temp = temp.next;
}
keyList = new KeyNode(data, keyList);
keyCounter++;
node.next = set[index];
set[index] = node;
size++;
return true;
}

public int calculateIndex(int hash) {
int index = hashCode() % maxSize;
return index;
}

public int getFrequency(char key) {
int hashcode = EntrySet.getHashCodeForChar(key);
int index = calculateIndex(hashcode);
if (set[index] == null) {
return 0;
} else {
EntrySet node = set[index];
while (node != null) {
if (key == node.key) {
return node.frequency;
}
node = node.next;
}
return 0;
}
}

public EntrySet getEntrySet(char key){
int hashcode = EntrySet.getHashCodeForChar(key);
int index = calculateIndex(hashcode);
if (set[index] == null) {
return null;
} else {
EntrySet node = set[index];
while (node != null) {
if (key == node.key) {
return node;
}
node = node.next;
}
return null;
}
}

public char[] getKeys() {
KeyNode temp = keyList;
char[] retValue = new char[keyCounter];
int retCount = 0;
while (temp != null) {
retValue[retCount++] = temp.key;
temp = temp.next;
}
return retValue;
}
}

public static void main(String[] args) {
char inputChars[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'a', 'a', 'a', 'b', 'a',
'b', 'a', 'z', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
'a', 'a', 'a' };
HashSet set = new HashSet();
for (char c : inputChars) {
set.add(c);
}
char keys[] = set.getKeys();
int n = keys.length;
PQ pq = new PQ(n);
for (char c : keys) {
pq.add(c, set.getFrequency(c));
}
while (pq.size > 1) {
HuffmanNode left = pq.remove();
HuffmanNode right = pq.remove();
HuffmanNode parent = new HuffmanNode(left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.add(parent);
}
HuffmanNode top = pq.remove();
StringBuilder code = new StringBuilder();
while(!top.isProcessed){
HuffmanNode temp = top;
code.replace(0, code.length(), ""); // reset
// now traverse till one of the leaf or a node with left and right both processed
while(true){
if(temp.left == null && temp.right == null){
// leaf node
temp.isProcessed = true;
set.getEntrySet(temp.c).code = code.toString();
break;
}
else if(!temp.left.isProcessed){
code.append(0);
temp = temp.left;
}
else if(!temp.right.isProcessed){
code.append(1);
temp = temp.right;
}
else{
// both processed
temp.isProcessed = true;
break;
}
}

}
for (char key : keys) {
System.out.println(key+" has code "+set.getEntrySet(key).code+" freq "+set.getEntrySet(key).frequency);
}
}

static class HuffmanNode {
HuffmanNode left;
HuffmanNode right;
char c;
int freq;
boolean isProcessed = false;

public HuffmanNode(char c, int freq) {
this.freq = freq;
this.c = c;
}

public HuffmanNode(int freq) {
this.freq = freq;
}
}

static public class PQ {
int maxSize;
int size = 0;;
HuffmanNode[] nodes;

public PQ(int maxSize) {
this.maxSize = maxSize;
nodes = new HuffmanNode[maxSize];
}

public void add(char c, int freq) {
HuffmanNode node = new HuffmanNode(c, freq);
nodes[size++] = node;
addNHeapify();
}

public void add(HuffmanNode node) {
nodes[size++] = node;
addNHeapify();
}

public void addNHeapify() {
int currentIndex = size - 1;
int currentData = nodes[currentIndex].freq;
int parentIndex = currentIndex / 2;
int parentData = nodes[parentIndex].freq;
while (currentData < parentData) {
swap(currentIndex, parentIndex);
currentIndex = parentIndex;
currentData = nodes[currentIndex].freq;
parentIndex = currentIndex / 2;
parentData = nodes[parentIndex].freq;
}
}

public HuffmanNode remove() {
HuffmanNode node = nodes[0];
swap(0, size - 1);
nodes[size - 1] = null;
size--;
if(size != 0){
removeNHeapify();
}
return node;
}

public void removeNHeapify() {
int currentIndex = 0;
int currentData = nodes[currentIndex].freq;
int childIndex;
int childData;
if (2 * currentIndex + 1 > size - 1) {
return;
}
if (2 * currentIndex + 2 < size) {
if (nodes[2 * currentIndex + 1].freq < nodes[2 * currentIndex + 2].freq) {
childIndex = 2 * currentIndex + 1;
} else {
childIndex = 2 * currentIndex + 2;
}
} else {
childIndex = 2 * currentIndex + 1;
}
childData = nodes[childIndex].freq;
while (currentData > childData) {
swap(childIndex, currentIndex);
currentIndex = childIndex;
currentData = nodes[currentIndex].freq;
if (2 * currentIndex + 1 > size - 1) {
return;
}
if (2 * currentIndex + 2 < size) {
if (nodes[2 * currentIndex + 1].freq < nodes[2 * currentIndex + 2].freq) {
childIndex = 2 * currentIndex + 1;
} else {
childIndex = 2 * currentIndex + 2;
}
} else {
childIndex = 2 * currentIndex + 1;
}
}
}

public void swap(int index1, int index2) {
HuffmanNode temp = nodes[index1];
nodes[index1] = nodes[index2];
nodes[index2] = temp;
}
}
}