6

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

提前致谢

4

5 回答 5

9

大多数文本文件都使用LZ 系列算法之一进行压缩，该算法将字典编码器与诸如 Huffman 之类的熵编码器结合在一起。

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

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

第二个建议是对英语单词进行 Huffman 编码，而忘掉 Dictionary Coder 部分。每个英语单词都映射到一个唯一的无前缀代码。

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

于 2011-04-06T06:51:56.680 回答
5

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

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

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

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

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

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

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

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

于 2011-07-22T21:17:06.367 回答
3

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

于 2011-04-06T06:42:36.393 回答
2

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

于 2011-04-06T06:40:31.747 回答
1

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

于 2017-12-28T06:52:45.857 回答