本节书摘来华章计算机《伟大的计算原理》一书中的第3章 ，［美］彼得 J. 丹宁（Peter J. Denning）
克雷格 H. 马特尔（Craig H. Martell）著 罗英伟 高良才 张 伟 熊瑞勤 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
信息的测量
香农设计了一个用于测量信息源中所含信息的方法，因为他想知道信息源中最短码的长度。编码的位数量并不能作为一个衡量标准，正如我们在上文中所看到的，单个信息源可以用任意数量的不同编码来表示。他的结论是一个好的衡量标准应该是消息集合中最短编码的长度，若编码再短一些则无法传输消息源的所有信息。
他认为衡量信息不应该依赖人类所观察到的编码的含义，而应该忽略信息的上下文，寻求编码、传输和解码的固定工作机制。邮政服务遵循相似的准则：他们的分发和传输系统从不依赖于所运输的信封中的内容。香农非凡的洞察力表现在“将信息的接收等同于不确定性的减少”。他定义信息为判断信息源正在传送哪个消息所需要回答的是非（yes-no）问题的最小数量。我们越了解某个信息源可能会发送什么消息，那么看到这条消息时所获得的信息量就越少。
假设你知道某人将会只回答一个是非问题，但提前无法得知回答者的答案，那么回答者通过回答解决了你的不确定性。香农认为回答者只给了你一位的信息（1或0），即从两种可能答案中选择其中一个。当答案有两个以上时，需要更多的位来区分发送的消息。
假设我们想在电话簿中找到含有某个朋友名字的那一页，那么需要多少位来对页数进行编码呢？一个聪明的方法回答了这个问题：我们从中间打开电话簿，然后询问哪一半含有朋友的名字（由于使用字母顺序编写电话簿，这个问题就很容易回答）。然后我们把含有名字的那一半电话簿再分割成两半，询问同样的问题。重复这个步骤，直到只剩一页，这个朋友的名字就应该在那一页上。这个重复的问题（“哪一半”或者说“是否在左边一半”）让我们快速定位。对于一本有512页的电话簿，第一个问题留下了256页来搜索，第二个问题留下128页，然后64，32，16，8，4，2，最后是1。需要9个“哪一半”问题来寻找包含名字的那一页。因此，当找到包含朋友名字的那一页时，我们获取了9位的信息量。
在构建编码时，人们需要思考消息的发生概率。塞缪尔·莫斯（Samuel Morse）发明了莫斯密码，并将之应用于19世纪30年代他参与发明的电报中。他分配最短的编码（单个点）来表示字母e，因为e是在英文中使用最频繁的字母（大约12%）。他将最长的编码分配给字母j，因为j是最少使用的字母之一（约0.15%）。这样的分配减少了传输的平均长度。图3.4说明了用以识别一个消息的问题可以用来定义信息编码，以及关于消息发生概率的先验知识会减少编码量。
假设我们有一长度为Li、概率为Pi的码字集合。那么编码的平均长度就是
对于图3.4中的编码，公式计算出第一种编码的平均长度是2位，而第二种编码的平均长度是1.75位。
在最优编码中，码字的长度即最小的L是多少呢？香农在他1948年论文的附录中回答了这个问题。他表示最优码字的长度是以2为底的码字出现概率的对数的相反数，即-log2Pi。因此，最优编码的平均长度是
这个公式和热力学的熵公式具有同样的形式，也有着相似的解释。熵是衡量系统状态的混乱程度或是不确定性的指标。一个系统的状态越混乱，熵就越高。最大的混乱度发生在所有的状态都有同等发生概率的情况下，最大的有序度则发生在某一种状态非常确定而其他的状态都绝不会发生的情况下。
香农认为熵是信息源中固有信息的衡量标准。一个信息源由一组可能的消息和消息发生的概率构成。熵只取决于消息的概率而不是它们的编码，熵可以确定最短可能编码的平均长度。任何更短的编码都将导致混淆从而无法得到唯一的解码结果。如下面的例子：
**A：1
B：0
C：01
D：10
**
图3.4 香农将一个消息中的信息量定义为将该消息从消息源中筛选出来需要回答的是非问题数，这些问题是用来减少“哪个是被发送消息”的不确定性的。试想，如果我们要从四个人中发现被某任务选中的人，则可以使用一个简单的决策树（上图），我们问：“是Alice或者Bob吗？”如果答案为是，则决策选择左边的子树。再问一个问题“是Alice吗？”，答案就揭晓了。每个个体的编码就是指向他/她的是非问题答案的路径。如果知道某个个体被选中的概率（下图括号里的数字），那么我们可以构造一个等级决策树，从而使得编码长度不等。例如，如果Alice是最有可能被选中的，我们就把编码1分配给他。Bob是下一个最有可能的，则分配编码为01，然后是Charlie和Diana，他们有相同的选中概率，则都被编码为3位
如果以上这些消息出现的概率分别是0.5、0.25、0.125和0.125，平均编码长度就是1.25位。然而，接收方对于1001代表ABBA，ABC，DBA还是DC却无法分辨。这条消息的熵（根据上面的公式计算得出）是H = 1.75，界定了编码是否能够解析的阈值。这条编码的平均长度是1.25位，低于此阈值，所以编码无法解析。
哈夫曼（Huffman）编码是一种快速在熵阈值内进行位编码的方法（图3.5）。
图3.5 1951年麻省理工学院的大卫·哈夫曼（David Huffman）设计了一套编码算法，在已知消息概率的情况下，此编码算法能够使得平均编码长度最小。该算法首先将每个消息都视为一棵单独的树。然后不断地将两棵具有最小概率的树进行合并，合并后树的概率为两棵子树的概率和。对于一个具有n条消息的编码，需要n次合并，形成最后的树。在本例中，Charlie和Diana首先合并，然后他们合并后的树和Bob合并，最后和Alice合并。树中的每条路径定义了每一条消息的二进制位编码。哈夫曼的方法所生成的编码能够将平均编码长度控制在熵阈值范围内。若所有的消息具有相等的概率，则生成图3.3前面所示的编码，若概率不相等，则生成后面这种编码
从另外一个角度来看，熵的阈值定义了信道是否可信。如果消息源每隔T秒传送一则新消息，最短编码的平均长度是H，那么这个消息源就产生了每秒传送H / T位的需求。如果信道的带宽是H / T位每秒或者更高，那么发送方所传送的所有位都能够到达接收端。若信道的带宽小于H /T位每秒，某些位就可能丢失，接收端就无法恢复原始消息。
文件压缩是信息论的一个重要应用，因为其可以减少存储空间和缩短传输时间。在大部分计算机程序中都使用标准码来表示文本，包括传统的固定长度编码ASCII和现代的变长编码Unicode。这两种情况下每个字母都使用了相同长度的编码，因而，通过寻找重复模式并基于文件上下文用更短的编码代替这些模式，文本文件可被大幅压缩。例如，一个包含很多字母“e”的文件，可以用新的更短小的编码替换它的编码来压缩文件。新的编码取决于“e”在文件中的出现频率——在“e”频繁出现的文件中，这个编码可能是3位，而在“e”不那么频繁出现的文件中，这个编码可能是5位。文件压缩算法会生成一个新编码到原始编码的转换表。“.zip”和“.rar”格式就采用了这种策略。这种压缩策略的设计也不会将信息“压缩”至低于熵的阈值。因为若是低于阈值，则无法保证完全恢复原始信息，这种策略被称为无损压缩。
另一种策略是有损压缩。有损压缩方法具有更大的压缩率，但无法完全恢复原始文件。例如，MP3音频压缩通过丢弃绝大部分人听不到的频率来压缩音频，其压缩率大约为10，但是没法恢复丢弃的频率。JPEG图像压缩舍弃了部分人眼基本会忽略的颜色信息位，当然也没法恢复这些原始的图像位。这些压缩方案使得DVD、在线电影和唱片等能够以更低廉的价格卖给消费者。这些方法在感知质量上的小小损失，对于减少文件大小而言通常被认为是一种很好的折中。
