算法课件Lecture12章节
37页1、 2004 SDU,Lecture 12 Huffman Codes Problem and Catalan Number,-ordered Tree Huffman Coding Problem Algorithm and correctness Catalan Number, 2004 SDU 2,-ordered trees,A -ordered tree is a tree-like graph satisfying There is a distinguished vertex called root Each internal vertex v has at most children and each edge starting from v is labeled by a unique symbol in = 0, 1, , -1; The leaves (out-degree=0) have no children.,An example of 3-ordered tree,Each vertex v corresponds to a word: the sequen
2、ce of symbols on the path from the root to the vertex. Example: 0, 01, 12, 2, 2004 SDU 3,-ordered trees vs prefix codes,A code C is called prefix code if no codeword in C is a prefix of some other codewords. Clearly, the leaves of a -ordered tree correspond to a prefix code, and Each prefix code can be described by a -ordered tree,Prefix Code C = 00, 01, 12, 2, 2004 SDU 4,Huffman Codes,Huffman code was proposed by David A. Huffman in 1952. A Huffman code is a prefix code, so is a uniquely decoda
3、ble code The main application of Huffman codes is data compression, typically saving 20% to 90%. A Huffman code can be constructed from the frequencies of each source symbol., 2004 SDU 5,English Alphabet,Sym Prob Sym Prob Sym Prob Blk 0.1859 I 0.0575 R 0.0484 A 0.0642 J 0.0008 S 0.0514 B 0.0127 K 0.0049 T 0.0796 C 0.0128 L 0.0321 U 0.0228 D 0.0317 M 0.0194 V 0.0083 E 0.1031 N 0.0574 W 0.0175 F 0.0208 O 0.0632 X 0.0013 G 0.0152 P 0.0152 Y 0.0164 H 0.0467 Q 0.0008 Z 0.0005, 2004 SDU 6,The Huffman
4、Coding Problem,Input: A set S = s1, s2, , sn of n source symbols with independent probabilities p1, p2, , pn. Output: A prefix code C = C1, C2, ,Cn for S on alphabet = 0, 1, 2, , -1 with minimum average length where li is the length of Ci. Note: This is equivalent to minimize the length of the code of the file given the source symbols. Given a file, does this method give a true shortest code?, 2004 SDU 7,Idea of Huffman Coding,Directly follow the proof of Property 2 of Kraft inequality: If a set
《算法课件Lecture12章节》由会员E****分享,可在线阅读,更多相关《算法课件Lecture12章节》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页