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

Question

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

7

我正在尝试通过铱星网络传输字符串，但发送数据的成本非常高。我想知道是否有一种方法可以压缩大字符串，例如：


{"packet":01,"reporting time":1500, "altitude":6500,"latitude":0,"longitude": 0,"ballast":34,"parachute":0}

将其压缩为一个更小的字符串，如： f5fk43d2。该过程必须是可逆的，以便在另一端解码并读取数据。如果可能的话，该如何实现？

我尝试了j.w.r提供的答案：Shortening a string in Java，但它似乎是不可逆的。它确实将大字符串转换为较小的字符串。

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

任何帮助都将不胜感激！

- Adam Frank

1

你可以查看一种常见的压缩方案，比如Deflate（用于.zip文件），Java标准库中有其实现（Deflater）。 - MTCoster

1

你考虑过使用类似 MessagePack 这样的东西吗？或者只是通过 zip 压缩文本并将其转换为 base64 来简单压缩它？ - MadProgrammer

1

CBOR 可能是一个选项。如果您不想发送二进制数据，可以使用 base64 进行编码。 - Robby Cornelissen

如果您在引号中的部分具有有限数量的可能值，并且还知道每个冒号后面的部分是某个范围内的数字，则可以利用这一点将其表达为较短的字符串。 - Dawood ibn Kareem

我所做的是将字符串转换为zip流，然后将字节再转换回base64字符串。然后可以将其转换回字节，解压缩，从而得到您的字符串。不过我是用C#完成的，没有Java代码。我还添加了一个参数“最大长度”，以便在超出所需字符串长度时抛出异常。 - Dan Rayson

3个回答

5

首先，希望清楚地指出，不存在任何无损压缩算法可以将长度为n的任意字符串始终压缩成唯一的较短字符串。这是数学事实。

尽管如此，现有一些流行的算法表现得相当不错：

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

Lempel-Ziv：我从未亲自实现过这个算法，但它是许多我们今天所知道的常见文件格式的基础，例如GIF。现在应该有相关库可供使用。

- chang_trenton

1

首先，希望清楚地表明，不存在任何无损压缩算法可以将任意长度为n的字符串始终压缩为唯一、更短的字符串。这是数学事实。但是，有大量的无损压缩方法。它们只是在可以删除的字符数量上稍微不那么有效。 - Jai

3

当然，这是数学事实。压缩算法依赖于某些字符串比其他字符串更常见的特定情况。它们使“常见”字符串变短，但使不太常见的字符串变长。绝对没有可逆算法能够使每个可能的字符串都变短。如果有这样的算法，你可以一遍又一遍地应用它，直到字符串变成单个位，然后神奇地将0或1转换为莎士比亚全集。 - Dawood ibn Kareem

1

@Jai 是的，但是没有“完美”的无损压缩方法。为了看清这一点，我们可以取一个长度为n的比特串。有2^n个可能的字符串。有2^(n-1) + 2^(n-2) + ... + 2^0个比那短的字符串。这总共是2^n - 1个字符串，因此根据鸽笼原理，要么两个字符串具有相同的压缩形式（这就像哈希冲突的想法一样），要么某些压缩形式比原始形式更长，在Huffman编码中存储映射时，如果您的原始字符串很短且由许多唯一字符组成，则这种情况很容易发生。 - chang_trenton

0

让我们以您的示例作为对“小得多”的描述。您将107个字符（856位）压缩成八个字母数字字符，这些字符似乎仅限于每个字符36种可能性。我会慷慨地假设大写字母也被允许，并且可能有两个标点符号来增加趣味性，将其提高到64个可能的字符。因此，每个字符的六位二进制数乘以八个字符，即48位。这是18倍的压缩比。不，你不会无损地获得它，至少不会在数据中没有大量冗余的情况下。我再次慷慨地假设要压缩的消息仅限于96个可能的ASCII字符（例如，删除127并包括换行符）。然后，该消息为705位，需要近15倍的压缩才能达到48位。仍然不可能。

无损压缩来自统计偏差和冗余。统计偏差是一些符号比其他符号更普遍，而冗余是数据中重复的模式，例如您的示例中的“itude”和“500”的重复子字符串。要获得良好的压缩效果，您需要利用这些东西，并且需要大量数据才能利用它们。像您的示例这样的短字符串几乎不会压缩或者在孤立状态下通常无法压缩。

你可以尝试在另一端维护一个压缩上下文和相关的解压上下文，通过这个上下文以明确定义的顺序发送一系列消息。也就是说，它们需要按照压缩的顺序进行解压缩。然后，您将能够利用多个消息中的冗余和偏差，并可能获得一些不错的压缩效果。如果那些相同的JSON属性不断出现，更好的是，如果它们经常具有相同的值，则可以获得显着的压缩效果。

例如，zlib的刷新操作将允许按顺序发送到目前为止压缩的数据，以避免压缩器在构建块时引入的延迟。如果可能的话，您会希望避免刷新，因为它们会降低压缩率。因此，在发送最后一个消息之前，您可以设置一个时间限制，等待另一条消息传输的时间不超过该限制，然后再进行刷新。

- Mark Adler

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sal · Accepted Answer

考虑将一个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次方个可能的2个字符的字符串（3800）。那么，我们会比2个字符的字符串多234,000个3个字符的字符串。

现在，想象一下我们尝试使用一些函数f（S），将每个3个字符的字符串都变成2个字符的字符串。然后，当我们尝试将一个2个字符的字符串转换回一个3个字符的字符串时，我们自然会遇到问题，因为这意味着f（S）必须将一些3个字符的字符串转换为相同的字符串（所以我们无法知道要映射回哪个！）。这是因为2个字符的字符串的定义域小于3个字符的字符串的定义域（并且发生了这种情况，因为f（S）不能是单射，这意味着没有有效的反函数）。

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

您可能会限制一些字符不在较大字符串的定义域内，但正如您所述的问题一样，这是不可能的。

编辑，因为我觉得我应该提一下：有算法用于将较少字符的字符串压缩为更多字符的较小字符串。话虽如此，我建议您看看这个：An efficient compression algorithm for short text strings