我有一个字符串,长度为53个字符,其中包含一组有限的可能字符。
[A-Za-z0-9\.\-~_+]{53}
我需要将此内容压缩到50个字符,同时不损失任何信息并使用相同的字符集。
我认为大多数字符串都可以压缩到50个长度,但对于所有可能的53个长度字符串是否也是如此呢?我们知道在最坏情况下,可能集合中会有14个字符未被使用。我们是否能利用这些信息呢?
谢谢阅读。
我有一个字符串,长度为53个字符,其中包含一组有限的可能字符。
[A-Za-z0-9\.\-~_+]{53}
我需要将此内容压缩到50个字符,同时不损失任何信息并使用相同的字符集。
我认为大多数字符串都可以压缩到50个长度,但对于所有可能的53个长度字符串是否也是如此呢?我们知道在最坏情况下,可能集合中会有14个字符未被使用。我们是否能利用这些信息呢?
谢谢阅读。
53^53
。现在,识别和使用这样的信息是另一个问题,但是..它有用吗?如果不是,为什么不是? - user16639067^53
。"14个输入字符未使用"是无关紧要的。这就像说"如果我有一个三位数,那么至少有7个可能的数字未被使用"。好吧,但谁在乎呢?这并不会以某种方式将10^3
组合变成3^3
。 - Joe White3^3
。 - Joe White在最一般的情况下,您所要求的是不可能的,这可以很简单地证明。
假设将任意的53个字符的字符串编码为同一集合中的50个字符是可能的。完成后,在编码后的字符串中添加三个随机字符,那么就有了另一个任意的、53个字符的字符串。如何压缩它呢?
因此,您希望的并不能保证适用于任何可能的数据。但是,您的所有实际数据的熵都足够低,可以设计出一种方案来解决这个问题。
在这种情况下,您可能需要进行一些变体的霍夫曼编码,它基本上为您集合中的字符分配可变位长编码,对于使用最多的字符使用最短的编码。可以分析所有数据以得出一组编码。在霍夫曼编码之后,您的字符串将成为一个(希望更短)的比特流,您可以将其编码为每个字符6位的字符集。它可能足够短,适用于您的所有实际数据。
类似 Smaz(在另一个答案中引用)的库编码也可以使用。同样,无法保证它适用于所有可能的数据。
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
作为一个例子,这三个字符不会节省任何空间,但是您的53个字符将始终保证输出为47个字符。
然而,请注意,如果原始字符集对您很重要,则输出将不会在原始字符集中。
该过程如下:
original-text --> encode --> store output-text (in database?)
retrieve --> decode --> original-text restored
Smaz 是一个适用于压缩非常短字符串的简单压缩库。