11

我想制作“压缩数组”/“压缩向量”类（详情如下），它允许以或多或少的恒定时间进行随机数据访问。

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

我有哪些选择（合适的算法/已经可用的容器——如果有的话）？

集装箱详情：

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

使用示例：
对数据进行二分搜索。

数据细节：
1. 数据是结构体，主要由浮点数和一些整数组成。浮点数比整数多。没有字符串。
2.数组中不可能有很多相同的元素，所以简单的索引数据是不可能的。
3. 一个元素的大小小于 100 字节。
4. 每个容器的总数据大小在几千字节到几兆字节之间。
5. 数据不是稀疏的——它是连续的元素块，它们都被分配，没有“空槽”。

与未压缩的数组表示相比，压缩的目标是减少块占用的内存量，同时保持某种合理的读取访问性能，并允许将元素随机访问为数组。即数据应该在内部以压缩形式存储，并且我应该能够访问它（只读），就好像它是 std::vector 或类似容器一样。

想法/意见？

4

5 回答 5

11

我认为您需要一个数组，其元素不是存储原版，而是压缩的，以尽量减少内存使用。

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

一种解决方案是使用Huffmann 编码和索引表。

Huffmann 编码通过将每个输入符号（例如，ASCII 字节）替换为另一个位长可变的符号来工作，具体取决于整个流中出现的频率。例如，字符E出现频率很高，所以它得到一个短的位序列，而“W”很少出现，得到一个长的位序列。

E -> 0b10
W -> 0b11110

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

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

因此，要获得第 15 项，您只需开始解压缩stream[index[15]]. 这是因为 Huffmann 编码对输出没有做任何花哨的事情，它只是连接新的代码字，您可以在流中开始解码，而不必解码所有以前的项目。

当然，索引表增加了一些开销；您可能需要调整粒度，使其compressed data + index table仍小于original data.

于 2010-08-06T14:13:01.977 回答
4

您是否正在为嵌入式系统编码和/或您是否拥有成百上千个这样的容器？如果不是，虽然我认为这是一个有趣的理论问题（+1），但我怀疑由于进行减压而导致的减速将是不平凡的，最好使用std::vector.

接下来，您确定要存储的数据足够冗余，以至于较小的数据块实际上是可压缩的吗？您是否尝试过保存不同大小的块（也许是 2 的幂）并尝试通过 gzip 运行它们作为练习？帮助解压缩算法（取决于方法）所需的任何额外数据可能会减少执行这种压缩容器的空间优势。

如果您认为进行压缩仍然是合理的，那么至少有两种可能性，但没有预先编写好的。您可以压缩每个单独的元素，存储指向压缩数据块的指针。那么索引访问还是不变的，只需要解压实际数据即可。可能使用代理对象会使实际的数据解压缩更容易和更透明（甚至可能允许您std::vector用作底层容器）。

或者，std::deque已经将其数据存储在块中，因此您可以在此处使用类似的方法。例如std::vector<compressed_data_chunk>，每个块包含 10 个压缩在一起作为底层容器的项目。然后你仍然可以直接索引你需要的chunk，解压它，然后从解压后的数据中返回item。如果您愿意，您的包含对象（包含vector）甚至可以缓存最近解压缩的一两个块，以提高连续访问的性能（尽管这对二进制搜索没有多大帮助）。

于 2010-08-06T14:09:11.627 回答
3

我已经考虑了一段时间了。从理论的角度来看，我确定了两种可能性：

  • Flyweight，因为这种模式可以减少重复。
  • 序列化（压缩是某种形式的序列化）

第一个是纯粹面向对象的，我认为总的来说很合适，它没有弄乱指针的缺点。

第二个似乎更适合这里，尽管它总体上确实有一个轻微的缺点：指针无效+指针编码/解码，虚拟表等问题......值得注意的是，如果项目使用指针相互引用，则它不起作用的指数。

我见过一些“霍夫曼编码”解决方案，但这意味着对于每个结构都需要提供一种压缩算法。很难一概而论。

所以我宁愿走另一条路，使用像'zlib'这样的压缩库，例如选择像lzo这样的快速算法。

  • B* 树（或变体），每个节点有大量项目（因为它不移动），比如 1001。每个节点都包含项目数组的压缩表示。索引未压缩。
  • 可能：cache_view在存储最后 5 个（左右）解压缩节点或其他东西的同时访问容器。另一个变体是实现引用计数并保持数据未压缩，只要有人获得节点中某个项目的句柄。

一些备注：

  • 如果您应该每个节点有大量的项目/键，那么您的访问时间接近恒定，例如 1001 这意味着只要您存储的项目少于一百万，则只有 2 级间接，3 级间接亿等...
  • 你可以用这样的结构构建一个可读/可写的容器。我会做到这一点，这样我只有在完成节点编写后才重新压缩。
于 2010-08-09T11:35:15.650 回答
0

好的，据我所知，您想要的是某种访问器模板。基本上，创建一个模板适配器，它的参数是您的元素类型之一，它通过指针、blob 的索引等在内部访问它。使适配器类似于指针：

const T &operator->(void) const;

等等，因为创建指针适配器比创建引用适配器更容易（尽管如果您想知道如何编写其中之一，请参阅向量）。请注意，我根据您的指南使此访问器保持不变。然后，在加载/压缩 blob 时预先计算偏移量，并使用模板化适配器类填充向量。这有意义吗？如果您需要更多详细信息，我将很乐意提供。

至于压缩算法，我建议您只需对 blob 中的字节进行频率分析，然后通过硬编码的 Huffman 编码（如前所述）运行未压缩的 blob，捕获每个元素的偏移量并存储它在您的代理适配器中，而代理适配器又是您的数组的元素。实际上，您可以将其全部作为某个压缩类的一部分，该类压缩并生成可以从一开始就复制回插入到您的向量中的元素。再次，如果您需要示例代码，请回复。

于 2010-08-06T13:43:19.790 回答
0

“什么是允许在文件中随机读/写的最佳压缩算法是什么？”的一些答案可以吗？ 适应您的内存数据？

于 2010-09-13T03:01:29.857 回答