信源剩余度与自然语言的熵
1、关于离散信源熵的总结 实际信源可能是非平稳的有记忆随机序列信源，其极限熵H∞不存在。 解决的方法是假设其为离散平稳随机序列信源，极限熵存在，但求解困难； 进一步假设其为m阶Markov信源，用其m阶条件熵Hm+1来近似，近似程度的 高低取决于记忆长度m 的大小； 最简单的是记忆长度 m =1的马尔可夫信源，其熵Hm+1=H2=H(X2|X1) 再进一步简化，可设信源为无记忆信源，信源符号有一定的概率分布。这时 可用信源的平均自信息量H1=H(X)来近似。 最后可假定是等概分布的离散无记忆信源，用最大熵H0 来近似。
补充：文本隐写技术
– 法轮功的信息传递：使用文本隐写工具软件Snow。
– 该软件使用公开对称加密算法ICE对秘密信息进行加密，再使用基于 行末不可见字符的文本隐写方法把秘密信息隐藏在文本中。
– 这种使用隐写技术传递隐秘信息的方法使得政府许多常规侦察方法失 去效果，从而使得相关职能部门对这些不法分子进行的不法活动更加 难以采取预防措施，给国家安全、社会稳定和经济的发展带来了严峻 的挑战。
补充：文本隐写技术
• 4)基于文件格式的文本隐写技术
• 该类方法利用文件格式中通常允许存在一定冗余的特性， 在文件格式中加入一些隐藏的信息。比如附加编码法， 是在文件中附加经过编码后的隐藏信息；PDF注释法， 是在PDF文件格式的注释部分加入编码后的隐藏信息等。
补充：文本本都当作一个独立的m阶时齐遍历马尔可夫信 源，以该文本中的单词作为信源符号；即检测方法只考虑每一篇文 本内部单词间的关系，而不将该文本与其所属的语种的总体特征进 行对比。 • 一般传统意义上关于文本的剩余度是指将某种自然语言作为信源并 计算该语言的剩余度，每个单独的文本只是作为该信源的一个输出。
信源符号的相关性与提供的平均信息量
把多符号离散信源都用马尔可夫信源来逼近，则记忆长度不同，熵 值就不同，意味着平均每发一个符号就有不同的信息量。 log2n=H0≥H1≥H2≥…≥Hm≥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。
• 从提高传输效率的观点出发，总是希望减少或去掉剩余度。 • 剩余度大的消息抗干扰能力强。能通过前后字之间的关联纠正错误。
第七节 信源剩余度与自然语言的熵
4、自然语言的熵
从提高传输信息效率的观点出发，总是希望减少或去掉
冗余度。 例如把“中华人民共和国”压缩成“中国”；“母亲病 愈，身体健康”压缩为“母病愈”。这样原意并没变，而电 文变得简洁，冗余度大大减少。
如果不考虑符号间的依赖 关系，近似认为信源是离 散无记忆的，则信源熵为
无记忆信源的熵：
H1 p(ei ) log2 p(ei ) 4.03(比特 / 符号)
i 1
27
• •
按上表的概率分布，随机选择英语字母排列起来，得到一个输出序列： AI_NGAE_ITE_NNR_ASAEV_OTE_BAINTHA_HYROO_PORE_SETRYGAIET
可夫的极限熵 H∞ =1.4(比特/符号)。
（1）对于英文字母 （2）对于中文
1 1
H 1.4 1 0.71 H0 log 27
H 9.733 1 1 1 0.264 4 H0 log10
• 写英语文章时，71%是由语言结构定好的，只有29%是写文字的人可以自 由选择的。100页的书，大约只传输29页就可以了，其余71页可以压缩 掉。信息的剩余度表示信源可压缩的程度。
程度。
4、自然语言的熵
① 把英语看成是离散无记忆信源
• 英语字母26个，加上一个空格，共27个符号。 • 英语信源的最大熵(等概率) H0=log227=4.76(比特/符号) • 英语字母并非等概率出现，字母之间有严格的依赖关系。对英文 书写中 表 2.2.227个符号出现的概率统计结果如下表。 27 个英语符号出现的概率
现Q, F, X。即英语字母之间有强烈的依赖性。上述序列仅考虑了字母出现的概率，
忽略了依赖关系。
② 把英语看成马尔可夫信源
• 为了进一步逼近实际情况，可把英语信源近似看做1阶，2阶，…∞阶 马尔可夫信源，它们的熵为 H2=3.32(比特/符号) H3=3.1(比特/符号)
• 若把英语信源近似成2阶马尔可夫信源，可得到某个输出序列： • IANKS_CAN_OU_ANG_RLER_THTTED_OF_TO_SHOR_OF_TO _HAVEMEM_A_I_MAND_AND_BUT_WHISS_ITABLY_THERVE REER…
补充：文本隐写技术
• 2)基于不可见字符的文本隐写技术
• 这类方法通过对文本中的不可见字符进行添加、删除、替 换等操作来进行信息隐藏，这些不可见字符主要包括文本 中显示为空白的字符或某些情况下不显示的字符，如空格 可以被加载在句末或行末等位置而不会显著改变文本的外 观。最早用于非格式化文本的隐写方法就是该类方法中的 行末空格编码方法。
信源剩余度
H 1 1 H0
可见，信源冗余度的大小能很好地反映离散信源输出的符号序列
中符号之间依赖关系的强弱。冗余度越大，表示信源的实际熵H∞越小。
这表明信源符号之间的依赖关系越强，即符号之间的记忆长度越长。 反之，冗余度越小，这表明信源符号之间依赖关系越弱，即符号 之间的记忆长度越短。 当冗余度等于零时，信源的信息熵就等于极大值H0 ，这表明信源 符号之间不但统计独立无记忆，而且各符号还是等概率分布。 所以冗余度可用来衡量信源输出的符号序列中各符号之间的依赖
实际信源 等概的离散 无记忆信源
离散平 稳信源 离散无记 忆信源
HN H∞
m阶Markov 信源 一阶Markov 信源
Hm+1
H0
H1
H2
① 实际信源近似为平稳信源
实际信源可能是非平稳的，极限熵H∞不一定 存在。 假设它是平稳的，测得N足够大时的条件概率 P(XN/X1X2…XN-1) ，再计算出平均符号熵HN(X)， 近似极限熵H∞ 。
补充：文本隐写技术
• 隐写术按载体分类，可分为图像信息隐藏、视频信息隐藏、 音频信息隐藏、文本信息隐藏等。 • 文本中的冗余信息非常有限，所以文本隐写所用的方法与 其他几类载体中使用的隐写方法往往截然不同。
补充：文本隐写技术
• 文本隐写算法分类： • 1)图像文本中的隐写技术 • 该类方法针对以图像格式保存的文本或印刷文本 进行信息隐藏，主要是利用图像文本的特点，使 用图像处理技术来进行信息隐藏。
符号 空格 E T O A N I R 概率 0.2 0.105 0.072 0.0654 0.063 0.059 0.055 0.054 符号 S H D L C F,U M P 概率 0.052 0.047 0.035 0.029 0.023 0.0225 0.021 0.0175 符号 Y,W G B V K X J,Q Z 概率 0.012 0.011 0.0105 0.008 0.003 0.002 0.001 0.001
第七节 信源剩余度与自然语言的熵
4、自然语言的熵
但是冗余度大的消息具有强的抗干扰能力。当干扰使消息在传输
过程中出现错误时，我们能从它的上下关联中纠正错误。 例如，当收到电文为“中×人民×和国”、“母亲病×，身体健
康”时，我们很容易把它纠正。
但若发的是压缩后的电文”中国”和“母病愈”，那么当接收电 文为”×国”和“母病×”时，就很难肯定所发的电文。由此将会造成很 大的错误。 所以，从提高抗干扰能力角度看，总希望增加或保留信源的冗余度。
5、 通信效率与可靠性的关系
• 信源编码就是通过减少或消除剩余度来提高通信效率。 • 信道编码是通过增加剩余度来提高通信的抗干扰能力，即提高 通信的可靠性。
• 通信的效率问题和可靠性问题往往是一对矛盾。
补充： Information Hiding Techniques 文本隐写
– 文本是一种使用非常广泛的数据形式，比图片等数据形式的使用更为 频繁，使用的领域也更为宽广。 – 隐写术(Steganography)，也称为信息隐藏技术。该技术是将秘密信 息隐藏在其他载体信息中，通过载体的存储与传输来实现秘密信息的 保存与传递。隐写术使秘密信息能很好地避免第三方的注意，从而比 单纯使用传统加密技术能更有效地保障秘密信息存储与传递的安全。 – 文本隐写工具：Ffencode、WbStego、ByteShelter、Snow、加密 奇兵、InfriHide、Crypto123、Stego、Texto、Sams Big Play Maker 、Nicetext、TextHide。
• 这个序列中被空格分开的两字母或三字母，组成的大都
是有意义的英语单词，而四个以上字母组成的“单词”，
很难从英语词典中查到。因为该序列仅考虑了3个以下字 母之间的依赖关系。实际英语字母之间的关系延伸到更
多的符号，单词之间也有依赖关系。
• 有依赖关系的字母数越多，即马尔可夫信源的阶数越高， 输出的序列就越接近于实际情况。当依赖关系延伸到无 穷远时，信源输出的就是真正的英语，此时可求出马尔