Stuff

/*** 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 > nelse if (frequency < n.frequency) { output = -1; } //this< nelse //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 tableMap<Character, Integer> freqTable = returnFreqTable(input);//Create Queue that will store NodesLinkedList<Node> nodeList = new LinkedList<Node>();//Create Nodes and add them to nodeListfor (Map.Entry<Character, Integer> entry : freqTable.entrySet()){nodeList.add(new Node(entry.getKey(), entry.getValue(), null));}//Sort the nodeList according to frequencyCollections.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 tableMap<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 thefollowing 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 isnot 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 NodesnodeList = new LinkedList<Node>();//Create Nodes and add them to nodeListfor (Map.Entry<Character, Integer> entry : freqTable.entrySet()){nodeList.add(new Node(entry.getKey(), entry.getValue(),null));}//Sort the nodeList according to frequencyCollections.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 outputfor (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 diskint 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 frequencyLinkedList<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 StringString huffmanCodes = input.substring(16 + charCount*8);//Sort the nodeList according to frequencyCollections.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 tableMap<String, Character> reverseHuffmanTable = new TreeMap<String,Character>();buildReverseHuffmanTable(root, reverseHuffmanTable, newStringBuilder(""));//Convert huffman codes to ASCII charsStringBuilder 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 recursionif ((node.left == null) && (node.right == null)){huffmanTable.put((Character)node.value, code.toString());//return because we're donereturn;}//Recurse leftif (node.left != null){code.append("0");buildHuffmanTable(node.left, huffmanTable, code);//Bring code back to previous statecode.deleteCharAt(code.length() - 1);}//Recurse rightif (node.right != null){code.append("1");buildHuffmanTable(node.right, huffmanTable, code);//Bring code back to previous statecode.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 recursionif ((node.left == null) && (node.right == null)){reverseHuffmanTable.put(code.toString(), (Character)node.value);//return because we're donereturn;}//Recurse leftif (node.left != null){code.append("0");buildReverseHuffmanTable(node.left, reverseHuffmanTable, code);//Bring code back to previous statecode.deleteCharAt(code.length() - 1);}//Recurse rightif (node.right != null){code.append("1");buildReverseHuffmanTable(node.right, reverseHuffmanTable, code);//Bring code back to previous statecode.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'texist}}return freqTable;}}