压缩格式对档案内的随机访问有很好的支持？

Question

这与之前的问题类似,但那里的答案不能满足我的需求,我的问题略有不同:

我目前对一些包含排序数据的非常大的文件使用gzip压缩.当文件未被压缩时,二进制搜索是支持在排序数据中寻找位置的便捷有效方式.

但是当文件被压缩时,事情变得棘手.我最近发现了zlib的Z_FULL_FLUSH选项,可以在压缩过程中使用它在压缩输出中插入"同步点"(inflateSync()然后可以从文件中的各个点开始读取).这是可以的,虽然我已经拥有的文件必须重新压缩才能添加此功能(奇怪的gzip是没有这个选项,但如果必须,我愿意编写自己的压缩程序).

从一个来源看来,即使Z_FULL_FLUSH不是一个完美的解决方案......不仅所有gzip档案都不支持它,而且在档案中检测同步点的想法可能会产生误报(或者与同步的幻数重合)点,或由于Z_SYNC_FLUSH也产生同步点但它们不能用于随机访问的事实.

有更好的解决方案吗？如果可能的话,我想避免使用辅助文件进行索引,并且对准随机访问的显式默认支持将是有帮助的(即使它是大粒度的 - 就像能够以每10 MB的间隔开始读取一样).是否有另一种压缩格式比gzip更好地支持随机读取？

编辑:正如我所提到的,我希望在压缩数据中进行二进制搜索.我不需要寻找特定的(未压缩的)位置 - 只是在压缩文件中寻找一些粗粒度.我只是希望能够支持诸如"将数据从大约50%(25%,12.5%等)开始压缩到此压缩文件中".

Answer 1

看看dictzip吧.它与gzip兼容,允许粗随机访问.

摘自其手册页:

dictzip使用gzip(1)算法(LZ77)以与gzip文件格式完全兼容的方式压缩文件.gzip文件格式的扩展(Extra Field,在RFC 1952的2.3.1.1中描述)允许将额外数据存储在压缩文件的头部中.像gzip和zcat这样的程序会忽略这些额外的数据.但是,[dictzcat --start]将利用此数据对文件执行伪随机访问.

我在Ubuntu中有dictzip包.或者它的源代码是在dictd - *.tar.gz中.它的许可证是GPL.你可以自由学习.

更新:

我改进了dictzip没有文件大小限制. 我的实施是在MIT许可下.

Answer 2

我不知道任何压缩文件格式可以支持随机访问未压缩数据中的特定位置(除了多媒体格式),但你可以酿造自己的.

例如,bzip2压缩文件由大小<1MB未压缩的独立压缩块组成,这些块由魔术字节序列分隔,因此您可以解析bzip2文件,获取块边界,然后只解压缩右块.这需要一些索引来记住块的起始位置.

尽管如此,我认为最好的解决方案是将文件拆分为您选择的块,然后使用zip或rar等一些归档程序压缩它,这些归档程序支持随机访问归档中的各个文件.

Answer 3

该.xz文件格式(使用LZMA压缩)似乎支持这一点:

随机访问读取:数据可以拆分为独立的压缩块.每个.xz文件都包含块的索引,当块大小足够小时,可以进行有限的随机访问读取.

这应该足以满足您的目的.缺点是liblzma的API(用于与这些容器交互)似乎没有很好的文档,因此可能需要花费一些精力来确定如何随机访问块.

Answer 4

存在用于提供对gzip和bzip2档案的随机访问的解决方案:

• 来自ghostscript源代码的gzip zran.c
• 詹姆斯泰勒的bzip2 seek-bzip

(我正在寻找7zip的东西)

Answer 5

bgzip可以以gzip可索引的变体形式压缩文件（并可以通过进行解压缩gzip）。在某些生物信息学应用程序中，它与tabix索引器一起使用。

请参阅以下说明：http : //blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html，以及此处：http : //www.htslib.org/doc/tabix.html。

我不知道它在多大程度上适用于其他应用程序。

Answer 6

如果先前已创建索引，则可以随机访问 gzip 格式，如zlib 的zran.c源代码所示。

我在 zlib 的zran.c 上开发了一个命令行工具，它为 gzip 文件创建索引：https : //github.com/circulosmeos/gztool

它甚至可以为仍在增长的 gzip 文件（例如由 rsyslog 直接以 gzip 格式创建的日志）创建索引，从而在实践中减少索引创建时间。请参阅-S（监督）选项。