我在c中有二进制数组，我想压缩数组，请建议我压缩二进制数组的算法。我使用了 Lempel-Ziv-Welch (LZW) 算法，但它不适合我，因为我的数据中没有重复。
问问题
3963 次
6 回答
1
您可能没有重复，但数据中仍然可能存在可以利用的模式。但是，这需要对数据有更多的了解，而不是没有重复。
如果您的数据实际上（或几乎）随机分布，那么压缩它将会遇到 Pidgin Hole 问题。这表明如果您只有 X 个洋泾浜和 Y 个孔可以放入它们，并且 X > Y，那么您就没有足够的空间。在压缩中，这意味着您无法利用不存储一些 pidgin 的能力，这些 pidgin 是一个已经在一个洞中的同卵双胞胎，而只需给解压缩算法留下注释以克隆该 pidgin。在霍夫曼编码中，所有的洋泾浜都是洋泾浜库中洋泾浜的克隆。在其他几种压缩方案中，一些 pidgins 可能是由其他 pidgins 组成的巨型 pidgins。
于 2010-08-22T17:21:02.653 回答
1
您可以轻松地将空间减半！
由于您的二进制数据没有重复，因此您唯一的选择是 [0, 1], [1, 0]。任何更多都会重复零或一。因此，您可以只用 0 表示第一组，用 1 表示第二组。编码看起来像这样......
encode [0, 1] = 0
encode [1, 0] = 1
解码将是......
decode 0 = [0, 1]
decode 1 = [1, 0]
抱歉，haskell 语法在这种情况下更具可读性。这会将您的二元素数组变成一个元素数组，并且可以存储在一半的空间中！魔法。
编辑：这忽略了 [0] 和 [1] 的琐碎情况。如果需要处理这些（尽管您实际上不应该压缩 1 位），则不可能获得比 100% 更好的压缩率。
于 2010-08-23T03:35:55.247 回答
0
如果您有二进制数据，您很可能会将它们视为char[]. char在您的问题和评论中，您声明（几乎）没有重复，这只有在您的数据项不超过 256 个（ ）时才有可能。
但我猜你有更多的数据，所以压缩是可能的。如果您的数据项的频率分布不均匀，您可能会通过简单的Huffman 编码获得一些运气。
为了给您更准确的建议，我们需要有关您要压缩的数据类型的更多详细信息。
于 2010-08-22T13:40:34.143 回答
0
压缩不是魔术。如果您的数据是完全随机的，则没有可用的压缩算法可以使其更小。
大多数数据都不是完全随机的，但您可以自行发现表达数据的最佳方式，以便检测到模式。图像和声音很常见，以至于已经开发了标准算法，但是如果不了解更多细节，就无法对您的具体问题进行更多说明。
于 2010-08-23T18:22:11.640 回答
0
或者：您的二进制数据代表某些值。您可以减少所有值的位数。您需要知道可能的范围并按位写入和读取数据。例如，如果您将值存储在只需要几位的 uint32 中，这可能会节省大量空间。
于 2010-08-23T09:05:28.753 回答