algorithm - 将整数数组编码为短字符串

Question

问题:

我想压缩一个非固定长度的非负整数数组(但它应该是 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,5,2,0,0,0,0,0,0,0,1,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,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 个零，1，3 个零，1，0 个零，1(这将添加到前一个，因此有一个 2)，1 个零，1 ".

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

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

Answer 1

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

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

您可能还想了解如何 JPEG -style 编码有效。经过DCT和量化后，JPEG熵编码问题看起来和你的差不多。

最后，如果您想获得最大压缩，您可能需要查找 arithmetic encoding ，它可以将您的数据任意压缩到接近统计最小熵。

---

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

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

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