Vfrdtyky

So I've been trying to decode using huffman, and I have this working function but it has horrible time and space complexity. What I've been doing so far is reading each byte, getting each bit and adding it to the currentBitString. I then reversed the string, and added it to a huge string which bascially contains all the byte data for the file. After that, I would trace the giant string and look for the Huffman code and then if its a match, i would write to file. This code takes about 60 seconds to decode a 200kb, which is very bad, but I'm not really sure how to improve it? I know I could for starters, write more than one byte to the file at a time, but it didn't seem to improve the time when I tried?

         public static void decode(File f) throws Exception {



    BufferedInputStream fin = new BufferedInputStream(new FileInputStream(f));

    int i = f.getName().lastIndexOf('.');

    String extension="txt";

    String newFileName=f.getName().substring(0, i)+extension;

    File nf = new File(newFileName);

    BufferedOutputStream fw = new BufferedOutputStream(new FileOutputStream(nf));

    int c;

    byte bits;

    byte current;

    String currentBitString="";

    String bitString="";

    //read each byte from file, reverse it, add to giant bitString

    //reads ALL BYTES

    while( (c=fin.read())!=-1 ) {

        current=(byte) c;

        currentBitString="";

        bits=0;

        for(int q=0;q<8;q++) {

            bits=getBit(current,q);

            currentBitString+=bits;

        }

        StringBuilder bitStringReverse=new StringBuilder(currentBitString);

        bitString+=bitStringReverse.reverse().toString();

    }

    currentBitString="";

    boolean foundCode=false;

    for(int j=0;j<bitString.length();j++) {

        currentBitString+=bitString.charAt(j);

        for(int k=0;k<nodes.length;k++) {

            //nodes is an array of huffman nodes which contains the the byte 

            //data and the huffman codes for each byte

            if(nodes[k].code.compareTo(currentBitString.trim())==0) {

                fw.write(nodes[k].data);    

                foundCode=true;

                break;

            }

        }

        if(foundCode) {

            currentBitString="";

            foundCode=false;

        }



    }

    fw.flush();

    fw.close();

    fin.close();



}

here's the gitBit function

        public static byte getBit(byte ID, int position) {

        // return cretin bit in selected byte

        return (byte) ((ID >> position) & 1);

        }

here's the data members of the HuffmanNode class (the nodes array is a array of HuffmanNodes)

       public class HuffmanNode{

       byte data;

       int repetitions;

       String code;

       HuffmanNode right;

       HuffmanNode left;

       }

You can replace the String concatination += with StringBuilder. This allocates less objects and puts less load on the garbage collector.

int c;

StringBuilder bitString = new StringBuilder();

//read each byte from file, reverse it, add to giant bitString

//reads ALL BYTES

while ((c = fin.read()) != -1) {

    byte current = (byte) c;

    StringBuilder currentBitString = new StringBuilder();

    for (int q = 0; q < 8; q++) {

        byte bits = getBit(current, q);

        currentBitString.append(bits);

    }

    bitString.append(currentBitString.reverse());

}

Instead of putting the codes and data into an array nodes you should use a HashMap here. You are comparing the code by iterating over the whole array until you find the right match. On average that are n/2 calls to String#equals() per item. With a HashMap you reduce this to ~1.

Fill your map with the data for the codes as keys.

Map<String, Integer> nodes = new HashMap<>();

nodes.put(code, data);

Access the data from the map

boolean foundCode = false;

for (int j = 0; j < bitString.length(); j++) {

    currentBitString.append(bitString.charAt(j));

    Integer data = nodes.get(currentBitString.toString().trim());

    if (data != null) {

        fw.write(data);

        foundCode = true;

    }

    if (foundCode) {

        currentBitString = new StringBuilder();

        foundCode = false;

    }

}

1. Don't read the whole thing into memory. Process your codes as they are encountered. Read enough bits to decode the next code, decode it, retain the unused bits for the subsequent code, repeat.




2. Don't use strings of characters to represent bits, where you are representing one bit per character. Use bits to represent bits. The shift, and, and or operators are what you should be using. You would have an integer as a bit buffer, with all the bits you need to decode the next code.




3. Don't do a search over all code lengths, and inside that a linear search of all codes to find your code! I would be hard pressed to come up with a slower approach. You should use a tree descent or table lookup for decoding. If you generate a canonical Huffman code in the first place, there is an easy lookup approach that can be implemented. See puff.c for an example. The textbook approach (which is slower than what puff.c does) is to build the same Huffman tree on the receiving end, and go down that tree bit-by-bit until you get to a symbol. Emit the symbol and repeat.

You should be able to process 200K of compressed input in a few milliseconds on a single core of a modern processor.