哈夫曼编码的方法

1．哈夫曼编码的方法编码过程如下:(1)将信源符号按概率递减顺序排列;(2)把两个最小的概率加起来,作为新符号的概率;(3)重复步骤(1)、(2),直到概率和达到1为止;(4)在每次合并消息时，将被合并的消息赋以1和0或0和1；(5)寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0；(6)对每个符号写出1、0序列（从码数的根到终节点）。2．哈夫曼编码的特点①哈夫曼方法构造出来的码不是唯一的。原因·在给两个分支赋值时,可以是左支(或上支)为0,也可以是右支(或下支)为0,造成编码的不唯一。·当两个消息的概率相等时,谁前谁后也是随机的,构造出来的码字就不是唯一的。②哈夫曼编码码字字长参差不齐,因此硬件实现起来不大方便。③哈夫曼编码对不同的信源的编码效率是不同的。·当信源概率是2的负幂时,哈夫曼码的编码效率达到100%;·当信源概率相等时,其编码效率最低。·只有在概率分布很不均匀时,哈夫曼编码才会收到显著的效果,而在信源分布均匀的情况下,一般不使用哈夫曼编码。④对信源进行哈夫曼编码后,形成了一个哈夫曼编码表。解码时,必须参照这一哈夫编码表才能正确译码。·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时,必须考虑哈夫曼编码表占有的比特数。在某些应用场合,信源概率服从于某一分布或存在一定规律(这主要由大量的统计得到),这样就可以在发送端和接收端固定哈夫曼编码表,在传输数据时就省去了传输哈夫曼编码表,这种方法称为哈夫曼编码表缺省使用。使用缺省的哈夫曼编码表有两点好处:·降低了编码的时间,改变了编码和解码的时间不对称性;·便于用硬件实现,编码和解码电路相对简单。这种方法适用于实时性要求较强的场合。虽然这种方法对某一个特定应用来说不一定最好,但从总体上说,只要哈夫曼编表基于大量概率统计,其编码效果是足够好的。3．哈夫曼编码举例现在有8个待编码的符号M0，….，M0它们的概率如下表所示，使用霍夫曼编码算法求出8个符号所分配的代码。（写出编码树）待编码的符号概率M00.2M10.4M20.1M30.15M40.03M50.04M60.07M70.01解：为了进行哈夫曼编码,先把这组数据由大到小排列,再按上方法处理（1）将信源符号按概率递减顺序排列。（2）首先将概率最小的两个符号的概率相加，合成一个新的数值。（3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。5．4．2Shannon-Famo编码Shannon-Famo(S-F)编码方法与Huffman的编码方法略有区别,但有时也能编出最佳码。1．S－F码主要准则符合即时码条件;在码字中,1和0是独立的,而且是(或差不多是)等概率的。这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有1位的信息量。2．S－F码的编码过程信源符号按概率递减顺序排列;把符号集分成两个子集,每个子集的概率和相等或近似相等;对第一个子集赋编码0,对第二个子集赋编码1;重复上述步骤,直到每个子集只包含一个信源符号为止。5．4．3游程编码游程编码(简写为RLE或RLC)是一种十分简单的压缩方法,它将数据流中连续出现的字符(称为游程)用单一的记号来表示。例如,字符串abaCCCbbaaaa可以压缩为aba3c2b4a游程编码的压缩效果不太好,但由于简单,编码/解码的速度非常快,因此仍然得到广泛的应用。许多图形和视频文件,如.BMP,.TIF及.AVI等,都使用了这种压缩。5．4．4算术编码1．算术编码算术编码把一个信源集合表示为实数线上的0到1之间的一个区间。这个集合中的每个元素都要用来缩短这个区间。信源集合的元素越多,所得到的区间就越小,当区间变小时,就需要更多的数位来表示这个区间,这就是区间作为代码的原理。算术编码首先假设一个信源的概率模型,然后用这些概率来缩小表示信源集的区间。2．举例说明算术编码过程[例]设英文元音字母采用固定模式符号概率分配如下:字符aeiou概率0.20.30.10.20.2范围[0,0.2][0.2,0.5][0.5,0.6][0.6,0.8][0.8,1.0]设编码的数据串为eai。令high为编码间隔的高端,low为编码间隔的低端,range为编码间隔的长度,rangelow为编码字符分配的间隔低端,rangehigh为编码字符分配的间隔高端。初始high=1,low=0,range＝high-low,一个字符编码后新的low和high按下式计算:·low=low＋range×rangelow·high=low＋range×rangehigh(1)在第一个字符e被编码时,e的rangelow＝0.2,rangehigh=0.5,因此:low＝0+1×0.2＝0.2high=0+1×0.5＝0.5range=high－low=0.5－0.2=0.3此时分配给e的范围为[0.2,0.5]。(2)第二个字符a编码时使用新生成范围[0.2,0.5],a的rangelow=0,rangehigh=0.2,因此：low=0.2十0.3×0=0.2high=0.2＋0.3×0.2=0.26range=0.06范围变成[0.2,0.26]。(3)对下一个字符i编号,i的rangelow=0.5,rangehigh=0.6,则：low=0.2＋0.06×0.5=0.23high=0.2＋0.06×0.6=0.236即用[0.23,0.236]表示数据串eai,如果解码器知道最后范围是[0.23,0.236]这一范围,它马上可解得一个字符为e,然后依次得到惟一解a,即最终得到eai。3.算术编码的特点①不必预先定义概率模型,自适应模式具有独特的优点;②信源符号概率接近时,建议使用算术编码,这种情况下其效率高于Huffman编码;③算术编码绕过了用一个特定的代码替代一个输入符号的想法,用一个浮点输出数值代替一个流的输入符号,较长的复杂的消息输出的数值中就需要更多的位数。④算术编码实现方法复杂一些,但JPEG成员对多幅图像的测试结果表明,算术编码比Huffman编码提高了5%左右的效率,因此在JPEG扩展系统中用算术编码取代Huffman编码。