如何从哈夫曼树生成哈夫曼代码
我正在用 C++ 制作 jpeg 编码器。我成功创建了霍夫曼树，但是如何从树生成霍夫曼代码？我尝试的一种方法是将 0 分配给左分支，将 1 分配给右分支，就像图中一样，但这种方法有一个问题，因为一个元素将用所有 1 进行编码（如下图所示的 sibol E ）使用 11) 进行编码，但 jpeg 标准不允许使用全 1 的哈夫曼编码。
I'm making jpeg encoder in C++. I successfully create Huffman tree, but how do I generate huffman codes from tree? One way I tried was to assign 0 to left branch and 1 to right branch, just like in the picture, but there is a problem in this approach, because one element will be coded with all ones (like sibol E in picture bellow which is coded with 11), but jpeg standard doesn't allow huffman codes with all ones.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
JPEG 使用基于统计的固定树。所以你永远不会得到最佳的代码。必须使用固定树，因为它是有效分布霍夫曼树的唯一方法（否则您必须将树保留在文件中，这会使文件变得更大）。我假设标准文档中描述了该树。
JPEG is using a fixed tree based on statistics. So you'll never get an optimal code. The fixed tree has to be used because it is the only way of distributing the Huffman tree in an efficient way (otherwise you would have to keep the tree within the file and this makes the file much bigger). I assume the tree is described within the standard documents.
如果您不能使用全 1 的字符串，那么您不一定能获得最佳代码（我的意思是在某些约束下是最佳的）。
如果你在全是“1”的字符串后面追加一个“0”，那么它就不再是全是“1”了。您仍然会有一个前缀代码，只是不是最佳的。所以这可能就足够了，但我不知道这是否是 jpeg 编码器应该做的。我本以为会有一个标准的解决方案。
If you can't use a string of all 1s, then you can't necessarily get an optimal code (optimal within certain constraints, I mean).
If you append a "0" to the string that's all "1"s, then it won't be all "1"s any more. You'll still have a prefix code, just not an optimal one. So that might suffice, but I don't know whether that's what jpeg encoders are supposed to do. I'd have thought there would be a standard solution.
我发现这是生成 jpeg 霍夫曼代码的完全错误的方法。霍夫曼表是通过两个步骤从统计数据集合中生成的，这在 JPEG 标准的附录 K 中给出。此外，同一文件的附录 C 中也给出了一些细节。
I found that this is totally wrong approach in generating jpeg huffman codes. A Huffman table is generated from a collection of statistics in two steps, which are given in Annex K of JPEG standard. Also, few details are given in Annex C of the same document.