高效的数据压缩方法，可将40,000字节压缩

Question

我在互联网上看到了一些数据压缩库，例如zlib和lzo。但我不确定最好的方法是什么，以将40,000字节（它们在一个byte[][](x,y = color)）压缩到类似于200字节的大小，但有一个限制：这不能花费太长时间，最多可能需要1/40秒。

我不确定这是否可能，以及应该采取哪种最佳选项。我还需要输出为byte[]，这意味着我需要失去数组的第二个维度，并且能够在解压缩发生时再次获得它。（我不想将任何数据保存到文件中，因为我将要将其发送到客户端，当我发送数据时，我只需要给它一个byte[]，它就会完成所有剩余的工作。（我无法更改向客户端发送数据的方法。）感谢任何帮助。

编辑：我不介意失去数据，只要每次发送的数据不是相同的数据，因为每隔1/4秒都会发送新信息的更新，我不发送图像，所以你所说的png并没有真正帮助，因为我正在服务器程序中编写颜色（而不是从文件中读取）。希望这可以帮到你。

- user1691444

---

40K->200?? 如果图像比“吃豆人”更复杂，你可能会有麻烦。 - Martin James

有两件事需要澄清：a）您对失去一些准确性的程度有多在意？b）您了解数据分布/模式的情况吗？ - mikera

如果这个要求是某个招标/合同的一部分，除非他们期望马丁提到的吃豆人图像，否则现在就退出。 - PeterJ

我已经编辑了问题，并提供了更多信息，例如它不是一个正在被读取的文件。 - user1691444

你有一个二维颜色数组，但它不是一张图片？那它是什么？ - John Dvorak

可实现的压缩率严重依赖于数据的结构。通过一般性方法，您很可能无法满足特定要求。但是，如果可以对数据的结构（例如内在逻辑）进行假设，则可能使用自定义压缩算法解决您的问题。同时，考虑仅在客户端存在先前版本数据的情况下发送数据更新的方案。 - R.Moeller

Answer 1

基本上，没有一种通用的压缩方案可以在无损的情况下显著地压缩任意数据输入。你可以接受可能会得到比开始时更多的数据，或者数据丢失...这是你的选择。通常情况下，试图将数据减少到原始数据的1/20是一个相当高的要求。

考虑到这是图像数据，你可能不应该使用通用的压缩程序，而是应该查看图像格式，例如JPEG、PNG等。除此之外，一些图像格式具有“质量”选项，允许您以牺牲保真度为代价实现更大的压缩。但是，200字节确实不是很多信息...

我建议先专注于获得可行的结果（足够小，但质量足够好），然后再专注于性能方面。当你得到任何结果时，你可以看看它是否足够快，但是如果它不能满足你的最初要求，那么努力使其快速是没有意义的。

如果你使用基于图像的压缩，1D/2D方面很可能会被舍弃。如果你选择某种自定义方案，存储一维长度并推断另一维就很容易了。这基本上是你要求中最不麻烦的部分 :)

- Jon Skeet

---

@mikera：如果你限制了有效输入的集合，那么你实际上并没有那么多字节的信息。如果你不限制有效输入的集合，那么很明显你不能总是压缩...你会有比潜在输出更多的潜在输入。 - Jon Skeet

@PeterLawrey：确实。但从信息论的角度来看... :) - Jon Skeet

@PeterLawrey：但在这种情况下，它又回到了“并非所有输入都有效”的问题——您基本上将输入集限制为少于40,000 * 8个独立位。 - Jon Skeet

我已经编辑了问题，并提供了更多信息，例如它不是一个正在被读取的文件。 - user1691444

但是你仍然可以将其视为图像，然后使用PNG压缩进行压缩。设置将在压缩时设置 - 而不是读取图像。再次强调，我的回答中没有要求您从文件中读取。 - Jon Skeet

Answer 2

你不能总是将40000字节压缩到200字节而不丢失数据。然而，如果你的数据是一张颜色较少的计算机生成图像，那么产生200字节或更少的可能性并不太小：

1）将数据提供给PNG压缩库。

最好的压缩需要一些时间，但是通过稍微牺牲压缩级别，你可以节省很多时间。如果你的库是OptiPNG，那么2或3级可能是速度和压缩之间的良好平衡。

2）由于你知道图像大小，所以删除头部和所有其他可以在接收端恢复的块。你应该只剩下IDAT块。即使如此，你也可以将其前面的几个位（块头）去掉。

解压缩时：

1）在数据前加上IHDR块（预先已知），如果使用调色板，则还需加上PLTE块（同样预先已知），以及IDAT块的头部。在末尾添加IEND块。

2）将这些数据提供给PNG解压缩库。

.png 文件格式有很好的文档记录。您可以使用 wikipedia 作为起点。

- John Dvorak

---

我已经编辑了问题，并提供了更多信息，例如它不是一个正在被读取的文件。 - user1691444

@user1691444 我从未声称它是一个文件。我只是假设它是一个易于压缩的颜色二维数组（即图像）。 - John Dvorak

Answer 3

为了检查你所尝试的是否在理论上是可能的，可以取一个或多个输入图像样本，并计算该数据的熵（或"香农熵"）。这将至少给出有多少信息（熵）实际上存在于你的数据中的估计。

如果一个输入图像中的熵计算结果超过200*8位，那么可能没有通用的无损压缩方案可以对单个图像进行所需的压缩。

然而，如果你有一系列图像，你可能只需要编码从一个图像到另一个图像的差异，并平均达到你的目标带宽；例如常见的视频编解码器。

也许还应该阅读一下"源编码"。

- JimmyB

---

没有熵计算可以对可压缩性设置良好的限制。您只需要尝试不同的现有压缩器，或编写自己的压缩器以利用现有压缩器未利用的冗余。例如，考虑一个随机序列，重复1250次以给出40000个字节。简单的熵计算（-p log p的总和）将给出25000个字节。比200个字节多得多。但是任何体面的压缩器都会将其减少到不到200个字节。 - Mark Adler

确保计算熵的准确结果，使用正确的“字长”至关重要。例如，在处理long数据时，基于数据的单个“byte”计算熵通常会产生过高的熵值。如果在您的示例中假设字长为32字节，则计算出的熵值将是正确的。 - JimmyB

我举了一个非常简单的例子。我可以构造另一个例子，它会击败这样的计算，但仍然可以使用任何现代无损压缩器压缩到少于200字节。关键是不可能提出一个熵计算来设置有用的限制，因为这样的计算不能表示数据的所有可能模型。请参阅您自己对源编码的评论，并查找Kolmogorov复杂性，这是不可计算的。 - Mark Adler