5

请推荐适合以下任务的技术。

我有一个相当大的(500MB)数据块,它基本上是一个数字矩阵。数据熵很低(它应该是可良好压缩的)并且存储在它所在的地方很昂贵。

我正在寻找的是用一个好的压缩算法(比如,GZip)压缩它,并带有可以实现非常偶然的随机访问的标记。随机访问,如“从原始(未压缩)流中的位置 [64 位地址] 读取字节”。这与 ZLIB 等经典的压缩器库略有不同,后者可以让您连续解压缩流。我想要的是在延迟的情况下进行随机访问,例如,每个字节读取多达 1MB 的解压缩工作。

当然,我希望使用现有的库而不是重新发明 NIH 的轮子。

4

8 回答 8

2

如果您使用 Java,我刚刚为此发布了一个库:http ://code.google.com/p/jzran 。

于 2010-11-07T06:46:45.420 回答
1

If you want to minimize the work involved, I'd just break the data into 1 MB (or whatever) chunks, then put the pieces into a PKZIP archive. You'd then need a tiny bit of front-end code to take a file offset, and divide by 1M to get the right file to decompress (and, obviously, use the remainder to get to the right offset in that file).

Edit: Yes, there is existing code to handle this. Recent versions of Info-zip's unzip (6.0 is current) include api.c. Among other things, that includes UzpUnzipToMemory -- you pass it the name of a ZIP file, and the name of one of the file in that archive that you want to retrieve. You then get a buffer holding the contents of that file. For updating, you'll need the api.c from zip3.0, using ZpInit and ZpArchive (though these aren't quite as simple to use as the unzip side).

Alternatively, you can just run a copy of zip/unzip in the background to do the work. This isn't quite as neat, but undoubtedly a bit simpler to implement (as well as allowing you to switch formats pretty easily if you choose).

于 2010-07-01T16:28:40.780 回答
1

字节对编码允许随机访问数据。

使用它您不会获得那么好的压缩,但是您会为单个树牺牲自适应(可变)哈希树,因此您可以访问它。

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

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

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

于 2010-07-01T16:18:49.247 回答
1

看看我的项目 - csio。我认为这正是您正在寻找的:包括标准输入输出接口和多线程压缩器。

它是用 C 语言编写的库,提供 CFILE 结构和函数cfopencfseekcftello等。您可以将它与常规(未压缩)文件和在 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

于 2015-06-18T04:42:13.400 回答
0

我认为压缩算法通常以块为单位工作,因此您也许可以根据块大小提出一些建议。

于 2010-07-01T16:13:57.647 回答
0

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

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

提升发布

Boost 入门指南注意:只有部分是boost::iostreams仅头文件库,在链接时不需要单独编译的库二进制文件或特殊处理。

于 2010-07-01T16:14:40.610 回答
0

您可以使用 bzip2 并根据 James Taylor 的seek-bzip2轻松制作自己的 API

于 2010-12-17T01:18:10.263 回答
0
  1. 先对大文件排序
  2. 将它分成你想要的大小(1MB)的块,名称中有一些序列(File_01,File_02,..,File_NN)
  3. 从每个块中获取第一个 ID 加上文件名并将两个数据放入另一个文件中
  4. 压缩块
  5. 您将能够使用您希望的方法对 ID 文件进行搜索,可能是二进制搜索并根据需要打开每个文件。

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

于 2010-07-01T16:47:36.210 回答