如题所述
赫夫曼编码的具体方法:先按出现的概率大小排队,把两个最小的概率相加,作为新的概率 和剩余的概率重新排队,再把最小的两个概率相加,再重新排队,直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率,读出时由该符号开始一直走到最后的“1”, 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好,就是该符号的赫夫曼编码。
例如a7从左至右,由U至U″″,其码字为1000;
a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好,其码字为1001…
用赫夫曼编码所得的平均比特率为:Σ码长×出现概率
上例为:0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit
可以算出本例的信源熵为2.61bit,二者已经是很接近了。
哈夫曼编码进行压缩的压缩率是根据平均码长来计算的,压缩率比较低。例如:用三位二进行数进行的等长编dao码平均长度为3,而根据哈夫曼树编码的平均码长为:
4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61
2.61/3=0.87=87%
其平均码长是等长码的87%,所以平均压缩率为13%。
扩展资料:
霍夫曼编码的基本方法先对图像数据扫描一遍,计算出各种像素出现的概率,按概率的大小指定不同长度的唯一码字,由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字,而码字与实际像素值的对应关系记录在码表中。
赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就称Huffman编码。下面引证一个定理,该定理保证了按字符出现概率分配码长,可使平均码长最短。
参考资料来源:百度百科-哈夫曼编码
参考资料来源:百度百科-压缩率