TwitterFacebook

香农说,要有熵。于是开启了信息时代。(4)

  • “二十个问题”游戏攒着玩和数据压缩

    既然用 L(X) 的均值定义所需要问题的个数依赖于把这“二十个问题”游戏玩很多次,那么考虑一下这个游戏的一个变种,就是把这很多次游戏攒起来一起玩:俺拿出一张很长很长的纸条,然后随机想 n 个相互独立的神秘数字,X1, X2, …, Xn (每个数字的分布都是同一个定义在 S={1, 2, …, M} 上的概率分布函数,P(x))。俺把这些数字一个一个地写到纸条上。这里 n 很大很大,所以纸条很长很长。然后你再来问俺“是不是”问题,目的是要把俺在纸条上写的序列猜到。注意,你不仅要猜到所有的数字,顺序也必须正确。当然,因为 n 很大,你要是算不过来,可以搬一台或一百台电脑来。你问俺的问题要是计算太复杂,俺也可以去搬电脑来算。总之,咱们不用管计算有多复杂,俺俩都有无限的计算能力。在这个攒着玩的“二十个问题”游戏中,怎样的问问题策略才最优呢?最优的策略所需要的平均问题数目又是多少呢?

    暂且先不讨论这个问题的答案,咱们先审视一下这个新的游戏设计的应用意义吧。

    想象一下, 俺写在纸条上的序列其实是俺刚写好的长篇小说(俺写下的每一个数其实对应于新华字典里的一个字),又或者俺写在纸条上的序列其实对应于俺长期夜观星象的结果,记录了不为人知的宇宙奥秘(俺写的每个数字都是对观测到的宇宙状态的描述)。在你问俺问题的时候,俺的回答将是一个长长的由Yes/No 组成的序列。如果把 Yes 记作 1,No 记作 0,俺的回答其实就是一个0/1组成的序列。

    一个可以取 0/1 两个值的变量,或者一个可以储存 0/1 两种不同状态的存储单元,就是人们常说的比特(bit)。所以俺的回答其实就是一个比特序列。你希望用最少的问题就等同于要求这个比特序列最短,或者说要求用最少的比特数表示俺纸条上的内容。这个问题其实就是通信中的数据压缩问题!
     

  •  


    数据压缩,又叫“信源编码”,大约是干这样一件事。假设有个信息源,就是一个能不停往外蹦信息的东西,比如一直在想神秘数字的俺,夜观星象的俺,写小说的俺,等等等等。信息源产生的信息从数学上说就是一个随机变量序列(更有文化的说法叫随机过程)。这个随机变量序列可以有很多种形式,最简单形式就是其中的随机变量都相互独立而且服从相同的分布。对这个信息源进行数据压缩包括了两个环节,编码和解码。编码就是把从信息源蹦出来的随机序列表示成比特序列,而且越短越好;解码就是从比特序列中还原出信息源蹦出来的随机序列。数据压缩可以大幅度降低数据存储和通讯需要的资源,已经是现代通信技术的一个重要组成部分。

    现在回到“二十个问题”游戏。如果这个游戏一个一个分开玩,其实就是在数据压缩的时候,对信息源里蹦出的每个随机变量单独做压缩。如果这个游戏攒 n 个一起玩,其实就是对随机序列中的 n 个随机变量同时进行压缩。显然,对每个随机变量单独进行压缩一定不会比对整个随机序列同时做压缩效率更高 (这里的效率是用平均每个随机变量压缩后的比特数来衡量的,比特数越低,效率越高)。这里的道理是这样的:比如俺俩攒 n 个“二十个问题”游戏一起玩,但你设计问题的时候,每个问题只是针对序列中的一个随机变量,而不是针对整个序列。这样的问问题策略显然等同于把每个游戏分开玩。也就是说, 这个游戏一个一个分别玩可以认为是攒起来一起玩的一种特例。因而分别玩能达到的效率,攒起来玩野可以达到。因为同样的道理,如果这个游戏攒 2n 个一起玩,其效率也一定不比攒 n 个一起玩低。也就是说,为了提高效率,n 应该越大越好。

    那么攒起来玩的效率到底最高可以达到多少呢?或者说,对一个给定的信息源,平均每个蹦出来的随机变量最少需要多少个比特来表示呢?这个数字通常跟序列的长度 n 相关,而且对于任意一个给定的 n,即使俺们能够确定最优的压缩方法,精确地确定这个数字也是一个很棘手的问题。不过既然俺们已经认识到 n 越大越好,那不妨考虑 n 取无穷大吧。

    当 n 取无穷大时,如果俺们能够计算出,信息源里平均每个蹦出的随机变量最少需要多少比特来表示,这个数字不仅标记了最优的压缩效率,它同时还有着更深刻的物理意义:它跟序列的长度 n 无关,也跟编码方法无关;换言之,这个比特数只取决于信息源本身(即 随机变量X或其分布 P(x))。因为这个比特数是由最优编码/解码方法实现的,它同时说明了两件事:

    1. 只要解码端接收到的平均比特数不到这个数字(平均到每个随机变量上),不论用什么编码/解码方法都一定无法重建信息源里蹦出的随机序列。
    2. 只要解码端接收到的平均比特数超过这个数字,就一定有一种编码/解码方法可以使解码端重建这个序列。 

    这就是说,在平均意义上,你一定需要这么多比特来表达信息源里蹦出的每一个随机变量,而且只要这么多比特就够了!因此,这个比特数实际上就标注了这个信息源在以什么样的“速率”释放“信息”,或者说标注了这个信息源里蹦出的每个随机变量平均包涵了多少“信息”!

    下面俺们就来看看是否可以导出这个最小比特数。

  • 嗯,没错,终于要掀开她的红盖头了。等不及了吧[呲牙笑]。

     

    (待续)

 

OTTAWAZINE特约撰稿人:学霸老张

分类标签

合作伙伴

旗下产品

成为粉丝

相关信息

加入我们

正在检测......