有没有一种方法可以将一个字符串压缩为一个可逆的更小的字符串？

Question

我正在尝试通过铱星网络传输字符串，并且发送数据的成本相当大。我想知道是否有办法压缩大字符串，例如： {"packet":01,"reporting time":1500, "altitude":6500,"latitude":0,"longitude": 0,"ballast":34,"parachute":0}

成一个更小的字符串，例如： f5fk43d2 . 该过程必须是可逆的，以便数据可以在另一端被解码和读取。这可能吗？如果可以，我将如何去做。

我已经尝试过 jwr: Shortening a string in Java的答案，但它似乎是不可逆的。它确实将大字符串转换为较小的字符串。

该过程产生的字符串必须小于原始字符串。

任何帮助表示赞赏！

Answer 1

首先，希望大家清楚，不存在任何无损压缩算法可以采用长度为 n 的任意字符串，并始终将其压缩为唯一的、较短的字符串。这是数学事实。

话虽这么说，有一些流行的算法效果很好：

霍夫曼编码：对初学者相当友好，并且可以自己实现。基本思想是将更常见的字符映射到较短的二进制字符串，将不太常见的字符映射到较长的二进制字符串，然后将其与告诉您如何解码结果位字符串的映射一起打包。缺点是需要额外的空间来存储解码指令

Lempel-Ziv：我自己从未实现过这个，但它是我们今天所知的许多常见文件格式的基础，比如 GIF。应该有相关的库。

Answer 2

考虑尝试将某些 X 字符串转换为 Y 字符串的数学原理，使得 X > Y（即您试图缩短字符串的长度）。

然后，假设该字符串是字母数字；这给了我们 26 个可能的小写字母、26 个可能的大写字母和 10 个可能的数字（即 62 种可能性）。这意味着对于 X 字符串，我们将有 62^X 个可能的字符串，对于 Y 字符串，我们将有 62^Y 个可能的字符串。

现在，考虑一下我们是否尝试将所有 X 字符串映射到 Y 字符串。让我们让函数 f(S) 将字符串 S（X 字符串）映射到 Y 字符串。然后，因为 X > Y，我们必须将一些 X 字符串映射到一些相同的 Y 字符串。考虑以下简单示例：

X = 3. Y = 2。那么，我们有 62^3 个可能的 3 字符字符串 (238,000) 和 62^2 (3800) 个可能的 Y 字符字符串。那么，3 字符字符串比 2 字符字符串多 234,000 个。

现在，假设我们尝试使用某个函数 f(S)，尝试将每个 3 字符字符串转换为 2 字符字符串。然后，当我们尝试将 2 个字符的字符串转换回 3 个字符的字符串时，我们自然会遇到问题，因为这意味着 f(S) 必须将一些 3 个字符的字符串转换为同一个字符串（因此我们无法不知道要映射回哪一个！）。这是因为 2 字符字符串的域小于 3 字符字符串的域（出现这种情况是因为 f(S) 不能是单射的，这意味着没有有效的逆）。

因此，没有足够的 2 字符字符串可能映射回每个 3 字符字符串，并且您会发现这可以推广到所有 X > Y。

您可以限制较大字符串域中的某些字符，尽管正如您所陈述的问题一样，这是不可能的。

编辑，因为我觉得我应该提到这一点：有一些算法用于将较少字符的字符串压缩为更多字符的较小字符串。话虽这么说，我建议看看这个： A effective Compression Algorithm for Short Text Strings