互信息和信息熵

信息熵

网址：https://blog.csdn.net/am290333566/article/details/81187124

又叫香农熵，是香农在1948年引入的一个概念，他指出，一个系统越是有序，信息熵就越低，一个系统越混乱信息熵就越高，信息熵被认为是一个系统有序程度的度量。

1．信息量

指一个样本所蕴含的信息，如果一个事件发生的概率越大，那么就认为该事件所蕴含的信息量越少。例如：

极端情况下，“太阳从东边升起”，因为是确定事件，所以不携带任何信息。

“昨儿逛街碰上了周杰伦”，这句话就包含很多信息 2．信息熵 信息熵公式如图所示：

信息熵公式

随机变量X中的有m个事件，每个事件平均需要bit位的个数就是信息熵得概念。如果某一个事件的概率特别大，那么该变量蕴含的信息量就会变少，从而信息熵就会变小。例子如下：

赛马比赛中，有两组赛马共八匹，获胜的概率如图：

赛马信息

对于第一组而言概率一样，很难猜测哪匹马会赢，对于第二组来说，很明显可以得出结论A马更容易获胜。算出信息熵第一组H(X)=2;第二组H(X)=1.336

条件熵（H(Y|X)）

总体来说就是熵的期望。

1．定义

给定条件X的情况下，随机变量Y的熵就叫条件熵：

例如图所示：

专业信息

专业（X为数学时）Y的信息熵H(Y|X=数学)=1在给定条件X的情况下，所有不同x值的情况下Y的信息上的平均值叫做条件熵。上述例子中求得的条件熵的结果如图所示：

image.png

互信息

互信息就是知道X，给Y的信息量带来多少损失（或者知道Y，给X的信息量带来多少损失）。

左右邻字信息熵

就是计算一个词的左邻字的信息熵。我们用信息熵来衡量一个文本片段的左邻字集合和右邻字集合有多随机

• 例子 考虑这么一句话“吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮”，“葡萄”一词出现了四次，其中左邻字分别为 {吃, 吐, 吃, 吐} ，右邻字分别为 {不, 皮, 倒, 皮} 。根据公式，“葡萄”一词的左邻字的信息熵为 – (1/2) · log(1/2) – (1/2) · log(1/2) ≈ 0.693 ，它的右邻字的信息熵则为 – (1/2) · log(1/2) – (1/4) · log(1/4) – (1/4) · log(1/4) ≈ 1.04 。可见，在这个句子中，“葡萄”一词的右邻字更加丰富一些。
• 观点 1、当该词的左信息熵比较低时候，该词很难是一个词

在人人网用户状态中，“被子”一词一共出现了 956 次，“辈子”一词一共出现了 2330 次，两者的右邻字集合的信息熵分别为 3.87404 和 4.11644 ，数值上非常接近。但“被子”的左邻字用例非常丰富：用得最多的是“晒被子”，它一共出现了 162 次；其次是“的被子”，出现了 85 次；接下来分别是“条被子”、“在被子”、“床被子”，分别出现了 69 次、 64 次和 52 次；当然，还有“叠被子”、“盖被子”、“加被子”、“新被子”、“掀被子”、“收被子”、“薄被子”、“踢被子”、“抢被子”等 100 多种不同的用法构成的长尾⋯⋯所有左邻字的信息熵为 3.67453 。但“辈子”的左邻字就很可怜了， 2330 个“辈子”中有 1276 个是“一辈子”，有 596 个“这辈子”，有 235 个“下辈子”，有 149 个“上辈子”，有 32 个“半辈子”，有 10 个“八辈子”，有 7 个“几辈子”，有 6 个“哪辈子”，以及“n 辈子”、“两辈子”等 13 种更罕见的用法。所有左邻字的信息熵仅为 1.25963 。因而，“辈子”能否成词，明显就有争议了。“下子”则是更典型的例子， 310 个“下子”的用例中有 294 个出自“一下子”， 5 个出自“两下子”， 5 个出自“这下子”，其余的都是只出现过一次的罕见用法。事实上，“下子”的左邻字信息熵仅为 0.294421 ，我们不应该把它看作一个能灵活运用的词。当然，一些文本片段的左邻字没啥问题，右邻字用例却非常贫乏，例如“交响”、“后遗”、“鹅卵”等，把它们看作单独的词似乎也不太合适。我们不妨就把一个文本片段的自由运用程度定义为它的左邻字信息熵和右邻字信息熵中的较小值

计算

利用trie树计算互信息和左右信息熵 https://github.com/zhanzecheng/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.09.md

trie树

Trie树（字典树）

方法介绍

1.1、什么是Trie树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

1.2、树的构建

咱们先来看一个问题：假如现在给你10万个长度不超过10的单词，对于每一个单词，我们要判断它出没出现过，如果出现了，求第一次出现在第几个位置。对于这个问题，我们该怎么解决呢？

如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于10万的范围难以接受。

换个思路想：

• 假设我要查询的单词是abcd，那么在它前面的单词中，以b，c，d，f之类开头的显然不必考虑，而只要找以a开头的中是否存在abcd就可以了。
• 同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。

即如果现在有b，abc，abd，bcd，abcd，efg，hii 这6个单词，我们可以构建一棵如下图所示的树：

image.png

如上图所示，对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。

那么，对于一个单词，只要顺着他从根走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。

这样一来我们查询和插入可以一起完成，所用时间仅仅为单词长度（在这个例子中，便是10）。这就是一棵trie树。

我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间，我们还可以用动态链表，或者用数组来模拟动态。而空间的花费，不会超过单词数×单词长度。

1.3、查询

Trie树是简单但实用的数据结构，通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时，就是Trie开始。本质上，Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符，这样树的每条分支代表一则子串，而树的叶节点则代表完整的字符串。和普通树不同的地方是，相同的字符串前缀共享同一条分支。

下面，再举一个例子。给出一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie：

[图片上传失败...(image-c0e559-1555409498421)]

可以看出：

• 每条边对应一个字母。
• 每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
• 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。同理，ate, age, adv, 和ant共享前缀"a"，所以他们共享从根节点到节点"a"的边。

查询操纵非常简单。比如要查找int，顺着路径i -> in -> int就找到了。

搭建Trie的基本算法也很简单，无非是逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在，就共享，否则创建对应的节点和边。比如要插入单词add，就有下面几步：

1. 考察前缀"a"，发现边a已经存在。于是顺着边a走到节点a。
2. 考察剩下的字符串"dd"的前缀"d"，发现从节点a出发，已经有边d存在。于是顺着边d走到节点ad
3. 考察最后一个字符"d"，这下从节点ad出发没有边d了，于是创建节点ad的子节点add，并把边ad->add标记为d。

问题实例

1、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析

提示：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平均长度），然后是找出出现最频繁的前10个词。当然，也可以用堆来实现，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。

2、寻找热门查询

原题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

提示：利用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。