作者Syncanph (go lifer)
看板CSSE
标题Re: [问题] 以bit为单位的无失真compressor...
时间Thu May 11 15:38:26 2006
恕删
原资料 0 跟 1 的比例为 75% : 25% 的情况下
可以算一下他的 entropy 是
-(0.75 * log2(0.75) + 0.25 * log2(0.25)) = 0.811 左右
这表示使用 general-purpose 的 entropy coder (如 arithmetic 或 Huffman coder)
的压缩极限就在 0.811 = 81.1% 左右
一般资料压缩的压缩率要能提升, 通常是因为资料本身有某些规则性,
例如 image (相邻的 pixel 颜色相近) 或统计性的资料,
但原 PO 有强调他的资料是乱数分布, 因此要再提升压缩率是相当困难的
也许用 RLE 之类的非 entropy coding 方法有可能再进一步
但那是有点运气问题的
至於无失真影像压缩的部分
我推荐原 PO 看一下 JPEG-LS
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.124.166.94
1F：推 jmren:感谢回应^^"，请问entropy的公式是根据哪个理论得来的...^^ 05/11 18:53
2F：→ reader:资讯理论 这公式在电脑科学的地位约等於物理学的E=MC^2呢 05/11 23:23
3F：→ reader:是连结资讯与自然世界之间的核心枢纽之一 意义相当重大 05/11 23:31
4F：→ reader:不过现在还真难得在科学史之外 看到有人用上那麽一回 05/11 23:32
5F：推 slzhao:不会很难得看到吧,Pattern Recognition相关的研究常用到. 05/12 02:08
6F：→ slzhao:是很重要的理论,但是有那麽夸张的地位吗? 05/12 02:12
7F：→ reader:主要是因为在其他学科上也有讯息传递的现象值得研究 05/12 02:29
8F：→ reader:若能通过资讯理论检验就能整合电脑作研究 算是很关键一步 05/12 02:39
9F：→ reader:所以是电脑科学中最能带给其他学科冲击的理论之一了 05/12 02:40
10F：→ reader:这和拿电脑做研究工具是不一样的事情 而是实在的理论连结 05/12 02:46
11F：→ slzhao:但这只是关键一步,关键的步可多了. 05/12 10:49
12F：→ slzhao:计算理论或正规语言中探讨的可计算性,不也是重要的一步. 05/12 10:50
13F：→ slzhao:这主要因素是因为计算机非传统科学,所以待整合的东西可多了 05/12 10:50
14F：→ slzhao:逻辑学,集合论中很多理论跟资讯科学整合也是很重要的"一步" 05/12 10:54
15F：→ slzhao:感觉起来,NP-complete观念的引入还比较接近E=MC^2. 05/12 10:54
16F：→ reader:可计算性一直被认为是数学 而且跟自然科学缺乏连结 05/12 17:56
17F：→ reader:但资讯熵的概念却是真实世界运作的一个部分 05/12 17:57
18F：→ reader:逐步在物理、化学、生物、生态、经济、哲学、政治等学科 05/12 18:02
19F：→ reader:建立起影响力 其他相关的如控制论也不被认为是电脑科学 05/12 18:05
20F：→ reader:到混沌学则已经是太过後期的新科学发展 但资讯理论是1948年 05/12 18:06
21F：→ reader:一般所谓战後新科学的组成中 电脑科学就是以资讯理论而进入 05/12 18:07
22F：→ reader:这样的体系当中 当然这比较是偏向科学史的观点而不是实用性 05/12 18:08
23F：→ reader:但E=MC^2也主要是作为科学认识的拓展大於实际作用 05/12 18:10
24F：→ reader:或者说计算理论是让电脑科学脱离数学的关键 05/12 18:18
25F：→ reader:资讯理论是让电脑科学成为科学的关键 05/12 18:18
26F：→ reader:现在习称系统论控制论和信息论(资讯理论)为系统科学老三论 05/12 18:23
27F：→ reader:可计算性则通常是放在数学发展史上来讲的 05/12 18:26
28F：→ slzhao:不是很能理解熵在电脑史中的重要性.因为我一直感觉是统计学 05/12 19:17
29F：→ slzhao:跟其他自然科学结合的关键,而计算机科学则是引用了统计学中 05/12 19:19
30F：→ slzhao:的这个概念. 05/12 19:19
31F：→ slzhao:有没有相关介绍这方面演进的文献资料可供参考? 05/12 19:20
32F：→ reader:统计学被引入自然科学是在热力学时就建立起来的吧... 05/12 21:48
33F：→ reader:透过资讯理论才建立了非能量的讯息的自然存在与传播原理 05/12 21:51
34F：→ reader:数学原理是一回事 概念的拓展才是重点 05/12 21:56
35F：→ reader:就像广义相对论和黎曼几何不能说是同样的东西 05/12 21:59
36F：→ reader:概念上也是广义相对论才具有重要的影响力 否则数学只是数学 05/12 22:00
37F：→ reader:其实上网找「信息论」就有一堆资料了 05/12 22:03
39F：推 slzhao:我不是指Information Theory的研究,相关论文我也有看过一些 05/12 22:21
40F：→ slzhao:我是想请问关於reader大大前面所说的历史演进,和其重要性的 05/12 22:22
41F：→ slzhao:相关资料. 05/12 22:24
42F：→ slzhao:刚才针对老三论查了一下,这似乎是由人文科学的观点来看, 05/12 23:03
43F：推 b6s:如果从资讯理论被人文科学广泛引用的情况来说，的确跟 05/14 15:01
44F：→ b6s:相对论被拿去扯是差不多的状况。 05/14 15:03