Huffman application

1/1/13 10:08 PM

Page 1 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/examples/HuffmanTree.html

import java.io.File; import java.io.FileNotFoundException; import java.util.Comparator; import java.util.Scanner; import java.util.Set;

/** * This class implements the basic functionality of Huffman compression and expansion. * * @author C. Andrews * */ public class HuffmanTree { Map<String, String> _lookupTable = new BSTMap<String, String>(); BinaryTree<CountPair> _huffmanTree;

/** * This is a factory method for reading in a fresh text file to initialize the Huffman tree. * * @param file the document to use for the code frequencies * @return a HuffmanTree containing the Huffman codes based on the frequencies observed in the document * @throws FileNotFoundException */ public static HuffmanTree newTreeFromFile(File file) throws FileNotFoundException{ HuffmanTree tree = new HuffmanTree(); tree.buildFromFile(file); return tree; }

/** * This is a factory method that builds a new HuffmanTree from a compressed file. * * @param file a file that has been compressed with a Huffman tool * @return a new HuffmanTree containing the codes for decoding the file * @throws FileNotFoundException */ public static HuffmanTree newTreeFromCompressedFile(File file) throws FileNotFoundException{ // TODO implement this } /** * This method builds the Huffman tree from the input file. * * @param file the file to use to construct the Huffman tree * @throws FileNotFoundException */ private void buildFromFile(File file) throws FileNotFoundException {

// read file and build the map of the character frequencies Map<String, Integer> freqMap = new BSTMap<String, Integer>(); Scanner scanner = new Scanner(file); scanner.useDelimiter(""); String character; while (scanner.hasNext()){ character = scanner.next(); Integer count = freqMap.get(character); if (count == null){ count = Integer.valueOf(0); }

freqMap.put(character, count+1);

} // for each key, make a tree and load it into the priority queue PriorityQueue<BinaryTree<CountPair>> treeQueue = new PriorityQueue<BinaryTree<CountPair>>(freqMap.keySet().size(), new CountPairTreeComparator BinaryTree<CountPair> tmpTree; for (String key: freqMap.keySet()){ int frequency = freqMap.get(key); tmpTree = new BinaryTree<CountPair>(null, new CountPair(key, frequency), null); treeQueue.add(tmpTree); } // while the size of the priority queue is greater than 1, combine the top items into a tree and put them back in the priority queue BinaryTree<CountPair> tree1, tree2; int newFrequency;

1/1/13 10:08 PM

Page 2 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/examples/HuffmanTree.html

String newText; while (treeQueue.size() > 1){ tree1 = treeQueue.remove(); tree2 = treeQueue.remove(); // If the height of the second tree is less than the height of the first, // or the heights are the same and tree2 precedes tree1 alphabetically, swap them so // the smaller/earlier tree is put on the left if (tree1.getValue()._text.length() > tree2.getValue()._text.length() ||( tree1.getValue()._text.length() == tree2.getValue()._text.length() && tree1.getValue()._text.compareTo(tree2.getValue()._text) > 0)){ tmpTree = tree1; tree1 = tree2; tree2 = tmpTree; } // create a new tree combining the two smaller trees, computing a new frequency that is the sum of the // children frequencies and a new text that is the appended combination of the children's text newFrequency = tree1.getValue()._count + tree2.getValue()._count; newText = tree1.getValue()._text + tree2.getValue()._text; tmpTree = new BinaryTree<CountPair>(tree1, new CountPair(newText, newFrequency), tree2); treeQueue.add(tmpTree); } // pull the completed tree from the priority queue BinaryTree<CountPair> tree = treeQueue.remove(); // create map of symbols to code lengths using the tree Map<String, Integer> codeLengthMap = new Map<String, Integer>(); // TODO implement this part buildTreeFromMap(codeLengthMap);

}

/** * Builds the tree using information found in a compressed file. * * The table is the first thing we find in the file. The first piece of data is the length * of the table (L). This is followed by L pairs of character and code length pairs. * * @param file the file to read the Huffman code from. */ private void buildFromCompressedFile(File file) throws FileNotFoundException{ // TODO implement this } /** * Read the original file and compress it using the Huffman codes, writing the result * into the output file. * * @param outputFile the output file */ public void saveCompressedFile(File outputFile){ // TODO implement this } /** * Read the compressed file that initialized this object and write the decoded version out * into the output file. * * @param outputFile the destination file for the uncompressed file. */ public void saveExpandedFile(File outputFile){ // TODO implement this } /** * This method reads in a String of text and returns a String of 0s and 1s corresponding to the Huffman code stored in this tree. * @param text the text to be encoded * @return a String representation of the Huffman code */ public String encode(String text){ StringBuilder builder = new StringBuilder(); String tmp; for (int i =0; i < text.length(); i++){ tmp = _lookupTable.get(String.valueOf(text.charAt(i))); builder.append(tmp); }

1/1/13 10:08 PM

Page 3 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/examples/HuffmanTree.html

return builder.toString(); } /** * This method reads in a String representation of a Huffman code corresponding to this Huffman tree and decodes it. * @param text a String representation of the a Huffman coded message * @return the original text */ public String decode(String text){ StringBuilder builder = new StringBuilder();

BinaryTree<CountPair> current = _huffmanTree; for (int i =0; i < text.length(); i++){ char c = text.charAt(i);

if (c == '0'){ current = current.getLeft(); }else if (c == '1'){ current = current.getRight(); }else{ throw new RuntimeException("Encountered unexpected character in coded String"); } if (current.isLeaf()){ builder.append(current.getValue()._text); current = _huffmanTree; } } return builder.toString(); }

private class CountPair{ int _count; String _text; private CountPair(String text, int count){ _text = text; _count = count; } }

private class CountPairTreeComparator implements Comparator<BinaryTree<CountPair>>{

@Override public int compare(BinaryTree<CountPair> t1, BinaryTree<CountPair> t2) { CountPair p1 = t1.getValue(); CountPair p2 = t2.getValue(); if (p1._count != p2._count){ return p2._count - p1._count; }else if (p1._text.length() != p2._text.length()){ return -p1._text.length() - p2._text.length(); } else{ return p1._text.compareTo(p2._text); } } }

}