数据的压缩

northwolves

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

gxqcn

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

Lwins_G

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

northwolves

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

liangbch

压缩率最高的软件是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

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

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

zeroieme

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

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

wayne

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

无心人

计算下各答案出现的概率，假设分别是是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:23
计算下各答案出现的概率，假设分别是是a, b, c, d, a+b+c+d=1
并假设a>=b>=c>=d，如果不是，显然，可以等 ...

大神,你说的是啥意思?
我觉得你的问题完全可以使用lingo求解出来!