我已经使用霍夫曼算法实现了文件压缩，但我遇到的问题是要启用压缩文件的解压缩，使用的编码树或代码本身也应该写入文件。问题是：我该怎么做？在压缩文件的开头编写编码树的最佳方法是什么？
问问题
3907 次
9 回答
5
在Basic Compression Library (BCL)中有一个非常标准的 Huffman 编码实现，包括一个将树写入文件的递归函数。看看霍夫曼.C。它只是按顺序写出叶子，以便解码器可以重建同一棵树。
BCL 也很好，因为其中还有一些其他非常简单的压缩算法。如果您需要推出自己的算法，这非常方便。
于 2009-05-24T09:11:54.530 回答
3
首先，您是否考虑过使用标准压缩流（如 .net 中的 GZipStream）？
关于如何/在何处写入数据，您可以使用 Seek 操作 Streams 位置（甚至以这种方式保留空间）。如果您提前知道 Tree 的大小，则可以在该位置之后开始编写。但是您可能希望将编码树放置在实际数据之后，并确保您知道从哪里开始。即前面预留一点空间，写压缩数据，记录位置，写树，走到最前面写出位置。
于 2009-05-24T09:05:40.610 回答
2
假设您压缩 8 位符号（即字节）并且算法是非自适应的，最简单的方法不是存储树，而是存储值的分布。例如，通过存储您找到字节 0 的频率、字节 1 的频率、...、字节 255 的频率。然后在读回文件时，您可以重新组装树。这是最简单的解决方案，但需要最多的存储空间（例如，要覆盖大文件，每个值需要 4 个字节，即 1kb）。
您可以通过不准确存储在文件中找到每个字节的频率来优化这一点，而是将值标准化为 0..255（0 = 找到最少，...），在这种情况下，您只需要保存 256 个字节. 基于这些值重新组装树将产生相同的树。（正如 Edmund 和问题759707所指出的那样，这不会起作用- 请参阅那里以获取更多链接和问题的答案）
PS：正如 Henk 所说，使用 seek() 可以让您在文件开头保留空间以便稍后存储值。
于 2009-05-24T09:13:44.947 回答
2
大多数实现都使用规范的霍夫曼编码。您只需以紧凑的方式存储符号长度。更进一步的实现：shcodec。另一种方法是使用半静态霍夫曼编码（定期重新缩放），然后您不必存储任何树。
于 2009-06-14T19:53:00.897 回答
1
由于霍夫曼树中的每个节点要么是一个有两个孩子的分支，要么是一个叶子，因此您可以使用单个位来明确表示每个节点。对于叶子，紧跟该节点的 8 位。
例如对于这棵树：
/\
/\ A
B /\
C D
您可以存储 001[B]01[C]1[D]1[A]
（事实证明这正是前面发布的 huffman.c 示例中发生的情况，但不是上面描述的方式）。
于 2009-05-24T09:28:20.597 回答
1
不要将代码树写入文件，而是写入每个字符被发现的频率，以便解压缩程序可以生成相同的树。
于 2009-05-24T09:07:58.873 回答
1
最天真的解决方案是预先解析压缩树并将 256 个值写入文件的标题中。
于 2009-05-24T09:13:28.740 回答
0
您是否尝试过自适应霍夫曼编码？乍一看，似乎根本不需要发送树，但需要做更多工作来优化和同步树。
于 2011-12-07T17:19:07.943 回答
0
最好发送字符的频率并在接收端构建树。对于固定字母表，此数据将具有恒定大小。我想这必须是可序列化的并放入文件中。发送树取决于它的实现，对于我所尝试的，基于数组的方法会导致更多的内存未用于树，因为大多数时候树可能不是平衡树。如果树是平衡的，那么数组表示将生成最佳选项。
于 2011-12-07T17:07:00.400 回答