信息熵与压缩编码基础

信息熵与压缩编码基础

• 信息熵

  • 一条消息序列由A,B,C,D,E五种不同类别的符号构成,其具体内容为AABBBBAAAACCCCCCCCCEEEEEEDDDDEEEEEEEEEEEEE,并分别采用香农编码与霍夫曼编码进行编码

• 香农编码

  • 霍夫曼编码
  • 一幅1024×768像素的24位RGB彩色图像在内存中总共占用多少字节？ 如果将其以未压缩格式保存为BMP文件，则文件大小为多少字节？

信息熵

如果说"信息"是一个难以捉摸的概念的话，
人们常说关于"信息"的数量问题往往模棱两可，
但确定具体的信息数量却始终是一个难题。
举个例子来说的话，则会面临这样的困惑：
一本五十万字的中文书究竟含有多少"信息量"？
到了1948年的时候，
香农首次提出了一种新的度量标准——
"信道容量",
正是从物理学领域中的热力学概念中取其精髓而得来的。
在物理学中则将"热熵"
一词用来衡量物质状态混乱的程度。

具体见:百度百科

一条信息流由五个不同的符号类别A、B、C、D、E组成，在具体信息流中表现为字符串AABBBBAAAACCCCCCCCCEEEEEEDDDDEEEEEEEEEEEEE的形式。针对该特定信息流序列的压缩编码问题，则分别采用香诺gentleman编码方法与哈夫曼编码策略进行分析比较研究

包含共计42个符号，在此过程中具体而言，则是包含了6个A即为6个A、4个B即为4个B、9个C即为9个C、4个D即为4个D以及19个E即为19个E等元素构成。这些符号各自对应的具体概率则分别为：1/7、2/21、3/14、2/21以及19/42等数值呈现的形式。具体而言，则是包含了这些数值的具体情况构成的概率分布情况如下：

P(A)=1/7
P(B)=2/21
P©=3/14
P(D)=2/21
P(E)=19/42

信息熵计算为2.043

香农编码

编码步骤 ：
(1)将信源符号按概率从大到小顺序排列，为方便起见

(2)按计算第i个符号对应的码字的码长(取整)；

(3) 计算第i个符号的累加概率 ；

(4)将累加概率变换成二进制小数，取小数点后 位数作为第i个符号的码字。

具体编码见：信息熵与压缩编码基础

霍夫曼编码

编码步骤 ：

1. 对每个符号创建一个单独的叶子节点，并为其分配相应的频率值。
2. 当当前队列中存在多个节点时，请执行以下操作：
   a. 将这些节点视为带权值的二叉树根节点（左、右子树为空）。
   b. 在所有根节点中选择权重最小的两个节点作为左右子树，并构造一棵新的二叉树；新二叉树的根结点权重为其左右子树根结点权重之和。需将被合并的两个最小权值节点从队列中移除，并将新生成的二叉树加入队列中继续处理。
3. 当队列中只剩下一个根节点时，则停止操作；此时生成的二叉树即为最终结果。

香农-范诺（Shannon-Fano）编码方法通常不产生最佳码。1952年, David A. Huffman开发了一种全新的编码方案,这种方案能够为各种可能性生成一棵具有最佳特性码树。

香农-范诺编码基于树干向分支延伸的方向进行编码，在构建码表时遵循自上而下的路径；而哈夫曼编码算法则采取相反策略，在生成最优树时采用自下而上的方式构建码表。

具体演算工程：同上

一张1024×768分辨率下的24位RGB彩色图像在内存中总共占用多少个字节？ 若将其以无压缩格式存储为BMP文件形式，则该文件含有多少个字节？

1.一幅1024*768的24位RGB彩色图像占用字节数：

1024 768 24/8=2359296 byte

BMP 文件则由四个组成部分构成：文件头、位图信息头、颜色信息以及图形数据。其中24 位真彩色图像无需额外的彩色板支持，这是因为位图中的RGB值直接反映了每个像素所具有的颜色信息。具体来说文件头+位图信息头+颜色信息为54字节再加上图形数据总共达到**2 , 359 , 350**字节的存储需求