Sig*_*erm 10 c++ compression algorithm data-compression
我想制作"压缩数组"/"压缩矢量"类(详见下文),它允许随机数据访问具有或多或少的恒定时间.
"或多或少的恒定时间"意味着虽然元素访问时间不是恒定的,但是当我接近数组的某个点时它不应该继续增加.即容器不应该做更多的计算(比如"再次解压缩所有内容以获取最后一个元素",并且"几乎不做任何事情来获得第一个")来获得一个元素.可以通过将数组拆分为压缩数据块来实现.即访问一个元素应该采用"averageTime"+ - 一些偏差.我可以说我希望最佳访问时间和最坏情况访问时间相对接近平均访问时间.
我有哪些选择(合适的算法/已有的容器 - 如果有的话)？
货柜详情:
用法示例:
对数据进行二进制搜索.
数据详情:
1.数据结构主要由浮点数和几个整数组成.浮点数多于整数.没有字符串.
2.阵列中不太可能存在许多相同的元素,因此无法简单地索引数据.
3.一个元素的大小小于100个字节.
4.每个容器的总数据大小介于几千字节和几兆字节之间.
5.数据不稀疏 - 它是连续的元素块,所有元素都被分配,没有"空槽".
压缩的目标是减少与未压缩表示形式相比较的块所占用的ram量,同时保持一定程度上合理的读取访问性能,并允许随机访问元素作为数组.即数据应该在内部以压缩形式存储,我应该能够访问它(只读),就像它是std :: vector或类似的容器一样.
想法/意见？
Hei*_*mus 10
我认为你想要一个数组,其元素不是存储,而是压缩,以最小化内存使用.
关于压缩,您对数据的结构没有特别的了解,因此您可以使用某种标准的熵编码.理想情况下,想要在整个阵列上运行GZIP并完成它,但这将失去O(1)访问权限,这对您至关重要.
一种解决方案是将霍夫曼编码与索引表一起使用.
霍夫曼编码通过将每个输入符号(例如,ASCII字节)替换为可变比特长度的另一个符号来工作,这取决于整个流中的出现频率.例如,字符E经常出现,因此它得到一个短位序列,而'W'很少,并获得一个长位序列.
E -> 0b10
W -> 0b11110
现在,使用此方法压缩整个数组.不幸的是,由于输出符号具有可变长度,因此您不能再像以前那样索引数据:项目编号15不再是stream[15*sizeof(item)].
幸运的是,通过使用存储每个项目在压缩流中开始的位置的附加索引表 可以解决此问题index.换句话说,项目15的压缩数据可以在stream[index[15]]; 索引表累积变量输出长度.
因此,要获得第15项,您只需开始解压缩字节stream[index[15]].这是因为霍夫曼编码不会对输出做任何事情,它只是连接新的代码字,你可以开始在流内解码,而不必解码所有以前的项目.
当然,索引表增加了一些开销 ; 你可能想要调整粒度,使其compressed data + index table仍小于original data.