范式Huffman编码

范式huffman编码是一种相对于正规的编码而言操作起来简单得多的编码方法，而且其效果能够起到和huffman编码相同的效果。

范式huffman编码的基础还是依靠于huffman编码。

1、首先对需要压缩的数据进行huffman排列，得出这个数据的huffman二叉树的模型。

得到的这个数据很有用，就是得到了每个数据样本到底分配几个bit。比如数据中出现了数据a，经过这一步后就得出了数据a的huffman码有几个bit。比如说，算下来是2位，就是表示在数据a的huffman编码中，用一个2位的数据来代表a。

2、得到上述的数据后，就要确定数据样本中的每一个样本对应的huffman码值。

比如上述的数据a，已经确定编码后的huffman码字为2位，则通过下面的规则，就可以确定这个2位值a对应的huffman码值到底是什么。

3、为了实现2的目的，按照如下的顺序来操作。

a、得到每个数据样本分配位数，举个例子如下：

                           Symbol     Length

                               a            2

                               b            2

                               c            3

                               d            3

                               e            4

                               f             4

                               i              4

                               g             5

                               h             5

b、根据上表，能够得出huffman码的最长的码的位数，比如说是5位。然后统计一下，从5位长的编码开始到1位长的编码为止（共5种编码），每种编码长度出现的个数（比如数据样本中编码出来后是4位的数据样本有多少个），可以得到另一个表，如下：

                           Length        Num

                               5             2

                               4             3

                               3             2

                               2             2

                               1             0

这个表表示编码长度为一个定值的样本个数是多少。第一行表示长度为5的样本个数为2个。

c、由上表能够简单的算出另一个表

                           Length        start code

                               5              00000

                               4               0001

                               3                010

                               2                 10

这个表的计算方法很简单，而且由这个表能够算出整个码表，现将计算方法归纳如下 ：

将最长码位的最开始的那个样本的huffman码值设为0，当然位数是确定的（在上述例子中，为00000），因为5位的码个数有2个，0加上2等于2，然后右移一位的值作为4位码的开始的码值，为0010，因为4位码值个数为3，0010加上3为0101，右移一位作为3位码的起始码值，为010，因为3位码个数为2个，则010加上2位100，右移一位为10，作为2位码的起始码值。

d、由上表，确定了每个不同码长的huffman码的起始样本的码值，从上面的表中能够非常容易的得到所有样本的码值。方法如下 ：

举5位码长的huffman码为例子：起始的码值为00000，它对应着h，即00000时h的huffman 编码。然而g的编码位数也是5位，对于g，只要在00000后面加1就得到了00001，这个就是g的编码，如果还有第三个5位码的话，那么它的编码就是 00001+1=00010（当然本例中只有2个5位码）

其他码长的同样处理，按照顺序加一的方法就可以得到所有样本的编码值。

如上，范式huffman编码工作就完成了。

 

但是值得注意的是 ，在jpeg编码中，存放的huffman表并不是像上面说的那样。恰恰相反，在jpeg系统中，解码时的huffman表的顺数是相反的，是将最低位赋予0 ，然后每次都左移 来得到其他的编码值的。

(完）

create@2009-10-23