压缩数据文件的简单随机访问API

6
请推荐一种适合以下任务的技术。
我有一个相当大(500MB)的数据块,基本上是由数字构成的矩阵。数据熵很低(应该可以很好地压缩),而存储空间则很昂贵。
我正在寻找的是使用良好的压缩算法(例如GZip)来压缩它,并通过标记实现非常偶尔的随机访问。所谓随机访问,是指“从原始(未压缩)流的[64位地址]处读取字节”。这与类似于ZLIB的经典deflator库有些不同,后者只能让您连续解压缩流。我希望的是,在每读取1个字节时具有延迟高达1MB的解压工作的随机访问。
当然,我希望使用现有的库,而不是重新发明轮子。
8个回答

2

1
请查看我的项目 - csio。我认为这正是您所寻找的:类似于stdio接口和多线程压缩器。
它是一个用C编写的库,提供了CFILE结构和函数cfopen、cfseek、cftello等。您可以将其与常规(未压缩)文件和使用dzip实用程序压缩的文件一起使用。该实用程序包含在项目中,用C++编写。它生成有效的gzip档案,可以由标准工具以及csio处理。dzip可以在许多线程中进行压缩(请参见-j选项),因此可以非常快速地压缩非常大的文件。
典型用法:
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


1

Byte Pair Encoding 允许对数据进行随机访问。

使用它时,你无法获得很好的压缩效果,但是你牺牲了自适应(可变)哈希树来换取单一树结构,以便于访问。

然而,你仍然需要某种类型的索引才能找到特定的“字节”。由于你可以接受 1 MB 的延迟,因此你将为每个 1 MB 创建一个索引。希望你能想出一种方法,使你的索引足够小,以便从压缩中获益。

这种方法的好处之一是随机访问编辑。你可以相对较小地更新、删除和插入数据。

如果它很少被访问,你可以使用 gzip 压缩索引,并在需要时解码它。


你能推荐一个现有的实现吗? - Pavel Radzivilovsky

1

如果你想要最小化工作量,我建议将数据分成1 MB(或其他大小)的块,然后将这些块放入PKZIP存档文件中。然后,你只需要一点前端代码来获取文件偏移量,并将其除以1M以获取正确的文件进行解压缩(显然,使用余数来获取该文件中正确的偏移量)。

编辑:是的,已经有现成的代码可以处理这个问题。Info-zip的unzip最近版本(6.0是当前版本)包括api.c。其中包括UzpUnzipToMemory等函数--你只需传递ZIP文件的名称和要检索的文件的名称,就可以获得一个包含该文件内容的缓冲区。对于更新操作,你需要从zip3.0中获取api.c,并使用ZpInitZpArchive(虽然这些不像unzip那么简单易用)。

另外,你也可以在后台运行zip/unzip的副本来完成工作。虽然这样做不太整洁,但实现起来无疑更简单(而且如果你选择,还可以轻松切换格式)。


那是个好主意。不幸的是,我不知道有任何现有的库可以做到这一点,但使用包装类来实现很容易。 - Marcus Adams
编辑数据可能会有一点棘手,但是可行的。 - Marcus Adams

0

你可以使用bzip2,并基于James Taylor的seek-bzip2很容易地制作自己的API。


0

压缩算法通常按块处理,因此您可以基于块大小想出一些东西。


虽然原始数据是以块的形式处理的,但压缩后的数据块大小不同,因此无法在压缩数据中跳转以查找特定块。 - Marcus Adams
如果文件被分成每个表示65,536字节源数据的块,可以在每个块上花费四个字节来记录每个块的起始位置。(*) 也可以使用1,048,576字节的块大小,但即使使用64K块,一个半GB的文件只需要一个32K字节的表。 - supercat

0

我建议使用Boost Iostreams Library。 Boost.Iostreams可用于创建流以访问TCP连接,也可用作加密和数据压缩的框架。该库包括用于访问内存映射文件的组件,用于使用操作系统文件描述符进行文件访问的组件,用于代码转换的组件,用于带有正则表达式的文本过滤的组件,用于行结束转换的组件以及用于zlib、gzip和bzip2格式的压缩和解压缩的组件。

Boost库已被C++标准委员会接受为TR2的一部分,因此它最终将内置于大多数编译器中(在std::tr2::sys下)。它还具有跨平台兼容性。

Boost Releases

Boost Getting Started Guide 注意:只有boost::iostreams的某些部分是头文件库,不需要单独编译库二进制文件或在链接时进行特殊处理。


boost::iostreams 不是一个仅包含头文件的库,尽管其中的某些部分是。 - Billy ONeal

0
  1. 首先对大文件进行排序
  2. 将其分成您所需大小的块(1MB),并在名称中添加一些序列(File_01,File_02,..,File_NN)
  3. 从每个块中取出第一个ID以及文件名,并将两个数据放入另一个文件中
  4. 压缩这些块
  5. 您可以使用任何您想要的方法在ID文件中进行搜索,例如二进制搜索,并根据需要打开每个文件。

如果您需要深度索引,则可以使用BTree算法,其中“页面”是文件。 因为代码有点棘手,所以在网上存在几种实现方式。


如果我们有索引,我认为我们不需要多个压缩文件。 - Marcus Adams
Gustavo,谢谢,但我知道如何自己设计它。我需要有人指引我到一个现有的库... 我不可能是第一个面对这个问题的人。 - Pavel Radzivilovsky

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接