我有一个正好 53 个字符长的字符串，其中包含一组有限的可能字符。
[A-Za-z0-9\.\-~_+]{53}
我需要在不丢失信息并使用相同字符集的情况下将其减少到 50。
我认为应该可以将大多数字符串压缩到 50 长度，但是所有可能长度为 53 的字符串都可以吗？我们知道，在最坏的情况下，可能集合中的 14 个字符将未被使用。我们可以使用这些信息吗？
谢谢阅读。
问问题
3892 次
5 回答
11
如果，如您所说，您的输出字符串必须使用与输入字符串相同的字符集，并且如果您对输入字符串的要求一无所知，那么不，不可能压缩所有可能的 53 - 最多 50 个字符的字符串。这是鸽巢原理的简单应用。
- 您的输入字符串可以表示为以67 为基数的 53 位数字，即从 0 到 67 53 - 1 ≅ 6*10 96的整数。
- 您想将这些数字映射到 0 到 67 50 - 1 ≅ 2*10 91之间的整数。
- So by the pigeonhole principle, you're guaranteed that 673 = 300,763 different inputs will map to each possible output -- which means that, when you go to decompress, you have no way to know which of those 300,763 originals you're supposed to map back to.
To make this work, you have to change your requirements. You could use a larger set of characters to encode the output (you could get it down to 50 characters if each one had 87 possible values, instead of the 67 in the input). Or you could identify redundancy in the input -- perhaps the first character can only be a '3' or a '5', the nineteenth and twentieth are a state abbreviation that can only have 62 different possible values, that sort of thing.
If you can't do either of those things, you'll have to use a compression algorithm, like Huffman coding, and accept the fact that some strings will be compressible (and get shorter) and others will not (and will get longer).
于 2012-11-20T21:41:39.060 回答
5
你问的问题在最一般的情况下是不可能的，这可以很简单地证明。
假设可以在同一组中将任意 53 个字符的字符串编码为 50 个字符。这样做，然后将三个随机字符添加到编码字符串中。然后你有另一个任意的 53 个字符的字符串。你如何压缩它？
因此，不能保证您想要的内容适用于任何可能的数据。但是，您的所有真实数据可能具有足够低的熵，您可以设计一个可行的方案。
在这种情况下，您可能想要做一些霍夫曼编码的变体，它基本上为您集中的字符分配可变位长度编码，对最常用的字符使用最短的编码。您可以分析所有数据以得出一组编码。在霍夫曼编码之后，您的字符串将是一个（希望更短的）比特流，您将其编码为每个字符 6 位的字符集。对于您的所有真实数据，它可能足够短。
像 Smaz （在另一个答案中引用）这样的基于库的编码也可以工作。同样，无法保证它适用于所有可能的数据。
于 2012-11-20T21:16:55.473 回答
5
一个字节（字符）可以编码 256 个值（0-255），但您的有效字符集仅使用 67 个值，可以用 7 位表示（唉，6 位只能得到 64）并且您的字符都没有使用高位字节的位。
鉴于此，您可以丢弃高位并仅存储 7 位，将下一个字符的初始位运行到第一个字符的“备用”空间中。这将只需要 47 个字节的空间来存储。（53 x 7 = 371 位，371 / 8 = 46.4 == 47）
这并不是真正考虑的压缩，而是编码的变化。
例如“ABC”是 0x41 0x42 0x43
0x41 0x42 0x43 // hex values
0100 0001 0100 0010 0100 0011 // binary
100 0001 100 0010 100 0011 // drop high bit
// run it all together
100000110000101000011
// split as 8 bits (and pad to 8)
10000011 00001010 00011[000]
0x83 0x0A 0x18
例如，这 3 个字符不会节省任何空间，但您的 53 个字符将始终显示为 47 个，保证。
但是请注意，如果这对您很重要，输出将不会使用您的原始字符集。
过程变为：
original-text --> encode --> store output-text (in database?)
retrieve --> decode --> original-text restored
于 2012-11-20T21:34:09.747 回答
2
Smaz是一个简单的压缩库，适用于压缩非常短的字符串。
于 2012-11-20T20:59:20.477 回答