c - LZW 压缩

Question

LZW 压缩算法在压缩后增加了位大小:

这是压缩函数的代码:

// compression
void compress(FILE *inputFile, FILE *outputFile) {    
    int prefix;
    int character;

    int nextCode;
    int index;

    // LZW starts out with a dictionary of 256 characters (in the case of 8 codeLength) and uses those as the "standard"
    //  character set.
    nextCode = 256; // next code is the next available string code
    dictionaryInit();

    // while (there is still data to be read)
    while ((character = getc(inputFile)) != (unsigned)EOF) { // ch = read a character;

        // if (dictionary contains prefix+character)
        if ((index = dictionaryLookup(prefix, character)) != -1) prefix = index; // prefix = prefix+character
        else { // ...no, try to add it
            // encode s to output file
            writeBinary(outputFile, prefix);

            // add prefix+character to dictionary
            if (nextCode < dictionarySize) dictionaryAdd(prefix, character, nextCode++);

            // prefix = character
            prefix = character; //... output the last string after adding the new one
        }
    }
    // encode s to output file
    writeBinary(outputFile, prefix); // output the last code

    if (leftover > 0) fputc(leftoverBits << 4, outputFile);

    // free the dictionary here
    dictionaryDestroy();
}

其中writeBinary(它在程序中充当缓冲区)函数如下:

void writeBinary(FILE * output, int code);

int leftover = 0;
int leftoverBits;

    void writeBinary(FILE * output, int code) {
        if (leftover > 0) {
            int previousCode = (leftoverBits << 4) + (code >> 8);

            fputc(previousCode, output);
            fputc(code, output);

            leftover = 0; // no leftover now
        } else {
            leftoverBits = code & 0xF; // save leftover, the last 00001111
            leftover = 1;

            fputc(code >> 4, output);
        }
    }

请问您能发现错误吗？我将不胜感激!

Answer 1

chux 已经向您指出了解决方案:您需要从 9 位代码开始，并在当前位大小的可用代码耗尽时将代码大小增加到 12。如果您从一开始就编写 12 位代码，那么当然没有压缩效果。