运行 C 中二进制文件的长度编码

Question

我编写了这个函数，它对 C 中的文本文件执行运行长度编码的稍微修改的变体。我试图将它概括为二进制文件，但我没有使用它们的经验。我明白，虽然我可以比较二进制数据的字节，就像我可以比较文本文件中的 chars 一样，但我不确定如何将一个字节的出现次数打印到压缩版本就像我在下面的代码中所做的那样。

关于我正在使用的 RLE 类型的注释：重复出现在一行中不止一次的字节以表示下一个数字实际上是出现的次数而不是后面的数字文件中的字符。对于超过一位数的出现次数，它们被分解为运行个，出现次数为 9 次。

例如，aaaaaaaaaaabccccc 变为 aa9aa2bcc5。

这是我的代码：

char* encode(char* str)
{
    char* ret = calloc(2 * strlen(str) + 1, 1);
    size_t retIdx = 0, inIdx = 0;
    while (str[inIdx]) {
        size_t count = 1;
        size_t contIdx = inIdx;
        while (str[inIdx] == str[++contIdx]) {
            count++;
        }
        size_t tmpCount = count;

        // break down counts with 2 or more digits into counts ≤ 9
        while (tmpCount > 9) {
            tmpCount -= 9;
            ret[retIdx++] = str[inIdx];
            ret[retIdx++] = str[inIdx];
            ret[retIdx++] = '9';
        }

        char tmp[2];

        ret[retIdx++] = str[inIdx];
        if (tmpCount > 1) {
            // repeat character (this tells the decompressor that the next digit
            // is in fact the # of consecutive occurrences of this char)
            ret[retIdx++] = str[inIdx];
            // convert single-digit count to string
            snprintf(tmp, 2, "%ld", tmpCount);
            ret[retIdx++] = tmp[0];
        }

        inIdx += count;
    }

    return ret;
}

为了使其适应二进制流，需要进行哪些更改？我看到的第一个问题是 snprintf 调用，因为它使用文本格式运行。敲响警钟的东西也是我处理多位数出现运行s 的方式。我们不再以 10 为基数工作，所以必须改变，我只是不确定几乎从未使用过二进制数据。

Answer 1

您只需解决 2 个问题：

你不能使用任何与 str 相关的函数，因为 C 字符串不能很好地处理 '[=11=]'。因此，例如，strlen 将 return 字符串中第一个 0x0 字节的索引。输入的长度必须作为附加参数传入：char *encode(char *start, size_t length)
您的输出不能有 strlen(ret) 的隐含长度，因为输出中可能散布着额外的 0 字节。您再次需要一个额外的参数：size_t encode(char *start, size_t length, char *output)（此版本需要在外部保留 output 缓冲区，大小至少为 length*2，return 的长度编码后的字符串）

其余代码，假设它之前可以正常工作，现在应该可以继续正常工作。如果你想超越 base-10，例如使用 base-256 进行更大的压缩，你只需要更改 break-things-up 循环中的常量（从 9 到 255 ), 并替换 snprintf 如下:

    // before
    snprintf(tmp, 2, "%ld", tmpCount);
    ret[retIdx++] = tmp[0];

    // after: much easier
    ret[retIdx++] = tmpCount;

Answer 2

一些对你有用的想法：

将 RLE 推广到二进制数据的一种简单方法是使用基于位的压缩。例如，位序列 00000000011111100111 可以转换为序列 0 9623。由于二进制字母表仅由两个符号组成，因此您只需存储第一个位值（这可以像将其存储在第一个位中一样简单），然后是连续相等值的数量。可以使用 Elias gamma coding 以二进制格式存储任意大的整数。可以添加额外的填充以使整个序列很好地适合整数个字节。所以使用这个方法，上面的序列可以这样编码：

00000000011111100111 -> 0 0001001 00110 010 011
                        ^    ^      ^    ^   ^
                first bit    9      6    2   3

如果你想保持它基于字节，一个想法是考虑所有偶数字节的频率（解释为无符号字符）和所有奇数字节的值。如果一个字节出现超过 255 次，则可以重复它。虽然这可能非常低效，但实现起来绝对简单，如果您可以对输入做出一些假设，它可能就足够了。
此外，您可以考虑退出 RLE 并实施 Huffman's coding or other sophisticated algorithms (e.g. LZW)。

实施方面，我想已经给了你一些提示。

运行 C 中二进制文件的长度编码

Run length encoding on binary files in C

c

binary-data

run-length-encoding