哈夫曼编码 Huffman编码,进行数据压缩 a假设某文本共有1000个字符,且只由a,b,c,d,e 5种字符组成 若已统计出各字符出现的概率分别为012,040,0.15, 008,025,则整个文本可用2150比特表示 平均编码长度(带权路径长度 1.0 B(T)=0.12*4+0.0834+0.153+0.25*2+0.40*1 2.15 符号概率 Huffman编码 040( (b) 0.6 0.12 1111 25(e 35 b 0.40 0.15 110 D15(c(02 d0.08 1110 08d.12a 0.25 16
哈夫曼编码 ◼ Huffman编码，进行数据压缩 假设某文本共有1000个字符，且只由 a, b, c, d, e 5种字符组成 ➢ 若已统计出各字符出现的概率分别为0.12, 0.40, 0.15, 0.08, 0.25，则整个文本可用2150比特表示 16 0.2 0.25(e) 0.15(c) 0.08(d) 0.12(a) 0.35 0.40(b) 0.6 1.0 0 0 0 0 1 1 1 1 符号 概率 Huffman编码 a 0.12 1111 b 0.40 0 c 0.15 110 d 0.08 1110 e 0.25 10 平均编码长度(带权路径长度) B(T) = 0.12*4 + 0.08*4 + 0.15*3 + 0.25*2 + 0.40*1 = 2.15
哈夫曼编码 Q百 a 最优子结构 口T是字符表C一棵哈夫曼树。设字符x和y是T中任 意两个相邻叶结点,z是其父结点,fx)和fy)是其 频率。将z看作频率是f(2)=fx)+(y)的字符,T=T xy}是字母表C=c-{xyU{2的哈夫曼树 证明: 若T不是C的哈夫曼树(最优解),则必存在T”,使 B(T”)<B(T)。因为z是C中字符,它必为T中的叶子 把结点x与y加入T,作为z的子结点,得到c的哈夫 曼树T”,B(T”)=B(Ty)+x+fy)<B(T)+f(x)+f(y)<B(T) 这与T是c的哈夫曼树矛盾 问题的最优解包含子问题的最优解 17
哈夫曼编码 17 ◼ 最优子结构 T是字符表C一棵哈夫曼树。设字符x和y是T中任 意两个相邻叶结点，z是其父结点，f(x)和f(y)是其 频率。将z看作频率是f(z)=f(x)+f(y)的字符，T’=T- {x,y}是字母表C’=C- {x,y}∪{z}的哈夫曼树 证明： ➢ 若T’不是C’的哈夫曼树(最优解) ，则必存在T’’，使 B(T’’)<B(T’)。因为z是C’中字符，它必为T’’中的叶子 。把结点x与y加入T’’，作为z的子结点，得到C的哈夫 曼树T’’’，B(T’’’)=B(T’’)+f(x)+f(y)<B(T’)+f(x)+f(y)<B(T)。 这与T是C的哈夫曼树矛盾。 z x y T T’ z 问题的最优解包含子问题的最优解