手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

关于信息墒与压缩编码基础的学习

时间:2021/5/22 12:41:21|来源:|点击: 次

文章目录

  • 一、信息论中的知识点
  • 二、统计编码
    • 香农-凡诺编码
    • 霍夫曼编码
  • 三、关于RGB

一、信息论中的知识点

决策量(decision content)

定义:在有限数目的互斥事件集合中,决策量是事件数的绝对值。
在数学上表示为
H 0 = l o g ( n )   , 其 中 , n 是 事 件 数 H_0 = log(n)\ ,其中,n是事件数 H0=log(n) ,n


决策量的单位由对数的底数决定

Sh(Shannon):用于以2为底的对数
Nat(natural unit):用于以e为底的对数
Hart(hartley):用于以10为底的对数


信息量(information content)

定义:具有确定概率事件的信息的定量度量
在数学上定义为
I ( x ) = l o g 2 [ 1 / p ( x ) ] = − l o g 2 p ( x ) I(x) = log_2[1/p(x)]=-log_2p(x) I(x)=log2[1/p(x)]=log2p(x)
其中,p(x)是事件出现的概率


举例:假设X={a,b,c}是由三个事件构成的合集,p(a)=0.5,p(b)=0.25,p©=0.25分别为事件a,b,c的概率,则信息量分别为

I ( a ) = l o g 2 [ 1 / 0.5 ] = 1 S h I(a) = log_2[1/0.5]=1 Sh I(a)=log2[1/0.5]=1Sh
I ( b ) = l o g 2 [ 1 / 0.25 ] = 2 S h I(b) = log_2[1/0.25]=2 Sh I(b)=log2[1/0.25]=2Sh
I ( c ) = l o g 2 [ 1 / 0.25 ] = 2 S h I(c) = log_2[1/0.25]=2 Sh I(c)=log2[1/0.25]=2Sh


信息熵(entropy)

定义:按照香农的理论,在有限的互斥和联合穷举事件合集中,熵为事件的信息量的平均值,也称事件的平均信息量。
在数学上表示为
H ( X ) = ∑ i = 1 n h ( x i ) = ∑ i = 1 n p ( x i ) I ( x i ) = − ∑ i = 1 n p ( x i ) l o g 2 p ( x i ) H(X) = \sum_{i=1}^nh(x_i)=\sum_{i=1}^np(x_i)I(x_i)=-\sum_{i=1}^np(x_i)log_2p(x_i) H(X)=i=1nh(xi)=i=1np(xi)I(xi)=i=1np(xi)log2p(xi)
其中,1、X={ x 1 , . . . , x n x_1,...,x_n x1,...,xn}是事件 x i ( i = 1 , 2 , . . . , n ) x_i(i=1,2,...,n) xi(i=1,2,...,n)的集合,并满足 ∑ i = 1 n p ( x i ) = 1 \sum_{i=1}^np(x_i)=1 i=1np(xi)=1
2、 I ( x i ) = − l o g 2 p ( x i ) I(x_i)=-log_2p(x_i) I(xi)=log2p(xi)表示莫格事件 x i x_i xi的信息量,其中 p ( x i ) p(x_i) p(xi)在事件 x i x_i xi出现的概率, 0 < p ( x i ) ≤ − p ( x i ) l o g 2 p ( x i ) 0<p(x_i)\le -p(x_i)log_2p(x_i) 0<p(xi)p(xi)log2p(xi)表示事件 x i x_i xi的熵。


举例:假设X={a,b,c}是由三个事件构成的合集,p(a)=0.5,p(b)=0.25,p©=0.25分别为事件a,b,c的概率,则a,b,c的熵分别为0.5,0.5和0.5。这个集合的熵为
H ( X ) = p ( a ) I ( a ) + p ( b ) I ( b ) + p ( c ) I ( c ) = 1.5 S h H(X)=p(a)I(a)+p(b)I(b)+p(c)I(c)=1.5 Sh H(X)=p(a)I(a)+p(b)I(b)+p(c)I(c)=1.5Sh

数据的冗余量

定义:在信息论中,数据的冗余量®定义为决策量 $(H_0) $超过熵(H)的量,数学上表示为 R = H 0 − H R=H_0-H R=H0H


举例:假设X={a,b,c}是由三个事件构成的合集,p(a)=0.5,p(b)=0.25,p©=0.25分别为事件a,b,c的概率,则这个数据集的冗余量则为,
R = H 0 − H = l o g 2 3 − [ − s u m i = 1 n l o g 2 p ( x i ) ] = 1.58 − 1.5 = 0.08 S h R=H_0-H=log_2 3-[-sum_{i=1}^{n}log_2p(x_i)]=1.58-1.5=0.08 Sh R=H0H=log23[sumi=1nlog2p(xi)]=1.581.5=0.08Sh

二、统计编码

香农-凡诺编码

在香农的源编码理论中,熵的大小表示非冗余的不可压缩的信息量。
在计算熵时,如果对数的底数用2,熵的单位就用"Sh"。


编码:对每个符号进行编码时采用“从上到下”的方法。首先先按照符号出现的频度或概率排序,然后用递归方法分成两个部分,每个部分具有近似相同的次数。

霍夫曼编码

与香农不同的是,霍夫曼提出和描述的“从下到上”熵编码方式。


编码:根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方式。这些元素出现的次数越多,其编码的额位数就越少。

·还有其他编码方式如算数编码、RLE编码等不在此次讨论

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

符号次数log(1/p(x))
A62.827
B43.392
C92.222
D43.392
E191.144
共计42-----

答:字符串的熵 H ( x ) = ∑ i = 1 n p ( x i ) l o g 2 p ( 1 / x i ) = 6 / 42 l o g ( 42 / 6 ) + 4 / 42 l o g ( 42 / 4 ) + 9 / 42 l o g ( 42 / 9 ) + 4 / 42 l o g ( 42 / 4 ) + 19 / 42 l o g ( 42 / 19 ) = 2.043 S h H(x)=\sum_{i=1}^np(x_i)log_2p(1/x_i)=6/42log(42/6)+4/42log(42/4)+9/42log(42/9)+4/42log(42/4)+19/42log(42/19)=2.043 Sh H(x)=i=1np(xi)log2p(1/xi)=6/42log(42/6)+4/42log(42/4)+9/42log(42/9)+4/42log(42/4)+19/42log(42/19)=2.043Sh


采用香农-凡诺编码
按照概率大小排序,再分割E,C分为19和23,再从C,A,B,D中分割C,A分为了9,14,再从A,B,D中分割为A,B分为6和8,再将B和D分割。

符号次数编码位数
E19119
C90018
A600018
B4011116
D4011016
共计42-----87

编码前:5个符号需要三位,42个字符共126。
编码后:共87位
压缩比:126:87=1.45:1


采用霍夫曼编码
根据符号的次数,E>C>A>B,D,B=D。
先将B,D组成节点共8,再与A组成节点共14,再与C组成节点共23,再与E组成节点。

符号次数编码位数
E19119
C90018
A600018
B4011116
D4011016
共计42-----87

编码前:5个符号需要三位,42个字符共126。
编码后:共87位
压缩比:126:87=1.45:1
感觉和香农-凡诺编码结果一样了

三、关于RGB

一幅1024768的24位RGB彩色图像一共在内存中占有多少字节? 如果将其保存为非压缩格式的BMP文件,文件有多少字节?
答:RGB占3字节的话,文件共1024
768*3=2359296字节。BMP文件由文件头、位图信息头、颜色信息和图形数据四部分组成。需要加上文件头和位图信息头,颜色信息,文件字节将大于2359296字节。

Copyright © 2002-2019 某某自媒体运营 版权所有