原创 哈夫曼(huffman)编码的基本原理

     哈夫曼编码是常用的无损编码方法，广泛应用于图像压缩技术。JPEG标准中的基准模式采用的就是哈夫曼编码。

    哈夫曼编码是不定长编码，即代表各元素的码字长度不等。该编码是基于不同符号的概率分布，对出现次数较多的符号（码值）赋予较短的代码（码字），对出现次数较少的符号赋予较长的代码。在这里举个例子说明如何生成哈夫曼表。

    假设对由1、2、3、4、5、6、7、8八个数字组成的原信息进行哈夫曼编码。首先应对信息中各数字出现的次数进行统计，得出各数字出现的相对概率。假设各数字出现的次数及概率如表1所示。

                                                         表1

   根据表一生成的哈夫曼树如图1所示。

                                                     图1

   具体过程是这样的，先将所有数字排成一行构成8个最底层节点。首先将这些节点中最小两个概率值相加：0.05+0.1=0.15,   得到新的节点，这时拥有的概率值为0.2, 0.1, 0.1, 0.15, 0.15, 0.15, 0.15。再将两个最小的概率值相加得到新的节点... ... 直到得到根节点概率为1.0为止。相加时，对于概率值相等的多个节点，可以任意选取。

     除根节点外，设节点左边分支为0，右边分支为1（也可以反过来），对于各值（码值）的代码（码字）就是从根节点出发到底层节点所经历的分支序列。如4的代码（码字）为00，6的代码为111... ...通常4和6等称为码值，00和111等称为码字。所有码值和码字对应关系如表2所示。进行压缩编码时，只要将码值用码字代替即可。如果概率统计十分不准确，则压缩效率会很低。甚至起不到压缩效果。

                                                    表2

     将所有码值和码字的关系整理成一张表，为了整字节输出码字，表中还含有各码字的长度。这种表就称为哈夫曼表。本例哈夫曼表如表3所示。

                                                 表3