use*_*210 3 algorithm huffman-code canonical-link
您好我正在尝试实现Canonical霍夫曼编码,但我不懂wiki和谷歌指南,我需要更抽象地解释...
我试过这个:1.获取常规霍夫曼编码长度代码的列表.像这样:
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.
Run Code Online (Sandbox Code Playgroud)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.
现在我不知道如何继续......
tnx很多
Mar*_*ler 10
扔掉你从霍夫曼算法得到的代码.你不需要那些.保持长度.
现在根据长度和符号分配代码.按长度排序,从最短到最长,在每个长度内,按升序对符号进行排序.(如果这样做完全无关紧要,只要每个符号严格小于或大于任何其他符号,编码器和解码器就如何做到这一点达成一致.)
所以我们做了订购:
C - 2
D - 2
E - 2
A - 3
B - 3
两个在三个之前,在二个之内,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开始向后计数,只要编码器和解码器对方法达成一致即可.整点是只需要将每个符号的长度从编码器传送到解码器,以便不必传输占用更多空间的代码本身.
Sem*_*rov -1
您应该按频率对符号进行排序，因此最常见的是在顶部，最不常见的是在底部。（总频率 - 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