小编doc*_*doc的帖子

我有一组整数,我希望有一个最紧凑的表示.我有以下约束/功能:

• 它被设置,或换句话说,一个唯一整数的列表,其中顺序无关紧要
• 集合L的大小相对较小(通常为1000个元素)
• 整数遵循0和N-1之间的均匀分布,N相对较大(比如2 ^ 32)
• 对压缩集的元素的访问是随机的,但如果解压缩过程不那么快就可以了
• 显然,压缩应该是无损的

我尝试了一些事情,但我对结果不满意,并且我确信存在更好的解决方案:

• delta编码(排序,然后编码差异),或者也排序,然后编码第i个元素和i*N/L之间的差异.两者都给出了合理的结果,但不是很好,可能是因为N和L的典型大小.编码增量的霍夫曼没有帮助,因为它们通常很大.
• 递归范围缩减(http://ygdes.com/ddj-3r/ddj-3r_compact.html).这看起来很聪明,但在指数减少的整数上效果最好,这绝对不是这里的情况.
• 关于stackoverflow的一些讨论类似但不完全等同于我的问题(C库用于压缩顺序正整数,压缩排序整数)

我很高兴听到你可能有任何想法.提前致谢!

更新:

事实证明,delta编码似乎接近最优解.对于集合中元素的其他其他分布,这可能不同.