Huffman(霍夫曼)编码是如何运算的?最好能举例说明霍夫曼编码算法的运算过程.
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 10:51:20
Huffman(霍夫曼)编码是如何运算的?最好能举例说明霍夫曼编码算法的运算过程.
Huffman(霍夫曼)编码是如何运算的?
最好能举例说明霍夫曼编码算法的运算过程.
Huffman(霍夫曼)编码是如何运算的?最好能举例说明霍夫曼编码算法的运算过程.
霍夫曼(Huffman)编码原理
霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码.属于无损压缩编码.
霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长.这样,处理全部信息的总码长一定小于实际信息的符号长度.
步骤进行:
l)将信号源的符号按照出现概率递减的顺序排列.
2)将两个最小出现概率进行合并相加,得到的结果作为新符号的出现概率.
3)重复进行步骤1和2直到概率相加的结果等于1为止.
4)在合并运算时,概率大的符号用编码0表示,概率小的符号用编码1表示.
5)记录下概率为1处到当前信号源符号之间的0,l序列,从而得到每个符号的编码.
例:
设信号源为 s={s1,s2,s3,s4,s5}
对应的概率为p={0.25,0.22,0.20,0.18,0.15}.
根据字符出现的概率来构造平均长度最短的异字头码字.
霍未曼编码通常采用两次扫描的办法,第一次扫描得到统计结果,第二次扫描进行编码.
霍夫曼编码具有一些明显的特点:
1) 编出来的码都是异字头码,保证了码的唯一可译性.
2) 由于编码长度可变.因此译码时间较长,使得霍夫曼编码的压缩与还原相当费时.
3) 编码长度不统一,硬件实现有难度.
4) 对不同信号源的编码效率不同,当信号源的符号概率为2的负幂次方时,达到100%的编码效率;若信号源符号的概率相等,则编码效率最低.
5) 由于"0"与"1"的指定是任意的,故由上述过程编出的最佳码不是唯一的,但其平均码长是一样的,故不影响编码效率与数据压缩性能.