第三章:Huffman编码 信源概率模型已知的Huffman编码 信源概率模型未知的Huffman编码 Huffman编码中的码字设计

Slides:



Advertisements
Similar presentations
七年级数学校本课程 台山市任远中学 李锦明. 1. 最古老的过河问题 1. 最古老的过河问题 一个农民携带一只狼,一只羊和一 箱卷心菜,要借助一条小船过河。 小船上除了农民只能再带狼、羊、 卷心菜中的一样。而农民不在时, 狼会吃羊,羊会吃菜。农民如何过 河呢?
Advertisements

专题复习 --- 走进名著 亲近经典 读完《鲁滨孙漂流记》这本精彩的小说 后,一个高大的形象时时浮现在我的眼 前,他就是勇敢的探险家、航海家鲁滨 孙。他凭着顽强的毅力,永不放弃的精 神,实现了自己航海的梦想。 我仿佛看到轮船甲板上站着这样的一 个人:他放弃了富裕而又舒适的生活, 厌恶那庸庸碌碌的人生,从而开始了一.
四、后期物理复习备考建议 不同阶段复习课教学设计(知识建构)的目的 复习课教学 设计的目的 理 解 · 对某知识的全面、抽 象理解 · 抽象知识和具体情景 的转化 综 合 · 多知识点联合解决问 题 基本素质 · 审题、表达、审视答 案等基本能力 复习 ( 一 ) 复习(二) ☆ ☆☆☆ ☆☆  进行科学规划.
电子商务专业人才培养方案 五年制高职. 一、招生对象、学制与办学层次  (一)招生对象:初中毕业生  (二)学制:五年  (三)办学层次:专科.
說 劍 《莊子‧雜篇》─ 第 一 組 賴泊錞 謝孟儒 張維真 羅苡芸
第一节 人口的数量变化.
德 国 鼓 励 生 育 的 宣 传 画.
第四章:长期股权投资 长期股权投资效果 1、控制:50%以上 有权决定对方财务和经营.
做 荷 包 的 主 人 第 一 桶 金 督導 張宏仁 財團法人「張老師」基金會 桃園分事務所 督導 張宏仁
控制方长投下的子公司,需要编制合并报表的演示思路
2011级高考地理复习(第一轮) 第三篇 中国地理 第一章 中国地理概况 第五节 河流和湖泊.
2013届高考复习方案(第一轮) 专题课件.
人民版必修三专题三复习 近代中国 思想解放的潮流 灵石中学 易吉华.
成才之路 · 语文 人教版 • 中国古代诗歌散文欣赏 路漫漫其修远兮 吾将上下而求索.
招考新政与高中学校面临的挑战 芜湖市教育科学研究所 俞宏胜
行政诉讼法.
判断推理,必须学会这些 主讲老师:小胡胡 2016年3月25日20:00 YY频道:
第二单元 生产、劳动与经营.
江苏省2008年普通高校 招生录取办法 常熟理工学院学生处
《中医基础理论》 考试题型特点和答题指导.
建筑业2007年年报 2008年定报培训会 及 工交城建科 蔡婉妮
氧气的制法 装置 原理 练习 随堂检测.
《旅游文化》项目二 姓氏称谓避讳 宁波东钱湖旅游学校.
8.生命活动的调节.
南美洲 吉林省延吉一高中 韩贵新.
2011年广西高考政治质量分析 广西师范大学附属外国语学校 蒋 楠.
第一单元 生活与消费 目 录 课时1 神奇的货币  课时2 多变的价格 课时3 多彩的消费.
透過教學鷹架引導 三年級學生形成科學議題 高雄市復興國小 李素貞 102年3月20日
现代企业高级职业经理人系列课程 管人理事与理人管事 —企业高效人力资源管理 主讲人:李青刚 副教授.
知识回顾 1、通过仔细观察酒精灯的火焰,你可以发现火焰可以分为 、 、 。 外焰 内焰 焰心 外焰 2、温度最高的是 。
2017/3/16 上 (興) 櫃 公 司 僑外資持股情形申報作業.
第一单元 人在社会中生活 综合探究一 从地图上获取信息 第1课时 带着地图定向越野间.
物理精讲精练课件 人教版物理 八年级(下).
长城国际酒店式公寓营销策划报告
项目2-1 店铺的定位.
1 实验目的 观察单缝夫琅和费衍射现象,加深对夫琅和费衍射理论的理解。
你不得不知的几件事 2、图书《10天行测通关特训》 3、网络课程 《网校9元课程系列》《考前强化夜校班》 4、地面课程 《10天10晚名师密授营》《考前预测集训营》
了解太平天国运动的主要史实,认识农民起义在民主革命时期的作用与局限性。
专题二 识图题增分技巧.
B F C D G E B E A 下图是沿20°经线所作的地形剖面示意图
专题一 种群和群落 [考纲要求] 1.种群的特征(Ⅰ)。2.种群的数量变化(Ⅱ)。3.群落的结构特征(Ⅰ)。4.群落的演替(Ⅰ)。
我是情緒管理小高手 黃玲蘭老師.
出入口Y27 往塔城街口/中興醫院 出入口Y25 往延平北路一段/中興醫院 出入口Y23往延平北路一段 出入口Y21往延平北路一段
第1节 光的干涉 (第2课时).
电在我们日常生活、现代化社会中的应用: 电 是 什 么?.
勾股定理 说课人:钱丹.
第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案. 第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案.
第二章 自然环境中的物质运动和能量交换.
XX信托 ·天鑫 9号集合资金信托计划 扬州广陵
江苏省2009年普通高校 招生录取办法 江苏省教育考试院
機車第六篇 事故預防 單元二 行駛中注意事項.
第十三章 收入和利润.
成才之路 · 语文 人教版 · 必修2 路漫漫其修远兮 吾将上下而求索.
編碼 用於資料傳輸及壓縮 漢明碼 霍夫曼編碼.
如何寫工程計畫書 臺北市童軍會考驗委員會 高級考驗營 版.
四川大学 计算机学院 陈 虎 多媒体技术基础 四川大学 计算机学院 陈 虎
人教版数学四年级(下) 乘法分配律 单击页面即可演示.
106年度 南科智慧製造產業聚落推動計畫 場域型計畫結案報告簡報格式 (簡報時請將此頁刪除).
第五章 相交线与平行线 三线八角.
電子白板百萬小學堂 本活動建議搭配電子白板 學生最多可分成2~6組(請按組別按鈕) 老師可以視時間多少,來進行活動 每一組要回答十個問題。
辽宁地区 第九讲 浮力.
第二节 山地的形成.
Welcome 实验:筷子提米.
直线与平行垂直的判定.
不等式的基本性质 本节内容 本课内容 4.2.
线段 射线 直线.
第四章 基本平面图形 线段、射线、直线.
第三章 植物的激素调节.
國立政治大學 96學年度學雜費調整 第二次公聽會
第5章 信源编码.
Presentation transcript:

第三章:Huffman编码 信源概率模型已知的Huffman编码 信源概率模型未知的Huffman编码 Huffman编码中的码字设计 应用:文本、图像、语音 对离散无记忆信源,其冗余度表现在各信源符号出现的概率不相等。通过去除或减少这种冗余,达到数据压缩的目的。

Shannon-Fano 编码 第一个基于Shannon理论的编码 算法 次优码(其研究生David Huffman 改进成了最优码) 以空码开始 计算所有符号的频率/概率 对所有符号按其概率排序 将符号集合划为为两个概率差异最小集合 在第一个集合的码字前加‘0’,在第二个集合的码字前加‘1’ 对划分得到的两个子集递归编码,知道每个集合不能被再划分

Shannon-Fano 编码 (2) a b c d e f a b c d e f 1 1 9 8 6 5 4 2 9 8 6 5 4 1 a b c d e f 9 8 6 5 4 2 a b 9 8 c d e f 6 5 4 2 1

Shannon-Fano 编码 (3) a b c d e f a b c d e f 1 1 1 1 1 9 8 6 5 4 2 9 8 1 1 1 1 a b c d e f 9 8 6 5 4 2 a b 9 8 c d e f 6 5 4 2 1

Shannon-Fano 编码 (4) a b c d e f c d e f a b 1 1 00 01 1 1 1 1 9 8 6 5 2 1 c d e f 6 5 4 2 1 a b 9 8

Shannon-Fano 编码 (5) a b c d e f c d e f a b 1 1 00 01 1 1 1 1 9 8 6 5 4 2 c d e f 6 5 4 2 1 1 a b 9 8

Shannon-Fano 编码 (6) a b c d e f a b c d e f 1 1 1 00 01 10 10 11 11 9 8 6 5 4 2 1 1 1 a b c d e f 9 8 6 5 4 2

Shannon-Fano 编码 (7) a b c d e f c d a b e f 1 1 1 1 00 01 10 10 11 11 9 8 6 5 4 2 1 1 c d 6 5 1 1 a b e f 9 8 4 2

Shannon-Fano 编码 (8) a b c d e f a b e f c d 1 1 1 1 00 01 100 101 11 9 8 6 5 4 2 1 1 1 a b e f 1 9 8 4 2 c d 6 5

Shannon-Fano 编码 (9) a b c d e f e f a b c d 1 1 1 1 00 01 100 101 11 8 6 5 4 2 1 1 1 e f 4 2 a b 1 9 8 c d 6 5

Shannon-Fano 编码 (10) a b c d e f a b c d e f 1 1 1 1 1 00 01 100 101 110 111 a b c d e f 9 8 6 5 4 2 1 1 1 a b 1 1 9 8 c d e f 6 5 4 2

Huffman编码 由David Huffman提出:Robert Fano的信息论作业 Shannon-Fano 编码的改进 对离散无记忆信源,其冗余度表现在各信源符号出现的概率不相等。通过去除或减少这种冗余,达到数据压缩的目的。 David. Huffman. A Method for the Construction of Minimum Redundancy Codes. Proceeding of the IRE, 40(9): 1098-1011

最优前缀码 最优码的一些重要性质 证明 则 !!! 这与最优码相矛盾 !!! 出现频率越高的符号的码长应该越短 出现频率最低的两个符号其长度应该相等 证明 假设相反—该编码肯定是次优的 假设相反 令X, Y 表示出现频率最低的两个符号,且 |code(X)| = k, |code(Y)| = k+1 则 由于是前缀码,code(X) 不能为code(Y)的前缀 同时,所有其他的码字更短  去掉|code(Y)| 的最后一个比特将产生一个新的、更短的前缀码 !!! 这与最优码相矛盾 !!!

Huffman Coding by Example 初始化:为每个字符创建一个集合 字母 码字 概率 集合 集合的概率 a 0.2 b 0.4 c d 0.1 e 字母 码字 概率 集合 集合的概率 a 0.2 b 0.4 c d 0.1 e

Huffman Coding by Example 根据集合的概率对集合进行排序(升序) 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 字母 码字 概率 集合 集合的概率 a 0.2 b 0.4 c d 0.1 e

Huffman Coding by Example 对最前面集合的字母的码字中插入前缀 ‘1’ 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 1 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c

Huffman Coding by Example 对第二个集合中字母的码字中插入前缀‘0’ 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 1 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 1

Huffman Coding by Example 合并最前面的两个集合 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 1 0.1 e 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 1

Huffman Coding by Example 根据集合的概率对集合进行排序(升序) 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 1 0.1 e

Huffman Coding by Example 对最前面集合的字母的码字中插入前缀 ‘1’ 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 1 0.1 e 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 11 0.1 e 10

Huffman Coding by Example 对第二个集合中字母的码字中插入前缀‘0’ 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 11 0.1 e 10

Huffman Coding by Example 合并前两个集合 字母 码字 概率 集合 集合的概率 a 0.2 dea 0.4 b c d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 11 0.1 e 10

Huffman Coding by Example 根据集合的概率对集合进行排序(升序) 字母 码字 概率 集合 集合的概率 a 0.2 dea 0.4 b c d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 0.2 c b 0.4 dea d 11 0.1 e 10

Huffman Coding by Example 对最前面集合的字母的码字中插入前缀 ‘1’ 字母 码字 概率 集合 集合的概率 a 0.2 c b 0.4 dea d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 0.2 c b 0.4 dea 1 d 11 0.1 e 10

Huffman Coding by Example 对第二个集合中字母的码字中插入前缀‘0’ 字母 码字 概率 集合 集合的概率 a 0.2 c b 0.4 dea 1 d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 00 0.2 c b 0.4 dea 1 d 011 0.1 e 001

Huffman Coding by Example 合并前两个集合 字母 码字 概率 集合 集合的概率 a 00 0.2 cdea 0.6 b 0.4 c 1 d 011 0.1 e 010 字母 码字 概率 集合 集合的概率 a 00 0.2 c b 0.4 dea 1 d 011 0.1 e 010

Huffman Coding by Example 根据集合的概率对集合进行排序(升序) 字母 码字 概率 集合 集合的概率 a 00 0.2 b 0.4 cdea 0.6 c 1 d 011 0.1 e 010 字母 码字 概率 集合 集合的概率 a 00 0.2 cdea 0.6 b 0.4 c 1 d 011 0.1 e 010

Huffman Coding by Example 对最前面集合的字母的码字中插入前缀 ‘1’ 字母 码字 概率 集合 集合的概率 a 00 0.2 b 0.4 cdea 0.6 c 1 d 011 0.1 e 010 字母 码字 概率 集合 集合的概率 a 00 0.2 b 0.4 1 cdea 0.6 c d 011 0.1 e 010

Huffman Coding by Example 对第二个集合中字母的码字中插入前缀‘0’ 字母 码字 概率 集合 集合的概率 a 00 0.2 b 0.4 1 cdea 0.6 c d 011 0.1 e 010 字母 码字 概率 集合 集合的概率 a 000 0.2 b 0.4 1 cdea 0.6 c 01 d 0011 0.1 e 0010

Huffman Coding by Example 合并前两个集合 字母 码字 概率 集合 集合的概率 a 000 0.2 b 0.4 1 cdea 0.6 c 01 d 0011 0.1 e 0010 字母 码字 概率 集合 集合的概率 a 000 0.2 abcde 1.0 b 1 0.4 c 01 d 0011 0.1 e 0010 The END

例:总结 平均码长 l = 0.4x1 + 0.2x2 + 0.2x3 + 0.1x4 + 0.1x4 = 2.2 bits/symbol 熵 H = s=a..eP(s) log2P(s) = 2.122 bits/symbol 冗余 l - H = 0.078 bits/symbol

Huffman 树 b c a e d 1 字母 码字 a 000 b 1 c 01 d 0011 e 0010 1 1 1 0.4 0.2 1 字母 码字 a 000 b 1 c 01 d 0011 e 0010 b 1 0.4 c 1 0.2 Huffman: 第一次在数据结构中讲二叉树的时候 为什么压缩领域中的编码方法总和二叉树联系在一起呢?原因非常简单,回忆一下我们介绍过的“前缀编码”:为了使用不固定的码长表示单个字符,编码必须符合“前缀编码”的要求,即较短的编码决不能是较长编码的前缀。要构造符合这一要求的二进制编码体系,二叉树是最理想的选择。 a 1 0.2 e d 0.1 0.1

构建Huffman树 b c a e d 字母 码字 a b c d 1 e 字母 码字 a b c d e 1 0.4 0.2 0.2 字母 码字 a b c d e b 0.4 c 0.2 a 1 0.2 0.2 e d 0.1 0.1

构建Huffman树 (2) b c a e d 字母 码字 a b c d 11 e 10 字母 码字 a b c d 1 e 1 1 b c d 11 e 10 字母 码字 a b c d 1 e b 0.4 1 0.4 c 0.2 a 1 0.2 0.2 e d 0.1 0.1

构建Huffman树 (3) b c a e d 字母 码字 a b c d 11 e 10 字母 码字 a 00 b c 1 d 011 b c d 11 e 10 字母 码字 a 00 b c 1 d 011 e 010 1 0.6 b 0.4 c 1 0.4 0.2 a 1 0.2 0.2 e d 0.1 0.1

构建Huffman树 (4) a b e c d 1 字母 码字 a 00 b c 1 d 011 e 010 字母 码字 a 000 b 1 0.1 0.2 0.4 0.6 1.0 字母 码字 a 00 b c 1 d 011 e 010 字母 码字 a 000 b 1 c 01 d 0011 e 0010

另一棵Huffman树 b a c e d 字母 码字 a b c d e 字母 码字 a b c d 1 e 1 0.4 0.2 0.2 b 0.4 1 0.2 a c e d 0.2 0.2 0.1 0.1

另一棵Huffman树 (2) b a c e d 字母 码字 a b c 1 d e 字母 码字 a b c d 1 e 1 1 0.4 b c 1 d e 字母 码字 a b c d 1 e b 0.4 1 0.4 1 0.2 a c e d 0.2 0.2 0.1 0.1

另一棵Huffman树 (3) b a c e d 字母 码字 a 00 b c 01 d 11 e 10 字母 码字 a b c 1 d b c 1 d e 0.6 1 b 0.4 1 1 0.4 0.2 a c e d 0.2 0.2 0.1 0.1

另一棵Huffman树 (4) b e d 0.1 0.4 1 0.2 a c 0.6 字母 码字 a 00 b c 01 d 11 e 10 字母 码字 a 000 b 1 c 001 d 011 e 010 平均码长 l = 0.4x1 + (0.2 + 0.2 + 0.1 + 0.1)x3= 2.2 bits/symbol

再一棵Huffman树 b e d 0.1 0.4 1 0.2 a c 0.6 字母 码字 a 00 b 11 c 01 d 101 e 100 平均码长 l = 0.4x2+ (0.2 + 0.2)x2 + (0.1 + 0.1)x3= 2.2 bits/symbol

最小方差Huffman树 Huffman编码不惟一 我们应该选择哪一个呢? 为什么? 怎样达到? 但所有编码的平均码长相同 答案:方差最小者为佳(码字长度方差最小) 即高度最小的树 为什么? 编码流中的编码变化最小 怎样达到? 在排序时,将较小的集合(元素数目少)尽可能放在上面 也可以将新合并的集合尽可能放在下面(即认为它们的码长应该更短一些)

最小方差Huffman树 (2) 码字长度的方差 :长度 与平均码长 之差的平方的数学期望,即 编码一码字长度方差: a b e c d 1 码字长度的方差 :长度 与平均码长 之差的平方的数学期望,即 编码一码字长度方差: 合并后的新符号排在其它相同概率符号的前面 a b e c d 1 0.1 0.2 0.4 0.6 1.0

最小方差Huffman树 (2) 编码二码字长度方差: 编码三码字长度方差: b e d a c 0.1 0.4 1 0.2 a c 0.6 编码二码字长度方差: 编码三码字长度方差: 采用第三种编码方法:码长变化较小(比较接近于平均码长) 第一种方法编出的5个码字有4种不同的码长; 第三种方法编出的码长只有两种不同的码长; 显然,第三 种编码方法更简单、更容易实现。 b e d 0.1 0.4 1 0.2 a c 0.6 合并后的新符号排在其它相同概率符号的前面

最小方差Huffman树 (3) a b e c d 1 0.1 0.2 0.4 0.6 1.0 由于码位要以固定的速率传输,所以编码器要用缓冲器平滑比特产生率的变化。码字的方差越大,码位进入缓冲器的速率越不稳定,因而编码器需要的缓冲器也越大 例:假设传输字符的速率固定,如10,000字符/秒,平均码长为2.2 bits/字符,则接收方每秒将平均收到22,000比特 几秒内一直产生包含a4,a5的字符串 采用第一种编码方式,这样产生的比特率为40,000比特/秒,缓冲区每秒需保存18,000比特 采用第三种编码方式,比特率为30,000比特/秒,缓冲区每秒需保存8,000比特 几秒内一直产生包含a1的字符串 采用第一种编码方式,这样产生的比特率为10,000比特/秒,传输带宽浪费12,000比特/秒 采用第三种编码方式,比特率为20,000比特/秒,传输带宽浪费2000比特/秒 方差大的代码将导致编码器的输出码率不断变化 由于比特产生率会在22,000比特/秒,编码器的输出通常被送到缓冲区,以平滑比特产生率的变化。但是缓冲区的大小总是固定的,而码字大的变化对使得缓冲区设计变得更难 b e d 0.1 0.4 1 0.2 a c 0.6

自适应Huffman编码 Huffman编码需要各符号的概率。概率来源: 静态概率模型 :根据训练数据得到,然后不同信源利用同一个概率表 半自适应统计模型: 必须传送Huffman码表和压缩流 需2遍扫描 但在很多情况下不实用:如压缩网络传输 自适应/动态概率模型: 1遍扫描 开始时认为是等概率 根据前k (k = 1, 2, …)个符号统计重新产生码字并编码第k+1st 个字符 Unix系统对程序的压缩:基于单词的自适应Huffman编码 在实际中太昂贵

Huffman解码 在开始压缩之前,编码器必须根据符号的概率(或出现的频率)确定码字 解码器利用这些信息对压缩流进行解码,所以应该将这些信息也写入压缩流中,以便解码器能解码该压缩流 变长码:不好,因为码长不同 写入频率/概率:将频率/概率标定为整数,然后解码器利用该频率信息构造Huffman树通常只会在压缩流中增加几百字节 写入Huffman树:比只写频率花费的字节数更多

Huffman解码 一. 比特串行解码(固定输入比特率——可变输出符号率(假定二进制码树在解码器端可得) 1. 逐个比特读入输入压缩流,并遍历树,直到到达一个叶节点。 2. 输入流的每个比特用过后即丢弃。当到达叶节点时,Huffman解码器输出叶节点处的符号。即完成该符号的解码。 3. 重复步骤1和2,直到所有的输入都解完。 由于所有码字长度不同,解码比特率对所有符号并不相同。

Huffman解码 二. 基于查找表的解码:对所有符号解码率恒定 1. 构造查找表: 在解码端从符号—码字映射表中构建查找表。如果表中的最长码字为l比特,则需要一个2l个入口的查找表。 空间限制:图象/视频最长的l=16~20 1. 构造查找表: 设 对应的码字为 ,假定 有 比特。构造一个l比特地址,前 个比特是 ,后 个比特取任意0和1的组合。所以,对符号 有 个地址。 在每个入口形成

Huffman解码 2. 解码步骤: 从压缩输入比特流中,读l个比特到缓冲区中; 重复步骤2和3,直到所有的符号都解码。

规范Huffman编码 并非只有使用二叉树建立的前缀编码才是 Huffman 编码,只要符合 (1) 是前缀编码 (2) 某一字符编码长度和使用二叉树建立的该字符的编码长度相同 这两个条件的编码都可以叫做 Huffman 编码。 规范(Canonical):简单快速

规范Huffman编码 编码步骤: 统计每个符号的频率 根据这些频率信息求出该符号所需的位数/编码长度 关心的仅仅是该符号在树中的深度,完全没有必要构造二叉树,仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度 (详见《数据压缩原理与应用》2.8.5节) 统计从最大编码长度到1的每个长度对应多少个符号,然后为每个符号递增分配编码 编码输出压缩信息

规范Huffman编码 例:一组16个字符 3比特:4个字符;5比特:5个字符;6比特:7个字符 (b):规范Huffman编码 可能码长: 每个码长的码字: 每组的第一个码字:

规范Huffman编码 例1:(续) 3比特:4个字符;5比特:5个字符;6比特:7个字符 (b)为规范Huffman编码 可能码长: 每个码长的码字: 每组的第一个码字: 保证所有长于l位的码字的前l位前缀小于first[l],满足前缀码的要求

规范Huffman编码 对大字母表且必须快速解码时,规范Huffman编码特别有用 解码规则: 解码器很容易逐个读入和检测输入位来识别码长 知道码长,即可进一步解码读出符号 解码规则: 所有长于l位的码字的前l位前缀小于first[l] 例:输入:00110 v:0,00=0,001=1,0011=3;00110=6 l: 1, 2, 3, 4, 5 first[l]: 2, 4, 3, 5, 4 码长为l=5, v-first[5] = 6-4=2,即符号为码长为5的3个字符(编号从0开始)

规范Huffman编码 码长的确定:用最小堆实现 满二叉树:除叶子节点外的所有节点都有两个分支的二叉树 平衡二叉树:底部有些节点缺少右分支的满二叉树 堆(heap):为平衡二叉树,且树中每个叶子都包含一个有序数据,使得从叶子到根的每条路径都已排序 最小堆:非增序的堆 堆筛选:将堆底部最右边节点的值作为新的树根保证筛选后的数仍是一课平衡二叉树,然后对堆排序,使得其为最小堆

规范Huffman编码 平衡:不用额外的指针就可将其保存在数组中 码长的确定:用一个长度为2m的数组A,其中m为信源符号的数目 数组第i节点的两个分支分别置于第2i和第2i+1位置 数组第j个节点的父亲节点第 位置 码长的确定:用一个长度为2m的数组A,其中m为信源符号的数目 将m个符号出现的频率放在数组的高半段A[m+1]到A [2m]中 将最小堆放在A [1]到A [m]中,堆中的数据项则指向数组高半段频率的指针 然后算法进入循环,在每次迭代中,用堆来找出两个频率最小的数据项,并用其和来替代它们;将和保存在前一个堆的位置A [h]中,这样堆就可以收缩一个位置 重复循环,直到堆中只剩下一个指针

规范Huffman编码 可以不依赖任何树结构进行高速解压缩 而且在整个压缩、解压缩过程中需要的空间比传统 Huffman 编码少得多

Huffman编码的局限性 当符号集较大且概率分布不是很悬殊时,Huffman的平均码长可接近于熵 对于概率分布悬殊的消息集合,上限可能很大,意味着编码冗余度较大 一个极端的例子:黑白传真 采用Huffman编码,得到 ,都需要l=1位,没起到压缩的作用。编码效率仅为 这是因为Huffman编码只能为每个信源符号分配整数个比特,只有当每个符号的概率是2的负整数倍时,才能达到熵值。

Huffman编码的局限性 Huffman编码的平均码长满足平均码长界定定理: 对Huffman编码,更紧致的上界: 令 表示最大概率,若 ,则平均码长满足: 若 ,则平均码长满足: 所以最大概率比较大(概率不均衡)时,上界离熵值相差较大,编码效率不高。

扩展Huffman编码 考虑信源: Huffman 编码: Q:能做得更好吗? A = {a, b, c}, P(a) = 0.8, P(b) = 0.02, P(c) = 0.18 H = 0.816 bits/symbol Huffman 编码: a 0 b 11 c 10 l = 1.2 bits/symbol 冗余 = 0.384 b/sym (47%!) Q:能做得更好吗?

扩展Huffman编码 (2) 思想 考虑对两个字母序列编码,而不是单个字母 l = 1.7228/2 = 0.8614 合并信源符号(联合熵) 字母 概率 码字 aa 0.6400 ab 0.0160 10101 ac 0.1440 11 ba 101000 bb 0.0004 10100101 bc 0.0036 1010011 ca 100 cb 10100100 cc 0.0324 1011 l = 1.7228/2 = 0.8614 冗余 = 0.0045 比特/字符

扩展Huffman编码 (3) 该思想还可以扩展 设码符号集 信源符号的k次扩展: ,其平均长度为 如果要求 为唯一可译码,则 考虑所有mk 的序列 设码符号集 信源符号的k次扩展: ,其平均长度为 如果要求 为唯一可译码,则 每个信源符号的平均码长 当k足够大时,平均码长l可以无限接近下界值,从而在一定程度上提高了编码的有效性

扩展Huffman编码 (4) 理论上,通过考虑更多序列可以改进编码 实践中,字母表随序列长度指数增长使得它不现实 大多数序列的频率为0 如,对长度为3的ASCII序列:2563 = 224 = 16M 大多数序列的频率为0  需要其他方法

例: 离散无记忆信源 X: x1 x2 P(X): 0.2 0.8 则: H(X) = -0.2 log 0.2 -0.8 log 0.8 =0.7219 比特/信符 用二进制符号集A:{0,1}进行无失真信源编码:   x1 → w1=0; x2 → w2=1;

例: 对其二次扩展信源进行编码: X2 p(wi) wi x1x1 1/25 000 x1x2 4/25 001 x2x1 4/25 01

Huffman编码的应用 在实际应用中, Huffman编码通常与其他编码技术一起使用 例:无损图像压缩 Gray images (0~255), Image size: 256*256 Sensin Sena Omaha Earth

在图像压缩中的应用 直接对像素用Huffman编码进行压缩 压缩率不是很高,平均每个像素约减少1比特 更实用的技术:与预测模型一起使用 Image Name Bits/Pexel Total Size (bytes) Compression Ratio Sena 7.01 57,504 1.14. Sensin 7.49 61,430 1.07 Eartch 4.94 40,534 1.62 Omaha 7.12 58.374 1.12

在图像压缩中的应用 对像素差分用Huffman编码进行压缩 利用预测模型 ,然后对预测残差,即像素差分进行编码,带来压缩率的提高 利用预测模型 ,然后对预测残差,即像素差分进行编码,带来压缩率的提高 对像素差分用Huffman编码进行压缩 Image Name Bits/Pexel Total Size (bytes) Compression Ratio Sena 4.02 32, 968 1.99 Sensin 4.70 38,541 1.70 Eartch 4.13 33,880 1.93 Omaha 6.42 52.643 1.24

在文本压缩中的应用 文本压缩比较适合Huffman编码 字母表是离散的,而且概率模型基本稳定 教材3.8.2节中Table 3.26和Table 3.27中不同文本的字母概率很相似 用Huffman编码对教材第三章进行编码,文件大小从70,000字节下降到43,000个字节 可以利用其他技术进一步去除文本中的相关性(教材第五章和第六章)

Estimated Compression 在音频压缩中的应用 CD质量的音频: 采样频率:44.1kHz;每个样本16比特 数据量巨大 对16比特的CD质量音频用Huffman编码进行压缩 File Name Original File Size (Bytes) Entropy (bits) Estimated Compression File Size (bytes) Compression Ratio Mozart 939,862 12.8 725,420 1.30 Cohn 402,442 13.8 349,300 1.15 Mir 884.020 13.7 759,540 1.16

Estimated Compression 在音频压缩中的应用 利用预测模型 ,然后对预测残差,即像素差分进行编码,带来压缩率的提高 对16比特的CD质量音频差分用Huffman编码进行压缩 File Name Original File Size (Bytes) Entropy (bits) Estimated Compression File Size (bytes) Compression Ratio Mozart 939,862 9.7 569,792 1.65 Cohn 402,442 10.4 261,590 1.54 Mir 884.020 10.9 602,240 1.47

小结 最早的Shannon—Fano 编码 Huffman编码 其他 考虑了信源的统计特性:经常出现的信源符号对应较短的码字 编码方法不惟一,码长方差较小的编码更好 对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单 其他 Huffman Optimality of Huffman Codes /3.2.2/ Non-binary Huffman Codes /3.3/ 相关编码 Golomb /3.5/ Rice /3.6/ Tunstall /3.7/

下节课内容: 作业:第三章2、3、4、5 2(c)不做 算术编码/自适应算术编码