哈夫曼编码的方法.doc

哈夫曼编码的方法————————————————————————————————作者:————————————————————————————————日期: :(1)将信源符号按概率递减顺序排列;(2)把两个最小的概率加起来,作为新符号的概率;(3)重复步骤(1)、(2),直到概率和达到1为止;(4)在每次合并消息时,将被合并的消息赋以1和0或0和1;(5)寻找从每个信源符号到概率为1处的路径,记录下路径上的1和0;(6)对每个符号写出"1"、"0"序列(从码数的根到终节点)。①哈夫曼方法构造出来的码不是唯一的。原因·在给两个分支赋值时,可以是左支(或上支)为0,也可以是右支(或下支)为0,造成编码的不唯一。·当两个消息的概率相等时,谁前谁后也是随机的,构造出来的码字就不是唯一的。②哈夫曼编码码字字长参差不齐,因此硬件实现起来不大方便。③哈夫曼编码对不同的信源的编码效率是不同的。·当信源概率是2的负幂时,哈夫曼码的编码效率达到100%;·当信源概率相等时,其编码效率最低。·只有在概率分布很不均匀时,哈夫曼编码才会收到显著的效果,而在信源分布均匀的情况下,一般不使用哈夫曼编码。④对信源进行哈夫曼编码后,形成了一个哈夫曼编码表。解码时,必须参照这一哈夫编码表才能正确译码。·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时,必须考虑哈夫曼编码表占有的比特数。在某些应用场合,信源概率服从于某一分布或存在一定规律(这主要由大量的统计得到),这样就可以在发送端和接收端固定哈夫曼编码表,在传输数据时就省去了传输哈夫曼编码表,这种方法称为哈夫曼编码表缺省使用。使用缺省的哈夫曼编码表有两点好处:·降低了编码的时间,改变了编码和解码的时间不对称性;·便于用硬件实现,编码和解码电路相对简单。这种方法适用于实时性要求较强的场合。虽然这种方法对某一个特定应用来说不一定最好,但从总体上说,只要哈夫曼编表基于大量概率统计,其编码效果是足够好的。,….,M0它们的概率如下表所示,使用霍夫曼编码算法求出8个符号所分配的代码。(写出编码树):为了进行哈夫曼编码,先把这组数据由大到小排列,再按上方法处理(1)将信源符号按概率递减顺序排列。(2)首先将概率最小的两个符号的概率相加,合成一个新的数值。(3)把合成的数值看成是一个新的组合符号概率,重复上述操作,直到剩下最后两个符号。  -Famo编码Shannon-Famo(S-F)编码方法与Huffman的编码方法略有区别,但有时也能编出最佳码。-F码主要准则符合即时码条件;在码字中,1和0是独立的,而且是(或差不多是)等概率的。这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有1位的信息量。-F码的编码过程信源符号按概率递减顺序排列;把符号集分成两个子集,每个子集的概率和相等或近似相等;对第一个子集赋编码"0",对第二个子集赋编码"1";重复上述步骤,直到每个子集只包含一个信源符号为止。(简写为RLE或RLC)是一种十分简单的压缩