我使用哈夫曼算法实现了文件压缩，但我遇到的问题是为了使压缩文件能够解压缩，使用的编码树或者编码本身也应该被写入文件中。问题是：我该如何做呢？在压缩文件开头写入编码树的最佳方法是什么？
霍夫曼压缩算法
3
- agnieszka
2
2重复的问题：https://dev59.com/uXRA5IYBdhLWcg3w_C8w - Lasse V. Karlsen
3实际上这是一个重复的项目。抱歉。 - agnieszka
9个回答
5
在基本压缩库（BCL）中有一个相当标准的Huffman编码实现，包括一个递归函数，将树写入文件。请查看huffman.C。它只是按顺序写出叶子，以便解码器可以重建相同的树。
BCL也很好，因为其中还有一些其他相当简单的压缩算法片段。如果您需要自己编写算法，它非常方便。
BCL也很好，因为其中还有一些其他相当简单的压缩算法片段。如果您需要自己编写算法，它非常方便。
- Todd Gamblin
3
首先，你考虑过使用标准压缩流（例如 .net 中的 GZipStream）吗？
关于如何/在哪里编写您的数据，您可以使用 Seek 操作流的位置（甚至可以通过此方式保留空间）。如果您事先知道树的大小，则可以从该位置后开始编写。但是，您可能希望在实际数据之后定位编码树，并确保您知道其起始位置。即，在前面保留一点空间，编写压缩数据，记录位置，编写树，到前面并写出位置。
关于如何/在哪里编写您的数据，您可以使用 Seek 操作流的位置（甚至可以通过此方式保留空间）。如果您事先知道树的大小，则可以从该位置后开始编写。但是，您可能希望在实际数据之后定位编码树，并确保您知道其起始位置。即，在前面保留一点空间，编写压缩数据，记录位置，编写树，到前面并写出位置。
- H H
2
假设您压缩的是8位符号（即字节），并且算法是非自适应的，最简单的方法是存储值的分布而不是树。例如，通过存储找到字节0的频率，找到字节1的频率，...，找到字节255的频率来实现。然后，在读回文件时，可以重新组装树。这是最简单的解决方案，但需要最多的存储空间（例如，为了覆盖大型文件，每个值需要4个字节，即1kb）。
您可以通过将值规范化为0..255（0 = 找到最少，...）而不是精确存储文件中找到每个字节的频率来优化此过程，在这种情况下，您只需要保存256个字节。基于这些值重新组装树将导致相同的树。（正如Edmund和问题759707所指出的那样，这不起作用-请参见那里以获取有关您的问题的更多链接和答案）
另外，正如Henk所说，使用seek()允许您在文件开头保留空间以便稍后存储值。
您可以通过将值规范化为0..255（0 = 找到最少，...）而不是精确存储文件中找到每个字节的频率来优化此过程，在这种情况下，您只需要保存256个字节。基于这些值重新组装树将导致相同的树。（正如Edmund和问题759707所指出的那样，这不起作用-请参见那里以获取有关您的问题的更多链接和答案）
另外，正如Henk所说，使用seek()允许您在文件开头保留空间以便稍后存储值。
- dseifert
1
据我所知，使用哈夫曼编码时，字符频率实际上会影响到生成的树形结构，仅仅排名是不够的。例如，在输入中，如果A出现的次数比其他字母多得多，你可能会期望0=A，但如果A和B都相当频繁地出现，你将得到00=A和01=B的结果。 - Edmund
1
不要将代码树写入文件，而是写下每个字符出现的频率，这样解压程序就可以生成相同的树。
- Erich Kitzmueller
1
最朴素的解决方案是按照前序遍历解析压缩树，并将256个值写入文件头。
- Blindy
1
由于哈夫曼树中的每个节点都是具有两个子节点的分支或叶子，因此可以使用单个位来明确表示每个节点。对于叶子节点，紧随其后跟随该节点的8位。
例如，对于这棵树：
/\
/\ A
B /\
C D
你可以存储001[B]01[C]1[D]1[A]
（事实证明，这正是之前发布的huffman.c示例中发生的情况，但不是上面描述的方式）。
- JimG
0
最好发送字符频率并在接收端构建树形结构。对于固定的字母表，这些数据的大小是恒定的。我猜这必须是可序列化的，并放入文件中。根据实现方式来发送树形结构，对于我尝试过的方法，基于数组的方法导致了更多未使用的内存，因为大多数时候该树形结构可能不是平衡的。如果该树形结构是平衡的，则数组表示将生成最佳选项。
- quiet_penguin
0
你尝试过自适应哈夫曼编码吗？乍一看，似乎树根本不需要被发送，但需要更多的工作来优化和同步树。
- quiet_penguin
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接