我在C中编写了一个压缩算法（主要是为了好玩），我需要能够以二进制形式存储数字列表 . 此列表的每个元素都将以两位数的形式出现，均低于10（如 (5,5), (3,6), (9,2) ） . 我可能会存储数千个这样的对（在我的压缩算法中，每个字符串中都有一对） .
显然，最简单的方法是连接每一对（ - > 55, 36, 92 ）以产生一个2位数字（因为它们're just one digit each), then store each pair as a 7-bit number (since 99 is the highest). Unfortunately, this isn' t这样节省空间（每对7位） .
然后我想也许如果我连接每一对，然后连接（ 553692 ），我就能够将其存储为二进制形式的普通数字（ 10000111001011011100 ，其中三对已经小于分别存储每个数字），并保留用于二进制数的位数的量词 . 唯一的问题是，这种方法需要一个bigint库，因此可能会很慢 . 随着数字变得越来越大（字符串中每个字符2个数字），内存使用和减速也会变得越来越大 .
所以这是我的问题：是否有更好的存储效率方式来存储我正在做的数字列表，或者我应该采用bignum还是7位方法？
1 回答
存储100个不同值的信息理论最小值是
log2100，约为6.644 . 换句话说，7位的可能压缩是头发超过5％ . （log2100 / 7是94.91％ . ）如果这些对在算法期间仅用于临时存储，那么即使你设法做到这一点，几乎肯定不值得花费大量精力来节省5％的存储空间 .
如果这些对形成了压缩输出的一部分，那么你的压缩就不会很大（一个字符只有八位，并且可能这些对是任何压缩字符数据的附加 . ）尽管如此，简单压缩技术最多可以存储6对在40位（5字节）中，可以在没有bigint包的情况下完成，假设是64位机器 . （或者，最多可存储3对20位，然后将两个20位序列打包成5个字节 . ）这样可以获得99.66％的最大压缩值 .
所有上述假设100个可能值均匀分布 . 如果分布不均匀且可以预测频率，则可以使用霍夫曼编码来改善压缩 . 即便如此，我也不建议将它用于临时存储 .