假设我有一个按其中一个字段排序的常规固定宽度文件。鉴于我知道记录的长度，我可以使用 lseek 实现二进制搜索来查找具有与给定值匹配的字段的记录，而无需读取整个文件。
现在的困难是文件被压缩了。是否可以在不完全膨胀文件的情况下做到这一点？如果不使用 gzip。是否有任何支持这种行为的压缩？
问问题
442 次
6 回答
3
bzip2 文件格式由多个独立压缩的块组成。如果你愿意在你的 bzip2 文件旁边维护一个索引，你可以知道去哪里寻找。
注意：这是问题的副本：
这些回答了相同的问题，但也将 BGZF 标识为与 gzip 兼容的输出格式，其中插入了同步点以重置压缩状态。
于 2010-05-03T14:52:51.993 回答
2
这对于使用 zip 和衍生文件压缩的文件是完全不可能的。这些基于滚动字典窗口，通常在此之上对输出代码的最高有效位进行某种基于缓冲区的压缩。底线是 zip 文件中的特定字节序列在没有上下文的情况下毫无意义。
如果您希望能够从压缩文件中随机读取特定记录，则必须独立压缩每条记录，然后在文件中建立索引。根据您的数据，这可能会使压缩步骤变得毫无价值。
于 2010-04-24T00:41:10.493 回答
2
我知道几乎所有压缩算法都在块模式下工作，这意味着不可能进行随机搜索。即使是不使用初始字典的 LZMA 也需要顺序解压缩。
流压缩通常意味着自适应有损压缩，带有一些重置状态（或实际切割成块）的键。细节更复杂。
现在有几个想法可以解决这个问题：
- 创建索引：就像打开 ZIP 时一样，您可以看到其中的所有文件
- 将压缩文件切成块，然后在每个块中使用二进制搜索（实际上类似于第一个）
- 在内存中解压缩，但实际上丢弃任何数据，直到找到要查找的数据的开头。
最后一种方式适用于小型压缩文件，block 方式适用于较大的压缩文件。您可以将两者混合使用。
PS：输入中的fixed with，不代表压缩后的文件会被fixed with。所以这是一个非常无用的信息。
于 2010-04-27T15:45:02.903 回答
1
在Wernight 所说的基础上，您可以在 gzip 之前将文件拆分为许多固定大小的子文件。您的二进制搜索可以从搜索包含范围的子文件开始，然后只需要解压缩小子文件而不是整个文件。您可以通过在包含每个子文件的第一行的存档中创建上层文件来进行优化。
于 2010-04-27T16:19:18.810 回答
1
继续 Liudvikas Bukys 所说的：如果您的压缩块具有唯一的标头，则不需要索引。这类似于如何在某些压缩视频格式中进行搜索。你寻找一个点并寻找下一个标题。不过，这确实需要可靠的验证（使用校验和），因为可能会出现错误识别。
于 2010-05-03T15:34:01.117 回答
1
你想要的是可搜索的压缩；dict 服务器具有与 gzip 格式兼容的 dictzip，因为它将可查找的内容存储在标头中的 gzip 扩展中，而 sleuth 工具包具有 sgzip，而不是因为它在每个块的开头存储块长度
于 2010-08-05T13:15:20.817 回答