计算机系统在存储或传输数据时通常有对数据进行压缩的需求。数据压缩可以减小存储介质的占用量（或用有限的存储介质存储更多的数据），也可以减小数据传输时需要的带宽（或用有限的位宽和频率实现更高的数据传输速率）。
哈夫曼编码（Huffman Coding）是一种常用的可变长编码，这种编码方式可用于无损数据压缩。哈夫曼编码的基本思想是：一个文本中不同字符的出现频率不同，用更短的二进制序列编码出现频率更高的字符，而用更长的二进制序列编码出现频率更低的字符，就可以实现用相比定长编码总和更短的二进制序列去编码整个文本，从而实现数据的无损压缩。
例如编码AAAAAAAABCCCCCDD这样一个文本。如果使用定长编码的方式，由于一共出现了4种字符（ABCD），因此如果使用最小的定长序列表示，每个字符需要[log2(4)]即两个二进制位（如果使用ASCII则为8位），总共需要32个二进制位（使用ASCII需要128位）来表示这个文本。但如果我们使用0编码A，10编码C，111编码B，110编码D，则总共需要1*8+3*1+2*5+3*2=27个二进制位进行编码，实现了15.625%的数据无损压缩（相对ASCII约78.9%）。至于为何要选取这几个二进制序列作为编码以及是否有其他的选择，我们将在下文中进行解释。
Huffman编码原理
不定长编码可以用二叉树的叶节点表示，每个不定长编码必定在二叉树的叶节点上，而每个二叉树的叶节点一定可以用来表示一个不定长编码，从而保证一段二进制序列中的不定长编码可以被区分出来。
Huffman编码的目的是让整段文本的总编码长度最短。即为让编码二叉树的加权深度最小：加权深度为每个叶节点的权重乘以其深度之和，每个叶节点的权重即为其对应字符在整段文本中出现的次数或频率。
以上文中文本AAAAAAAABCCCCCDD为例，创建其Huffman编码分为以下步骤：
步骤一：将四个字符按照出现频率由小到大排列:
步骤二：创建一个临时节点t1，其两个子节点为频率最小（B）和次之的（D）字符。将两个字符的权重之和作为t1的权重并加入排序:
步骤三：如果比t1权重小的字符大于等于2，则使用权重最小的两个字符再创建一个带有两个子节点的临时节点，并同步骤二中处理。
如果比t1权重小的字符只有1个或没有，则创建一个新节点t2，其子节点分别为比t1旁的自核和t1，并同步骤二中处理
重复步骤三
完成二叉树的创建，并分配编码的二进制序列。具体的分配方式为：左子树分配1，右子树分配0；深度每增加1则在序列后添加一位。如下图所示，我们为四个字符分配了编码：
文章作者：速易芯李昊翔
更多详细文章可关注公众号 “速易芯Fastchip” ！
