數據壓縮與熵

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

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

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

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