在压缩排序的固定宽度文件内搜索

Question

假设我有一个固定宽度的文件，该文件在其中一个字段上排序。考虑到我知道记录的长度，我可以使用lseek实现二分查找，以查找具有匹配给定值的字段而不必读取整个文件的记录。

现在的困难是，该文件是gzip压缩。是否有可能做到这一点，而不是完全膨胀文件？如果没有使用gzip。有没有支持这种行为的压缩？

Answer 1

这是完全不可能与拉链和衍生物压缩的文件。这些基于滚动字典窗口，通常对输出代码的最高有效位进行基于缓冲区的压缩。底线是压缩文件中的特定字节序列在没有上下文的情况下是没有意义的。

如果你希望能够随机读取特定记录了一个压缩文件，你可以分别压缩每个记录，然后有一个索引文件。根据你的数据，这可能会使压缩步骤变得毫无价值。

Answer 2

几乎所有的压缩算法我知道在块模式下工作，这意味着随机查找是不可能的。即使不使用初始字典的LZMA也需要连续的解压缩。

流压缩通常意味着自适应有损压缩一些密钥复位状态（或者实际上切成块）。细节更复杂。

现在这里有一对夫妇的想法来解决这个问题：

• 创建索引：就像当你打开ZIP，你可以看到所有文件，也
• 削减你压缩文件成块，然后在每个块内使用二进制搜索（实际上与第一个块相似）
• 解压缩到内存中但实际上放弃任何数据，直到找到您要查找的数据的开头f要么。

最后一种方法适用于小型压缩文件，块方法适用于大型压缩文件。你可以混合这两个。

PS：利用固定于输入，并不意味着压缩文件将被固定。所以这是一个非常无用的信息。

Answer 3

建立在什么Wernight said，您可以将您的文件gzip压缩之前分割成许多固定大小的子文件。你的二分查找可以通过搜索包含该范围的子文件开始，那么它只需要解压缩小的子文件而不是整个东西。您可以通过在包含每个子文件的第一行的归档中创建一个上层文件来进行优化。

Answer 4

bzip2的文件格式由多个独立地压缩块。 如果您愿意保留与您的bzip2文件并列的索引，您可以知道在哪里找到。

注：这是一个问题重复：

• Compression formats with good support for random access within archives?
• Random access gzip stream
• Multi-part gzip file random access (in Java)

这些回答同样的问题，而且身份BGZF作为一个gzip兼容输出格式，插入同步点以重置压缩状态。

Answer 5

继续在什么Liudvikas Bukys说：如果你的压缩块有一个独特的头，你不需要索引。这与如何在某些压缩视频格式中查找相似。你寻找一个点并寻找下一个标题。这并不需要强大的验证（使用校验）虽然，因为误识别是可能的。

Answer 6

你想要的是可搜索的压缩;所述字典服务器具有dictzip这与gzip格式兼容，因为它存储它在标题和侦探套件一个gzip延伸seektable具有sgzip这不是因为它在每个块的开头存储块长度