开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算：无损压缩编码（下）】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/811/detail/15682
无损压缩编码（下）
内容介绍：
一、香农-范诺编码
二、举例
一、香农-范诺编码
1.香农-范诺(Shannon-Fano）编码
最早阐述和实现这种编码的是 Shannon ( 1948年)和 Fano ( 1949年)
2.采用从上到下的方法进行编码
按照符号出现的频度或概率排序，编码中的符号可以是多媒体信号中音频的采样、可以是图像中的灰度值，也可以是图像中的颜色值、也可以是颜色值中的某一个分量.
排序可以从大到小排，例如 A、B、C、D 和 E，分别统计他们的概率后把其排序出来。
3. 使用递归方法分成两个部分，每一部分具有近似相同的概率
例如有五个 A、B、C、D 和 E，可以分为两组，这两组的依据是使这两组有最可能接近的和。
二、举例
香农-范诺编码中继续二分就是递归，分到只有两个部分不能再分为止。如下表：
符号 |
出现的次数 |
概率 |
A |
15 |
15/40（0.375） |
B |
7 |
7/40（0.175） |
C |
7 |
7/40（0.175） |
D |
6 |
6/40（0.150） |
E |
5 |
5/40（0.125） |
根据其概率再进行排序，如下(从大到小排序)：
A(0.375) B(0.175) C(0.175) D(0.150) E(0.125)
第二步是将这五个按照其概率值再进行分组：
可以将 A 和 B 分在一起，加一起概率是0.55，C、D、E 为一组，概率和就为0.45，这样分两组的概率和才接近。
将其中一组用0表示，另一组用1表示。
（分成两组的原因：因为是用二进制编码）
继续分，可以将 C、D、E 这一组再分为两组，发现 D、E 分为一组然后 C 为单独一组的概率和更加接近。然后将 C 这单独一组赋为0，D、E 组赋为1。
然后 D、E 也可以继续二分，再将 D赋为0，E赋为1，A、B 组也可以拆分，将 A 赋0，B赋1。
这样后就可以将编码输出，编码为：00 01 10 110 111
如下图所示：
最小的概率是0.125，编码是由3位表示，大概率用2位表示，说明概率越大，码字越短。
然后可以计算需要多少位，如下表：
符号 |
出现的次数（Pi） |
log2(1/Pi) |
分配的代码 |
需要的位数 |
A |
15（0.375） |
1.4150 |
00 |
30 |
B |
7（0.175） |
2.5145 |
01 |
14 |
C |
7（0.175） |
2.5145 |
10 |
14 |
D |
6（0.150） |
2.7369 |
110 |
18 |
E |
5（0.125） |
3.0000 |
111 |
15 |
计算出编码得到的总位数为91（说明是无损的）
压缩比如何计算：
压缩比如果都用三位表示，需要120位，120/91 就是其压缩比（也就是1.3：1），以上就是最早的统计编码。
