c++ - 具有随机数据访问的压缩 vector/数组类

Question

我想制作“压缩数组”/“压缩 vector ”类(详情如下)，它允许随机数据访问或多或少的常数时间。

“或多或少恒定时间”意味着虽然元素访问时间不是恒定的，但当我接近数组的某个点时它不应该继续增加。 IE。容器不应该做更多的计算(比如“再次解压所有东西以获得最后一个元素”，以及“几乎不做任何事情来获得第一个元素”)来获得一个元素。可以通过将数组拆分为压缩数据 block 来实现。 IE。访问一个元素应该采取 "averageTime"+- 一些偏差。我可以说我希望最好情况下的访问时间和最坏情况下的访问时间相对接近平均访问时间。

我有哪些选择(合适的算法/已经可用的容器 - 如果有的话)？

容器详细信息:

1. 容器充当相同元素(例如 std::vector)的线性数组
2. 一旦容器被初始化，数据是不变的，永远不会改变。容器需要提供只读访问权限。
3. 容器的行为应该像 array/std::vector - 即通过 operator[] 访问的值，有 .size() 等。
4. 如果我能把它做成模板类就好了。
5. 对数据的访问应该或多或少是恒定时间的。我不需要对每个元素都使用相同的访问时间，但我不必解压缩所有内容来获取最后一个元素。

使用示例:
对数据进行二分查找。

数据详情:
1. 数据是主要由 float 和一些整数组成的结构。 float 多于整数。没有字符串。
2. 数组中不太可能有很多相同的元素，所以简单地索引数据是不可能的。
3. 一个元素的大小小于100字节。
4. 每个容器的总数据大小在几千字节到几兆字节之间。
5. 数据不是稀疏的——它是连续的元素 block ，所有元素都被赋值，没有“空槽”。

与未压缩的数组形式相比，压缩的目标是减少 block 占用的内存量，同时保持合理的读取访问性能，并允许随机访问数组元素。 IE。数据应该在内部以压缩形式存储，我应该能够像访问 std::vector 或类似容器一样访问它(只读)。

想法/意见？

Answer 1

我认为您需要一个数组，其元素不是原版存储，而是压缩，以最大限度地减少内存使用。

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

一个解决方案是使用Huffmann coding连同一个索引表。

霍夫曼编码的工作原理是将每个输入符号(例如，ASCII 字节)替换为另一个可变 位长度的符号，具体取决于整个流中出现的频率。例如字符E出现的频率很高，所以它的位序列很短，而'W'很少出现，位序列很长。

E -> 0b10
W -> 0b11110

现在，用这个方法压缩你的整个数组。不幸的是，由于输出符号的长度可变，您无法再像以前那样为数据编制索引:项目编号 15 不再位于 stream[15*sizeof(item)] 中。

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

因此，要获得第 15 项，您只需开始解压缩 stream[index[15]] 中的字节即可。这是可行的，因为霍夫曼编码不会对输出做任何花哨的事情，它只是连接新的代码字，您可以在流内部开始解码，而无需解码所有以前的项目。

当然，索引表增加了一些开销；您可能需要调整粒度，以便 压缩数据 + 索引表 仍然小于 原始数据。