我有一个相当大(500MB)的数据块,基本上是由数字构成的矩阵。数据熵很低(应该可以很好地压缩),而存储空间则很昂贵。
我正在寻找的是使用良好的压缩算法(例如GZip)来压缩它,并通过标记实现非常偶尔的随机访问。所谓随机访问,是指“从原始(未压缩)流的[64位地址]处读取字节”。这与类似于ZLIB的经典deflator库有些不同,后者只能让您连续解压缩流。我希望的是,在每读取1个字节时具有延迟高达1MB的解压工作的随机访问。
当然,我希望使用现有的库,而不是重新发明轮子。
dzip -j4 myfile
...
CFILE file = cfopen("myfile.dz", "r");
off_t some_offset = 673820;
cfseek(file, some_offset);
char buf[100];
cfread(buf, 100, 1, file);
cfclose(file);
它是MIT许可证,因此您可以在项目中无限制地使用它。有关更多信息,请访问github上的项目页面:https://github.com/hoxnox/csio
Byte Pair Encoding 允许对数据进行随机访问。
使用它时,你无法获得很好的压缩效果,但是你牺牲了自适应(可变)哈希树来换取单一树结构,以便于访问。
然而,你仍然需要某种类型的索引才能找到特定的“字节”。由于你可以接受 1 MB 的延迟,因此你将为每个 1 MB 创建一个索引。希望你能想出一种方法,使你的索引足够小,以便从压缩中获益。
这种方法的好处之一是随机访问编辑。你可以相对较小地更新、删除和插入数据。
如果它很少被访问,你可以使用 gzip 压缩索引,并在需要时解码它。
如果你想要最小化工作量,我建议将数据分成1 MB(或其他大小)的块,然后将这些块放入PKZIP存档文件中。然后,你只需要一点前端代码来获取文件偏移量,并将其除以1M以获取正确的文件进行解压缩(显然,使用余数来获取该文件中正确的偏移量)。
编辑:是的,已经有现成的代码可以处理这个问题。Info-zip的unzip最近版本(6.0是当前版本)包括api.c
。其中包括UzpUnzipToMemory
等函数--你只需传递ZIP文件的名称和要检索的文件的名称,就可以获得一个包含该文件内容的缓冲区。对于更新操作,你需要从zip3.0中获取api.c
,并使用ZpInit
和ZpArchive
(虽然这些不像unzip那么简单易用)。
另外,你也可以在后台运行zip/unzip的副本来完成工作。虽然这样做不太整洁,但实现起来无疑更简单(而且如果你选择,还可以轻松切换格式)。
压缩算法通常按块处理,因此您可以基于块大小想出一些东西。
我建议使用Boost Iostreams Library。 Boost.Iostreams可用于创建流以访问TCP连接,也可用作加密和数据压缩的框架。该库包括用于访问内存映射文件的组件,用于使用操作系统文件描述符进行文件访问的组件,用于代码转换的组件,用于带有正则表达式的文本过滤的组件,用于行结束转换的组件以及用于zlib、gzip和bzip2格式的压缩和解压缩的组件。
Boost库已被C++标准委员会接受为TR2的一部分,因此它最终将内置于大多数编译器中(在std::tr2::sys下
)。它还具有跨平台兼容性。
Boost Getting Started Guide 注意:只有boost::iostreams
的某些部分是头文件库,不需要单独编译库二进制文件或在链接时进行特殊处理。
boost::iostreams
不是一个仅包含头文件的库,尽管其中的某些部分是。 - Billy ONeal如果您需要深度索引,则可以使用BTree算法,其中“页面”是文件。 因为代码有点棘手,所以在网上存在几种实现方式。