霍夫曼编码

霍夫曼树主要应用于远距离通信时的信息编码，将需要传送的文字转换为由二进制字符组成的串。例如给定一段报文CASTCASTSATATATASA，在报文中出现的字符的集合是｛C,A,S,T｝，各个字符出现的频度是｛2，7，4，5｝。若将每个字符用多个等长的二进制编码表示，例如 C:00， A:01， S:10， T:11。则所发的报文将是000110110001101110011101110111011001，共计（2＋7＋5＋4）×2＝36个码。若按字符出现的频度给予每个字符不同长度的编码：出现频度较大的字符采用为数较少的编码，出现频度较小的字符采用位书较多的编码，则可以使报文的码数降到最小，这就是不定长编码。在上文的报文段中，字符A出的次数最多，可将它的编码位数减少一位为0，其次是字符T，可以编码为1，而字符C和S可以分别编码为00、01，这样总的编码位数自然就少了。但是不定长编码在译码时可能会出现问题，例如对方传输过来的000，可以译为AAA，也可以译为AC或CA，这显然是不行的。

为了解决这个问题，霍夫曼在不定长编码思想的基础上利用霍夫曼树提出了一种编码方式：一般的，设需要编码的字符集为｛a1,a2,a3,…,an｝，各个字符出现的频率为｛w1,w2,…,wn｝，以字符出现的频率作为结点字符的权值来构造霍夫曼树。规定左权分支为0，右权分支为1，则从根结点到叶子结点经过的分支所组成的0和1串便是对应字符的编码，这就是霍夫曼编码。

霍夫曼编码遵循的基本思想是：若要设计不等长编码，则必须使任一个字符的编码都不是另一个字符编码的前缀。根据霍夫曼编码规则对上述报文按字符出现的频度进行编码，其中A:0，T:10，S:110，C:111。则最终加密之后的报文只有35个码。这种编码方式既节省了传输中使用的存储单元，又不会引起编码混乱。

霍夫曼编码的算法需要三步来实现：

（1）对于需要编码的字符进行扫描，统计每个字符出现的频次，得到一个整数数组；

（2）根据这个频次数组构造一棵霍夫曼树，这一步是霍夫曼编码的核心内容；

（3）再次扫描一遍历待编码的字符，对每个字符，在霍夫曼树里搜索该字符，得到它的编码。

在编码算法中，从树根处开始查找某一个结点，如果向左走则标记为0，向右走则标记为1。假设要发送一段报文，报文中的字母A、B、C、D出现的频率分别为60%、15%、20%、5%，以其出现频率为权值构建出一棵霍夫曼树，如图1所示。

图1 霍夫曼树

按照左权分支为0，右权分支为1的规则， A编码为1，B编码为011，C编码为00，D编码为010，如果要发送内容为“ABCD”的报文，其编码为101100010。

在解码时，还需要用到霍夫曼树，因为发送方和接收方需要用到同一套霍夫曼编码。