作者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