【机器学习】信息熵基础学习_字符串的熵怎么求

一、信息熵

1、什么是信息？

最初定义：

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

现代定义：

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

2、什么是信息熵？

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

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

二、两种编码方式

题例：

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

信息熵求值：

求字符串的熵：
$$H(x)=\sum _{i=1}^{n}p(x_i)lo{g}_{2}p(\frac{1}{x_i})=2.043Sh$$

1、香农-凡诺编码

算法：

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

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

2、霍夫曼编码

算法：

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

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

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

三、RGB图像分析

题例：

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

四、参考

①百度百科——信息熵
②百度百科——香农-范诺编码
③哈夫曼编码的理解(Huffman Coding)