有可靠的方法可以压缩短字符串吗？

Question

我有一个字符串，长度为53个字符，其中包含一组有限的可能字符。

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

我需要将此内容压缩到50个字符，同时不损失任何信息并使用相同的字符集。 我认为大多数字符串都可以压缩到50个长度，但对于所有可能的53个长度字符串是否也是如此呢？我们知道在最坏情况下，可能集合中会有14个字符未被使用。我们是否能利用这些信息呢？ 谢谢阅读。

- diolemo

---

我们知道，在最坏的情况下，可能集合中会有14个字符未被使用。你能详细说明一下吗？ - John Kugelman

我认为这里需要的是 编码，而不是压缩。 - user166390

@JohnKugelman 一个长度为53的字符串，每个字符都不同。共有67个可能的字符（52个字母，10个数字，5个符号）。67-53 = 14未被使用。 - diolemo

Answer 1

如果您所述的输出字符串必须使用与输入字符串相同的字符集，并且如果您对输入字符串的要求没有任何特殊了解，则不可能将每个可能的53个字符的字符串压缩到50个字符。这是鸽笼原理的一个简单应用。

• 您的输入字符串可以表示为基数67进制的53位数字，即从0到67⁵³-1≅6*10⁹⁶的整数。
• 您希望将这些数字映射到从0到67⁵⁰-1≅2*10⁹¹的整数。
• 因此，根据鸽笼原理，您保证会有67³=300,763个不同的输入将映射到每个可能的输出--这意味着，当您进行解压缩时，您无法知道应该将哪个原始数据映射回去。

为了使其工作，您需要更改您的要求。您可以使用更大的字符集来编码输出（如果每个字符具有87个可能值而不是输入中的67个，则可以将其减少到50个字符）。或者您可以在输入中识别冗余性 - 也许第一个字符只能是“3”或“5”，第19和20个字符是只能有62种不同可能值的州缩写等等。 如果您无法执行上述任何操作，则必须使用压缩算法（如Huffman编码），并接受某些字符串可压缩（变短），而其他字符串则不可压缩（变长）的事实。

- Joe White

---

我喜欢这个方向（+1），但这并没有直接回答问题的一部分：如果14个未使用的字符被识别出来，那么输入空间只有53^53。现在，识别和使用这样的信息是另一个问题，但是..它有用吗？如果不是，为什么不是？ - user166390

不，输入空间仍然是67^53。"14个输入字符未使用"是无关紧要的。这就像说"如果我有一个三位数，那么至少有7个可能的数字未被使用"。好吧，但谁在乎呢？这并不会以某种方式将10^3组合变成3^3。 - Joe White

如果已经确定了未使用的字符（已知），比如因为我在别人编码时从肩膀上看到了，只有第一行（1、2、3）被使用了...这会改变问题吗？ - user166390

@pst，完全正确。这不是关于“可能集合中有14个字符未使用”的部分，但如果您确实知道3位数仅由三个可能的数字组成，则它变成了一个基于3的3位数，而不是基于10的，那么它将是3^3。 - Joe White

Answer 2

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

假设将任意的53个字符的字符串编码为同一集合中的50个字符是可能的。完成后，在编码后的字符串中添加三个随机字符，那么就有了另一个任意的、53个字符的字符串。如何压缩它呢？

因此，您希望的并不能保证适用于任何可能的数据。但是，您的所有实际数据的熵都足够低，可以设计出一种方案来解决这个问题。

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

类似 Smaz（在另一个答案中引用）的库编码也可以使用。同样，无法保证它适用于所有可能的数据。

- antlersoft

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

作为一个例子，这三个字符不会节省任何空间，但是您的53个字符将始终保证输出为47个字符。 然而，请注意，如果原始字符集对您很重要，则输出将不会在原始字符集中。 该过程如下：

original-text --> encode --> store output-text (in database?)
retrieve --> decode --> original-text restored

- Stephen P

---

@wared - 我的意思是，如果你看一下我的编码方法的输出，它看起来与输入完全不同 - "abc" 可能会变成 "•=" - 因为我将每个位都向左移动了。它确实是无损的，因此解码始终会得到正确的原始字符串。但在输入字符数不超过7个时，它并不会节省任何空间。 - Stephen P

@wared 是的，可以无损地获取原始字符串。编码需要占用8位，丢弃高位，左移并附加下一个重新编码的8位；解码时，您需要从流中取出前7位，右移并填充0，再加上第一个序列的低位，即可得到原始的8位。由于实际上是读取字节流，因此您需要保存低位以用作下一个序列的第一位。请注意，所有这些都仅适用于原始输入（问题）保证高位始终为零的情况。 - Stephen P

Answer 4

如果我没记错的话，哈夫曼编码应该是存储数据最紧凑的方式。虽然我已经很久没有用它来快速写出算法了，但是这里介绍了大致的思路，如果我没记错的话具体步骤如下：

1. 获取每个字符使用的次数
2. 按照使用频率对它们进行排序
3. 根据优先级构建树
4. 通过遍历树（从根节点开始，左边为0，右边为1）获取每个字符的压缩位表示
5. 用树中的位替换每个字符

- zbrunson

---

我认为在每个字符都不同的情况下，这种方法可能行不通。据我所知，第一个字符的出现需要按照正常方式进行编码，然后将其添加到内部树结构中。 - diolemo

这是正确的，你确实需要一个前导表示来说明编码转换的内容，因此它可能无法在你正在使用的字符串长度较短的情况下工作。 - zbrunson

请查看此问题的链接：https://dev59.com/wnM_5IYBdhLWcg3w-4nw。 - zbrunson

Answer 5

Smaz 是一个适用于压缩非常短字符串的简单压缩库。

- Rahul Tripathi

---

你能确定在再次使用字符集对结果进行编码后，这将针对来自该字符集的每个可能长度为53的字符串压缩3个字符吗？ - diolemo

从示例来看，这个输入可能不起作用，因为smaz只能很好地压缩自然语言，因为它使用字典而不是通用算法。 - Christoph

Smaz 对我来说也很有前途，我想在 Java 项目中使用 JSmaz。不幸的是，目前只支持 ASCII 输入。 - dajood