Huffman Tree Decompression

[infiniteloop56]

Hey Guys,

I am building app using a huffman tree, and am building this java program to just test a few things and I am having some trouble. I have everything working except that I am having troble decompressing a huffman string back into the original string. I would appreciate any help on this. Please find attached my code so far. As you can see so far, I have most of it down, its just the decompression part that I need trouble with. Essentially, I need to rebuild a huffman tree using the huffman tree string and then use that tree to find the original string.

/**
 * It is okay to use ArrayList class but you are not allowed to use any other
 * predefined class supplied by Java.
 */
import java.util.ArrayList;

public class CompressDecompress
{

        /**
         * Get a string representing a Huffman tree where its root node is root
         * @param root the root node of a Huffman tree
         * @return a string representing a Huffman tree
         */

        private static ArrayList <Character> list = new ArrayList <Character>();
        public static String getTreeString(final BinaryNodeInterface<Character> root)

        {
                // TO DO
                String result = "";

                if (root != null){

                if(root.isLeaf()){
                        result += "L" + root.getData();
                }else{
                        result += "I";
                }

                result += getTreeString(root.getLeftChild());
                result += getTreeString(root.getRightChild());
                }

                return result;
        // Do not forget to change this line!!!
        }

        /**
         * Compress the message using Huffman tree represented by treeString
         * @param root the root node of a Huffman tree
         * @param message the message to be compressed
         * @return a string representing compressed message.
         */
        public static String compress(final BinaryNodeInterface<Character> root, final String message)
        {
                // TO DO
                ArrayList<Character> letter = new ArrayList<Character>();
                ArrayList<String> code = new ArrayList<String>();

                //add to letter all unique characters
                for (int i = 0; i < message.length(); i ++){
                        boolean isIn = false;
                        int ind = 0;

                        //check is letter same
                        for(int j = 0; j < letter.size(); j ++){
                                if (message.charAt(i) == letter.get(j)){
                                        isIn = true;
                                        break;
                                }
                                ind++;
                        }

                        //add to letter array
                        if (isIn == false){
                                letter.add(message.charAt(ind));
                        }
                }

                //add each code
                for(int i = 0; i < letter.size(); i ++){
                        code.add(getPathTo(root,letter.get(i)));
                }

                //make result
                String result = "";
                for(int i = 0; i < message.length(); i ++){
                        for(int j = 0; j < letter.size(); j ++){
                                if(message.charAt(i) == letter.get(j)){
                                        result += code.get(j);
                                }
                        }      
                }
                return result;
        }

        /**
         * Decompress the message using Huffman tree represented by treeString
         * @param treeString the string represents the Huffman tree of the
         * compressed message
         * @param message the compressed message to be decompressed
         * @return a string representing decompressed message
         */
        public static String decompress(final String treeString, final String message)
        {
                // TO DO
                HuffmanTree huffmantree = new HuffmanTree(treeString);
                return treeString + " " + message;      // Do not forget to change this line!!!
        }
        private static String getPathTo(final BinaryNodeInterface<Character> root, char c)
    {
        // TO DO
        String path = "";
        String total = "";

        if(root.getData() != null){
                if(root.getData() == c)
                {
                        return path;
                }
        }

        if(root.hasLeftChild())
        {
            total = getPathTo(root.getLeftChild(), c);

            if( total != null )
            {
                path = path + "0";
                path = path + total;
                return path;
            }
        }

        if( root.hasRightChild() )
        {
            total = getPathTo(root.getRightChild(), c);

            if( total != null )
            {
                path = path + "1";
                path = path + total;
                return path;
            }
        }
        return null;
    }
}

[Taywin]

To do decompress, you have to remember that the incoming String message needs to be the compressed version which consists of '0' and '1'. Before you can do that, your compress string must have a specific rules applied to the compress (i.e. fixed string of how many bits you are reading, etc.). If you look at the bottom of here, the author explained how to compose a compressed string using Huffman tree. There must be a leading message to let your decompress method know how to decompress the message.

PS: The explanation at the bottom is a bit obscure but not too difficult to understand. The example starts from the node 22:*, not from 102:*.