熵本來是熱動力學的概念,但在上世紀二十年代,熵的概念便移植到量子物理學,這主要是Von Neumann的功勞。到了四十年代,Shannon便把熵的概念用到資訊上。當時主要是為密碼學服務,但這亦可以用在數據壓縮上。當然,數據壓縮真正的大量出現就是八十年代的事。這也說明了數學的超前性!
今天,數據壓縮已是生活的一部份,mp3是聲音資料壓縮的先驅,可以有十倍或以上的壓縮比率。繼mp3後,出現了多種的聲音壓縮方案,很多都聲稱比mp3有更高的壓縮比。今天,一部ipod隨時可以下載幾千首歌,沒有數據壓縮,這實在難以想像。
用還用,天天用的東西未必等如我們會了解它的原理。今天便讓我們認識一下數據壓縮的基本原理。
我們首先由文字說起,看看下面的句子
She i beautiful.
打錯字!應該漏了一個s,句子應該是‘She is beautiful.’。非常好!我們為這句除錯了。但為甚麼我們可以做得到呢?白痴,懂英文的都看得出這個錯處。數學家與一般人不同的地方,就是數學家會尋根究底,很多一般人認為是常識的東西都不能令數學家滿意。
Shannon就是對文字做了很深入的研究,他引入了Redundancy的概念。由於我避免使用正統的數學和邏輯符號,接著的討論可能會有偏差,但概念是不會錯得太厲害的!就以上例來說,句子內就有redundancy,如果少傳送一個字母,但接收者仍可以獲得相同的資訊,那麼這個子母在某程度上便是‘多餘’的!
‘多餘’又與‘有序’有關。‘有序’即是‘有規律’,‘有規律’即‘多餘’。很多男人都說害怕和C9(師奶)談話,原因是很多C9的語言太有‘規律’了!Shannon把熵的概念推廣到資訊,推導出計算資訊的熵的公式。C9的語言的熵便是很低。也即是非常‘有序’!
Shannon於是進一步推論到,若提高資訊的熵,便可以減低資訊長度,這便是數據壓縮的基本原理。舉一個實例,例如,我們要傳送一篇英文,約一千字,約七千個字母(這裏字母廣泛包括空格和標點符號),若我們以一個byte來傳一個字母,這個資息便是7k byte。但我們可以想像,很多資訊都是‘重覆’或‘多餘’的。例如,文中可能會有很多個‘she’字,若我們把‘she’換成一個特別符號,那麼由傳送四個符號(三個字母加一個空格),便變成一個,單以這個對‘she’字的動作,便有四倍的壓宿比率。(這忽略了metadata,即我們要先傳送轉換表,所以設計得不好的壓縮算法,有時反變成數據膨漲)。
現代的數據壓縮算法,其實就是要發現資訊內的‘規律’,然後把這些‘規律’以更簡單的符號代替,這就等如將‘規律’去除。亦即令資訊的熵上升,但資訊的長度便隨之下降!
由於很多人的努力,今天的數據壓縮算法,經已很有效地發現自然語言的‘規律’,一般的‘文字檔’兩三倍壓縮比律是沒有甚麼問題的。
但對一些自然的參量,例如,聲音,問題就大得多了,可以想像,就算是重覆讀一個字一百次,若在示波器上作觀察,每次都會是不一樣的!理論上,我們差不多不可能完全相同地重覆讀出同一個字。但壓縮是基於重覆,沒有重覆就不能壓縮,那麼我們又如何壓縮聲音和影像等自然參量呢?下次再討論。
網誌存檔
-
▼
2008
(193)
-
▼
08
(52)
- 陰陽論(七)
- 思想開放
- 對與錯
- 觀點與角度
- 陰陽論(六)
- Less is more
- 語言謬誤
- 短暫的記憶
- 半導體(二)
- Tautology
- 自制電子管
- 半導體(一)
- 陰陽論(五)
- 語音廣播
- 陰陽論(四)
- 陰陽論(三)
- 不是P2P
- 陰陽論(二)
- 色即是空
- 四大皆空
- 陰陽論(一)
- 水下通訊
- 長波與短波
- AM與FM(二)
- 乘數表
- 古老科技!?
- AM與FM(一)
- 道德節
- ‘風’鳴
- 圖像壓縮與三角學(二)
- 圖像壓縮與三角學(一)
- 神與魔
- 重典
- FM立體聲(二)
- 相生相尅
- 圖像壓縮(二)
- FM立體聲(一)
- 過程vs.結果
- 生命的光輝
- 罵政府,正確嗎?
- 圖像壓縮(一)
- 匪夷所思
- 胡說八道
- 印象
- Who guard the guard? (2)
- Who guard the guard?
- 熱動力學第二定律的非數學理解
- 幾何學
- 忍辱波羅密與偉大政治家
- 數據壓縮與熵
- 熱動力學第二定律與時間
- 偱環
-
▼
08
(52)
沒有留言:
張貼留言