/** * This method performs the uncompression of the file inFilename. It writes the * results to the OutputStream out. * * IMPORTANT: We use this method for testing your solution. * Don't modify the signature of this method. * * Implement a Huffman Tree based uncompression. * The used code table is stored at the begin of the file. * You can use the class HuffmanStreamReader to get the table. * This class also offers methods to read a file bit by bit. * * @param inFilename the file to uncompress * @param out outputStram to wirte the results * @throws IOException */ public void uncompress(String inFilename, OutputStream out) throws IOException { HuffmanStreamReader stream = new HuffmanStreamReader(new FileInputStream(inFilename)); table = stream.getCodeTable(); HuffmannTree tree = createHuffmannTree(table); while (stream.available() > 0){ int temp = getChar(stream, tree); out.write(temp); } } /** * This method returns the code table used by the last * compress/uncompress operation. * * @return the code table */ public BitString[] getCodeTable() { return table; } /** * To create a huffman-tree based on a given codetable. * * @param codes * the codetable * @return * the resulting huffman-tree */ private HuffmannTree createHuffmannTree(BitString[] codes){ HuffmannTree result = new HuffmannTree(); for (int i = 0 ; i < codes.length ; i++){ BitString actChar = codes[i]; HuffmannTree actTree = result; String temp = actChar.toString(); for (int j = 0 ; j < actChar.getLength() ; j++){ if (temp.charAt(j) == 0){ if (actTree.isEmpty()){ actTree = new HuffmannTree(); actTree = actTree.left; } else actTree = actTree.left; } else{ if (actTree.isEmpty()){ actTree = new HuffmannTree(); actTree = actTree.right; } else actTree = actTree.right; } } actTree.name = (char)i; } return result; } /** * To get the next char of a stream (encoding based on huffmann-tree) * * @param stream * stream to get next char of * @param tree * huffmann-tree for encoding * @return * ascii-code of next char * @throws IOException */ private int getChar(HuffmanStreamReader stream, HuffmannTree tree) throws IOException{ while (!tree.isLeaf()){ int newChar = stream.readBit(); if (newChar == 0) tree = tree.left; else if (newChar == 1) tree = tree.right; } if (tree.name == 0) throw new InvalidCharacterException(); else return tree.name; }public class HuffmannTree { // name of node (-> char represented by node) public int name; // weight of huffmann-tree public int weight; // right subtree public HuffmannTree right; // left subtree public HuffmannTree left; /** * To construct a new empty HT (subtrees are null and weight is 0). */ public HuffmannTree(){ right = null; left = null; weight = 0; } /** * To construct a leaf of the HT with given name (subtrees are empty HTs). * * @param name * name of leaf */ public HuffmannTree(int name){ this.name = name; right = new HuffmannTree(); left = new HuffmannTree(); } /** * To construct a new HT with 2 given subtrees. * * @param left * left subtree * @param right * right subtree */ public HuffmannTree(HuffmannTree left, HuffmannTree right){ // set left subtree this.left = left; // set right subtree this.right = right; // update weight (sum of weights of both subtrees) this.weight = left.weight + right.weight; } /** * To check if HT is empty or not. * * @return * true, if both subtrees are null */ public boolean isEmpty(){ return left == null && right == null; } /** * To check if HT is a leaf. * * @return * true, if actual HT is non-empty, but both subtrees are */ public boolean isLeaf(){ return !isEmpty() && left.isEmpty() && right.isEmpty(); } /** * To check if HT is lighter than another one. * * @param tree * other tree to check * @return * true, if actual HT is lighter than given HT */ public boolean lighter(HuffmannTree tree){ return this.weight < tree.weight; }}