规范霍夫曼编码算法

Question

你好，我正在尝试实现Canonical Huffman编码，但我不理解维基百科和谷歌指南，我需要更抽象的解释...

我尝试了以下步骤： 1. 获取常规Huffman编码长度代码的列表。例如：

A - code: 110, length: 3.
B - code: 111, length: 3.
C - code: 10, length 2.
D - code: 01, length 2.
E - code: 00, length 2.

我将表格按照符号和长度进行排序，具体如下：

2. 我按照以下方式对表格进行排序：

C - code: 10, length 2.
D - code: 01, length 2.
E - code: 00, length 2.
A - code: 110, length: 3.
B - code: 111, length: 3.

现在我不知道该怎么继续...

非常感谢。

- user165210

Answer 1

使用霍夫曼算法得到的编码可以丢弃，只需要保留长度信息。

然后根据长度和符号分配编码。按照长度从短到长的顺序进行排序，在每个长度内，按照符号的升序排序（具体如何排序并不重要，只要每个符号都严格小于或大于任何其他符号，并且编码器和解码器在如何排序方面达成一致即可）。

因此，我们进行排序：

C - 2
D - 2
E - 2
A - 3
B - 3

2出现在3之前，在2中，C、D、E按顺序排列，在3中，A、B按顺序排列。

现在我们在每个长度内按整数顺序分配代码，在每次增加一个长度时在末尾添加一个零位：

C - 2 - 00
D - 2 - 01
E - 2 - 10
A - 3 - 110 <- after incrementing to 11, a zero was added to make 110
B - 3 - 111

这是一种规范编码。

如果你愿意，你可以用其他方法来实现，但只要编码器和解码器在方法上达成一致，仍然可以算作是规范的，例如从11开始倒数。整个重点是只需要将每个符号的长度从编码器传输到解码器，以免不必要地传输更大的代码。

- Mark Adler

---

你好。感谢您的回答。我正在寻找同样的东西。我不明白的是您如何以“整数顺序”分配代码。我的意思是，00 = 0，01 = 1，10 = 2，110 = 6，111 = 7，那么我们为什么从2跳到6呢？或者它不是按二进制顺序排列的，整数顺序意味着其他什么？ - Bogdan Daniel

@BogdanDaniel 这在答案的灰色框中有解释。当你进入下一个长度时，你在末尾添加零位。整数顺序在每个长度内。 - Mark Adler

谢谢。我现在明白了。我错过了“每个长度”的部分。 - Bogdan Daniel

Answer 2

你应该按照符号的频率进行排序，最常见的放在顶部，最不常见的放在底部。（总体频率-1）：

A (0.5)
B (0.2)
C (0.15)
D (0.15)

然后用0标记一个符号，用1标记另一个符号，将它们的频率相加并插入到列表的适当位置，并再次使用0和1标记两个最小的符号：

A (0.5)      A (0.5)
B (0.2)      C&D (0.3) 0
C (0.15) 0   B (0.2)   1
D (0.15) 1

再一次...

A (0.5)      A (0.5)        A (0.5)      0
B (0.2)      C&D (0.3) 0    B&C&D (0.5)  1
C (0.15) 0   B (0.2)   1
D (0.15) 1

直到你获得最后一对。 从尾部到符号标记的路径，由0和1组成，将对应哈夫曼编码：

A 0
B 11
C 100
D 101

- Semyon Burov

---

此外，OP 特别询问了“规范”的哈夫曼编码。 - 500 - Internal Server Error

查找“规范哈夫曼编码”。您完全不理解它。 - Mark Adler