第九个知识点:香农(Shannon)定义的熵和信息是什么?
第九个知识点:香农(Shannon)定义的熵和信息是什么
这是计算机理论的最后一篇.我们讨论信息理论的基础概念,什么是香农定义的熵和信息.
信息论在1948年被Claude E.Shannon建立.信息论最开始被应用于信号处理,但是经过几十年的发展,它现在已经被应用到各个学科了.这篇文章尝试简洁的介绍两个基础的概念,熵(entropy)和信息(information).如果你对这个感兴趣,我个人推荐你在这里学习更多.[1]
熵
熵是衡量一个或者多个变量不确定性的度量.
假设我们调查人们打开浏览器的时候打开的第一个网页.我们用抽样的方法将测试人员分出两组.四个来自Bristol Cryptogroup的密码学研究人员和在Bristol客车站被抽取的四个乘客.让我们做一个激进的假设,假设四个密码学研究者第一次都会访问http://bristolcrypto.blogspot.co.uk/ .
现在让我们评价一下他们的答案:显然,密码学家的答案是相当确定的(低不确定性),而如果答案来自乘客,则很难猜到(高不确定性).换句话说,我们说密码学家组的答案熵低,而乘客组的答案熵高.
因此香农的一个最著名的贡献就是香农熵的定义:
\(H = - \sum_ip_ilog_bp_i\)
其中\(p_i\)是一个之前答案出现的可能性.在计算机科学中,我们通常使用\(b = 2\)(bits).
如果我们计算熵值,我们就有
\(H_{cryptographer} = - \sum_i^41log_21=0\)
\(H_{passenger} = -\sum_1^4log_2(1/4)=2\)
所以乘客的答案的熵确实比密码学家的高!
信息
形式上,Shannon信息的定义在[2]中给出:
信息是衡量一个人在选择信息时的选择自由.
为了解释这个问题,让我们对前面的事例做一个小的修改.让我们从Bristol火车站再抓四个乘客,假设他们的答案也是随机门户,就像长途汽车站的乘客一样.
问题是:给定一个答案\(y\),你能说答案来自哪一组?
如果\(y\)是http://bristolcrypto.blogspot.co.uk/,那么我们马上就可以知道答案来自于我们的密码编码员组.但是如果y是随机的,我们就会遇到困难.因此我们就可以说http://bristolcrypto.blogspot.co.uk/包含比随机的更多的信息.
因此它们跟熵有什么关系?
扩展熵的定义,我们将条件熵定义为:
\]
这个公式描述了当\(X=x\)条件\(Y\)的熵.更明确的说,因为熵是一个变量的不确定性.因此,先前条件熵的定义实际上是当给定条件为"线索"(条件)\(X\)的不确定的\(Y\).
观察:考虑两个变量\(X\)和\(Y\).如果\(X\)包括\(Y\)的最小信息,然后给出一个额外的\(X\)的精确值对我们推断\(Y\)的值应该没有多大帮助,也就是说,它并没有明显的降低\(Y\)的不确定性.另一方面,如果\(X\)包含了\(Y\)的基本信息.那么当\(X\)给定时,\(Y\)的熵应该是低了很多.因此,条件熵可以看作是看作是对\(X\)对\(Y\)的信息是一种合理的度量!
另一个重要的指标就是互信息(Mutual Information).它是两个变量测量的度量.一种定义它的方法就是熵的减少值.
\(I(X;Y) = H(X)-H(X|Y)=H(Y)-H(Y|X)\)
密码学实例
信息论的概念广泛应用于密码学.一个典型的例子就是把密码学看作一个信道,明文是输入,密文是输出.侧信道的研究也得益于信息论.
[1] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory
2nd Edition. Wiley-Interscience, 2 edition, July 2006.
[2] S. Vajda, Claude E. Shannon, and Warren Weaver. The mathematical
theory of communication. The Mathematical Gazette, 34(310):312+,
December 1950.
[3] http://en.wikipedia.org/wiki/Entropy_(information_theory)
最新文章
- 一劳永逸:域名支持通配符,ASP.NET Core中配置CORS更轻松
- 使用samba实现linux与windows共享(测试成功)
- CXF:通过WebService上传文件,包括大文件的处理
- asp批量查询
- db2 常用命令(一)
- JS正则表达式验证数字(很全)
- Qt编程之实现在QFileDialog上添加自定义的widget
- http 请求安全
- Python爬虫(一)
- android 控件自定义样式
- 关于个人网站选择虚拟主机还是VPS服务器的讨论
- LeetCode 104. Maximum Depth of Binary Tree (二叉树的最大深度)
- 在HTML页面中加载js文件和css文件的方法
- 2018年3月份的PTA(一)
- list tuple
- P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib (数论—素数 + DFS)
- TStack与IBM LinuxONE通过兼容性认证
- nslookup dig iptables,sudoer,jenkins
- BZOJ3613 南园满地堆轻絮 二分/贪心
- Android中activity的四个启动模式
热门文章
- accelerate
- 静态库动态库的编译、链接, binutils工具集, 代码段\数据段\bss段解释
- Windows Server 2016域控制器升级到Windows Server 2022遇到的问题记录Fix error 0x800F081E – 0x20003
- 快速挂起VIM以及调出被挂起的VIM的方法
- Java Web 实现Mysql 数据库备份与还原
- Dubbo多注册中心
- 【编程思想】【设计模式】【行为模式Behavioral】Publish_Subscribe
- Docker通过阿里云镜像仓库使用Gitlab_CI部署SpringBoot项目
- [BUUCTF]PWN——0ctf_2017_babyheap
- YC-Framework版本更新:V1.0.3