我正在用 C 语言编写一个压缩算法(主要是为了好玩)，并且我需要能够以二进制形式存储数字列表。该列表的每个元素都将采用两位数字的形式，均小于 10(如 (5,5), (3,6), (9,2) )。我可能会存储数千个这样的对(在我的压缩算法中为字符串中的每个字符生成一对)。
显然，最简单的方法是将每对 (-> 55, 36, 92 ) 连接起来形成一个 2 位数字(因为它们只是一位数字)，然后将每对存储为 7 位数字(因为 99 是最高的)。不幸的是，这不太节省空间(每对 7 位)。
然后我想，如果我连接每一对，然后连接它( 553692 )，我就可以将其存储为二进制形式的普通数字( 10000111001011011100 ，对于三对来说已经较小了而不是单独存储每个数字)，并保留用于二进制数的位数的量词。唯一的问题是，这种方法需要一个 bigint 库，因此可能会很慢。随着数字越来越大(字符串中每个字符 +2 位)，内存使用量和速度减慢也会越来越大。
所以这是我的问题:是否有更好的存储效率的方法来存储像我正在做的数字列表，或者我应该使用 bignum 或 7 位方法？
最佳答案
存储 100 个不同值的信息论最小值为 log<sub>2</sub>100 ，约为 6.644。换句话说，7 位的可能压缩率超过 5%。 ( log<sub>2</sub>100 / 7 为 94.91%。)
如果这些对只是在算法过程中临时存储，那么几乎肯定不值得花费大量精力来节省 5% 的存储空间，即使您设法做到了这一点。
如果这些对构成压缩输出的一部分，那么您的压缩就不可能很好(一个字符只有八位，并且大概这些对是任何压缩字符数据的附加值。)尽管如此，简单的压缩技术是存储到 40 位(5 字节)中的 6 对，假设是 64 位机器，无需使用 bigint 包即可完成。 (或者，以 20 位存储最多 3 对，然后将两个 20 位序列打包为 5 个字节。)这将为值提供 99.66% 的最大压缩率。
以上所有内容都假设 100 个可能的值是均匀分布的。如果分布不均匀并且可以预测频率，则可以使用霍夫曼编码来改进压缩。即便如此，我也不推荐将其用于临时存储。
关于algorithm - 以二进制格式有效存储数字列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27386287/