军 的个人资料tell you a story to make...照片日志列表更多 工具 帮助

日志


5月9日

范式huffman编码

    范式huffman编码是一种相对于正规的编码而言操作起来简单的多的编码方法,而且其效果能够起到和huffman编码相同的效果。
    范式huffman编码的基础还是依靠于huffman编码。
    1,首先对需要压缩的数据进行huffman排列,得出这个数据的huffman二叉树的模型。
      ******     得到这个数据很有用,就是得到了每一个数据样本到底分配给几位。比如数据中出现了数据a,经过这一步后就得出了数据a的huffman码有几位。比如说算下来是2位,就是表示在数据a的huffman编码中,用一个2位的数据来代表a。
    2,得到了上述的数据后,就要确定数据样本中的每一个样本到底对应了一个什么样的huffman码值。
      ******     比如上述的数据a,已经确定编码后的huffman码字为2位,则,下面就是确定这个2位的值到底是什么。
    3,为了实现2的目的,按照如下的顺序来操作。
          a。根据1得到的二叉树,能够得出huffman码的最长的码的位数,比如说是5位。然后统计一下,从5位长的编码开始,到1位长的编码为止,共5种编码,统计每种编码的个数(比如数据样本中编码出来后是4位的数据样本有多少个),举个想象的例子如下:
                   Symbol  Length 
      a    2
      b  2
      c   3
     d   3
     e   4
     f  4
     i               4
    g  5
    h  5
           b。由上面的表可以得到另一个表,如下:
              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。c得到的表,确定了每个不同码长的huffman码的起始样本的码值,从上面的表中能够非常容易的得到所有的样本的码值。
方法如下:
 举5位码长的huffman码为例子:起始的码值为00000,它对应着h,即00000时h的huffman编码,然而g的编码位数也是5位,对于g,只要在00000后面加1就得到了00001,这个就是g的编码,如果还有第三个5位码的话,那么它的编码就是00001+1=00010(当然本例中只有两个5位码)
 其他码长的同样处理,按照顺序加一的方法就可以得到所有样本的编码值。
 
如上,则范式huffman编码的工作就完成了。
 
 
 
 
 
但是要注意的是,在jpeg编码中,存放的huffman表并不是像上面说的那样的,恰恰相反,在jpeg系统中,解码时的huffman表的得到的顺序是相反的,是将最低位赋予0,然后每次都左移来得到其他的编码的,这一点要注意。