霍夫曼压缩算法与其压缩比

《霍夫曼压缩算法与其压缩比》由会员分享，可在线阅读，更多相关《霍夫曼压缩算法与其压缩比（2页珍藏版）》请在金锄头文库上搜索。

1、霍夫曼压缩算法与其压缩比霍夫曼压缩算法是一种不失真的压缩方法，下面分别说明其算法执行过程与数据压缩率的计 算方法：1霍夫曼压缩算法我们为了说明方法本身，不妨做一些简化假定。假定信源S包含的码元有SI、S2、S3、S4、S5、S6、S7，而它们在通信消息中出现的概率分别是0.21、0.11、0.08、0.18、0.03、0.25、0. 14。即 S=S1，S2, S3, S4, S5, S6, S7，而其相应的出现概率P=P1, P2, P3,P4， P5， P6， P7=0.21， 0.11， 0.08， 0.18， 0.03， 0.25， 0.14。霍夫曼编码过程中需要使 用霍夫曼树,即如下

2、图所示：算法的计算步骤叙述如下：1）将信源中的码元按照其在消息中出现概率的降序排列，即S6, S1, S4, S7, S2, S3, S5，作 为霍夫曼树的叶子；2）将其中最小的两个码元概率相加组成一个新概率值,以此信概率值做自树的根形成一棵 子树,并分别将连连接其中较小概率叶子的边标为“1”,较大概率叶子的边标为“0”；3）再找出两个概率较小的节点,重复 2）的操作,形成新的子树。直到最后形成子树的根 节点概率值为 1 时停止。这个根就是霍夫曼树的根。4）从霍夫曼树的根沿着每棵子树的边向叶节点察看,并记录经过的每条边上的“0”与“1” 的数字,结果便组成了该叶节点的霍夫曼编码。按照上述方法计

3、算得到的霍夫曼编码为：码元S6S1S4S7S2S3S5概率P6P1P4P7P2P3P50.250.210.180.140.110.080.03编码011100000110010101011码长22333442压缩率计算1）原来码元共有7个，它们可用 4 位二进制数编码，因为4 位二进制数可描述8 种组合。 所以平均码长为4 位。2）压缩后的平均码长L应按照下式计算：L = E Si*Pii=1所以，上述S信源霍夫曼编码的平均码长为：L = 2*0.25+2*0.21+3*0.18+3*0.14+3*0.11+4*0.08+4*0.03 = 2.64位3）所以 S 信源的霍夫曼编码压缩率为：4

4、/ 2.54 = 1.52 倍总之，由以上计算可以看出，不失真压缩算法的压缩率一般并不是十分高的。对于一幅静态图像来说，要计算其霍夫曼压缩编码和压缩率就比较复杂了。假定一幅图像屏 幕的分辨率为800*600个像素，总计的像素数目共计有800*600 = 480000个，其中相同颜 色的像素可编成一组，一组就是一个码元。每个码元在一幅图像内出现概率由每组码元内 像素的数目/480000 决定。如上所述，码元组数目即码元的数目。压缩前码元的编码长度不会超过17 位二进制数。计 算每个码元的霍夫曼编码就是要对每个码元的概率做上述霍夫曼树的计算。由于码元数量过 大，可见计算量是十分巨大的。但不管计算量有多大，但计算的过程都是相同的。（完）