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

作者 | 發布日期 2015 年 10 月 19 日 14:00 | 分類 推薦書摘 , 科技教育 follow us in feedly

生活中隱藏許多邏輯,例如蛋糕怎麼分?俊男美女怎麼挑?數學怎麼學?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,因為學生的成績彼此之間往往相差不大,差額編碼可以有助於資料的壓縮。

新聞稿

 

《你沒聽過的邏輯課》簡介

有時直覺會告訴我們正確的答案,但是數學上的計算才是最可靠的!中研院士劉炯朗以親切的語法,引領思考的階梯,以深入淺出的方式,讓邏輯和數學不再深奧,生活變得更有趣。詳見《時報出版》。

(首圖來源:Flickr/A Health Blog CC BY 2.0) 

關鍵字: , , ,

發表迴響