快速搜索压缩文本文件

Question

我需要能够在压缩的大量文件(.txt)中搜索文本.压缩可以改为其他东西,甚至可以变成专有的.我想避免解压缩所有文件并压缩(编码)搜索字符串并在压缩文件中搜索.这应该可以使用霍夫曼压缩与所有文件的相同码本.我不想重新发明轮子,所以..任何人都知道,做这样的事情或霍夫曼算法实现和测试,或者一个更好的主意库？

提前致谢

Answer 1

大多数文本文件都是使用LZ系列算法压缩的,这些算法将字典编码器与熵编码器(如Huffman)结合在一起.

因为字典编码器依赖于不断更新的"字典",其编码结果取决于历史(字典中从输入数据直到当前符号的所有代码),因此无法跳转到某个位置并开始解码,而不首先解码所有先前的数据.

在我看来,你可以使用一个zlib流解码器,它可以随时返回解压缩数据,而无需等待整个文件解压缩.这不会节省执行时间,但会节省内存.

第二个建议是对英语单词进行霍夫曼编码,并忘记字典编码器部分.每个英语单词都映射到一个唯一的无前缀代码.

最后,@ SHODAN给出了最明智的建议,即索引文件,压缩索引并捆绑压缩文本文件.要进行搜索,只需解压缩索引文件并查找单词.这实际上是对单词执行霍夫曼编码的改进 - 一旦找到单词的频率(为了最佳地分配前缀代码),您已经构建了索引,因此您可以保留索引以进行搜索.

Answer 2

在压缩文件中搜索文本比在未压缩文本文件中搜索相同内容更快。

我见过的一种压缩技术会牺牲一些空间来进行快速搜索：

• 维护一个字典，其中包含文本中每个单词的 2^16 个条目。为文字字节保留前 256 个条目，以防您遇到字典中没有的单词——即使许多大型文本的唯一单词少于 32,000，因此它们永远不需要使用这些文字字节。
• 通过为每个单词替换 16 位字典索引来压缩原始文本。
• （可选）在两个单词由单个空格字符分隔的正常情况下，丢弃该空格字符；否则将单词之间的字符串中的所有字节作为特殊的“单词”（例如，“.”和“，”和“\n”）放入字典中，并标记为“无默认空格”属性，然后“压缩" 将这些字符串替换为相应的字典索引。
• 通过以相同的方式压缩短语来搜索单词或短语，并以与在原始文本中搜索原始字符串完全相同的方式在压缩文本中搜索压缩的字节字符串。

特别是，搜索单个单词通常简化为比较压缩文本中的 16 位索引，这比在原始文本中搜索该单词要快，因为

• 每次比较都需要比较较少的字节——2，而不是该字中有多少字节，并且
• 我们做的比较较少，因为压缩文件更短。

某些类型的正则表达式可以转换为另一种直接在压缩文件中查找项目的正则表达式（也可能还会发现一些误报）。这样的搜索也比在原始文本文件上使用原始正则表达式进行的比较更少，因为压缩文件更短，但通常每个正则表达式比较都需要更多的工作，因此它可能会也可能不会比原始正则表达式操作更快原文。

（原则上你可以用可变长度的霍夫曼前缀代码替换固定长度的 16 位代码，正如 rwong 提到的那样——生成的压缩文件会更小，但处理这些文件的软件会慢一点，更多复杂的）。

对于更复杂的技术，您可以查看

• MG4J：管理 Java 的千兆字节
• “管理千兆字节：压缩和索引文档和图像”，作者：Ian H. Witten、Alistair Moffat 和 Timothy C. Bell