一、信息熵

1、什么是信息？

最初定义：

信息理论的鼻祖之一香农把信息（熵）定义为离散随机事件的出现概率。

现代定义：

信息是物质、能量、信息及其属性的标示。 信息是确定性的增加。 信息是事物现象及其属性标识的集合。

2、什么是信息熵？

香农在他著名的《通信的数学原理》论文中提出：“信息是用来消除随机不确定性的东西”，并提出了“信息熵”的概念（借用了热力学中熵的概念），来解决信息的度量问题。

信息熵是消除不确定性所需信息量的度量，也即未知事件可能含有的信息量。 日常语境中的信息量与信息熵的关系。 在自然语言处理中，信息熵只反映内容的随机性（不确定性）和编码情况，与内容本身无关。 随机变量的信息熵大小是客观的，又是主观的，与观测者的观测粒度有关。 信息熵与热力学熵有相似之处，但不是同一个东西。

二、两种编码方式

题例：

一串消息内容是AABBBBAAAACCCCCCCCCEEEEEEDDDDEEEEEEEEEEEEE,包含A，B，C，D，E共5类符号，请问其信息熵是多少？如果分别采用香农-凡诺编码，霍夫曼编码，压缩率分别是多少？

信息熵求值：

求字符串的熵： H ( x ) = ∑ i = 1 n p ( x i ) l o g 2 p ( 1 x i ) = 2.043 S h H(x)=sum_{i=1}^np(x_i)log_2p({1 over x_i}) =2.043Sh H(x)=i=1∑np(xi)log2p(xi1)=2.043Sh

1、香农-凡诺编码

算法：

对于一个给定的符号列表，制定了概率相应的列表或频率计数，使每个符号的相对发生频率是已知。 排序根据频率的符号列表，最常出现的符号在左边，最少出现的符号在右边。 清单分为两部分，使左边部分的总频率和尽可能接近右边部分的总频率和。 该列表的左半边分配二进制数字0，右半边是分配的数字1。这意味着，在第一半符号代都是将所有从0开始，第二半的代码都从1开始。 对左、右半部分递归应用步骤3和4，细分群体，并添加位的代码，直到每个符号已成为一个相应的代码树的叶。

编码前：5种符号至少需要3位二进制编码，共42个字符，则需3×42=126位。 编码后：共87位。 压缩比：126:87=1.45:1

2、霍夫曼编码

算法：

初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。 重复第2步，直到形成一个符号为止（树），其概率最后等于1。 从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。

编码前：5种符号至少需要3位二进制编码，共42个字符，则需3×42=126位。 编码后：共87位。 压缩比：126:87=1.45:1

两种编码方式不同，但此题最终得到得压缩比相同。

三、RGB图像分析

题例：

一幅1024*768的24位RGB彩色图像一共在内存中占有多少字节？ 如果将其保存为非压缩格式的BMP文件，文件有多少字节？请用实例验证。

四、参考

① ② ③