huff.md

计算机基础

哈夫曼编码

1. 编码方式

1. 固定长度编码

   对于一个待处理的一个字符串序列，如果对每个字符用同样长度的二进制位来表示

2. 可变长度编码

   允许对不同字符用不等长的二进制位表示，其特点

   1. 对频率高的字符赋予短编码

   2. 对频率较低的字符赋予较长的一些的编码

   这样从而可以使平均编码长度减短，起到压缩数据的效果

3. 前缀编码

   如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

2. 形成哈夫曼树

给定N个权值分别为{W1,W2,...,Wn}的节点

1. 将这N个节点分别作为N棵仅含一个节点的二叉树，构成森林F

2. 构造一个新节点，并从F中选取两个根节点权值最小的树作为新节点的左、右子树，并且将新节点的权值置为左、右子树上根节点的权值之和。

3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。

4. 重复步骤2，3，直至F中只剩下一棵树为止

• 例子：用二进制来编码字符串abcdabaa，需要能够根据编码，解码会原来的字符串，最少需要多少的二进制字符串？

  对字符串中字符出现的频率进行统计，作为字符的权重

  {a:4,b:2,c:1,d:1}

  1. c和d结合
  2. 再和b结合
  3. 再和a结合

  

  因此，各个字符对应的编码是{a:0,b:10,c:110,d:111}，最后字符串的编码为：

  0 10 110 111 0 10 0 0