LZW Compression - A modified version

Question

I have an LZW algorithm -

private void start(int maxNumBits) throws IOException{
    System.out.println("Beginning");
    /** Compress a string to a list of output symbols. */
    // Build the dictionary.
    for (int i = 0; i < 256; i++)
        dict.put("" + (char)i, i);
    int i;
    String w = "";
    int bitsRead = 0;
    int bitsOutput = 0;
    int trieLength = 0;
    float lastCr = 0f;
    while((i = reader.read()) != EOF){
        bitsRead += 8;
        float currentCr = (float)bitsRead / (float)bitsOutput;
        if(bytesRead % 1024 == 0)
            System.out.println(currentCr);
        String wi = w + (char)i;
        if (dict.containsKey(wi) && ((currentCr >= lastCr) || (trieLength < maxNumBits))){
            w = wi;
            trieLength += 8;
        }
        else {
            fos.write(dict.get(w));
            bitsOutput += 8;
            // Add wi to the dictionary.
            dict.put(wi, mapSize++);
            w = "" + (char)i;
            trieLength = 0;
        }
        lastCr = currentCr;
    }
    // Output the code for w.
    if (!w.equals("")){
        fos.write(dict.get(w));
        bitsOutput += 8;
    }
}

where maxNumBits is supposed to be the maximum size of the trie. Assume the exception is caught in a main class which passes the maxNumBits parameter. Assume dict is a HashMap, reader is a FileInputStream and fos is a FileOutputStream.

In my version, if the trie becomes full ( that is, trieLength > maxNumBits ), the compression continues until the current compression ratio (currentCr) is less than the last compression ratio (lastCr).

I've run this on a ~8mb file and changing the trie length doesn't do anything to the cumulative compression ratio. Is this code

if(dict.containsKey(wi) && ((currentCr >= lastCr)||(trieLength < maxNumBits)))

correct for the requirements described?

Thanks for your help,

Sam

edit - thanks for the help with formatting, Edward

Answer 1

It turns out that the trieLength wasn't being checked for before the next iteration was being checked, meaning that a new trie wasn't being generated when it became full.