赫夫曼编码原理分析

骑猪看日落 2021-09-01 07:32 363阅读 0赞

# 赫夫曼编码原理分析 #

## 通信领域中信息的处理1 – 定长编码 ##

**例：can you can a can as a can canner can a can.**  
**第一步**：将上面的字符转化成ASCII码

99 97 110 32 121 111 117 32 99 97 110 32 97 32 99 97 110 32 97 115 32 97 32 99 97 110 32 99 97 110 110 101 114 32 99 97 
    110 32 97 32 99 97 110 46

**第二步**：将ASCII码转换成二进制

01100011 01100001 01101110 00100000 01111001 01101111 01110101 00100000 01100011 01100001 01101110 00100000 01100001 00100000 01100011 01100001 01101110 00100000 01100001 01110011 00100000 01100001 00100000 01100011 01100001 01101110 00100000 01100011 01100001 01101110 01101110 01100101 01110010 00100000 01100011 01100001 01101110 00100000 01100001 00100000 01100011 01100001 01101110 00101110

定长编码的优缺点：定长编码 我的理解是将一串字符 首先转换成ASCII码 然后在转换成计算机所能认识的二进制编码 
    定长编码所需要的是固定长度的编码， 而固定长度所需要的数会太长 所以不是很有好。

## 通信领域中信息的处理2 – 非定长编码 ##

**例：can you can a can as a can canner can a can.**  
**第一步**：统计每个字母出现的次数

r:1 ， s:1 ， e:1  ，u:1   ，  y:1 ，.:1  ，  o:1   ， c:7  ，   n:8   ，  [ ]:11   ，   a:11

**第二步**：将出现频率最高的设置为最短

0=a  ， 1=[ ]   ，  10=n ，  11=c ，  100=o ，  101=.  ， 110=y ，  111=e  ， 1000=u  ， 1001=s ，  1010=r

**第三步**：对应的数字进行编码

10 1 10  1 110 100 11010 11 100 1010011 ············

非定长编码的缺点：计算机传值是不会出现空格，而计算机在解码是会出现失误
    前缀编码 ： 字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码

## 通信领域中信息的处理3 – 赫夫曼编码 ##

**例：can you can a can as a can canner can a can.**  
**第一步**：统计每个字母出现的次数

r:1 ， s:1 ， e:1  ，u:1   ，  y:1 ，.:1  ，  o:1   ， c:7  ，   n:8   ，  [ ]:11   ，   a:11

**第二步**：放入树中

设置编码：左节点为0，右节点为1，字母为对应的节点，数字为对应的权

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]  
所对应的节点为：

111 10 00 01 110010 11000 110100 01 111 10 00 01 10 01 111 10 00 01 10 110110 01 10 01 111 10 11 01 111 10 00 00 110101 
    110111 01 111 10 00 01 10 01 111 10 11 110011

###### 针对于定长编码、非定编码以及赫夫曼编码的总结：定长编码如上面例子 长度是396 而且都需要固定长度编码；非定长编码：不会出现定长编码的固定长度，但是在解码时有可能会出现前缀编码相同的两个字符，所以可能会造成解码失误；赫夫曼编码 如上图例子 长度是 122 压缩了70% 在解码时也很少会出现解码失误的情况。 ######

*注：计算机在转换二进制编码是不会出现空格的情况 上述例子出现空格 是为了在书写的时候好确认信息*

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]: /images/20210901/862861564d7a45be998b3505e87a1ee4.png