斯坦福 算法2 第二周笔记

来自斯坦福网站的Algorithms: Design and Analysis，与目前coursera上的版本内容没有变化，不过时间安排略有不同。

1. KRUSKAL’S MINIMUM SPANNING TREE ALGORITHM

1.1 算法

回顾最小生成树的问题：

除了Prim算法之外还有一种算法能够实现最小生成树的输出，那就是Kruskal算法：

简单的说就是从小到大加入不会构成环的边。

1.2 正确性证明

听起来算法很简单，但是可以证明它的正确性。

证明分为两个部分，第一部分证明算法得到的是生成树，其中用到了输入G是个联通图以及Lonely Cut引理。

第二部分证明这个算法加入的每条边都符合The Cut Property。

1.3 实现

假如使用最naive的方法，首先给边排序复杂度为$O(mlogn)$O(mlogn)，然后需要遍历每条边（m次），每次遍历都需要用用$O(n)$O(n)次操作判断是否会构成环。因此总复杂度会是$O(mn)$O(mn)。

我们希望有个新的数据结构能够让我们查看是否构成环的操作为$O(1)$O(1)复杂度，这样总的复杂度就由排序决定，也就是$O(mlogn)$O(mlogn)。

事实上确实有一种数据结构能够满足，那就是Union-Find。这个数据结构支持Find操作，返回的是对应X属于那个集合。以及Union操作，合并两个集合。这两个操作正好适合kruskal算法。

因为我们想要实现$O(1)$O(1)复杂度实现判断是否构成环，想法一：

让每个结点都保持一个指向其所属集合的leader结点的指针。这样Find操作就可以直接在$O(1)$O(1)时间判断两个点是否属于同一集合，也就能够判断是否会构成环。但是这样做的问题在于，合并两个集合的Union操作会是$\Theta(n)$Θ(n)级别的。

想法二：在想法一的基础上，每次Union操作时保证改变的是较小的Union中的结点指向的leader结点（需要额外的Size属性）。但是这样做每次Union操作同样是$\Theta(n)$Θ(n)的。但是这样做是有进步的，因为每个结点在Kruskal算法中只会改变$\Theta(log(n))$Θ(log(n))次指向的leader结点。原因在于每次当前集合如果改变了leader结点，它的size最少会翻倍，最多有$log_{2}(n)$log2​(n)次。

于是这种实现的复杂度为$O(mlogn)$O(mlogn)。

1.4 在Clustering中的应用

聚类（Clustering）是一种常见的机器学习算法，它的目标是将一些结点（网页，图片等）自动划分为某些相关的类别。一般假设两个点之间有一个（非）相似性度量$d(p,q)$d(p,q)表示两个点之间的距离。

比较好的聚类算法能够让不同类别之间的距离尽量得大。在这里我们假设知道需要分类的类别k，因此我们需要做的就是让每个类别最近的两个点之间距离最大。

问题：也就是已知一堆点以及它们之间的距离度量$d(p,q)$d(p,q)，已知类别数k，目标是最大化不同类别之间的$min_{p,q}d(p,q)$minp,q​d(p,q)。

直接利用Kruskal算法就可以解决这个问题，只需要在得到k个集合之后提前停止：

正确性证明：假设用上述算法得到的k个集合$C_{1},...,C_{k}$C1​,...,Ck​之间最小距离为S。任意一个其它算法得到的k个集合为$\widehat{C}_{1},...,\widehat{C}_{k}$C1​,...,Ck​。

Case 1：如果它们两种分类本质上是相同的则无需证明。
Case 2：负责一定能找到一对点p，q在前一个算法中属于同一个集合$C_{i}$Ci​，而在后一个结果中分属于$\widehat{C}_{i},\widehat{C}_{j}$Ci​,Cj​。

需要注意的是，如果p和q在前一个算法中是直接相连的，那么它们之间的距离$d(p,q) \leq S$d(p,q)≤S。（因为选择边的顺序是按cost从小到大）。

那么case2中的简单情形为p和q确实直接相连，则$S\geq d(p,q) \geq space of \widehat{C}_{1},...,\widehat{C}_{k}$S≥d(p,q)≥spaceofC1​,...,Ck​。

case2中的复杂情形是p和q在$C_{i}$Ci​中没有直接相连。那么依然能够找到两个本应在$C_{i}$Ci​中直接相连但是在第二个结果中没有相连的点$a_{j},a_{j+1}$aj​,aj+1​在第二个结果中不相连。因此又转换成了第一种情况。得证。

2 Union Find

2.1 Lazy Union

在前面提到的Union-Find的实现，每个结点指向当前集合的leader结点，每次union操作确保改变的是更小的集合中的点的指向。因此Find操作是$O(1)$O(1)而 n个union操作的复杂度是$O(nlogn)$O(nlogn)。

但是有另一种方法，能够更快地实现union操作。那就是每次union时只更改更小集合的leader结点的指向。

这样做的好处是将union操作变成了两次Find操作加上一次$O(1)$O(1)的改变leader结点的指向。但坏处是原先能够直接返回结果的Find操作可能需要经过一些路程才能找到真正的leader结点（因为结点不一定直接指向真正的leader结点了）。

但实际上这样做最坏情况下find和union操作依然可能是$\Theta(n)$Θ(n)的。

2.2 Union by Rank

想要避免这种情况，需要保证每次都让深度更小的集合指向深度较大集合的leader结点。

这么做之后，每次union操作后两个集合的rank只有在相同时才会有其中之一会加一，否则两个leader结点的rank都不变。

这样实现的Union-find结构每个Find和Union操作的复杂度都是$O(logn)$O(logn)的。证明省略。

2.3 Path Compression

我们如果重复的调用Find，可能就会导致算法一遍遍地遍历相同的路径到达leader结点，因此可以继续优化。这种优化叫做path compression，具体的就是在每次s=find(x)操作的时候将x以及x的祖先节点指向的leader结点直接改为最终的s。这样下次再次查询就可以直接得到结果而不需要再次遍历路径。

这种做法可以让m次union+find操作的复杂度降为$O(mlog^{*}(n))$O(mlog∗(n))。证明略。

3. Huffman Codes

3.1 Problem

编码问题是一个计算机领域的常见问题。具体的是指将一些符号利用数字进行重新表示，如果只使用0和1进行编码，那么就叫做二进制编码。比如可以用5位二进制数将字母a-z进行编码。

但是这么做有可能导致解码时候出现一些歧义，比如：

出现歧义的原因是有的符号的编码是另一个符号编码的前缀。如果能够让每个编码都不是另外任何编码的前缀，就能够避免这种歧义，这样的编码叫做前缀码（Prefix-free codes)。而如果每个符号编码的长度是相同的，叫做固定长度编码，否则叫做变长编码。

比如上一个例子中的ABCD可以用变长前缀码重新编码避免歧义。而如果知道一个文本或是序列中每个符号出现的概率，那么我们就能知道编码一个符号需要的平均码长。考虑到信息的传输，一套编码的平均码长自然是越短越好。

如果把编码利用一个二叉树来表示，那么就很容易理解前缀树不会产生歧义的原因。

而平均码长也就变成了叶子节点到根节点长度的概率加权和。

3.2 算法

那么我们需要得到一个平均码长最短的前缀编码的算法实际上也是一个建立编码树的算法。

与直觉相反，最优的算法是从下到上建树而非从上到下的。而哈弗曼编码就是最优的算法，它的实现是每次将出现概率最小的两个结点进行结合组成一个新的树。而把两个结点结合后的树当做一个新的结点，新节点的概率是两个子节点概率的和。如此递归而得到最终结果。

3.3 正确性证明

证明的目标是证明哈弗曼编码得到的编码平均码长是最短的。

利用归纳法来进行证明。

首先base case：n=2，每个符号需要一个字节编码。肯定是最优解。
然后需要递推得到$n>2$n>2时也是最优的。

首先假设哈弗曼算法得到一个更小的符号集合$\sum'$∑′的编码是最优的。假设这个集合$\sum'$∑′相当于一个更大的集合$\sum$∑将其中频率最小的两个结点a和b组成的树看成一个结点ab的样子。这个新结点的概率$p_{ab}=p_{a}+p_{b}$pab​=pa​+pb​。

而我们发现对于这两个符号集合，它们之间编码结果的平均码长的差值是一个与编码结果无关的定值。而我们递推的假设是集合$\sum'$∑′的编码结果$T'$T′是最优的，那么只需要证明更大的编码集合$\sum$∑的结果$T$T也是最优的即可。

递推已知：由于$L(T)-L(T')$L(T)−L(T′)是一个定值，也就是说在a和b作为sibiling的情况下，编码结果$T$T是此时的最优结果。（这时的编码树叫做$X_{ab}$Xab​)（感觉好像并不是那么的直接）

递推成立的条件：因此我们只需要证明对于编码集合$\sum$∑，在a和b在编码树中是siblings的情况下（即编码树在集合$X_{ab}$Xab​中）存在编码的全局最优解即可。证明如下：

于是base case与递推case都正确，于是算法最优性得证。

自己的理解：
在归纳法中，带有a和b的符号集合$\sum$∑相当于n=k+1的情况。而将a和b作为sibling看为一个结点的符号集合$\sum'$∑′相当于n=k的情况。现在假设集合$\sum'$∑′的结果$T'$T′是最优的，这也就意味着在$\sum$∑中a和b作为sibling的情况对应$T'$T′的结果$T$T是此时最优的。因此只需要证明集合$\sum$∑的全局最优解可以出现在a和b作为sibling的情况下就行。