1、减少存储空间，每个字符我们用3个二进制位来表示。那存储这1000个字符只需要3000bits就可以了，比原来的存储方式节省了很多空间。不过，还有没 有更加节省空间的存储方式呢？ a(000)、b(001)、c(010)、d(011)、e(100)、f(101) 霍夫曼编码就要登场了。霍夫曼编码是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在20%90%之间。 霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。霍夫曼编码试图用这种不等长的编码 方法，来进一步增加压缩的效率。如何给不同频率的字符选择不同长度的编码呢？根据贪心的思
2、想，我们可以把出现频率比较多的字符，用稍微短一些的编码； 出现频率比较少的字符，用稍微长一些的编码。 对于等长的编码来说，我们解压缩起来很简单。比如刚才那个例子中，我们用3个bit表示一个字符。在解压缩的时候，我们每次从文本中读取3位二进制码，然后 翻译成对应的字符。但是，霍夫曼编码是不等长的，每次应该读取1位还是2位、3位等等来解压缩呢？这个问题就导致霍夫曼编码解压缩起来比较复杂。为了避免 解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。 假设这6个字符出现的频率从高到低依次是a、b、c、d、e、f。我们把它们编码下面这个样子，任何一个字符的编码
3、都不是另一个的前缀，在解压缩的时候，我们 每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。经过这种编码压缩之后，这1000个字符只需要2100bits就可以了。 37|贪心算法：如何用贪心算法实现Huffman压缩编码？ file:/F/temp/geektime/数据结构与算法之美/37贪心算法：如何用贪心算法实现Huffman压缩编码？.html2019/1/15 15:36:23 尽管霍夫曼编码的思想并不难理解，但是如何根据字符出现频率的不同，给不同的字符进行不同长度的编码呢？这里的处理稍微有些技巧。 我们把每个字符看作一个节点，并且辅带着把频率放到优先级队列中。我们
4、从队列中取出频率最小的两个节点A、B，然后新建一个节点C，把频率设置为两个节 点的频率之和，并把这个新节点C作为节点A、B的父节点。最后再把C节点放入到优先级队列中。重复这个过程，直到队列中没有数据。 37|贪心算法：如何用贪心算法实现Huffman压缩编码？ file:/F/temp/geektime/数据结构与算法之美/37贪心算法：如何用贪心算法实现Huffman压缩编码？.html2019/1/15 15:36:23 现在，我们给每一条边加上画一个权值，指向左子节点的边我们统统标记为0，指向右子节点的边，我们统统标记为1，那从根节点到叶节点的路径就是叶节点对 37|贪心算法：如何用贪心
5、算法实现Huffman压缩编码？ file:/F/temp/geektime/数据结构与算法之美/37贪心算法：如何用贪心算法实现Huffman压缩编码？.html2019/1/15 15:36:23 应字符的霍夫曼编码。 内容小结 今天我们学习了贪心算法。 实际上，贪心算法适用的场景比较有限。这种算法思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法，这些算法都用到了贪心算法。从 我个人的学习经验来讲，不要刻意去记忆贪心算法的原理，多练习才是最有效的学习方法。 贪心算法的最难的一块是如何将要解决的问题抽象成贪心算法模型，只要这一步搞定之后，贪心算法的编码一般都很简单。贪心算法
6、解决问题的正确性虽然很多 时候都看起来是显而易见的，但是要严谨地证明算法能够得到最优解，并不是件容易的事。所以，很多时候，我们只需要多举几个例子，看一下贪心算法的解决 方案是否真的能得到最优解就可以了。 37|贪心算法：如何用贪心算法实现Huffman压缩编码？ file:/F/temp/geektime/数据结构与算法之美/37贪心算法：如何用贪心算法实现Huffman压缩编码？.html2019/1/15 15:36:23 课后思考 1. 在一个非负整数a中，我们希望从中移除k个数字，让剩下的数字值最小，如何选择移除哪k个数字呢？ 2. 假设有n个人等待被服务，但是服务窗口只有一个，每个人
7、需要被服务的时间长度是不同的，如何安排被服务的先后顺序，才能让这n个人总的等待时间最 短？ 欢迎留言和我分享，也欢迎点击“请朋友读”，把今天的内容分享给你的好友，和他一起讨论、学习。 37|贪心算法：如何用贪心算法实现Huffman压缩编码？ file:/F/temp/geektime/数据结构与算法之美/37贪心算法：如何用贪心算法实现Huffman压缩编码？.html2019/1/15 15:36:23 精选留言： cirno 2018-12-17 03:04:31 1、由最高位开始，比较低一位数字，如高位大，移除，若高位小，则向右移一位继续比较两个数字，直到高位大于低位则移除，循环k次，
8、如： 4556847594546移除5位-455647594546-45547594546-4547594546-4447594546-444594546 37|贪心算法：如何用贪心算法实现Huffman压缩编码？ file:/F/temp/geektime/数据结构与算法之美/37贪心算法：如何用贪心算法实现Huffman压缩编码？.html2019/1/15 15:36:23 2、由等待时间最短的开始服务 30赞 luxinfeng 2018-12-17 03:12:54 老师能详细讲讲区间覆盖这个问题的选择过程么？ 7赞 Jalyn 2018-12-17 00:34:45 想知道目前没掉
9、队的有多少 哈哈 7赞 作者回复2018-12-17 01:27:39 慢慢学 不着急 开心小毛 2018-12-31 02:01:10 找零问题不能用贪婪算法，即使有面值为一元的币值也不行：考虑币值为100，99和1的币种，每种各一百张，找396元。 动态规划可求出四张99元，但贪心算法解出需三张一百和96张一元。 3赞 作者回复2019-01-02 02:06:45 是的 feifei 2018-12-20 00:20:06 1，在一个非负整数 a 中，我们希望从中移除 k 个数字，让剩下的数字值最小，如何选择移除哪 k 个数字呢？ 对于此题，我的求解思路是每次选择数据的最高位的数据值进行
10、移除，这样我们每次选择的移除的数值都是最大的，剩下的数值也是最小的。 比如，数据5892，将数据拆成5000,800,90,2，然后使用大顶堆来进行存储，然后每次移除大顶堆中堆顶最大的元素。 2，假设有 n 个人等待被服务，但是服务窗口只有一个，每个人需要被服务的时间长度是不同的，如何安排被服务的先后顺序，才能让这 n 个人总的等待时 间最短？ 对于此问题，我的求解思路是让待时间最长的来安排先后顺序 比如，现在有3个人，a、b、c,a等待了10分钟，b待待了20分钟，c待待了30分钟 同样使用大顶堆来进行存储等待时间，堆顶的元素就是当前等待时间最长的人 然后每次从堆拿出堆顶元素的人来进行服务，
11、这样就可以让这n个人的总的等待时间最短。 对于学习的贪心算法，老师虽然只进行了理论讲解，但我看完了老师所讲的，我对贪心算法的理解有了一定的认识，我就试着把贪心算法的内容中涉及的东 西，都翻译成了代码， 感觉收获良多，也把这个分享给童鞋，希望对他们有帮助。 37|贪心算法：如何用贪心算法实现Huffman压缩编码？ file:/F/temp/geektime/数据结构与算法之美/37贪心算法：如何用贪心算法实现Huffman压缩编码？.html2019/1/15 15:36:23 1，这是第一个示例，背包中豆子的最大价值的问题 2，这是孩子分糖果的问题 3，这是钱币支付的问题 4，这是区间覆盖的
12、问题 5，这是霍夫漫编码的实现 欢迎大家与我交流，也欢迎老师给我指正，谢谢 3赞 您的好友William 2018-12-17 06:04:52 给大家提个醒，货币找零问题如果没有C1货币的话得用动态规划去解，如果出现C2，C7，C10货币找零11块的时候使用greedy就会出现找不开的情况。 。有C1就不会出现找不开的情况且多个C1可以构成任何面值，所以这种情况下使用greedy是对的！（leetcode322题调了一下午的路过。） 3赞 白若 2018-12-17 04:50:40 思考题(自己的想法，不知道对不对，希望老师能给我评论。) 1.从前往后两两比较，若前数大于等于后数，选择移除
13、。如果一轮下来没达到k个数，就移除最后的m个数，m为k-已选出个数。 2.时间越短位置越靠前。 2赞 小美 2018-12-17 02:32:41 老师 区间覆盖的问题， (1-5) 和 (2-4) 中为什么选(2-4) 方便老师解释下吗， 贪心不能全局最优 用贪心 如何在这个问题上全局最优呢 2赞 作者回复2018-12-18 02:02:44 24让剩下的没有被覆盖的区间最大 如果你选15 那我完全可以用24替代15 这样子 只有更好 不会更差 观弈道人 2019-01-03 10:51:56 感觉追求最优解的算法都可以称为贪心算法了，比如哈夫曼编码 1赞 新丁 2018-12-19 12
14、:07:39 贪心算法并不一定能获得最优解！学习做事也一样不能总看眼前的最优选择，坚定目标，踏踏实实的往wxPython in Action 译文 1 / 565 本书由 H a r r i Pa s a n e n 和 Ro b i n D u n n 所著 由 滴水（w w w . p y t h o n t i k . c o m ）翻译 由 l a . o n g e r ( l a -o n g e r . l o n g -e r . n a m e ) 整理成p d f 版本 Part1 wxPython入门 19 1. 欢迎来到wxPython 19 1.1 开始wxPytho
15、n 20 1.2 创建最小的空的wxPython程序 20 1.2.1 导入wxPython 21 1.2.2 使用应用程序和框架工作 22 子类化wxPython application类 23 定义一个应用程序的初始化方法 23 创建一个应用程序实例并进入它的主事件循环 23 1.3 扩展这个最小的空的wxPython程序 24 1.4 创建最终的hello.py程序 26 2、给你的wxPython程序一个稳固的基础 28 2.1 关于所要求的对象我们需要知道些什么？ 28 2.2 如何创建和使用一个应用程序对象？ 29 2.2.1 创建一个wx.App的子类 29 何时省略wx.App
16、的子类 30 2.2.2 理解应用程序对象的生命周期 31 2.3 如何定向wxPython程序的输出? 31 2.3.1 重定向输出 32 2.3.2 修改默认的重定向行为 34 2.4 如何关闭wxPython应用程序? 34 2.4.1 管理正常的关闭 35 2.4.2 管理紧急关闭 35 2.5 如何创建和使用顶级窗口对象? 36 2.5.1 使用wx.Frame 36 2 / 565 2.5.2 使用wxPython的ID 37 明确地选择ID号 38 使用全局性的NewID()函数 38 2.5.3 使用wx.Size和wx.Point 38 2.5.4 使用wx.Frame的样式
17、 39 2.6 如何为一个框架增加对象和子窗口? 41 2.6.1 给框架增加窗口部件 42 2.6.2 给框架增加菜单栏、工具栏和状态栏。 44 2.7 如何使用一般的对话框? 45 消息对话框 46 文本输入对话框 47 从一个列表中选择 47 2.8 一些最常见的错误现象及解决方法? 48 2.9 总结 49 3、在事件驱动环境中工作 51 3.1 要理解事件，我们需要知道哪些术语？ 51 3.2 什么是事件驱动编程? 52 3.2.1 编写事件处理器 54 3.2.2 设计事件驱动程序 55 3.2.3 事件触发 55 3.3 如何将事件绑定到处理器? 56 3.3.1 使用wx.Ev
18、tHandler的方法工作 57 3.4 wxPython是如何处理事件的? 61 3.4.1 理解事件处理过程 62 第一步，创建事件 64 第二步，确定事件对象是否被允许处理事件。 64 第三步 定位绑定器对象 65 3 / 565 第四步 决定是否继续处理 66 第五步 决定是否展开 67 3.4.2 使用Skip()方法 68 3.5 在应用程序对象中还包含哪些其它的属性？ 70 3.6 如何创建自己的事件？ 71 3.6.1 为一个定制的窗口部件定义一个定制的事件。 71 创建自定义事件的步骤： 71 3.7 总结 75 4、用PyCrust使得wxPython更易处理 76 4.1
19、 如何与wxPython程序交互？ 76 PyCrust配置了标准的Python shell 77 4.2 PyCrust的有用特性是什么？ 79 4.2.1 自动完成 80 4.2.2 调用提示和参数默认 80 4.2.3 语法高亮 81 4.2.4 Python 帮助 81 4.2.5 命令重调用 82 4.2.6 剪切和粘贴 83 4.2.7 标准shell环境 84 4.2.8 动态更新 85 4.3 PyCrust notebook的标签是干什么的？ 87 4.3.1 Namespace标签 87 4.3.2 Display标签 89 4.3.3 Calltip（调用提示）标签 89
20、 4.3.4 Session标签 90 4.3.5 Dispatcher 标签 90 4.4 如何将PyCrust应用于wxPython应用程序。 92 4 / 565 4.5 在Py包中还有其它什么？ 96 4.5.1 使用GUI程序工作 97 4.5.2 使用支持模块工作 97 buffer模块 98 crust 模块 100 dispatcher模块 100 editor模块 102 fi lling模块 102 interpreter模块 103 introspect模块 103 shell模块 103 4.6 如何在wxPython中使用Py包中的模块? 104 4.7 本章小结 1
21、08 5、创建你的蓝图 109 5.1 重构如何帮我改进我的代码？ 109 5.1.1 一个重构的例子 110 5.1.2 开始重构 113 5.1.3 进一步重构 114 5.2 如何保持模型(Model)与视图(View)分离？ 118 5.2.1 MVC(Model-View-Controller)系统是什么？ 118 5.2.2 一个wxPython模型：PyGridTableBase 120 PyGridTableBase的方法 122 使用PyGridTableBase 123 使用PyGridTableBase：特定于应用程序（不通用）的子类 123 使用PyGridTableB
22、ase：一个通用的例子 125 使用PyGridTableBase：一个独立的模型类 127 5.2.3 自定义模型 129 5 / 565 欢迎加入非盈利Py t h o n 编程学习交流QQ群783462347，群里免费提供500+本Py t h o n 书籍！ 5.3 如何对一个GUI程序进行单元测试？ 133 5.3.1 unittest模块 134 5.3.2 一个unittest范例 135 5.3.3 测试用户事件 137 5.4 本章小结 138 6、使用基本的建造部件 140 6.1 在屏幕上绘画 141 6.1.1 如何在屏幕上绘画 141 使用设备上下文 141 设备上下
23、文的函数 147 6.2 添加窗口装饰 149 6.2.1 如何添加和更新一个状态栏 149 6.2.2 如何添加菜单？ 152 6.3 得到标准信息 156 6.3.1 如何使用标准文件对话框？ 156 6.3.2 如何使用标准的颜色选择器？ 160 6.4 给应用程序一个好看的外观 161 6.4.1 如何布局窗口部件？ 161 创建一个sizer 161 使用sizer 162 6.4.2 如何建造一个关于(about)框？ 168 6.4.3 如何建造一个启动画面？ 170 6.5 本章小结 172 Part 2 基本的wxPython 174 7、使用基本的控件工作 175 7.1
24、显示文本 175 6 / 565 欢迎加入非盈利Py t h o n 编程学习交流QQ群783462347，群里免费提供500+本Py t h o n 书籍！ 7.1.1 如何显示静态文本？ 175 如何显示静态文本 176 使用样式工作 178 其它显示文本的技术 178 7.1.2 如何让用户输入文本？ 179 如何创建文本输入控件 179 使用单行文本控件样式 180 7.1.3 不输入的情况下如何改变文本？ 181 7.1.4 如何创建一个多行或样式文本控件? 182 使用多行或丰富文本样式 184 7.1.5 如何创建一个字体？ 186 7.1.6 如果我们系统不支持丰富文本，那么我
25、还能使用样式文本吗？ 187 7.1.7 如果我的文本控件不匹配我的字符串该怎么办？ 187 7.1.8 如何响应文本事件？ 188 7.2 使用按钮工作 189 7.2.1 如何生成一个按钮？ 189 7.2.2 如何生成一个位图按钮？ 191 7.2.3 如何创建开关按钮（toggle button）？ 192 7.2.4 什么是通用按钮，我为什么要使用它？ 193 7.3 输入并显示数字 196 7.3.1 如何生成一个滑块？ 196 如何使用滑块 197 使用滑块样式工作 198 7.3.2 如何得到那些灵巧的上下箭头按钮？ 199 如何创建一个微调控制器 199 7.3.3 如何生成一个进度条？ 201 7.4 给用户以选择 202 7.4.1 如何创建一个复选框？ 202 7 / 565 欢迎加入非盈利Py t h o n 编程学习交流QQ群783462347，群里免费提供500+本Py t h o n
个人主页