快速搜索压缩文本文件

Question

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

提前致谢

Answer 1

大多数文本文件都是使用LZ-family算法之一压缩的，这些算法将Dictionary Coder与像Huffman这样的Entropy Coder结合在一起。

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

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

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

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

Answer 2

您不太可能在压缩文件中搜索未压缩的字符串。我猜你最好的选择之一是以某种方式索引文件。或许使用Lucene？

Answer 3

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

我见过的一种压缩技术为了快速搜索而牺牲了一些空间：

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

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

• 每次比较都需要比较更少的字节 - 2，而不是那个字中有多少字节，和
• 我们进行的比较较少，因为压缩文件较短。

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

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

对于更复杂的技术，您可能会看一下

• MG4J：Managing Gigabytes for Java
• qanxswpoi，Ian H. Witten，Alistair Moffat和Timothy C. Bell

Answer 4

我可能在这里完全错了，但我认为没有可靠的方法来搜索给定的字符串而不解码文件。我对压缩算法的理解是，对应于给定字符串的比特流很大程度上取决于未压缩文件中字符串之前的内容。您可能能够在给定文件中找到特定字符串的给定编码，但我很确定它们在文件之间不一致。

Answer 5

这是可能的，并且可以非常有效地完成。关于这个主题有很多令人兴奋的研究，更正式地称为简洁的数据结构。我建议考虑一些主题：小波树，FM索引/ RRR，简洁后缀数组。您还可以有效地搜索霍夫曼编码的字符串，正如许多出版物所证明的那样。