计算之魂总和最大区间(计算之魂扫描版)

本文节选自《计算之魂》电子版：

/第3章//万物皆编码一抽象与表示/要求。能够理解那些编码算法的原理，是四级工程师的要求。如果你想达到三级工程师的水平，就需要能根据情况修改那些标准的编码，在特定情况下将其性能提高一个数量级，或至少提高几倍。要点有效编码的关键在于将较短的码字给予出现概率高的信息，将较长的码字给予不常出现的信息。但不论如何编码，编码的平均码长不会短于相应信号源的信息粒。思考题3.5Ql.假定常用的汉字有10000个，根据出现概率将它们分为50组，每组汉字的数量不同。第一组汉字出现频率最高，第二组为次高频率，以此类推，最后一组为最低频率。每一组汉字出现的总概率都是1%上左右，如何用10个数字，设计对这10000个字的编码，让平均码长最短。(议食密帘将)Q2.在输夫曼编码中以及例题3.4中，除了最长的编码，其余均以0结束【当然也可以以1结尾)，这是为什么?【〔(帘福)3.6”和矩阵的有效表示对于同样的信息，用不同编码方式存储，效率显然不同，有些方式效率比较高，有些则带有大量的元余，效率较低。比如要表示一个人的年龄，如果用三个字符存储，需要三字节，毕竟高寿100多岁的长者并不少见。但

吴军 计算之魂

是，如果把一字节对应为一个“很短”的整数，可以表示0~255的动态范围，而今天还没有人能够接近255岁这个年龄马，因此用一个八位无符号的整数表示年龄是最有效的信息表示方法，比接写成三位数的字符串能节省2/3的存储空间。优秀的从业者在做工程时，脑子里一会有一根弦，会认真考虑信息编码的效率。向”世界上没有争议的长寿纪录是119岁，即使算上有争议的纪录，也不过122岁。123//计算之魂//当然，在上面的例子中，好的信息表示方式和差的之间不过是相差几倍而已，但是对于稍微复杂一点的问题，信息表示得有效和无效，就能差出几十、几百甚至成干上万倍。在计算机的应用中，经常会遇到的一类问题就是如何有效地表示一个多维的矩阵，这也是那些做信息处理的公司在面试时经常问到的问题。我们先从二维矩阵的表示说起。二维矩阵其实很简单，它的形式如下00iD芭..09010=[)上己尼尼ID上已已与扣在计算机数据结构中，最直接的做法是用一个二维数组表示这个矩阵，而所需存储空间就是矩阵两个维度的乘积，记作MXN，M表示行数，N表示列数。我们把这种表示二维矩阵的方法称为“方法零\"。如果和六这两个值非常

计算之魂作者吴军

大，就要占用大量空间。比如，我们想了解两个单词一前一后出现的频率，可以将这两个词用两个数字进行编号，一个数字对应矩阵的行，另一个对应矩阵的列，频率就是相应行/列位置上的元素。比如,，“of”和“the”这两个词，of对应于数字3425，the对应于118382。ofthe出现的频率，就是矩阵中第3425行、第118382列对应的那个元素值。，大型字典里大约有20万个单词，这样一个矩阵就大得不得了，大约有400亿个元素。如果每一个元素需要2字节表示，就需要80吉字节(GB)的存储空间。即使是中文字典里通常也有6万~10万个字，相应的矩阵也不小。当然，还在英语有很多比单词之间同现频率矩阵大得多的二维数组，比如在计算网页排名(PageRank)时所需要的网页和网页之间的链接信息，其实也是一个二维数组。假定世界上有100亿个网页(实际的数目远大于此)，那么这个二维数组就有!万亿亿个元素。即使把Google、亚马逊和微软等全世界大型互联网公司的服务器都用上，也存不下这一个数组。然而Google毕竟实现了PageRank算法，这说明在有效表示二维数组方面存在非常124

计算之魂作者

综上：计算之魂扫描版值得推荐阅读