霍算法

‘壹’ 贪心算法：最小生成树，霍夫曼编码

连通图： 在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。
强连通图（Strongly Connected Graph） 是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
连通网： 在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树： 一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树： 在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
示例：
分别使用 Kruskal算法 和 Prim算法 ，找出下图的最小生成树。

使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
具体步骤
1.将信源符号的概率按减小的顺序排队。
2.把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率1。
3.画出由概率1处到每个信源符号的路径，顺序记下沿路径的0和1，所得就是该符号的霍夫曼码字。
4.将每对组合的左边一个指定为0，右边一个指定为1（或相反）。
示例：
假设字符a,b,c,d,e出现的概率分别为1/2,1/4,1/8,1/16,1/16。
1.求出各字符哈夫曼编码表。
2.假设一个文件有1,000,000个字符，求出编码之后文件的字节长度。

A:0
B:10
C:110
D:1110
E:1111
a所占长度l1为：（1,000,000/2） 1
b所占长度l2为：（1,000,000/4） 2
c所占长度l3为：（1,000,000/8） 3
d所占长度l4为：（1,000,000/16） 4
e所占长度l5为：（1,000,000/16）*4
文件的总长度l = l1 + l2 + l3 + l4 + l5 = 1875000

‘贰’ 有损压缩算法

基本的分为两大类：有损和无损。
有损压缩：主要是一些量化算法，比如a率，u率，lloyds最优量化。
无损压缩：主要是一些编码算法，比如子带编码，差分编码，哈夫曼编码等。
另外时频变换虽然没压缩效果，但是是很好的压缩工具，比如fft，dct等。
最后就是压缩感知稀疏重建等。
由于信息丢失意味着在误差和比特率之间进行一些权衡，我们首先考虑失真度量---例如，平方误差。本文引入了不同的量化器，每个量化器都具有不同的失真行为。许多有损数据压缩算法开发的数学基础是随机过程的研究。

介绍：

当图像直方图相对平坦时，使用无损压缩技术（例如，霍夫曼编码，算术编码，LZW）的图像数据的压缩比较低。对于需要更高压缩比的多媒体应用中的图像压缩，通常采用有损方法。在有损压缩中，压缩图像通常与原始图像不同，但在感知上与原始图像近似。为了定量描述近似值与原始数据的接近程度，需要某种形式的失真度量。

失真测量：

失真度量是一种数学量，它使用一些失真标准指定近似值与其原始值的接近程度。在查看压缩数据时，很自然地会根据原始数据和重建数据之间的数值差异来考虑失真。 然而，当要压缩的数据是图像时，这样的度量可能不会产生预期的结果。

例如，如果重建的图像与原始图像相同，只是它被向右移动一条垂直扫描线，那么普通的人类观察者将难以将其与原始图像区分开，因此可以得出结论：失真很小。 然而，当以数字方式执行计算时，由于重建图像的各个像素的大的变化，我们发现大的失真。问题是我们需要一种感知失真的测量，而不是一种更天真的数值方法。然而，对感知扭曲的研究超出了本书的范围。

在已经定义的许多数值失真度量中，我们提出了图像压缩中最常用的三种。如果我们对平均像素差异感兴趣，则经常使用均方误差（MSE）。 它被定义为

‘叁’ 有8个待编码的符号A,B,C,D,E,F,G，H,使用霍夫曼编码算法

1、将A到H按其概率的大小，从上到下依次排列写出。
2、每次都将两个最小的概率合并成一个概率，然后重新按概率从大到小排列。
例如：第一次需要将H(0.01)和G(0.03)合并，合并后概率为0.04，这时从大到小排列0.04最小，且有两个0.04,一个为F的概率，一个为H和G合并后的概率。此时，再将两个0.04合并，重复以上步骤。
3、重复步骤2，直至概率合并为1。
4、将被合并的两个消息分支分别赋予0和1。
5、从概率为1的一头向其自身概率一头读数。
具体答案：
A 1
B 011
C 010
D 001
E 0001
F 00001
G 000001
H 000000

‘肆’ 大概描述一下霍夫森林和霍夫投票算法，谢谢~

霍夫森林（houghforests）

霍夫森林是随机森林和霍夫投票在计算机视觉中的应用，用在物体检测，跟踪和动作识别。主要特点是：

（1）每个叶子节点都是一个判别性的码本，对到达这个叶子节点的patch做出一个预测：它来自前景的概率是多少？它距离物体中心有多远？

（2）在节点分裂的时候，随机选择类别不纯度或是偏移量不纯度：