logo标签列表

压缩格式中哪些支持在存档文件中进行随机访问的比较好？

compressiongziparchivezlibrandom-access
72

这和一个之前的问题类似，但是那里的答案并不能满足我的需求，而且我的问题略有不同：

我目前针对一些非常大的包含排序数据的文件使用gzip压缩。当这些文件未经压缩时，二分查找是一种方便有效的支持随机访问到排序数据位置的方式。

但是当文件进行压缩后，情况就变得棘手了。我最近发现了zlib的Z_FULL_FLUSH选项，可以在压缩过程中插入“同步点”到压缩输出中（inflateSync()然后可以从文件中的各个点开始读取）。这还好，尽管已经存在的文件需要重新压缩才能添加此功能（奇怪的是，gzip没有这个选项，但如果必须，我愿意编写自己的压缩程序）。

从一个消息来源来看，即使Z_FULL_FLUSH也不是完美的解决方案...不仅它不受所有gzip存档的支持，而且在档案中检测同步点的想法可能会产生误报（由于与同步点的幻数巧合或者由于Z_SYNC_FLUSH也会产生同步点但不能用于随机访问）。

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

编辑：如我所述，我希望在压缩数据中进行二分查找。我不需要定位到特定的（未压缩的）位置——只需要在压缩文件中以一些粗略的粒度进行搜索。我只需要支持类似于“从这个压缩文件的大约50％（25％、12.5％等）处开始解压数据”的功能。

10个回答
36
看看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许可证。
2
我通过使用gzip同步/刷新点来解决了我的问题，这使我能够很好地浏览文件（进行二进制搜索）。我不得不在libz的基础上编写自己的类似gzip的程序，因为标准的gzip由于某种原因没有包括写同步点的功能。无论如何，在我的情况下，这非常有效，因为我不关心是否能够“从第10000个字节开始阅读”，而只是“从文件中途开始阅读”。 Dictzip方法看起来非常有趣，可以解决比我的问题更普遍的问题。 - John Zwinck
1
@TroyJ：如果您控制文件的编写，那么误报情况不会经常发生，而且当它们发生时，您可能会知道，因为从这些点进行解压缩将失败（然后您可以重试）。如果您无法控制编写，则情况会更加棘手：标准gzip编写程序将发出大量误报和零个真正的报告。您可以在放弃之前尝试N次；根据我的经验，N只需要是一个小数字（小于10），系统就可以相当准确。 - John Zwinck
2
我编写了类似于stdio的库和多线程压缩实用程序。源代码可在Github上获取：https://github.com/hoxnox/csio - hoxnox
1
@AdamKatz：我不能分享代码，部分原因是它与专有数据格式紧密集成，所以没有人能直接使用它。然而，这个想法是在压缩时每隔一段时间写入“完整同步点”，比如说每MB一次，然后让读者扫描这些点并验证消息在解压缩时是否正确。困难主要在于（1）标准的gzip工具没有选项可以插入完整的同步点，（2）您需要编写自己的启发式算法来验证在恢复时有效的消息。 - John Zwinck
1
@AdamKatz - 由csio或dictzip创建的gzipped数据 - hoxnox
显示剩余7条评论
19

我不知道任何一种压缩文件格式可以支持在未解压的数据中随机访问特定位置(除了多媒体格式)，但你可以自己创建。

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

仍然，我认为最好的解决方案是将文件分成您选择的块，然后使用一些存档程序(如zip或rar)进行压缩，它支持对存档中单个文件进行随机访问。

我不需要寻找特定的未压缩位置——只需要在压缩文件中以一些粗略的粒度进行随机搜索。如果我只能说“从这里开始解压数据，在这个文件中大约700MB”，那也完全没有关系。 - John Zwinck
@John Zwinck：请将您的评论作为更新添加到您的问题中。请注意，由于数据的可变压缩（我压缩的一些东西会缩小约94％左右 - 通常情况下，除非它只缩小了约50％左右），您估计何时开始解压缩可能会非常难以预测。 - Jonathan Leffler
请注意，由于bzip2块边界位于字节内部，因此这会使事情变得复杂，但是这是可行的，只需要更多的簿记工作。 - Alex Reynolds
11
.xz文件格式 (使用LZMA压缩)似乎支持此功能:

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

这对您的目的应该足够了。缺点是liblzma API（用于与这些容器交互）的文档不太完整，所以可能需要一些努力来弄清楚如何随机访问块。
4
是的，例如 pixz 用于随机访问 tar 存档中的成员，或者 nbdkit 用于将 xz 压缩文件作为 nbd 设备进行访问（以便能够挂载压缩的磁盘镜像）。qcow2（qemu 磁盘镜像的本地格式）是另一种允许压缩和随机访问的格式。 - Stephane Chazelas
8

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

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

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

7
1
请注意：tabix 可以通过生物坐标（例如染色体 + 核苷酸位置）进行索引和访问，而 grabix 则可以通过文件坐标（例如行号）进行索引和访问。它们都非常适合表格数据，但对于其他数据可能会有些棘手。 - jena
1
顺便提一下，Heng Li在他的博客上讲述了bgzip和BGZF格式的一个不错的背景故事，并且还有一个时间轴记录了这些想法的发展历程。令人惊叹的是，这一切都在两个月内完成了。 - jena
4
因为无损压缩在某些领域的效果比其他领域更好，如果将压缩数据存储到方便长度BLOCKSIZE的块中，即使每个块具有完全相同数量的压缩字节，一些压缩块将扩展为比其他块更长的明文片段。
你可以查看由Nivio Ziviani、Edleno Silva de Moura、Gonzalo Navarro和Ricardo Baeza-Yates在2000年11月的《计算机》杂志上发表的文章《Compression: A Key for Next-Generation Text Retrieval Systems》，链接为http://doi.ieeecomputersociety.org/10.1109/2.881693。
他们的解压器需要1、2或3个压缩数据字节，并（使用词汇表）解压成一个完整单词。可以直接搜索压缩后的文本中的单词或短语，这事实上比搜索未经压缩的文本更快。
他们的解压器允许您指向文本中的任何单词并以正常（字节）指针开始立即解压该点。
您可以为每个单词分配一个独特的2字节代码，因为您的文本中可能有不到65,000个独特的单词。(《圣经》中有近13,000个独特的单词)。即使有超过65,000个单词，也很容易将前256个双字节代码“单词”分配给所有可能的字节，这样您就可以拼写出不在65,000个最常见的“单词和短语”的词汇表中的单词。(通过将频繁出现的单词和短语压缩成两个字节来获得压缩效果，通常值得偶尔用两个字节拼写一个字母的单词来扩展)。有多种方法可以选择一个“常用单词和短语”的词汇表，以获得足够的压缩。例如，您可以调整LZW压缩器，将其使用超过一次的“短语”转储到一个词汇表文件中，每行一个短语，并在所有数据上运行它。或者你可以任意地将未压缩的数据分成5个字节的短语，在一个词汇表文件中，每行一个短语。或者你可以将未压缩的数据分解成实际的英语单词，并将每个单词(包括单词开头的空格)放入词汇表文件中。然后使用“sort --unique”来消除该词汇表文件中重复的单词。(挑选完美的“最优”词汇表仍被认为是NP-hard吗？)
将词典存储在巨大压缩文件的开头，填充到某个方便的BLOCKSIZE，然后从那里到文件末尾存储压缩文本——一系列由两个字节组成的“单词”。 搜索器可能会在解压缩期间将其读取一次并以某种快速解码格式保存在RAM中，以加快将“双字节代码”解压缩为“可变长度短语”的速度。 我的第一版草稿将从每个短语列表开始，每行一个简单的短语列表，但是您稍后可以切换到使用某种增量编码或zlib将词典以更紧凑的形式存储。

您可以选择任何随机偶数字节偏移量进入压缩文本，并从那里开始解压缩。 我认为不可能制作出更精细的随机访问压缩文件格式。

4

我不知道是否已经提到过，但是 Kiwix 项目 在这方面做出了巨大的贡献。通过他们的Kiwix程序，他们提供对 ZIM文件归档 的随机访问。良好的压缩效果。该项目最初起源于对维基百科的离线副本的需求（包括所有媒体，其未经压缩的形式已达到100 GB以上）。他们已成功将一个25 GB的文件（维基百科的单个文件体，没有大部分媒体）压缩为仅有8 GB的zim文件归档。而且通过Kiwix程序，您可以调用维基百科的任何页面及其所有相关数据，速度比上网冲浪还要快。

尽管Kiwix程序是围绕维基百科数据库结构构建的技术，但它证明了您可以同时具有优秀的压缩比和随机访问功能。

4

两个可能的解决方案：

  1. 让操作系统处理压缩，创建并挂载一个压缩文件系统 (SquashFS、clicfs、cloop、cramfs、e2compr或其他)，包含所有你的文本文件，并且在应用程序中不对压缩进行任何处理。

  2. 直接在每个文本文件上使用clicfs(一个文本文件对应一个clicfs)，而非压缩文件系统映像。将“mkclicfs mytextfile mycompressedfile”视为“gzip <mytextfile >mycompressedfile”，将“clicfs mycompressedfile directory”视为通过文件“directory/mytextfile”随机访问数据的一种方式。

哇，你对我的一个老问题提出了有趣的想法。你的第一个建议（squashfs）并不完全符合我的要求，因为它对远程存储有影响：使用压缩文件系统和压缩的SSH连接，你需要解压数据并重新压缩以便通过网络发送。令人惊奇的是，如果有一种像压缩文件系统那样可以通过NFS共享的东西就好了。我猜这就是你的clicfs建议可能会产生的结果。关于clicfs的文档似乎很难找到（至少在我快速搜索时是这样），但它很有前途。谢谢。 - John Zwinck
从原始问题的信息来看，SquashFS 正是你所要求的。当然，如果你不必在网络上进行解压缩和重新压缩，那会更理想，但如果你的 SquashFS 设置了快速解压算法，那么解压缩+压缩的总成本可能可以忽略不计。 - malthe
3
我不确定在你的具体情况下是否实用，但是你可以将每个大文件压缩成小文件，比如每个文件10 MB。这样，你就会得到一堆文件：file0.gz、file1.gz、file2.gz等等。基于原始大文件中给定的偏移量，在名为"file" + (offset / 10485760) + ".gz"的文件中进行搜索。未压缩存档中的偏移量将是offset % 10485760。
3
你可以对它们全部进行打包，最终得到一个 .GZ.TAR 文件。 :) - Vilx-
那肯定可以使事情更加整洁。我只是想要简单，但你的建议很好 :-) - William Brendel
2
.gz.tar并不是真正的随机访问，因为您必须跳过所有头文件才能访问一个文件。 - jpalecek
嗯，是和不是。使用固定大小块（在这种情况下为10 MB），您将不必遍历标头列表。这取决于tar会按字母顺序排序文件的假设（在GNU-land中恰好是这种情况）。 - William Brendel
是的，但是文件就不会被压缩了（10 MB 未压缩以使您的索引表达式起作用，10 MB 压缩以使 tar 直接访问起作用）。将任何东西压缩到固定大小很难，尽管您可以将该大小设置得足够大，并使用稀疏文件处理多余空间。 - jpalecek
显示剩余4条评论
1

我是一种开源工具的作者，用于压缩特定类型的生物数据。这个工具叫做starch，它将数据按染色体分割，并使用这些分割作为索引，以便在更大的存档中快速访问压缩数据单元。

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

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

对于您的情况，您可以将（10 MB或其他大小的）偏移量存储在自定义存档格式的头文件中。您解析头文件，检索偏移量，并通过current_offset_sum+header_size逐步使用fseek浏览文件。

更新了 Github 网站的链接。 - Alex Reynolds
BEDOPS 还引入了一种新颖的无损压缩格式，称为 Starch，可以将整个基因组 BED 数据集压缩至其原始大小的约 5%（BAM 数据集压缩至其原始大小的约 35%）。这太神奇了，你应该宣传你的工具。 - tommy.carstensen
我们写了一篇论文：http://bioinformatics.oxfordjournals.org/content/28/14/1919.abstract - Alex Reynolds
Samtools faidx的压缩效果远不如Starch，并且需要保留第二个包含基因组数据的文件，但它提供了更精细的索引，因此更受欢迎。如果您需要挤出空间或者正在进行整个基因组的工作并希望通过染色体并行化任务，则Starch非常有效。我正在开发“Starch 2”，它将提供基于碱基水平的区间查询，但可能需要几个月的时间。 - Alex Reynolds
将bam压缩到35%甚至比cram格式更好。回家后我一定要读这篇论文。我无法相信这种方法没有被广泛使用。 - tommy.carstensen
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接