萬能資料壓縮演算法

有一個定理說，不存在一個萬能的無損資料壓縮演算法，總是能把任何長度的輸入字串，壓縮到比原來的長度還小。

這個定理的證明也不難。以長度為n的位元串(bit string)為例，總共有2ⁿ個，而長度小於等於n-1的位元串有2^n-1個。資料壓縮演算法可以視作一個將輸入字串對應到輸出字串的函數，而無損壓縮的要求是這個函數必須為一對一(injective)，否則解壓縮會有問題。但是，不存在從n個元素到n-1個函數的一對一函數，所以推論不存在這種演算法。

事實上，如果存在這樣的壓縮演算法，那把它的壓縮結果用同樣演算法再壓縮一次，豈不可以再縮得更小? 重複此動作，資料大小終究會為0。

換句話說，對於任何無損資料壓縮演算法，我們總是可以找到某個輸入字串， 使得壓縮後的結果沒有更好。

我不記得我唸書的時候有沒有學過這個定理，但說真的我們應用時好像不太care(?) zip 程式好像偵測到原始資料的entropy高到一種程度，就直接原文照登不壓縮，加上表頭後最後產生的檔案比原始檔還大。

部落格原作者的講解真不錯。