java - LZW 压缩 - 修改版本

Question

我有一个 LZW 算法 -

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;
    }
}

其中 maxNumBits 应该是 trie 的最大大小。假设异常在传递 maxNumBits 参数的主类中捕获。假设dict是一个HashMap，reader是一个FileInputStream，fos是一个FileOutputStream.

在我的版本中，如果 trie 已满(即 trieLength > maxNumBits )，压缩将继续，直到当前压缩比 (currentCr) 小于最后的压缩比 (lastCr)。

我已经在一个 ~8mb 文件上运行了这个，并且更改 trie 长度不会对累积压缩比产生任何影响。是这段代码吗

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

所描述的要求正确吗？

感谢您的帮助，

山姆

编辑 - 感谢爱德华在格式化方面的帮助

Answer 1

事实证明，在检查下一次迭代之前，没有检查 trieLength，这意味着当它变满时，不会生成新的 trie。