如何高效解压哈夫曼编码文件 [英] How to efficiently decompress huffman coded file

问题描述

我发现了很多问这个问题的问题，但其中一些解释很难理解，我也不能完全理解如何有效地解压缩文件的概念。 我发现了这些相关的问题： Huffman code with lookup table How to decode huffman code quickly?

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

我计划做的是获取一个文本文件，将其分离为小的文本文件并分别压缩每个文件，然后通过将所有小的压缩文件与它们各自的查找表(不知道如何做这一部分)一起发送到Nvidia GPU来尝试使用某种查找表并行解压缩文件来解压缩该文件。

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

推荐答案

不要费心自己写，除非这是一种说教练习。使用zlib、lz4或其他几个免费的压缩/解压缩库中的任何一个，这些库比您所能做的任何事情都要经过更好的测试。

您只是在谈论Huffman编码，这表明您将只获得可用压缩的一小部分。文中提到的库中的大多数压缩都来自匹配字符串。查找"LZ77"。

至于高效的哈夫曼解码，您可以看看zlib的Expate是如何做到的。它为代码的最重要的九位创建查找表。表中的每个条目具有用于该代码的符号和位数(小于或等于9)，或者如果所提供的9位是较长代码的前缀，则该条目具有指向另一个表的指针，以解析代码的其余部分和该辅助表所需的位数。(有几个这样的辅助表。)如果代码长度小于9，则同一符号有多个条目。事实上，n位码有2个⁹多个条目。

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

这篇关于如何高效解压哈夫曼编码文件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！