2^k 个均匀分布的 m位整型数据集合，如何压缩达到最大的压缩率？

Mon Nov 06 2023 · json · rss

Subscribe:

About

对于任何压缩问题我们都需要计算一下信息熵。

对于2^32个64位的整型数据集合（无序），那么

$H=\frac{2^{64*2^{32}}}{2^{32}!}$

那么它的压缩率可以通过取对数和stirling公式进行估算

(log(2^32*2*3.1415926,2)+2^32*log((2^32)/2.718,2))/(64*2^32)

使用sagemath运算可以得到结果是47.7%左右。

而我认为压缩方法上面，一阶差分方法的效果可能还不够好，二阶差分法就应该接近极限了。

因为我们知道两个数字间隔平均在2^32的间隔，那么我们应当取差分值与2^32的偏差值(像APPLE的图片一样处理)，那么就可以再节约一些，从而达到最优化。