c++ - 如何高效解压哈夫曼编码文件

Question

我发现很多问题都在问这个问题，但有些解释很难理解，我不太理解如何有效解压缩文件的概念。我发现了这些相关问题: Huffman code with lookup table How to decode huffman code quickly?

但是我看不懂这个解释。我知道如何定期编码和解码霍夫曼树。现在在我的压缩程序中，我可以将以下任何信息写入文件象征霍夫曼代码(无符号长)霍夫曼编码长度

我打算做的是获取一个文本文件，将其分成小文本文件并单独压缩，然后通过发送所有小压缩文件及其各自的查找表来解压缩该文件(不知道如何执行此操作)部分)到 Nvidia GPU 以尝试使用某种查找表并行解压缩文件。

我有 3 个问题:我应该在文件头中写入哪些信息来构造查找表？如何从文件中重新创建此表？如何使用它快速解码霍夫曼编码文件？

Answer 1

不要费心自己写，除非这是一个教学练习。使用 zlib , lz4 ，或其他几个免费的压缩/解压缩库中的任何一个，这些库的测试比你能做的任何事情都要好得多。

您只是在谈论霍夫曼编码，表明您只会获得可用压缩的一小部分。提到的库中的大部分压缩来自匹配字符串。查找“LZ77”。

关于高效的哈夫曼解码，可以看看zlib的inflate是怎么做的。它为代码的最高九位创建一个查找表。表中的每个条目都有一个符号和该代码的位数(小于或等于九)，或者如果提供的九位是更长代码的前缀，则该条目有一个指向另一个表的指针来解析其余代码和该辅助表所需的位数。 (有几个这样的辅助表。)如果代码长度小于九，则同一符号有多个条目。事实上，一个 n 位代码有 2^9-n 个条目。

因此，要解码，您需要从输入中获取九位并从表中获取条目。如果它是一个符号，那么您从流中删除为代码指示的位数并发出该符号。如果它是指向辅助表的指针，则从流中删除九位，获取表指示的位数，并在那里查找。现在你肯定会得到一个要发出的符号，以及要从流中删除的剩余位数。