2

问题：

我想压缩一个非固定长度的非负整数数组（但它应该是 300 到 400），主要包含 0、一些 1、一些 2。虽然不太可能，但也有可能拥有更大的数字。

例如，这是一个包含 360 个元素的数组：

0,0,0, 1 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1 , 0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 1 ,0,0,0,0,0,0, 2 ,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0, 1,1 ,0,0,0,0,0,0, 0,0, 4 ,0,0, 0,0,0,0, 3 ,0,0,0,0,0,0,0,0,0, 1 ,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0, 2 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0, 1 ,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0, 1 ,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0, 1 ,0,0,0,0,0,0,0, 1 ,0,0,0,0,0,0,0, 1 5,2 ,0,0,0, 0,0,0,0, ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 1,2,1 ,0,0,0,0,0,0, 0,0, 1 ,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0。

目标：

目标是将这样的数组压缩成使用字母和数字的最短编码。理想情况下，类似于：sd58x7y

我试过的：

我尝试使用“增量编码”，并使用零表示任何高于 1 的值。例如：{0,0,1,0,0,0, 2 ,0,1} 将表示为：2,3 , 0 ,1。要解码它，一个人将从左到右读取，并写下“2 个零，一个，3 个零，一个，0 个零，一个（这将添加到前一个，因此有一个 2），1 个零，一个”。

为了消除分隔符（逗号）的需要，从而节省更多空间，我尝试仅使用一个字母数字字符来表示 0 到 35 的增量值（使用 0 到 y），同时将字母 z 保留为“35 PLUS the next character” . 我认为这被称为“变量位”或类似的东西。例如，如果一行中有 40 个零，我会将其编码为“z5”。

据我所知……结果字符串仍然很长（在上面的示例中大约有 20 个字符）。理想情况下，我想要8个字符甚至更短的东西。谢谢你的时间; 任何帮助或灵感将不胜感激！

4

2 回答 2

2

在您的数据中，您有：

14 1s (3.89% of data)
4 2s (1.11%)
1 3s, 4s and 5s (0.28%)
339 0s (94.17%)

假设您的数字不是相互独立的并且您没有任何其他信息，那么您的数据的总熵为每个数字 0.407 位，即总共 146.4212 位（18.3 字节）。所以不可能用 8 个字节编码。

于 2013-11-06T20:02:47.330 回答
2

由于您的示例包含长时间运行的零，因此您的第一步（看起来您已经采取了）可能是使用run-lenth 编码(RLE) 来压缩它们。此步骤的输出将是一个整数列表，从零的运行长度计数开始，然后在该值和非零值之间交替。（零游程长度0将指示连续的非零值......）

其次，您可以使用一类称为通用代码的方法将整数编码为少量位。这些方法通常使用比大整数更少的位数来压缩小整数，并且还提供了对任何大小的整数进行编码的能力（这非常漂亮......）。您可以根据您期望的确切分布调整编码以改进压缩。

您可能还想了解JPEG样式编码的工作原理。在 DCT 和量化之后，JPEG 熵编码问题似乎与您的相似。

最后，如果您想进行最大压缩，您可能需要查找算术编码，它可以将您的数据任意压缩到接近统计最小熵。

上面的链接解释了如何压缩成原始比特流。为了将它们转换为一串字母和数字，您需要添加另一个编码步骤，将原始位转换为这样的字符串。正如一位评论者指出的那样，您可能需要研究base64表示；或者（对于任何可用字母表的最大效率）您可以尝试“反向”使用算术压缩。

一般压缩的附加说明：“最短可能编码”很大程度上取决于数据源的确切属性。实际上，任何给定的压缩技术都描述了它压缩得最好的数据类型的统计模型。

此外，一旦您根据您期望的数据类型设置了编码，如果您尝试在与您期望的类型不同的数据上使用它，结果可能是扩展，而不是压缩。您可以通过提供一种替代的未压缩格式来限制这种扩展，以便在这种情况下使用......

于 2013-11-06T20:06:36.567 回答