zlib 压缩输出可以避免使用某个字节值吗?

Question

似乎zlib.compress的输出使用了所有可能的字节值。是否可以使用 256 个字节值中的 255 个(例如避免使用n(？

请注意，我只是使用 python 手册作为参考，但这个问题并不特定于 python(即任何其他具有zlib库的语言(。

Answer 1

不，这是不可能的。除了压缩数据本身之外，还有包含整数的标准化控制结构。这些整数可能会意外地导致任何 8 位字符最终出现在字节流中。

你唯一的机会是将zlib字节流编码为另一种格式，例如base64。

Answer 2

压缩的全部意义在于尽可能减小大小。如果 zlib 或任何压缩器仅使用 256 字节值中的 255 个，则输出的大小将至少增加 0.07%。

这对您来说可能完全没问题，因此您可以简单地对压缩输出或任何数据进行后处理，以删除一个特定的字节值，但代价是一些扩展。最简单的方法是在出现该字节时将其替换为双字节转义序列。然后，还需要将转义前缀替换为不同的双字节转义序列。这将使数据平均扩展0.8%。这正是汉斯在这里的另一个答案中提供的。

如果成本太高，你可以做一些更复杂的事情，即解码一个固定的霍夫曼码，该码编码255个概率相等的符号。要解码，然后对霍夫曼代码进行编码。输入是位序列，而不是字节序列，大多数情况下，您需要用一些零位填充输入以对最后一个符号进行编码。霍夫曼码将一个符号转换为七位，将其他 254 个符号转换为八位。因此，反过来，它将使输入扩展不到0.1%。对于短消息，它会多一点，因为通常最后不到七位将被编码成一个符号。

C 语言中的实现：

// Placed in the public domain by Mark Adler, 26 June 2020.
// Encode an arbitrary stream of bytes into a stream of symbols limited to 255
// values. In particular, avoid the n (10) byte value. With -d, decode back to
// the original byte stream. Take input from stdin, and write output to stdout.
#include <stdio.h>
#include <string.h>
// Encode arbitrary bytes to a sequence of 255 symbols, which are written out
// as bytes that exclude the value 'n' (10). This encoding is actually a
// decoding of a fixed Huffman code of 255 symbols of equal probability. The
// output will be on average a little less than 0.1% larger than the input,
// plus one byte, assuming random input. This is intended to be used on
// compressed data, which will appear random. An input of all zero bits will
// have the maximum possible expansion, which is 14.3%, plus one byte.
int nolf_encode(FILE *in, FILE *out) {
unsigned buf = 0;
int bits = 0, ch;
do {
if (bits < 8) {
ch = getc(in);
if (ch != EOF) {
buf |= (unsigned)ch << bits;
bits += 8;
}
else if (bits == 0)
break;
}
if ((buf & 0x7f) == 0) {
buf >>= 7;
bits -= 7;
putc(0, out);
continue;
}
int sym = buf & 0xff;
buf >>= 8;
bits -= 8;
if (sym >= 'n' && sym < 128)
sym++;
putc(sym, out);
} while (ch != EOF);
return 0;
}
// Decode a sequence of symbols from a set of 255 that was encoded by
// nolf_encode(). The input is read as bytes that exclude the value 'n' (10).
// Any such values in the input are ignored and flagged in an error message.
// The sequence is decoded to the original sequence of arbitrary bytes. The
// decoding is actually an encoding of a fixed Huffman code of 255 symbols of
// equal probability.
int nolf_decode(FILE *in, FILE *out) {
unsigned long lfs = 0;
unsigned buf = 0;
int bits = 0, ch;
while ((ch = getc(in)) != EOF) {
if (ch == 'n') {
lfs++;
continue;
}
if (ch == 0) {
if (bits == 0) {
bits = 7;
continue;
}
bits--;
}
else {
if (ch > 'n' && ch <= 128)
ch--;
buf |= (unsigned)ch << bits;
}
putc(buf, out);
buf >>= 8;
}
if (lfs)
fprintf(stderr, "nolf: %lu unexpected line feeds ignoredn", lfs);
return lfs != 0;
}
// Encode (no arguments) or decode (-d) from stdin to stdout.
int main(int argc, char **argv) {
if (argc == 1)
return nolf_encode(stdin, stdout);
else if (argc == 2 && strcmp(argv[1], "-d") == 0)
return nolf_decode(stdin, stdout);
fputs("nolf: unknown options (use -d to decode)n", stderr);
return 1;
}

Answer 3

正如@ypnos所说，这在 zlib 本身中是不可能的。您提到 base64 编码效率太低，但使用转义字符对要避免的字符(如换行符(进行编码非常容易。

这不是世界上最高效的代码(您可能想做一些事情，例如查找最少使用的字节以节省更多空间(，但它具有足够的可读性并演示了这个想法。您可以无损编码/解码，编码后的流不会有任何换行符。

def encode(data):
# order matters
return data.replace(b'a', b'aa').replace(b'n', b'ab')
def decode(data):
def _foo():
pair = False
for b in data:
if pair:
# yield b'a' if b==b'a' else b'n'
yield 97 if b==97 else 10
pair = False
elif b==97:  # b'a'
pair = True
else:
yield b
return bytes(_foo())

作为某种置信度，您可以在小字节串上详尽地检查这一点：

from itertools import *
all(
bytes(p) == decode(encode(bytes(p)))
for c in combinations_with_replacement(b'abnc', r=6)
for p in permutations(c)
)