c – 具有随机数据访问的压缩向量/数组类

发布时间：2020-12-16 05:47:50 所属栏目：百科来源：网络整理

导读：我想制作“压缩数组”/“压缩向量”类(下面的细节),允许随机数据访问或多或少的恒定时间. “或多或少的恒定时间”意味着虽然元素访问时间不是恒定的,但是当我接近数组的某个点时,它不应该保持增加.即容器不应该做更多的计算(如“再次解压缩所有的东西以获得

我想制作“压缩数组”/“压缩向量”类(下面的细节),允许随机数据访问或多或少的恒定时间.

“或多或少的恒定时间”意味着虽然元素访问时间不是恒定的,但是当我接近数组的某个点时,它不应该保持增加.即容器不应该做更多的计算(如“再次解压缩所有的东西以获得最后一个元素”,并且“几乎没有什么可以获得第一个”)来获取一个元素.可以通过将数组拆分成大量的压缩数据来实现.即访问一个元素应该采取“平均时间” – 一些偏差.我可以说,我想要最好的访问时间和最坏的访问时间相对接近平均访问时间.

我有什么选择(合适的算法/已经可用的容器 – 如果有的话)？

集装箱细节：

>容器作为一个相同元素的线性数组(如std :: vector)
>一旦容器初始化,数据是恒定的,永远不会改变.容器需要提供只读访问.
>容器应该像array / std :: vector这样的行为,即通过operator []访问的值,有.size()等.
>如果我可以将其作为模板类,这将是很好的
>访问数据应该是或多或少的恒定时间.我不需要每个元素的访问时间相同,但是我不需要解压缩所有内容以获取最后一个元素.

用法示例：
二进制搜索数据.

资料详情：
数据是主要由浮点数和几个int组成的结构体.有比浮点数更多的浮点数.没有字符串
在阵列中不太可能有相同的元素,所以只能索引数据是不可能的.
一个元素的大小小于100字节.
4.每个容器的总数据大小在几千字节和几兆字节之间.
数据不稀疏 – 它是连续的元素块,它们都被分配,没有“空槽”.

压缩的目的是减少与未压缩表示作为数组相比的块所需的RAM数量,同时保持一些合理的读取访问性能,并允许随机访问元素作为数组.即数据应该以内部的压缩形式存储,我应该能够访问它(只读),就像它是一个std :: vector或类似容器一样.

想法/意见？

解决方法

我认为,你想要一个数组,其元素不是存储的,而是被压缩,以最小化内存使用.

关于压缩,您对数据的结构没有任何特别的了解,因此您可以使用某种标准熵编码.理想情况下,想要在整个阵列上运行GZIP并完成它,但是会丢失O(1)访问,这对您至关重要.

一个解决方案是使用Huffmann coding和索引表.

霍夫曼编码通过用可变位长度的另一个符号替换每个输入符号(例如,ASCII字节),取决于整个流中的发生频率.例如,字符E经常出现,所以它得到一个短的序列,而’W’很少得到一个很长的序列.

E -> 0b10
W -> 0b11110

现在,用这种方法压缩整个数组.不幸的是,由于输出符号具有可变长度,因此您可能不再像以前一样索引数据：项目号15不再在流[15 * sizeof(item)].

幸运的是,这个问题可以通过使用附加的索引表索引来解决,该索引存储在压缩流中每个项目开始的位置.换句话说,项目15的压缩数据可以在stream [index [15]]找到;索引表累加变量输出长度.

所以,要获得项目15,你只需要在stream [index [15]]开始解压缩字节.这是因为霍夫曼编码对输出不做任何奇怪的事情,它只是连接新的代码字,你可以在流内开始解码,而无需解码所有以前的项目.

当然,索引表增加了一些开销;您可能需要调整粒度,使压缩数据索引表仍然小于原始数据.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!