c++ - 高度压缩数字网格

Question

我有一个包含数字的方形网格，我需要对其进行大量压缩，以便可以轻松地通过网络传输。例如，我需要能够将 40x40 的网格压缩为小于 512 字节，而不管网格中数字的值如何。这是我的基本要求。

每个网格的单元格都包含一个从 0 到 7 的数字，因此每个单元格可以容纳 3 位。

有谁知道可以实现我想要的好的算法？

Answer 1

您可以对信息进行不同的编码。您不需要为所有数字 0 到 7 分配具有相同位数的代码。您可以根据序列中的次数进行分配。

首先阅读整个序列，计算每个数字的出现次数。基于此，您可以将代码分配给每个号码。如果您分配以下代码，例如霍夫曼代码，代码将是前缀代码，这意味着没有额外的字符来分隔数字。

您可以根据测试结果在算法上引入某些变体，以微调压缩比。

我在一个项目（大学）中使用了这种技术，总的来说，它提供了很好的结果。至少它应该近似于每个字符的理论 3 位，如果概率分布有帮助，它会更好。

Answer 2

正如其他人所说，所陈述的问题是不可能的，因为需要 600 个字节来表示所有可能的网格。600 字节来自 40 行、40 列、每单元 3 位和每字节 8 位 ( 40 * 40 * 3 / 8)。正如 Kerrek SB 在评论中解释的那样，您将 8 个单元打包成 3 个字节。

在您自己的评论中，您提到这是通过网络传输的游戏状态。假设您有一种机制来确保数据的可靠传输，那么如果在更新之间可以更改的单元格数量有合理的限制，或者如果允许您在一定数量的单元格更改时发送更新，您可以实现 512 字节的表示。如果您使用 1 位来表示单元格是否已更改，则需要 200 个字节。然后，您有 312 个剩余字节来表示已更改单元格的新值。因此，您最多可以表示已312*8/3 = 832修改的单元格。

顺便说一句，这种表示可以在不到 600 字节的时间内表示多达 1064 个更改的单元。

Answer 3

您要做的是对数据执行“burrowes-wheeler”转换，然后对其进行压缩。在这种情况下，运行长度编码就足够了。

http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

在您的情况下，这可能会胜过霍夫曼。

确实在某些情况下您需要超过 512 个字节。因此，在您的协议中，只需对“反常”网格进行例外处理。但在一般情况下，您应该轻松低于 512。