首页 > 信息论 > 数据压缩方法

数据压缩方法

数据压缩data compression),或者称为信源编码,对利用数据中的冗余(redundancy),来实现减少数据集大小的方法。

(1)统计冗余

传统的信息论的方法,是利用统计冗余(statistical redundancy)。何谓统计冗余?一般的说法是符号出现的概率不相等。为什么这样就叫冗余呢?因为一个各符号出现概率相等的信源(也即看起来完全随机)是最简洁的,也是我们对它没有任何知识的信源——这对应于物理中的能量均分原理。如果概率不相等,那我们对这个信源有一定的(统计)知识,就可以用来变换这个信源到另一个更接近完全随机信源的的信源,从而实现压缩。

大体有这样一些方法

定长块编码(Fixed-length block codes)。如果令X是一个信号源,X随机独立重复n次,那得到的n长序列,有很多可能。不过根据大数定理,其中只有很少一部分是典型的,也就是说,其他的序列,概率极小,统计上可以忽略。所以,我们只需要对这部分典型序列做编码。而且这些典型序列的出现概率都是近乎相等的。这个特性也就是著名的渐进等分原理(AEP)。香农信源编码定理利用这个原理,证明,用定长块编码,我们可以用nH(X)码长实现对X的n长序列的任意小错误率的编码。这种编码,只有理论价值,没有工程价值。

符号编码(symbol codes)做一个从原符号集到编码集的映射,并保证可以唯一解码。典型的是一些变长(variable-length)前缀码(prefix codes),如霍夫曼(Huffman)编码。基本原理是经常出现的符号给以短码。这也是利用统计冗余。

流编码(stream codes)不依赖一个事先定义的一一对应编码,而通过读输入数据流,动态构造编码。算术码arithmetic codes)把每个字符串映射到[0,1)上的一个区间,区间的长度就是这个字符串的概率;收发端都知道这个概率分布。Lempel-Ziv编码记住已经见过的字符串,构造一个字典,这样下次遇到同样的字符串,只要给出它在字典中的位置即可。

(2)统计语义冗余 (statistical semantic redundancy )

目前主要是用在数据库领域。这是利用有结构的数据中存在的统计依赖关系来压缩。

SPARTAN是利用决策树,去除关系数据表中的某些列(column)——因为这些列现在可以通过决策树恢复。

ItCompress是一种聚类的方法,对表中的行(row),指定一些行为代表,其他行只记录和代表行之间的差别。fascicles算法类似。

一般的,机器学习就是一个信息压缩的过程。现在有很多本体学习的算法(例:DL-Learner),都可以看作信息压缩算法。

统计语义依赖可以表达一般的统计依赖(贝叶斯依赖)不能表达的关系,例如使用量词: P(C(x)|\exists R(x,a))=0.7

(3)演绎语义冗余(deductive semantic redundancy)

给定一个逻辑知识库,如果数据集的一部分可以通过其他部分经逻辑演绎获得,那这部分数据属于语义冗余,可以除去。对RDF和OWL,都有冗余检测算法。

不过彻底的冗余除去是计算代价很高的过程。可能通过一些启发式算法来估计某些数据是冗余数据的可能行,以提高可扩展性。

Advertisements
分类:信息论
  1. 还没有评论。
  1. No trackbacks yet.

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: