38分治算法:谈一谈大规模计算框架MapReduce中的分治思想.pdf
《38分治算法:谈一谈大规模计算框架MapReduce中的分治思想.pdf》由会员分享,可在线阅读,更多相关《38分治算法:谈一谈大规模计算框架MapReduce中的分治思想.pdf(10页珍藏版)》请在文库网上搜索。
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.从前往后两两比较,若前数大于等于后数,选择移除
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 38 分治 算法 谈一谈 大规模 计算 框架 MapReduce 中的 思想