算法导论课件第10讲赫夫曼编码
43页1、1,第4章 贪心算法,赫夫曼编码 单源最短路径,2,Huffman codes,3,Huffman codes,Data Compression via Huffman Coding Motivation Limited network bandwidth. Limited disk space. Human codes are used for data compression. Reducing time to transmit large files, and Reducing the space required to store them on disk or tape. Huffman codes are a widely used and very effective technique for compressing data, savings of 20% to 90% are typical, depending on the characteristics of the data.,4,Problem Suppose that you have a file of
2、 100K characters. To keep the example simple, suppose that each character is one of the 6 letters from a through f. Since we have just 6 characters, we need just 3 bits to represent a character, so the file requires 300K bits to store. Can we do better? Suppose that we have more information about the file: the frequency which each character appears. Solution The idea is that we will use a variable length code instead of a fixed length code (3 bits for each character), with fewer bits to store th
3、e common characters, and more bits to store the rare characters.,Huffman codes,5,Example of Data Compression,For example, suppose that the characters appear with the following frequencies, and following codes: Then the variable-length coded version will take not 300K bits but 45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4 = 224K bits to store, a 25% saving. In fact this is the optimal way to encode the 6 characters present, as we shall see.,6,Characteristic of Optimal Code,Represented as a binary tree wh
4、ose leaves are the given characters. In an optimal code each non-leaf node has two children.,7,Prefix-free Code,In a Prefix code no codeword is a prefix of another code word. Easy encoding and decoding. To encode, we need only concatenate the codes of consecutive characters in the message. The string 110001001101 parses uniquely as 1100-0-100-1101, which decodes to FACE. To decode, we have to decide where each code begins and ends. Easy, since, no codes share a prefix.,8,Example of Huffman codes
《算法导论课件第10讲赫夫曼编码》由会员E****分享,可在线阅读,更多相关《算法导论课件第10讲赫夫曼编码》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页