1

当我尝试通过 Huffman 代码对以下流进行编码时遇到了一些问题。如果编码系统是

A:0 B:10 C:110 D:111

那么序列 ABBADC 将是 010100111110。当我收到这个比特流时如何解码它？编码系统是否必要？如果是这样，我如何发送此表？如果没有，我应该如何解码它们？

4

3 回答 3

1

你必须建一棵树

   Start
 /0    \1
 |    /0 \1 
 A   |   / \
     B   | |
         C D

并在您的二进制数字之后的每一步中沿着它移动。每次找到叶子 - 回到根

您应该在文件的特殊标题部分或完全单独发送此表

于 2013-07-05T07:29:10.340 回答
1

您不需要发送表格，只需发送位长度。即，1,2,3,3。给定比特长度，可以在编码和解码端以相同的方式构造规范前缀码。有关规范代码的更多信息，请参阅此答案。

解码前缀码的方法有很多种。你可以一点一点地走，就好像你正在穿过一棵树，最终到达一片叶子，这是一个象征。然后从树的根部开始下一点。

或者对于确保较短长度比较长长度具有较低整数值的规范代码，将位收集成整数并与每个长度的值表进行比较。一旦确定了长度，整数就会索引符号表。这就是示例代码puff.c所做的。

最快的方法之一是创建一个长度包含最长代码的表，其中每个表条目是符号和位数。具有较少位的代码具有多个表条目。在这种情况下：

000: A 1
001: A 1
010: A 1
011: A 1
100: B 2
101: B 2
110: C 3
111: D 3

然后读取三位，查找，发出表中的符号，并消耗指示的位数。然后根据需要获取更多位以恢复到三位并重复。如果您到达输入的末尾，只需填充零位，但请注意有多少位。如果解码的代码使用填充位，则标记错误。

这就是zlib 的膨胀代码所做的，尽管它更复杂一点，因为它构建了一个两级表，因此不会花费太多时间来构建长表。

于 2013-07-05T16:18:45.020 回答
0

传统上，树数据结构用于存储霍夫曼数据。因此，当您处理 A、B、C、D 时，您将继续构建二叉树。编码的值，即 A、B、C、D 存储在叶中。当您收到比特流时，您只需遍历您已经必须解码代码的树。

但是，在您的情况下，如果您只有这 4 个输入，那么我建议您使用哈希图而不是树，因为它会使您的查找更容易。

于 2013-07-05T07:35:46.207 回答