数据结构|哈夫曼编码

若对每个字符编制相同长度的二进制码，则称为等长编码。例如，英文字符集中的26个字母可采用5位二进制位串标识，按等长编码格式构造一个字符编码表。发送方按照编码表对信息原文进行编码后送出电文，接收方对接收到二进制代码按每5位一组进行分割，通过查字符的编码表即可得到对应字符，实现译码。

等长编码方案实现方法比较简单，但对通信中的原文进行编码后，所得电文的码串过长，不利于提高通信效率，因此希望缩短码串的总长度。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，那么传送的电文码串总长度则可减少。

如果要设计长度不等的编码，必须满足下面的条件：任一字符的编码都不是另一个字符的编码的前缀，这种编码也称为前缀码。对给定的字符集D=｛d1,d2,…,dn｝及字符的使用频率W=｛w1,w2,…,wn｝，构造其最优前缀码的方法为：以d1,d2,…,dn作为叶子结点，w1,w2,…,wn作为叶子结点的权值，构造出一棵最优二叉树，然后将树中每个结点的左分支标上0，右分支标上1，则每个叶子结点代表的字符的编码就是从根到叶子的路径上的0、1组成的串。

译码时就从树根开始，若编码序列中当前编码是0，则进入当前结点的左子树；为1则进入右子树，到达叶子时一个字符就翻译出来了，然后再从树根开始重复上述过程，直到编码序列结束。

利用哈夫曼树译码的过程为：从根结点出发，按二进制位串中的0和1确定是进入左分支还是右分支，当到达叶子结点时译出一个字符。若位串未结束，则回到根结点继续上述译码过程，直到位串结束。