哈夫曼编码的方法
更新时间:2023-10-07 08:05:01 阅读量: 综合文库 文档下载
1.哈夫曼编码的方法
编码过程如下 :
(1) 将信源符号按概率递减顺序排列 ;
(2) 把两个最小的概率加起来 , 作为新符号的概率 ; (3) 重复步骤 (1) 、 (2), 直到概率和达到 1 为止 ;
(4) 在每次合并消息时,将被合并的消息赋以1和0或0和1; (5) 寻找从每个信源符号到概率为1处的路径,记录下路径上的1和0; (6) 对每个符号写出\、\序列(从码数的根到终节点)。
2.哈夫曼编码的特点
①哈夫曼方法构造出来的码不是唯一的 。
原因
·在给两个分支赋值时 , 可以是左支 ( 或上支 ) 为 0, 也可以是右支 ( 或下支 ) 为 0, 造成编码的不唯一。
·当两个消息的概率 相等时, 谁前谁后也是随机的 , 构造出来的码字就不是唯一的。
②哈夫曼编码码字字长参差不齐 , 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。
· 当信源概率是 2 的负幂时 , 哈夫曼码的编码效率达到 100%; · 当信源概率相等时 , 其编码效率最低。
· 只有在概率分布很不均匀时 , 哈夫曼编码才会收到显著的效果 , 而在信源分布均匀的情况下 , 一般不使用哈夫曼编码。
④对信源进行哈夫曼编码后 , 形成了一个哈夫曼编码表。解码时 , 必须参照这一哈夫编码表才能正确译码。
·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时 , 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律
( 这主要由大量的统计得到 ), 这样就可以在发送端和接收端固定哈夫曼编码表 , 在传输数据时就省去了传输哈夫曼编码表 , 这种方法称为哈夫曼编码表缺省使用。 使用缺省的哈夫曼编码表有两点好处: · 降低了编码的时间 , 改变了编码和解码的时间不对称性 ; · 便于用硬件实现 , 编码和解码电路相对简单。这种方法适用于实时性要求较强的场合。虽然这种方法对某一个特定应用来说不一定最好 , 但从总体上说 , 只要哈夫曼编表基于大量概率统计,其编码效果是足够好的。 3. 哈夫曼编码举例 现在有8个待编码的符号 M0,….,M0 它们的概率如下表所示,使用霍夫曼编码算法求出8个符号所分配的代码。(写出编码树) 待编码的符号 概率 M0 0.2 M1 0.4 M2 0.1 M3 0.15 M4 0.03 M5 0.04 M6 0.07 M7 0.01 解: 为了进行哈夫曼编码 , 先把这组数据由大到小排列 , 再按上方法处理 (1) 将信源符号按概率递减顺序排列。
(2) 首先将概率最小的两个符号的概率相加,合成一个新的数值。
(3) 把合成的数值看成是一个新的组合符号概率,重复上述操作,直到剩下最后两个符号。
5.4.2 Shannon-Famo编码
Shannon-Famo(S-F) 编码方法与 Huffman 的编码方法略有区别 , 但有时也能编出最佳码。
1.S-F码主要准则
符合即时码条件 ;
在码字中 ,1 和 0 是独立的 , 而且是 ( 或差不多是 )等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有1位的信息量。
2.S-F码的编码过程
信源符号按概率递减顺序排列 ;
把符号集分成两个子集 , 每个子集的概率和相等或近似相等 ;
对第一个子集赋编码 \对第二个子集赋编码 \重复上述步骤 , 直到每个子集只包含一个信源符号为止。
5.4.3 游程编码
游程编码(简写为RLE或RLC)是一种十分简单的压缩方法 ,它将数据流中连续出现的字符 ( 称为游程 ) 用单一的记号来表示。例如,字符串
a b a C C C b b a a a a
可以压缩为
a b a 3c 2b 4a
游程编码的压缩效果不太好, 但由于简单, 编码 / 解码的速度非常快 , 因此仍然得到广 泛的应用。许多图形和视频文件, 如 .BMP,.TIF 及 .AVI 等 , 都使用了这种压缩。
5.4.4 算术编码
1.算术编码
算术编码把一个信源集合表示为实数线上的 0 到 1 之间的一个区间。这个集合中的每个元素都要用来缩短这个区间。信源集合的元素越多,所得到的区间就越小,当区间变小时,就需要更多的数位来表示这个区间,这就是区间作为代码的原理。算术编码首先假设一个信源的概率模型,然后用这些概率来缩小表示信源集的区间。
2.举例说明算术编码过程
[ 例 ]设英文元音字母采用固定模式符号概率分配如下:
字符 a e i o u 概率 0.2 0.3 0.1 0.2 0.2 范围 [0,0.2] [0.2,0.5] [0.5,0.6] [0.6,0.8] [0.8,1.0] 设编码的数据串为 eai 。令 high 为编码间隔的高端 ,low 为编码间隔的低端 , range 为编码间隔的长度 ,rangelow 为编码字符分配的间隔低端 ,rangehigh 为编码字符分配的间隔高端。 初始 high=1,low=0,range=high-low, 一个字符编码后新的 low 和 high 按下式计算 : ·low =low+range × rangelow ·high =low+range×rangehigh (1) 在第一个字符 e 被编码时 ,e 的 rangelow=0.2,rangehigh=0.5, 因此 : low=0 + 1 × 0.2 = 0.2 high=0 + 1 × 0.5 = 0.5 range=high-low=0.5-0.2=0.3 此时分配给 e 的范围为 [0.2,0.5] 。 (2)第二个字符 a 编码时使用新生成范围 [0.2,0.5],a 的 rangelow=0, rangehigh=0.2, 因此: low=0.2 十 0.3 × 0=0.2 high=0.2 +0.3 × 0.2=0.26 range=0.06 范围变成 [0.2,0.26] 。
(3) 对下一个字符 i 编号,i 的 rangelow=0.5,rangehigh=0.6, 则: low=0.2 + 0.06 × 0.5=0.23 high=0.2 + 0.06 × 0.6=0.236
即用 [0.23,0.236] 表示数据串 eai, 如果解码器知道最后范围是 [0.23,0.236 ]这一范 围 , 它马上可解得一个字符为 e, 然后依次得到惟一解 a, 即最终得到 eai 。
3.算术编码的特点
①不必预先定义概率模型 , 自适应模式具有独特的优点;
②信源符号概率接近时 , 建议使用算术编码 , 这种情况下其效率高于 Huffman 编码;
③算术编码绕过了用一个特定的代码替代一个输入符号的想法 , 用一个浮点输出数值代替一个流的输入符号 , 较长的复杂的消息输出的数值中就需要更多的位数。 ④算术编码实现方法复杂一些 , 但 JPEG 成员对多幅图像的测试结果表明 , 算术编码比Huffman 编码提高了 5% 左右的效率 , 因此在 JPEG 扩展系统中用算术编码取代 Huffman 编码。
正在阅读:
哈夫曼编码的方法10-07
计算机网络及信息安全管理规程03-27
4、××律师(法律工作者)普法教育讲课稿02-27
爱在点滴08-22
《NBA梦之队》高手进阶攻略详解06-01
第八章桥梁美学 - 图文01-02
从目的论角度分析中文景点名称的翻译01-23
windows操作系统练习题及答案06-26
公共营养师三级理论试题及答案09-24
麻阳县水岸明珠二期工程住宅楼02-02
- 必修一物理寒假作业
- 2019-201X年5月大学生入党积极分子思想汇报-word范文模板(3页)
- 药物分析习题五
- 重拾应用意识 体会数学价值(沈建军)
- 2017全国高校辅导员结构化面试题集及参考答案
- 广东徐闻县实验中学2014届高三第二次月测地理试题
- 今天你共鸣了么?
- 2018-2019正能量读后感1000字-推荐word版(6页)
- 2018年中国截切型盖板针布行业专题研究分析报告目录
- 中国移动业务处理流程大全
- 公文写作常用词汇和句子集锦2016
- ARM课程设计说明书
- 教师资格证教育学论文
- 中考试卷分析
- 环境监测试卷(五)
- 党风廉政建设广播稿1
- 快速制作香香宫煮麻辣烫教程
- 《国际金融学》习题
- 文明施工保障措施方案
- 春兰维修资料故障代码
- 哈夫曼
- 编码
- 方法
- 分析化学第六版课后答案-(2)
- 人机工程学实验报告(1)
- 混凝土强度评定(两个例题) 暴了!!!!
- 7 公元1949年~公元1976年生命科学发展大事
- 入党积极分子思想汇报(全年合集共计四篇)
- 学校三八红旗手事迹
- 生物化学复习题
- 课程与教学论2014年10月考试真题 - 图文
- 《概率论与数理统计教程》课后习题解答
- 制造业企业主要经济业务的会计处理、会计与税法差异
- 关于增加社区老年人娱乐活动设施的建议
- 哈工大物理化学本科期末自测题
- 研究生学术规范网上考试答案解析
- 网络会计面临的问题及对策
- 关于防寒防冻的基本措施
- 答案波谱分析概论作业离线
- 2018年优质护理工作计划
- 智能化弱电集成施工组织设计方案最全完整版
- 招聘特设岗位教师考试实施办法
- 顺丰快递的外部环境分析