/**
* Huffman.java
* 12/22/2006
*
* This class allows access to the public methods encode() and decode()
* which will do their respective operations and return a String
* with the result of the operation.
*/
import java.io.*;
import java.util.*;
/**
* @author phillijw
*/
public class Huffman
{
/**
* A node of a tree.
* @author phillijw
* @param <T>
*/
protected static class Node<T> implements Comparable
{
protected Node<T> parent = null;
protected Node<T> left = null;
protected Node<T> right = null;
protected T value = null;
protected int frequency = 0;
public Node() { }
public Node(T value, int frequency, Node<T> parent)
{
this.value = value;
this.frequency = frequency;
}
/**
* This method allows Nodes to be compared by their frequency
*/
public int compareTo(Object o) {
int output = 0;
if (o instanceof Node)
{
Node n = (Node)o;
if (frequency > n.frequency) { output = 1; } //this > n
else if (frequency < n.frequency) { output = -1; } //this
< n
else //this = n; check for children children
{
if ((value == null) && (n.value != null)) { output =
1; }
else if ((value != null) && (n.value == null)) {
output = -1; }
}
}
return output;
}
}
/**
* Encodes the input into a stream of bits.
* @param file
* @param input
*/
public static String encode(String input) throws FileNotFoundException,
IOException
{
//Generate a frequency table
Map<Character, Integer> freqTable = returnFreqTable(input);
//Create Queue that will store Nodes
LinkedList<Node> nodeList = new LinkedList<Node>();
//Create Nodes and add them to nodeList
for (Map.Entry<Character, Integer> entry : freqTable.entrySet())
{
nodeList.add(new Node(entry.getKey(), entry.getValue(), null));
}
//Sort the nodeList according to frequency
Collections.sort(nodeList);
//Build the huffman tree from the min-priority queue (nodeList)
while (nodeList.size() > 1)
{
Node a = nodeList.poll();
Node b = nodeList.poll();
Node c = new Node(null, a.frequency + b.frequency, null);
c.left = a;
c.right = b;
nodeList.offer(c);
}
Node root = nodeList.poll();
//Make huffman table
Map<Character, String> huffmanTable = new TreeMap<Character, String>();
buildHuffmanTable(root, huffmanTable, new StringBuilder(""));
//This is where we actually build the output string. It will be in the
following form:
//
// <character count. 1byte> <ignore-bit count. 1byte> <character codes.
1byte x character count> <huffman codes. arbitrary lengths>
//
// The bit mask is used for the very last byte of the huffman codes. It is
not gauranteed that they will each be 1 byte each
// but something has to be stored on the drive either way that is 1 byte.
So we use this mask to know how many bits to ignore
// for the last byte of the huffman codes.
StringBuilder output = new StringBuilder();
//Append the character count (1byte)
output.append(padBits(Integer.toBinaryString(freqTable.size()), 8));
//Append ignore-bit count (filler, will be calculated later)
output.append("00000000");
//Append character codes (1byte x character count)
//Create Queue that will store Nodes
nodeList = new LinkedList<Node>();
//Create Nodes and add them to nodeList
for (Map.Entry<Character, Integer> entry : freqTable.entrySet())
{
nodeList.add(new Node(entry.getKey(), entry.getValue(),
null));
}
//Sort the nodeList according to frequency
Collections.sort(nodeList);
for (Node n : nodeList)
{
output.append(padBits(Integer.toBinaryString(
(int)((Character)n.value) ), 8));
}
//Convert input to huffman codes and append them to the output
for (int i=0; i < input.length(); i++)
{
output.append(huffmanTable.get(input.charAt(i)));
}
//Calculate the ignore-bit count and replace the previous filler
// this is how many extra bits are added onto the output in order
// to preserve the fact that file systems require full bytes to
// output to the hard disk
int bitmask = 8 - (output.length() % 8);
String filler = "";
for (int i=0; i < bitmask; i++)
{
filler += "0";
}
return output.toString() + filler;
}
/**
* Decodes a Huffman coded String.
* @param input Encoded huffman String
* @return The decoded String
* @throws FileNotFoundException
* @throws IOException
*/
public static String decode(String input) throws FileNotFoundException,
IOException
{
StringBuilder output = new StringBuilder();
//How many chars are there?
int charCount = Integer.parseInt(input.substring(0, 8), 2);
//Store those chars as Nodes in order of frequency
LinkedList<Node> nodeList = new LinkedList<Node>();
int tmpCount = charCount;
for (int i=0; i < charCount; i++)
{
nodeList.add(new Node(
(char)Integer.parseInt(input.substring(i*8+16, i*8+24), 2) , tmpCount--, null));
}
//How many bits at the end of the file to ignore? (stored as bit mask)
int bitmask = Integer.parseInt(input.substring(8, 15), 2);
//The huffman code String
String huffmanCodes = input.substring(16 + charCount*8);
//Sort the nodeList according to frequency
Collections.sort(nodeList);
Collections.reverse(nodeList);
//Build the huffman tree from the min-priority queue (nodeList)
while (nodeList.size() > 1)
{
Node a = nodeList.poll();
Node b = nodeList.poll();
Node c = new Node(null, a.frequency + b.frequency, null);
c.left = a;
c.right = b;
nodeList.offer(c);
}
Node root = nodeList.poll();
//Make huffman table
Map<String, Character> reverseHuffmanTable = new TreeMap<String,
Character>();
buildReverseHuffmanTable(root, reverseHuffmanTable, new
StringBuilder(""));
//Convert huffman codes to ASCII chars
StringBuilder code = new StringBuilder();
for (int i=0; i < huffmanCodes.length(); i++)
{
code.append(huffmanCodes.substring(i, i+1));
if (reverseHuffmanTable.containsKey(code.toString()))
{
output.append(reverseHuffmanTable.get(code.toString()));
code.delete(0, code.length());
}
}
return output.toString();
}
/**
*
* @param bits
* @param size
* @return
*/
private static String padBits(String bits, int size)
{
StringBuilder output = new StringBuilder(bits);
while (output.length() < size)
{
output.insert(0, "0");
}
return output.toString();
}
/**
* Recursively builds a Huffman Table from a Huffman Tree
* while given the root node of the tree.
* @param root The root node of the Huffman Tree
* @return
*/
private static void buildHuffmanTable(Node node, Map<Character, String>
huffmanTable, StringBuilder code)
{
//Leaf node means we are done with this branch of recursion
if ((node.left == null) && (node.right == null))
{
huffmanTable.put((Character)node.value, code.toString());
//return because we're done
return;
}
//Recurse left
if (node.left != null)
{
code.append("0");
buildHuffmanTable(node.left, huffmanTable, code);
//Bring code back to previous state
code.deleteCharAt(code.length() - 1);
}
//Recurse right
if (node.right != null)
{
code.append("1");
buildHuffmanTable(node.right, huffmanTable, code);
//Bring code back to previous state
code.deleteCharAt(code.length() - 1);
}
}
/**
* Recursively builds a Reverse Huffman Table from a Huffman Tree
* while given the root node of the tree.
* @param root The root node of the Huffman Tree
* @return
*/
private static void buildReverseHuffmanTable(Node node, Map<String, Character>
reverseHuffmanTable, StringBuilder code)
{
//Leaf node means we are done with this branch of recursion
if ((node.left == null) && (node.right == null))
{
reverseHuffmanTable.put(code.toString(), (Character)node.value);
//return because we're done
return;
}
//Recurse left
if (node.left != null)
{
code.append("0");
buildReverseHuffmanTable(node.left, reverseHuffmanTable, code);
//Bring code back to previous state
code.deleteCharAt(code.length() - 1);
}
//Recurse right
if (node.right != null)
{
code.append("1");
buildReverseHuffmanTable(node.right, reverseHuffmanTable, code);
//Bring code back to previous state
code.deleteCharAt(code.length() - 1);
}
}
/**
* Returns the frequency table stored as a TreeMap
* @param input The input String
* @return A Map of the frequency of each character from the input
*/
private static Map<Character, Integer> returnFreqTable(String input)
{
Map<Character, Integer> freqTable = new TreeMap<Character, Integer>();
for (int i=0; i < input.length(); i++)
{
Character character = input.charAt(i);
if (freqTable.containsKey(character))
{
freqTable.put(character, freqTable.get(character) + 1);
//Inc the value if it exists
}
else
{
freqTable.put(character, 1); //Set the value if it doesn't
exist
}
}
return freqTable;
}
}