random - 您可以实现的随机二进制数据的最佳文件压缩是什么？

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

这个问题似乎与 help center 中定义的范围内的编程无关。 .

已关闭10 年前。

Improve this question

具体来说，有哪些程序以及哪些程序的压缩率最高？我尝试用谷歌搜索它，但似乎经验会胜过搜索结果，所以我问。

Answer 1

如果文件大小可以精确到位，则对于任何文件大小 N，将精确地存在 2^(N+1)-1 个可能的 N 位或更小的文件。为了将大小为 X 的文件映射到某个较小大小的 Y，必须将某个大小为 Y 或更小的文件映射到大小为 X 或更大的文件。无损压缩发挥作用的唯一方法是，某些可能的文件可以被识别为比其他文件更有可能；在这种情况下，可能的文件将缩小，而不太可能的文件将增大。

举一个简单的例子，假设一个人希望无损地存储一个文件，其中的位是随机且独立的，但不是 50% 的位被设置，而是只有 33% 被设置。可以通过获取每对位来压缩这样的文件，如果两个位都被清除，则写入“0”，如果设置了第一个位而第二个位未设置，则写入“10”，如果设置了第二个位而第一个位未设置，则写入“110” ，或“111”(如果两个位均已设置)。其结果是，每对比特在 44% 的情况下变为一位，在 22% 的情况下变为两位，在 33% 的情况下变为三位。虽然某些数据串会增长，但其他数据串会缩小；如果概率分布符合预期，缩小的文件对数量将超过增长的文件对(4/9 文件将缩小一点，2/9 将保持不变，3/9 将增长，因此文件对将继续存在)平均缩小 1/9 位，文件平均缩小 1/18 [因为 1/9 数字是每对位])。

请注意，如果这些位实际上具有 50% 的分布，则只有 25% 的对将变为一位，25% 将保留两位，50% 将变为三位。因此，25% 的位将缩小，50% 的位将增长，因此平均对将增长 25%，文件将增长 12.5%。盈亏平衡点约为 38.2% 的位被设置(2 减去黄金分割)，这将导致 38.2% 的位对缩小，并以相同的百分比增长。