1

我发现很多问题都在问这个问题,但有些解释很难理解,我不太了解如何有效解压缩文件的概念。我发现了这些相关问题: Huffman code with lookup table 如何快速解码霍夫曼代码?

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

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

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

4

1 回答 1

2

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

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

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

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

于 2015-04-27T17:26:31.720 回答