压缩格式,支持档案中的随机访问?

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

我目前使用gzip压缩包含sorting数据的一些非常大的文件。 当文件未被压缩时,二进制search是一种方便有效的方式来支持在sorting后的数据中寻找位置。

但是,当文件被压缩,事情变得棘手。 我最近发现了zlib的Z_FULL_FLUSH选项,可以在压缩过程中使用Z_FULL_FLUSH选项在压缩输出中插入“同步点” inflateSync()然后inflateSync()可以从文件中的各个点开始读取)。 这是好的,虽然我已经有文件将不得不重新join这个function(奇怪的是gzip没有这个选项,但我愿意编写自己的压缩程序,如果我必须)。

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

有更好的解决scheme吗? 如果可能的话,我想避免使用辅助文件进行索引,显式的,对准随机访问的默认支持将会有帮助(即使它是大粒度的,就像能够在每个10 MB间隔开始读取一样)。 有没有比gzip更好的支持随机读取的压缩格式?

编辑 :正如我所提到的,我希望在压缩数据中进行二分search。 我不需要寻找一个特定的(未压缩的)位置 – 只是在压缩文件中寻求一些粗略的粒度。 我只是想支持一些东西,如“解压缩大约50%(25%,12.5%等)的数据到这个压缩文件”。

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

例如,bzip2压缩文件由大小为<1MB的独立压缩块组成,这些压缩块是由魔术字节序列分隔的,因此您可以parsingbzip2文件,获取块边界,然后解压缩右边的块。 这将需要一些索引来记住块在哪里开始。

尽pipe如此,我认为最好的解决scheme是将文件分割成不同的块,然后使用zip或rar等压缩文件进行压缩,这些压缩文件可以随机访问存档中的单个文件。

看看dictzip 。 它与gzip兼容并允许粗糙的随机访问。

摘自手册页:

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

我有在Ubuntu的包装dictzip。 或者它的源代码是dictd – *。tar.gz 。 它的许可证是GPL。 你可以自由研究它。

更新:

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

解决scheme提供随机访问gzip和bzip2档案:

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

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

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

随机读取 :数据可以分成独立压缩的块。 每个.xz文件都包含一个块的索引,当块大小足够时,这使得有限的随机访问读取成为可能。

这应该足够你的目的。 缺点是liblzma的API(用于与这些容器进行交互)似乎没有很好的logging,因此可能需要花费一些努力来计算如何随机访问块。

bgzip可以压缩gzipvariables中的文件,这个variables是可以索引的(可以用gzip解压缩)。 这与一些生物信息学应用程序,以及tabix索引器一起使用。

请参阅此处的解释: http : //blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html ,以及此处: http : //www.htslib.org/doc/tabix.html 。

我不知道它是适用于其他应用程序的程度。

我不确定这是否适用于您的确切情况,但是您不能将每个大文件gzip压缩成更小的文件,例如每个10 MB。 你最终会得到一堆文件:file0.gz,file1.gz,file2.gz等等。基于给定的偏移量,你可以在文件名为"file" + (offset / 10485760) + ".gz" 。 未压缩存档中的offset % 10485760将被offset % 10485760

由于无损压缩在某些区域比其他区域的效果更好,因此如果将压缩数据存储到BLOCKSIZE长度合适的块中,即使每个块的压缩字节数完全相同,某些压缩块也会扩展为比其他块更长的明文。

您可以参阅Nivio Ziviani,Edleno Silva de Moura,Gonzalo Navarro和Ricardo Baeza-Yates在“ 计算机 ”杂志2000年11月的“压缩:下一代文本检索系统的关键” http://doi.ieeecomputersociety.org/10.1109 /2.881693

它们的解压缩器将压缩数据的整个字节分成1,2,3或3个字节,并将其解压(使用词汇列表)为一个单词。 人们可以直接在压缩的文本中search单词或短语,这比search未压缩的文本更快。

他们的解压缩器让你用正常的(字节)指针指向文本中的任何一个字,并立即从那个点开始解压缩。

您可以为每个单词指定一个唯一的2字节代码,因为您的文本中可能只有less于65,000个独特单词。 (KJV圣经中有近13,000个独特的词)。 即使有超过65,000个字,将前256个双字节代码“words”分配给所有可能的字节也是非常简单的,因此您可以拼出不在65,000左右的词典中的词“最频繁单词和短语”。 (通过将频繁的单词和短语打包成两个字节获得的压缩通常值得使用每个字母两个字节偶尔拼出一个单词的“扩展”)。 有很多方法可以select一个“常用单词和短语”的词汇,这个词典能够提供足够的压缩。 例如,您可以调整一个LZW压缩器,将不止一次使用的“短语”转储到词典文件,每个短语一行,然后在所有数据上运行。 或者你可以任意地将你的未压缩的数据分成一个词典文件中的5个字节的短语,每个短语一行。 或者,您可以将未压缩的数据分解为实际的英文单词,并将每个单词(包括单词开头的空格)放入词典文件中。 然后使用“sort –unique”来消除该词典文件中的重复单词。 (是select一个完美的“最佳”的词汇表,仍然被认为是NP难?)

将词典存储在巨大的压缩文件的开头,将其放在一些方便的BLOCKSIZE中,然后将压缩后的文本 – 一系列两个字节的“文字” – 从那里存储到文件末尾。 据推测,search者将在解压缩期间读取该词典一次,并将其保存在RAM中的一些快速解码格式中,以加速解压缩“两字节码”为“可变长度短语”。 我的第一份草案将以每个短语列表的简单一行开始,但是稍后您可能会转而使用某种增量编码或zlib以更加压缩的forms存储词典。

你可以select任意的偶数字节偏移到压缩文本中,然后从那里开始解压缩。 我不认为有可能做一个更细粒度的随机访问压缩文件格式。

两种可能的解决方

  1. 让操作系统处理压缩,创build并装载包含所有文本文件的压缩文件系统(SquashFS,clicfs,cloop,cramfs,e2compr或其他),在应用程序中不做任何有关压缩的操作。

  2. 直接在每个文本文件上使用clicfs(每个文本文件一个clicfs),而不是压缩文件系统映像。 将“mkclicfs mytextfile mycompressedfile”设为“gzip <mytextfile> mycompressedfile”和“clicfs mycompressedfile目录”,作为通过文件“directory / mytextfile”随机访问数据的一种方式。

我不知道它是否被提及,但Kiwix项目在这方面做了很多工作。 通过他们的程序Kiwix,他们提供随机访问ZIM文件档案。 压缩也很好。 该项目是在需要维基百科的离线拷贝(已经以非压缩forms达到100GB以上,包括所有媒体)的情况下产生的。 他们已经成功地采取了一个25 GB的文件(没有大多数媒体的维基百科的单一文件的体现),并压缩到一个可怜的8 GB zim文件档案。 通过Kiwix程序,您可以调用维基百科的任何页面以及所有相关的数据,速度比上网快。

尽pipeKiwix程序是基于维基百科数据库结构的技术,但它certificate了您可以同时拥有出色的压缩率和随机访问。

这是一个非常古老的问题,但看起来zindex可以提供一个很好的解决scheme(虽然我没有太多的经验)

razip支持比gzip / bzip2更好的随机访问,必须对此进行调整 – 以“ok”为代价减less压缩随机访问:

http://sourceforge.net/projects/razip/

我是压缩特定types的生物数据的开源工具的作者。 这个名为starch工具通过染色体分割数据,并使用这些分割作为快速访问较大档案库中压缩数据单元的索引。

对每个染色体数据进行转换以消除基因组坐标中的冗余,并且转换后的数据用bzip2gzipalgorithm进行压缩。 偏移量,元数据和压缩的基因组数据被连接成一个文件。

源代码可从我们的GitHub网站获得。 我们已经在Linux和Mac OS X下编译了它。

对于你的情况,你可以在一个标题中存储(10 MB,或其他)偏移量到自定义的存档格式。 你parsing头文件,检索偏移量,并通过current_offset_sum + header_size递增fseek文件。