northwolves 发表于 2013-11-6 21:04:35

数据的压缩

10000个单项 选择题,答案ABCD中的一个。32位下,为了比较方便地存取,最少需要多少字节?

gxqcn 发表于 2013-11-6 21:22:40

用0~3分别对应于A~D,占用2bit,所以可用 10000*2/8=2500 字节储存,
至于是否最小没有推敲,但存取是非常方便的。

Lwins_G 发表于 2013-11-6 21:27:52

根据信息论,2500Byte已经是最小的。不否认存在一个极端情况下更小的方案(如全选A时的储存方案),但是如果我们假设每道题选择ABCD的概率都是各25%的话,取任何一种可能的编码算法,消费空间的期望皆不小于2500Byte。

northwolves 发表于 2013-11-7 06:59:06

我现在就是用2500byte保存的:
00 A
01 B
10 C
11 D

liangbch 发表于 2013-11-7 10:35:10

压缩率最高的软件是PAQ,它使用算法编码,速度慢而压缩率极高。
我曾经编写过一个使用哈夫曼编码压缩的程序。测试的数据文件是Super PI计算100万位圆周率的输出,这个文件中,数字‘0’到‘9’出现次数最多,其次是空格,再次是回车和换行符,其他字符则仅仅出现一次。使用我的程序进行压缩,效果很好,平均每个字符的编码仅为3.6989比特,压缩比超过WinRAR.但和PAQ相比,则显的相形见绌。我的测算表明,PAQ的压缩比超过信息熵理论,不知道其背后的原理是什么。各位有兴趣的话,可以用PAQ试试。下面的内容摘自我在csdn发的一个帖子 http://bbs.csdn.net/topics/390042776#post-391258654。


我们考虑圆周率的2进制形式存储,用30比特来表示9位10进制数,这种方式完全丢弃了格式。即使这样,每个10进制字符依然需要30/9=3.33比特 (2^30=1073741824,刚好可以表示9位10进制数)。可以看到huffman编码和直接使用2进制存储相差无几了。

下面我们看看目前最强的使用算术编码技术的压缩软件,其压缩比如何,我使用PeaZip 4.5,压缩格式选择PAQ80,对supper-pi产生的包括小数点后1048576数字的文件进行压缩,其结果令人吃惊。1176511字节的源文件压缩后仅为436597字节,按此推算,原文件的1个字节,压缩后仅仅2.969比特,比2进制格式表示圆周率的还要小。不过这个软件的压缩速度可以用恐怖来形容,用我现在正在使用的电脑(2005年买的CPU为迅驰1.7G的笔记本电脑)对这个仅为1.1M字节的文件进行压缩,耗时竟然达到7分钟左右。

liangbch 发表于 2013-11-7 11:32:27

liangbch 发表于 2013-11-7 10:35
压缩率最高的软件是PAQ,它使用算法编码,速度慢而压缩率极高。
我曾经编写过一个使用哈夫曼编码压缩的程 ...

我是用 super-pi 产生的100万位10进制数的文本文件来测试的。

zeroieme 发表于 2013-11-8 09:11:53

liangbch 发表于 2013-11-7 10:35
压缩率最高的软件是PAQ,它使用算法编码,速度慢而压缩率极高。
我曾经编写过一个使用哈夫曼编码压缩的程 ...

楼主的前提是“为了比较方便地存取”。
PAQ那玩意适合一次压缩,永久存档。除非计算数学出现重大突破。

wayne 发表于 2013-11-14 13:02:52

楼主为啥强调 在32位下。
我觉得应该强调 是在二值电子计算机下,还是在三值光学计算机 吧,:lol

无心人 发表于 2013-11-25 14:23:05

计算下各答案出现的概率,假设分别是是a, b, c, d, a+b+c+d=1
并假设a>=b>=c>=d,如果不是,显然,可以等价替换出来
计算如下方案哪个最小
一、2b情况下是2a+2b+2c+2d=2
二、方案1,01,001,000
      长度a + 2b + 3c + 3d,当a > c + d时,优于一

mathematica 发表于 2013-11-25 14:30:48

无心人 发表于 2013-11-25 14:23
计算下各答案出现的概率,假设分别是是a, b, c, d, a+b+c+d=1
并假设a>=b>=c>=d,如果不是,显然,可以等 ...

大神,你说的是啥意思?
我觉得你的问题完全可以使用lingo求解出来!
页: [1]
查看完整版本: 数据的压缩