有什么办法可靠地压缩短串？

Question

我有一个长度恰好为53个字符的字符串,其中包含一组有限的可能字符.

[A-Za-z0-9\.\-~_+]{53}

我需要将其减少到50而不会丢失信息并使用相同的字符集.

我认为应该可以将大多数字符串压缩到50长度,但所有可能长度为53的字符串是否可能？我们知道在最坏的情况下,可能的集合中的14个字符将被使用.我们可以使用这些信息吗？

谢谢阅读.

Answer 1

如果如你所说的那样,你的输出字符串必须使用与输入字符串相同的字符集,如果你对输入字符串的要求一无所知,那么不可能压缩每一个字符串53 - 字符串最多50个字符.这是鸽子原理的简单应用.

• 您的输入字符串可以表示为基数 67中的53位数字,即0到67 ⁵³ - 1≅6*10 ^96之间的整数.
• 您希望将这些数字映射到0到67之间的整数⁵⁰ - 1≅2*10 ⁹¹.
• 因此,通过鸽子原理,你可以保证67 ³ = 300,763个不同的输入将映射到每个可能的输出 - 这意味着,当你去解压缩时,你无法知道你所假设的300,763个原件中的哪一个映射回来.

要使这项工作,您必须改变您的要求.您可以使用更大的字符集对输出进行编码(如果每个字符有87个可能的值,则可以将其缩小到50个字符,而不是输入中的67个字符).或者你可以识别输入中的冗余 - 也许第一个字符只能是'3'或'5',第十九和第二十个是一个州名缩写,它只能有62种不同的可能值,就是那种东西.

如果你不能做这些事情中的任何一个,你将不得不使用压缩算法,如霍夫曼编码,并接受一些字符串将是可压缩的(并且变得更短)而其他字符串将不会(并且将变得更长)的事实.

Answer 2

您所要求的在最一般的情况下是不可能的，这可以非常简单地证明。

假设可以将任意 53 个字符串编码为同一组中的 50 个字符。这样做，然后将三个随机字符添加到编码字符串中。然后你就有了另一个任意的 53 个字符的字符串。你如何压缩它？

因此，不能保证您想要的内容适用于任何可能的数据。然而，所有真实数据的熵可能都足够低，因此您可以设计出可行的方案。

在这种情况下，您可能需要执行霍夫曼编码的某种变体，它基本上为集合中的字符分配可变位长度编码，对最常用的字符使用最短的编码。您可以分析所有数据以得出一组编码。经过霍夫曼编码后，您的字符串将是一个（希望更短）比特流，您可以将其编码为每个字符 6 位的字符集。对于您的所有真实数据来说，它可能足够短。

像 Smaz（在另一个答案中引用）这样的基于库的编码也可能有效。同样，不可能保证它适用于所有可能的数据。

Answer 3

一个字节(字符)可以编码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