2008年8月6日 星期三

數據壓縮與熵

熵本來是熱動力學的概念,但在上世紀二十年代,熵的概念便移植到量子物理學,這主要是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,即我們要先傳送轉換表,所以設計得不好的壓縮算法,有時反變成數據膨漲)。

現代的數據壓縮算法,其實就是要發現資訊內的‘規律’,然後把這些‘規律’以更簡單的符號代替,這就等如將‘規律’去除。亦即令資訊的熵上升,但資訊的長度便隨之下降!

由於很多人的努力,今天的數據壓縮算法,經已很有效地發現自然語言的‘規律’,一般的‘文字檔’兩三倍壓縮比律是沒有甚麼問題的。

但對一些自然的參量,例如,聲音,問題就大得多了,可以想像,就算是重覆讀一個字一百次,若在示波器上作觀察,每次都會是不一樣的!理論上,我們差不多不可能完全相同地重覆讀出同一個字。但壓縮是基於重覆,沒有重覆就不能壓縮,那麼我們又如何壓縮聲音和影像等自然參量呢?下次再討論。

沒有留言:

網誌存檔