在压缩文本文件中快速搜索

Question

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

在此先感谢

Answer 1

大多数文本文件都使用LZ-family算法进行压缩，该算法将Dictionary Coder和Entropy Coder（如Huffman）组合在一起。

由于字典编码器依赖于不断更新的“字典”，其编码结果取决于历史（从输入数据到当前符号的字典中的所有代码），所以它不是可能跳到某个位置并开始解码，而不先解码所有先前的数据。

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

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

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

Answer 2

我可能是完全错误的在这里，但我不认为会是搜索一个给定的字符串没有文件解码的可靠方法。我对压缩算法的理解是，对应于给定字符串的比特流将非常依赖于未压缩文件中的字符串之前的内容。您可能能够找到给定文件中特定字符串的给定编码，但我很确定它们在文件之间不一致。

Answer 3

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

Answer 4

在压缩文件中搜索文本可能比在未压缩文本文件中搜索同样的东西快。我见过

一种压缩技术，即牺牲，以一定的空间，做到快速搜索：

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

特别地，搜索一个字通常会减少到比较在压缩的文本，这是比搜索原始文本字更快的16位索引，因为

• 每个比较需要比较较少的字节数 - 2，而不是那个字中包含的字节数，并且
• 由于压缩文件更短，因此我们正在进行较少的比较。

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

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

对于更复杂的技术，你可能看

• MG4J：Managing Gigabytes for Java
• "Managing Gigabytes: Compressing and Indexing Documents and Images"由伊恩·H·威滕，阿利斯泰尔·莫法特，和Timothy C.贝尔

Answer 5

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