信息论讲义.ppt

typoglecymia现象表明单词的语义信息并非需要完整无误且排列正确的字符序列才能唯一的正确表达，即英文单词内部的字符顺序里存在大量冗余，可称之为“字序冗余”，是字形冗余的一种．然而这一现象存在争议，比如如果对单词中间的所有字母完全地随机置乱，很多情况下会对理解产生明显的影响． 对于单词两端的字符顺序进行置乱造成的影响的确比内部字符更大； 对于字符进行临近位置的置乱要比远距离的置乱更容易理解； 在单词长度较长时置乱后对理解的影响明显大于短单词． 提高嵌入效率？ * 安德雷·马尔可夫(Andrei Markov 1856－1922），俄国数学家。 1874年马尔可夫入圣彼得堡大学，师从切比雪夫，1886年当选为圣彼得堡科学院院士。 开创了随机过程这个新的领域，以他的名字命名的马尔可夫链在现代工程、自然科学和社会科学各个领域都有很广泛的应用。 马尔可夫性：一个过程的“将来”仅依赖“现在”而不依赖“过去” 马尔可夫链的应用 排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码 著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码。 生物学应用， 人口过程，可以帮助模拟生物人口过程的建模。 隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。 马尔可夫链最近的应用是在地理统计学（geostatistics）中,被称为是“马尔可夫链地理统计学”。仍在发展过程中。 “基于马尔可夫链的我国城乡居民收入演进分析” 信源剩余度与自然语言的熵 离散平稳信源 m阶Markov信源 一阶Markov信源 实际信源 离散无记忆信源 等概的离散无记忆信源 实际信源可能是非平稳的有记忆随机序列信源，其极限熵H∞不存在。 解决的方法是假设其为离散平稳随机序列信源，极限熵存在，但求解困难； 1、关于离散信源熵的总结 进一步假设其为m阶Markov信源，用其m阶条件熵Hm+1来近似，近似程度的高低取决于记忆长度m 的大小； 最简单的是记忆长度 m =1的马尔可夫信源，其熵Hm+1=H2=H(X2|X1) 再进一步简化，可设信源为无记忆信源，信源符号有一定的概率分布。这时 可用信源的平均自信息量H1=H(X)来近似。 最后可假定是等概分布的离散无记忆信源，用最大熵H0 来近似。 HN Hm+1 H2 H1 H0 H∞ ① 实际信源近似为平稳信源 实际信源可能是非平稳的，极限熵H∞不一定存在。 假设它是平稳的，测得N足够大时的条件概率P(XN/X1X2…XN-1) ，再计算出平均符号熵HN(X)，近似极限熵H∞ 。 ② 离散平稳信源近似为马尔可夫信源 计算N足够大时的HN (X)往往也十分困难，可进一步假设离散平稳信源是m阶马尔可夫信源。信源熵用m阶马尔可夫信源的熵Hm+1来近似，需要测定的条件概率要少的多。近似程度的高低取决于记忆长度m。 越接近实际信源，m值越大；反之对信源简化的越多，m值越小。 最简单的马尔可夫信源记忆长度m=1，信源熵H2= H1+1= H(X2/X1)。 当m=0时，信源变为离散无记忆信源，其熵可用H1(X)表示。 继续简化，假定信源是等概率分布的无记忆离散信源，这种信源的熵就是最大熵值 H0(X)=log2n。 信源符号的相关性与提供的平均信息量 把多符号离散信源都用马尔可夫信源来逼近，则记忆长度不同，熵值就不同，意味着平均每发一个符号就有不同的信息量。 log2n=H0≥H1≥H2≥…≥Hm≥H∞ 由此可见，由于信源符号间的依赖关系使信源的熵减小。如果它们的前后依赖关系越长，则信源的熵越小。并且仅当信源符号间彼此无依赖、等概率分布时，信源的熵才最大，即信源符号的相关性越强，提供的平均信息量越小。 为此，引进信源的冗余度来衡量信源的相关性程度(有时也称为多余度或剩余度)。 冗余度与结构信息 1、冗余度 冗余 压缩 信息论的创始人Shannon提出把数据看作是信息和冗余度（redundancy）的组合。 如在一份计算机文件中，某些符号会重复出现、某些符号比其他符号出现得更频繁、某些字符总是在各数据块中可预见的位置上出现等，这些冗余部分便可在数据编码中除去或减少。 相邻的数据之间存在着相关性。如图片中常常有色彩均匀的背影，电视信号的相邻两帧之间可能只有少量的变化影物是不同的，声音信号有时具有一定的规律性和周期性等等。 人们由于耳、目对信号的时间变化和幅度变化的感受能力都有一定的极限 信源编码 可利用一些编码的方法删去它们，从而达到减少冗余压缩数据的目的。 图像压缩编码 (1)无损压缩编码 (2)有损压缩编码 (3)混合编码，如 H261，JPEG，MPEG等技术标准 简单地说，如果没有数据压