相关疑难解决方法(0)

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

• 它被设置,或换句话说,一个唯一整数的列表,其中顺序无关紧要
• 集合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编码似乎接近最优解.对于集合中元素的其他其他分布,这可能不同.

我有一个非常普遍的问题,就是为磁盘内的字符串数组创建一个索引.简而言之,我需要将每个字符串的位置存储在磁盘表示中.例如,一个非常天真的解决方案是索引数组,如下所示:

uint64 idx [] = {0,20,500,1024,...,103434};

其中第一个字符串位于第0位,第二个字符串位于第20位,第三个位于第500位,第n个位于第103434位.

这些位置总是按顺序排列为非负64位整数.虽然数字可能会有所不同,但实际上我认为典型的差异在2 ^ 8到2 ^ 20的范围内.我希望这个索引在内存中是mmap的,并且将随机访问这些位置(假设均匀分布).

我正在考虑编写自己的代码来进行某种块增量编码或其他更复杂的编码,但在编码/解码速度和空间之间有很多不同的权衡,我宁愿把工作库作为一个起点甚至可能在没有任何自定义的情况下解决问题.

任何提示？一个c库是理想的,但是c ++也可以让我运行一些初步的基准测试.

如果您还在关注,还有一些细节.这将被用来建立类似于CDB库(http://cr.yp.to/cdb/cdbmake.html顶部的库CMPH()http://cmph.sf.net).简而言之,它适用于基于磁盘的大型只读关联映射,内存中的索引很小.

既然是一个图书馆,我没有在输入控件,但我要优化典型的用例有数亿值的,在几KB平均值尺寸范围在2 ^ 31最大值.

为了记录,如果我没有找到准备使用的库,我打算在64个整数的块中实现delta编码,其中初始字节指定到目前为止的块偏移量.块本身将用树索引,给我O(log(n/64))访问时间.有太多其他选择,我宁愿不讨论它们.我真的很期待使用代码而不是如何实现编码的想法.我很乐意与大家分享我工作后的所作所为.

感谢您的帮助,如果您有任何疑问,请告诉我.

我有大量的整数数组.每个整数都有几千个整数,每个整数通常与之前的整数相同,或者只有一两个或两个不同.我想将每个阵列缩小尽可能小,以减少我的磁盘IO.

Zlib将其缩小到原始尺寸的约25%.这很好,但我不认为它的算法特别适合这个问题.有没有人知道压缩库或简单的算法可能会更好地执行此类信息？

更新:将zlib转换为xor deltas数组后,将其缩小到原始大小的20%左右.

我有一个大文件,每行一个单词.整个文件已排序,我现在需要压缩它.我可以简单地使用GZIP,结果会非常好.但是我想知道我们是否有可能做得更好,知道我们正在处理已排序的单词列表.

这是我的排序单词列表的片段:

[...]
ABAISSAT
ABAISSATES
ABAISSE
ABAISSEE
ABAISSEES
ABAISSEMENT
ABAISSEMENTS
ABAISSENT
ABAISSER
ABAISSERA
ABAISSERAI
ABAISSERAIENT
ABAISSERAIS
[...]

使用前缀压缩文件会产生比GZIP更好的结果吗？

[...]
ABAISS AT ATES E EE EES EMENT EMENTS ENT ER ERA ERAI ERAIENT ERAIS
[...]

什么是允许我使用我描述的那种压缩来压缩我的单词列表的算法？还有其他想法我如何压缩数据？

PS我虽然使用Trie并且我实现了它.Trie的最终大小是内存几乎与列表本身一样大,加载列表的时间非常长.由于这些原因,我决定不去那条路.