第8讲自然语言的熵.pptVIP

* 第8讲 信源冗余度与自然语言的熵 背景知识: 实际的信源可能是非平稳的，其极限熵 不一定存在。 可以假定它是平稳的，用平稳信源的 来代替。 对于一般平稳的离散信源，求 值也是极其困难的。 进一步假设它是m阶马尔可夫信源，用m阶马尔可夫信源的信息熵 来近似。 最简单的马尔可夫信源是记忆长度为m=1的信源，信源的熵： 对于一般的离散信源都可以近似地用不同记忆长度的马尔可夫信源来逼近。进一步简化，可以建设信源为无记忆信源，信源符号有一定的概率分布。最后可以假定是等概率分布的离散无记忆信源。 由此看出，由于信源输出符号间的依赖关系也就是信源信号的相关性使信源的实际熵减小。信源输出符号间统计约束关系越长，信源的实际熵越小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源的实际熵等于最大熵。 定义：一个信源的熵率（极限熵）与具有相同符号集的最大熵的比值称为熵的相对率： 可见对于有记忆信源，最小单个消息熵应为 ，即从理论上看，对有记忆信源只需传送 即可。但是这必需要掌握信源全部概率统计特性和所有的记忆关系。这显然是不现实的。实际上，往往只能掌握有限的N维，这时只需传送 ，那么与理论值相比，就多传送了 。 为了定量描述信源熵的有效性，定义了信源冗余度： 信源的冗余度来自两个方面: 1、信源符号间的相关性 信源符号间相关程度越大，符号间的依赖关系越长，信源的实际熵越小; 2、另一方面是信源符号分布的不均匀性使信源的实际熵越小。 为了更经济有效的传送信息，需要尽量压缩信源的冗余度，压缩冗余度的方法就是尽量减小符号间的相关性，并且尽可能的使信源符号等概率分布。 从提高信息传输效率的观点出发，人们总是希望尽量去掉冗余度。 但是从提高抗干扰能力角度来看，却希望增加或保留信源的冗余度，因为冗余度大的消息抗干扰能力强。 信源编码是减少或消除信源的冗余度以提高信息的传输效率。 信道编码则通过增加冗余度来提高信息传输的抗干扰能力。 中华人民共和国 中国 母亲病愈，身体健康 母病愈 例：一个输出A、B、C、D四个符号的信源，它输出10个符号的序列包含最大可能的信息量为： 当信源的符号间有依赖关系时，或概率分布不均匀时，信源熵要下降，因此信源输出的序列总信息量也要下降。假定信源由于符号间的相关性或不等概率，信源熵下降到 比特/符号 正由于信源存在着冗余度，即存在着不必要传送的信息，因此信源也就存在进一步压缩信息率的可能性。冗余度越大，压缩潜力也就越大。可见它是信源编码，数据压缩的前提与理论基础。 下面，以英文为例，计算文字信源的冗余度。 首先给出英文字母（含空档）出现概率如下： 0.012 0.011 0.0105 0.008 0.003 0.002 0.001 0.001 Y.W G B V K X J.Q Z 0.0502 0.047 0.035 0.029 0.023 0.0225 0.021 0.0175 S H D L C F.U M P 0.2 0.105 0.072 0.0654 0.063 0.059 0.055 0.054 空档 E T O A N I R 字母 字母 字母 下面，首先求得独立等概率情况，即 其次，计算独立不等概率情况 再次，若仅考虑字母有一维相关性，求 还可进一步求出： 最后，利用统计推断方法求出 ，由于采用的逼近的方法和所取的样本的不同，推算值也有不同，这里采用Shannon的推断值。 这样，可以计算出： 这一结论说明，英文信源，从理论上看71％是多余成分。即有71%是由语言结构定好的，而剩下的29%可由写文章的人自由发挥的。 直观地说100页英文书，理论上看仅有29页是有效的，其余71页是多余的。正是由于这一多余量的存在，才有可能对英文信源进行压缩编码。 为计算这些熵，要计算字母之间的一维条件概率、二维条件概率 二阶马尔可夫信源，条件概率为 个。 香农做法： 对于其它文字，也有不少人作了大量的统计工作，现简述如下： 英文 法文 德文 西班牙文 中文 （按8千汉字计算） 汉字的编码 GB2312-80 国家标准汉字编码简称国标码。该编码集的全称是“信息交换用汉字编码字符集—基本集”，国家标准代号是“GB2312-80”。该编码的主要用途是作为汉字信息交换码使用。