互信息和信息熵

信息熵

参考：信息熵（CSDN）

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

1. 信息量

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

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

「昨儿逛街碰上了周杰伦」，这句话就包含很多信息。

2. 信息熵

信息熵公式如图所示：

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

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

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

条件熵 H(Y|X)

总体来说就是熵的期望。

定义： 给定条件 X 的情况下，随机变量 Y 的熵就叫条件熵。例如图所示：

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

互信息

互信息就是：知道 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。可见，在这个句子中，「葡萄」一词的右邻字更加丰富一些。

观点： 当该词的左信息熵比较低时候，该词很难是一个词。

在人人网用户状态中，「被子」一词一共出现了 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 树计算互信息和左右信息熵：编程之法 · 06.09

Trie 树（字典树）

什么是 Trie 树

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

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

它有 3 个基本性质：

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

树的构建

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

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

换个思路想：

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

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

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

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

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

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

查询

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

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

• 每条边对应一个字母。
• 每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
• 单词 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 个元素的最小堆来对出现频率进行排序。