对档案中的随机访问提供良好支持的压缩格式？

StackOverflow https://stackoverflow.com/questions/429987

题

这类似于一个 上一个问题, ，但那里的答案不能满足我的需求，我的问题略有不同：

我目前对一些包含排序数据的非常大的文件使用 gzip 压缩。当文件未压缩时，二分搜索是支持在排序数据中查找位置的便捷且有效的方法。

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

看来是从 一个来源 即使 Z_FULL_FLUSH 不是一个完美的解决方案...不仅不是所有 gzip 存档都支持它，而且检测存档中的同步点的想法可能会产生误报（要么与同步点的幻数一致，要么由于以下事实）那 Z_SYNC_FLUSH 也产生同步点，但它们不可用于随机访问）。

有更好的解决方案吗？如果可能的话，我希望避免使用用于索引的辅助文件，并且对准随机访问的显式默认支持会很有帮助（即使它是大粒度的，例如能够以每个 10 MB 的间隔开始读取）。是否有其他压缩格式比 gzip 更好地支持随机读取？

编辑: ：正如我提到的，我希望在压缩数据中进行二分搜索。我不需要寻找特定的（未压缩的）位置——只需在压缩文件中以一些粗粒度进行寻找。我只想支持“从大约 50%（25%、12.5% 等）开始将数据解压缩到此压缩文件中”之类的内容。

有帮助吗？

解决方案

我不知道任何压缩文件格式会支持随机访问未压缩数据中的特定位置（除多媒体格式外），但您可以自己酿造。

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

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

其他提示

看看 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，没有文件大小限制。 我的实施已获得麻省理工学院的许可。

.xz文件格式（使用LZMA压缩）似乎支持这一点：

  

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

这应该足以满足您的目的。缺点是liblzma的API（用于与这些容器进行交互）似乎没有详细记录，因此可能需要花费一些精力来确定如何随机访问块。

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

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

bgzip可以压缩gzip变体中的文件，该变体是可索引的（并且可以通过tabix解压缩）。这在一些生物信息学应用程序中与<=>索引器一起使用。

请参阅此处的说明： http：// blastedbio .blogspot.fr / 2011/11 / bgzf-blocked-greater-better-gzip.html ，这里： http://www.htslib.org/doc/tabix.html 。

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

我不确定这在您的确切情况下是否实用，但您不能将每个大文件压缩成较小的文件，比如10 MB吗？您最终会得到一堆文件：file0.gz，file1.gz，file2.gz等。根据原始大小中的给定偏移量，您可以搜索名为"file" + (offset / 10485760) + ".gz"的文件。未压缩存档中的偏移量为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个整个字节的压缩数据，并将（使用词汇表）解压缩成一个完整的单词。 可以直接在压缩文本中搜索单词或短语， 结果比搜索未压缩的文本更快。

它们的解压缩程序允许您使用普通（字节）指针指向文本中的任何单词，并立即从该点开始解压缩。

您可以为每个单词提供唯一的2字节代码，因为您的文本中可能只有少于65,000个唯一单词。 （KJV圣经中有近13,000个独特单词）。 即使有超过65,000个单词，分配前256个双字节代码<！>“单词<！>”是非常简单的。对于所有可能的字节，所以你可以拼出不在65,000左右的词典中的单词<！>“最常用的单词和短语<！>”; （通过将频繁的单词和短语打包成两个字节而获得的压缩 通常值得<！>“扩展<！>”;偶尔使用每个字母两个字节来拼写单词）。 有多种方法可以选择<！>“频繁的单词和短语<！>”的词典。这将提供足够的压缩。 例如，您可以调整LZW压缩器以转储<！>“短语<！>”;它对词典文件使用多次，每个短语一行，并在所有数据上运行。 或者你可以在词典文件中任意将你的未压缩数据切换成5个字节的短语，每个短语一行。 或者，您可以将未压缩的数据切换为实际的英语单词，并将每个单词（包括单词开头的空格）放入词典文件中。 然后使用<！> quot; sort --unique <！> quot;消除该词典文件中的重复单词。 （选择完美的<！>“最佳<！>”词典词典仍然被认为是NP难？）

将词典存储在巨大压缩文件的开头，将其填充到一些方便的BLOCKSIZE，然后存储压缩文本 - 一系列两个字节<！>“单词<！>”; - 从那里到文件的末尾。 据推测，搜索者会在解压缩过程中读取一次该词典并将其保存在RAM中的某种快速解码格式中，以加速解压缩<！>“两字节代码<！>”; to <！> quot;变长短语<！>“; 我的第一个草稿将从每个短语列表中简单的一行开始，但您可能稍后转而使用某种增量编码或zlib以更压缩的形式存储词典。

您可以在压缩文本中选择任意随机字节偏移量，然后从那里开始解压缩。 我认为不可能制作更精细的随机访问压缩文件格式。

两种可能的解决方案：

  1. 让操作系统处理压缩，创建和挂载包含所有文本文件的压缩文件系统（SquashFS，clicfs，cloop，cramfs，e2compr或其他），并且不要在应用程序中执行任何有关压缩的操作

  2. 直接在每个文本文件上使用clicfs（每个文本文件一个clicfs），而不是压缩文件系统映像。想想<！>“mkclicfs mytextfile mycompressedfile <！>”;是<！>“gzip <！> lt; mytextfile <！> gt; mycompressedfile <！> quot;和<！>“clicfs mycompressedfile目录<！>”;作为通过文件<！>“directory / mytextfile <！>”获得对数据的随机访问的一种方式。

我不知道它是否已被提及，但Kiwix项目在这方面做了很多工作。通过他们的程序Kiwix，他们提供随机访问ZIM文件档案。压缩也很好。该项目源于对维基百科的离线副本的需求（已经以非压缩形式达到100 GB以上，包括所有媒体）。他们成功地获取了25 GB的文件（没有大多数媒体的维基百科的单文件实施例）并将其压缩为一个可怜的8 GB zim文件存档。通过Kiwix计划，您可以使用所有相关数据调用维基百科的任何页面，比网上冲浪更快。

尽管Kiwix程序是基于维基百科数据库结构的技术，但它证明您可以同时具有出色的压缩率和随机访问。

这是一个非常古老的问题，但看起来像 zindex 可以提供一个很好的解决方案（虽然我不喜欢对它有很多经验）

razip支持随机访问，其性能优于gzip / bzip2，必须针对此支持进行调整 - 以<！>“ok <！>”为代价减少压缩。随机访问：

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

我是压缩特定类型生物数据的开源工具的作者。这个名为starch的工具按染色体分割数据，并使用这些分区作为索引，以便快速访问较大档案中的压缩数据单元。

转换每个染色体数据以去除基因组坐标中的冗余，并使用bzip2或gzip算法压缩转换后的数据。偏移量，元数据和压缩基因组数据连接成一个文件。

我们的 GitHub 网站提供了源代码。我们已经在Linux和Mac OS X下编译了它。

对于您的情况，您可以在标头中存储（10 MB或其他）偏移到自定义存档格式。您解析标题，检索偏移量，并通过fseek + current_offset_sum逐步header_size遍历文件。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top