香农编码码字
霍夫曼编码和香农编码的优缺点?
霍夫曼编码和香农编码的优缺点?
香农编码
编码步骤
S1 将q个信源符号按概率递减的方式进行排序:P1≥P2≥……Pq。
S2 按式-logP(Si)≤li≤1-logP(Si)(i=1,2,……q),计算出每个信源符号的码长li。
S3 为编成唯一可译码,计算第i个信源符号的累加概率。
S4 将累加概率Gi用二进制表示。
S5 取Gi对应二进制数的小数点后li位构成该信源符号的二进制码字。
优点
== 有重要的理论意义。
缺点
== 编码效率不高。
== 其平均码长不是最短的。
== 冗余度稍大,实用性不大。
== 由于码长总是进一取整,香浓编码方法不一定是最佳的。
哈夫曼编码
编码步骤
S1 将信源符号按照概率大小从大到小排列;
S2 把概率最小的两个信源符号分成一组,其中,上面一个编码为0,下面一个编码为1,并将这两个符号的概率加起来,其结果再与尚未处理过的符号重新按照大小排序;
S3 重复步骤2,直到所有的信源符号都处理完毕;
S4 从右至左按照编码路径返回,即可得到各个码字。
优点
== 赫夫曼码的码字(各符号的代码)是异前置码字,即任一码字不会是另一码字的前面部分。
== 赫夫曼码的各码字可以连在一起传送,中间不需另加隔离符号,只要传送时不出错,收端仍可分离各个码字,不致混淆。
== 当信息源各符号出现的概率很不平均的时候,哈夫曼编码的效果才明显。当信号源的符号概率为2的负幂次方时,达到100\%的编码效率。
缺点
== 当信息源各符号出现的概率较为平均的时候,哈夫曼编码的效果不明显。
== 哈夫曼编码必须精确地统计出原始文件中每个符号的出现频率,如果没有这些精确的统计,将达不到预期的压缩效果。霍夫曼编码通常要经过两遍操作,第一遍进行统计,第二遍产生编码,所以编码速度相对慢。
== 编码长度不统一,硬件实现有难度。
== 由于编码长度可变。因此译码时间较长,使得霍夫曼编码的压缩与还原相当费时。
== 哈夫曼编码只能用整数来表示单个符号而不能用小数,这很大程度上限制了压缩效果。
== 哈夫曼所有位都是合在一起的,如果改动其中一位就可以使其数据变得面目全非。