《你沒聽過的邏輯課》書摘──科技時代的壓縮邏輯

生活中隱藏許多邏輯，例如蛋糕怎麼分？俊男美女怎麼挑？數學怎麼學？MLB 怎麼看？魔術怎麼學？樂透彩怎麼買？當我們要回答這些問題時，必須跳脫慣性思惟，才能破解這些花招。中研院士劉炯朗以親切的語法，引領思考的階梯，以深入淺出的方式，帶領讀者逐步破解各類日常迷思。以下是由《時報出版》授權，摘自該書的部份內容。

從遠古時代開始，文字的發明讓我們可以儲存語言的資料；照相機發明於 1820 年左右，讓我們可以儲存圖像的資料；愛迪生於1877 年發明留聲機，讓我們可以儲存聲音的資料；電影發明於1895 年，讓我們可以儲存動畫的資料。有了電腦之後，文字、語言、圖像、聲音、動畫的資料都可以用 0 和 1 來表達，也就可以由電腦來處理，用記憶體來儲存，並且透過網路來傳送。當用 0 和 1 以某一個形式來表達資料時，資料壓縮就是指能否找到另一個形式，以較少的 0 和1 來表達。資料壓縮是一項重要的技術，可以減少儲存空間和傳送的時間。

資料壓縮的技術可以分成兩大類：無失真壓縮（Lossless Compression）與失真壓縮（Lossy Compression）。無失真壓縮減少使用 0 和 1 的數目，但原來的資料仍保持完整無缺，原因是原始資料的表達形式不見得是最有效率的，因此可以有改進的空間；而失真壓縮減少了更多 0 和 1 的數目，並造成一部份原始資料消失了，如果消失的部份不是那麼重要的話，為了讓資料量變得更小，倒也是一個值得的代價。

先來看幾個資料壓縮的例子：從十九世紀電報的發明開始，工程師已經訂定了一個規格，用由 5 個 0 和 1 的組合來表示英文裡的字母 a、b、c、d……。5 個 0 和 1 可以產生 32 個不同的組合，對 26 個英文字母已足夠了，但是為了區分大寫和小寫，再加上標點符號等，所以在 1960 年代訂定了至今大家仍相當熟悉的 ASCII 規格（American Standard Code 和 Information Interchange 的縮寫），使用由 7 個 0 和 1 的組合來表示英文字母和標點符號。7 個 0 和 1 有 128 個不同的組合，已足夠大小寫及標點符號的需求了。

因此，一篇有 1,000 個字母和標點符號的文件就要用 7,000 個 0 和 1 來表達，這些 0 和 1 的資料有沒有不失真壓縮的可能呢？

答案是可能的，語言學家分析過 26 個字母在英文裡使用的頻率，e 是最常用的字母，頻率是 12%，其次是 t 的 9%，a 是 8%，接下來是 o、i、n；在另一個極端，z 用的最少，0.07%、q 是0.09%、x 是 0.1%，如果我們不硬性地用一連串 7 個 0 和 1 來代表每一個字母，可以用比較少的 0 和 1，例如一連串 5 個或者 6 個 0 和 1 來代表比較常用的字母，用比較多的 0 和1，例如一連串 8 個或者 9 個 0 和 1 來代表比較不常用的字母，那麼平均下來可能不必用到 7,000 個 0 和1，就能達到壓縮的目的了。

如果我們硬性地用一連串 7 個 0 和1 來代表每一個字母，那麼當我們接收到轉送過來的 0 和 1 的時候，只要把每 7 個 0 和 1 切開來就對了，如果不同的字母用不同數目的 0 和 1 來代表的時候，應該怎樣把傳送過來的 0 和 1 正確地切開來呢？還有常用的字母用比較少的 0 和 1，不常用的字母用比較多的 0 和 1 來表達，「常用」和「不常用」、「比較多」和「比較少」這些觀念都可以精準地量化，在資訊科學裡「霍夫曼樹」（Huffman Tree）的方法就同時回答了這兩個問題。

在十九世紀，電報通訊技術發明的時候，英文字母是用一連串短的點「•（dot）」和長的劃「—（dash）」來代表的，例如 e 用點「• 」來代表，i 用點點「• • 」來代表，a 用點劃「• —」來代表，g 用劃劃點劃「—— • —」來代表，也符合了常用的字母用比較短的訊號來代表的觀念。

這個例子也指出資料壓縮裡一個重要的觀念，那就是壓縮的效率和資料的內容有關，當我們傳送一份用英文寫的文件的時候，上面講的壓縮方法是相當有效的，但是如果傳送的是一份閩南語羅馬字拼音的文件，那麼 a、b、c、d、e……的使用頻率可能和英文不同，上面講的壓縮方法，效率可能不會那麼高，甚至可能適得其反，增加了一共要使用 0 和 1 的數目了。

第二個我要講的例子，使用相似的觀念，那就是常用的字和詞彙用比較精簡的形式來表達，以達到資料壓縮的目的。用過微軟視窗作業系統的讀者，都知道 winzip 是常用的資料壓縮的工具，winzip 和其他壓縮工具的基本觀念是，每一個文件都會有用得比較多的字和詞彙，譬如說一份有關股票市場的報告，「買超」、「賣超」、「漲停板」、「跌停板」這些詞會重複出現，一份有關能源的報告，「節能」、「減碳」、「替代能源」這些詞會重複出現，所以如果對每一份文件，先製作一本字典，這本字典有幾千個在這份文件裡出現得比較多的字和詞，這些字和詞有一個相對的數字代號，當字典裡的一個詞在文件裡出現的時候，例如「漲停板」，我們不必把「漲停板」三個字傳送出去，而且它在字典中的數字代號，譬如說「168」傳送出去就可以了，這也是不失真的資料壓縮。

第三個資料壓縮的方法叫做「連續長度編碼法」（Run-Length Encoding），譬如說我們要傳送一連串的 011100001，可以直接把 011100001 傳送出去，也可以傳送 0（3 個 1）（4 個 0）1，不直接傳送 111 而傳送（3 個 1），不直接傳送 0000 而傳送（4 個 0），可能是多費了力氣增加要傳送的 0 和 1，但是如果我們要傳 0（15 個1）（32 個 0）（89 個 1），那就比直接傳送 0111111……來得有效率了。當我們存送一張圖像的時候，會用 0 來代表白色，1 代表黑色，如果圖裡有一大片白色的空白或者一大片黑色背景的時候，那就是一長串的 0 和一長串的 1，那麼連續長度編碼就是有效的資料壓縮方法了。

第四個壓縮方法叫做「差額編碼」（Delta Encoding），例如我們要把班上學生考試的成績記錄下來，可以寫 97、93、95、86……，但也可以寫 97、－4、＋2、－9，表示第一個學生成績是97，第二個學生的成績是第一個學生的成績－4 等於93，第三個學生的成績是第二個學生的成績＋2 等於95，因為學生的成績彼此之間往往相差不大，差額編碼可以有助於資料的壓縮。