68

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

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

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

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

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

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

4

13 回答 13

35

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

其手册页的摘录：

dictzip使用gzip (1) 算法 (LZ77) 以与 gzip 文件格式完全兼容的方式压缩文件。gzip 文件格式的扩展（额外字段，在 RFC 1952 的 2.3.1.1 中描述）允许将额外数据存储在压缩文件的标题中。gzip 和 zcat 等程序将忽略这些额外数据。但是，[dictzcat --start] 将利用这些数据对文件执行伪随机访问。

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

更新：

我改进了 dictzip，使其没有文件大小限制。 我的实现在 MIT 许可下。

于 2010-10-24T19:48:35.027 回答
20

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

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

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

于 2009-01-09T23:19:55.317 回答
10

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

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

这应该足以满足您的目的。一个缺点是 liblzma 的 API（用于与这些容器交互）似乎没有很好的文档记录，因此可能需要一些努力来弄清楚如何随机访问块。

于 2014-05-03T11:53:47.397 回答
7

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

（我正在寻找 7zip 的东西）

于 2010-12-17T01:42:32.667 回答
6

bgzip可以以可索引的变体压缩文件gzip（并且可以通过 解压缩gzip）。tabix这与索引器一起用于一些生物信息学应用程序。

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

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

于 2016-02-04T13:11:23.670 回答
5

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

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

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

于 2019-07-24T21:10:31.430 回答
3

我不确定这在您的确切情况下是否实用，但是您不能将每个大文件压缩成较小的文件，例如每个 10 MB 吗？您最终会得到一堆文件：file0.gz、file1.gz、file2.gz 等。基于原始大文件中的给定偏移量，您可以在名为"file" + (offset / 10485760) + ".gz". 未压缩存档中的偏移量为offset % 10485760.

于 2009-01-09T22:41:07.283 回答
3

因为无损压缩在某些区域比其他区域效果更好，如果您将压缩数据存储到方便长度 BLOCKSIZE 的块中，即使每个块具有完全相同数量的压缩字节，某些压缩块将扩展为比其他块更长的明文.

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

他们的解压器将 1、2 或 3 个完整字节的压缩数据解压缩（使用词汇表）成一个完整的单词。可以直接在压缩文本中搜索单词或短语，这比搜索未压缩文本还要快。

他们的解压器让你可以用一个普通的（字节）指针指向文本中的任何单词，并从那个点立即开始解压。

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

将词典存储在巨大压缩文件的开头，将其填充到某个方便的 BLOCKSIZE，然后存储压缩文本——一系列两字节“单词”——从那里到文件末尾。大概搜索者会读一遍这个词典，并在解压缩过程中将它以某种快速解码的格式保存在 RAM 中，以加快将“两字节代码”解压缩为“可变长度短语”的速度。我的初稿会从每个短语列表一个简单的一行开始，但您稍后可能会切换到使用某种增量编码或 zlib 以更压缩的形式存储词典。

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

于 2010-08-07T20:52:23.410 回答
3

两种可能的解决方案：

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

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

于 2012-02-10T16:52:46.720 回答
1

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

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

于 2013-04-08T03:14:55.180 回答
1

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

于 2015-09-04T07:26:19.120 回答
0

razip 支持具有比 gzip/bzip2 更好的性能的随机访问，而 gzip/bzip2 必须针对这种支持进行调整 - 以“正常”随机访问为代价来减少压缩：

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

于 2011-08-23T15:07:36.277 回答
0

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

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

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

对于您的情况，您可以将（10 MB 或其他）偏移量存储在自定义存档格式的标头中。您解析标头，检索偏移量，并通过+递增地fseek通过文件。current_offset_sumheader_size

于 2011-10-26T21:02:04.010 回答