《計算機科學概論（第12版）》—第1章1.9節資料壓縮

本節書摘來自異步社群《計算機科學概論（第12版）》一書中的第1章1.9節資料壓縮，作者【美】j. 格倫•布魯克希爾（j. glenn brookshear） , 丹尼斯•布裡羅（dennis brylow）,更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

*1.9　資料壓縮

為了存儲或傳輸資料，在保留原有内容的同時，縮小所涉及資料的大小是有益的（有時也是必須的）。用于完成這一過程的技術稱為資料壓縮（data compression）。本節，我們首先要學習一些普通的資料壓縮方法，然後要了解一些為特殊應用設計的方法。

1.9.1　通用的資料壓縮技術

資料壓縮方案有兩類，一類是無損的（lossless），另一類是有損的（lossy）。無損方案在壓縮過程中是不丢失資訊的，有損方案在壓縮過程中會丢失資訊。通常有損技術比無損技術更能壓縮，是以在可以容忍小錯誤的應用中很流行，如圖像和音頻壓縮。

對于被壓縮資料由一長串相同的數值組成的情況，普遍使用稱為行程長度編碼（run-length encoding）的壓縮技術，這是一種無損方法。它的過程是，将一組相同的資料成分替換成一個編碼，指出重複的成分以及其在序列中出現的次數。例如，指出一個位模式包括253個1，接着118個0，接着87個1，這樣要比實際列出458個位節省空間。

另外一種無損資料壓縮技術是頻率相關編碼（frequency-dependent encoding），在這個系統裡，用于表示資料項的位模式的長度與這個項的使用頻率是反相關的。這種編碼是變長編碼的例子，意思是項由不同長度的模式表示。戴維·赫夫曼的功勞是發現了一般用于開發頻率相關編碼的算法，人們一般稱用這種方法開發的編碼為赫夫曼編碼（huffman code）。是以，現在使用的大多數頻率相關編碼都是赫夫曼編碼。

讓我們看一個頻率相關編碼的例子，考慮一下編碼英文文本的任務。在英文中，字母e、t、a和i的使用頻率要大于字母z、q和x。是以，當為英文文本編碼時，如果用短位模式表示前面的字母，用長位模式表示後面的字母，那麼就能節省空間。結果得到的編碼中，英文文本的表示長度要比用統一長度編碼時的短。

在某些情況下，壓縮的資料流由各個資料單元組成，每一個資料單元與其前面一個差别很小。動畫的連續幀就是一個例子。這時，使用相對編碼（relative encoding）——也稱為差分編碼（differential encoding）——技術是很有用的。這些技術記錄下了兩個連續資料單元之間的差別，而不是全部單元；也就是說，每個單元是根據其與前一個單元的關系被編碼的。相對編碼用無損形式或有損形式都可以實作，具體取決于兩個連續資料單元之間的差别是精确編碼還是近似編碼。

還有其他流行的基于字典編碼（dictionary encoding）技術的壓縮系統，這裡的術語字典（dictionary）指的是一組構造塊，壓縮的資訊通過它們建造起來，而資訊本身被編碼成字典的一系列參照符。我們一般認為字典編碼系統是無損系統，不過在學習圖像壓縮時我們将看到，有時候字典條目僅僅是正确資料成分的近似值，這就使其成了有損壓縮系統。

字處理程式可以使用字典編碼來壓縮文本文檔，因為這些字處理程式中已經包含了用于拼寫檢查的字典，而這些字典都是出色的壓縮字典。特别值得一提的是，一個完整的單詞可以編碼成字典的一個單獨參照符，而不是像使用utf-8系統那樣編碼成一系列單獨的字元。在字處理程式中，一個典型的字典大約有25 000個條目，這就意味着，單個的字典條目可以用0到24999範圍内的整數來辨別。也就是說，字典中的一個特定條目用15位的模式就足可辨別。相反，如果用到的單詞包括6個字母，則它的逐字元編碼在使用utf-8時需要48位。

字典編碼的一個變體是自适應字典編碼（adaptive dictionary encoding，也稱動态字典編碼）。在自适應字典編碼系統中，字典在編碼過程中是可以改變的。一個流行的例子是lzw編碼（lempel-ziv-welsh encoding），這個編碼的名稱是根據它的創造者abraham lempel、jacob ziv和terry welsh的姓氏命名的。要用lzw對資訊編碼，首先要從包含基礎構造塊的字典開始，用字典中的構造塊來構造資訊。但是，當人們在資訊中發現更大的單元時，會把它們加到字典上——這意味着，這些單元在未來出現時可以被編碼為一個（而不是多個）字典參照符。例如，當對英文文本編碼時，人們首先要從包含單獨字元、數字和标點符号的字典開始。但是，當資訊中的單詞被辨別後，會被加到字典中。是以，随着資訊的不斷編碼，字典會不斷增大，而随着字典的不斷增大，資訊中會有更多的單詞（或者重複的單詞模式）被編碼為單個的字典參照符。

結果是，資訊用一部相當大的、完全針對本資訊的字典進行編碼。但是在對這條資訊進行解碼時，不必用這個大字典，隻需要用原始的小字典即可。事實上，解碼過程可以與編碼過程用同一個小字典。接着，随着解碼程序的繼續，會遇到編碼過程中發現的相同單元，是以可以将它們加到字典中，作為未來編碼過程的參照符。

舉例說明，考慮對下列資訊應用lzw編碼：

xyx xyx xyx xyx

首先從一個隻有3個條目的字典開始，第1個條目是x，第2個條目是y，第3個條目是空格。我們先将xyx編碼為121，意思是這個資訊的第一個模式依次包括第一個字典條目、第二個字典條目、第一個字典條目。接着，空格被編碼産生結果1213。但是因為有了一個空格，我們知道前面的字元串已經形成了一個單詞，是以我們将模式xyx加到字典裡作為第4個條目。繼續使用這種編碼方式，整個資訊将被編碼為121343434。

如果我們現在從原始的3條目字典開始對這條資訊進行解碼，那麼我們首先要将起始的1213串解碼為xyx加1個空格。這時我們意識到xyx串形成了一個單詞，是以将其加到字典中作為第4個條目，同編碼過程中所做的一樣。我們接着對這個資訊解碼，發現資訊中的4指的是這第4個新條目，将其解碼為單詞xyx，是以産生模式：

xyx xyx

繼續使用這種解碼方式，我們最終把121343434串解碼為：

這就是原始資訊。

1.9.2　圖像壓縮

在1.4節中，我們已經看到如何用位圖技術對圖像編碼。不過，得到的位圖通常是非常大的。是以，人們專門為圖像表示開發出了許多壓縮方案。

一種稱為gif（是graphic interchange format的縮寫，即圖像交換格式，一些人将其讀作“giff”，還有一些人将其讀作“jiff”）的系統是一個字典編碼系統，由compuserve公司研制開發。它處理壓縮問題的方法是，将賦予一個像素的顔色數量減少到隻有256個。每一種顔色的“紅—綠—藍”組合都用3個位元組編碼，這256個編碼被存儲在一個稱為調色闆的表格（一個字典）裡。圖像中的每個像素都可以用一個位元組表示，該位元組的值指出了這個像素的顔色是由256個調色闆條目中的哪一個表示的。（回顧：一個位元組能夠包括256個不同位模式中的任意一個。）需要注意的是，在将gif應用于任意圖像時，它是一個有損壓縮系統，因為調色闆中的顔色可能與原始圖像中的顔色不一緻。

通過使用lzw技術将這個簡單的字典系統擴充為自适應字典系統，gif可以進一步壓縮。尤其是，編碼過程中遇到的像素模式可以被加到字典中，使得這些模式在将來出現時可以被更加高效地編碼。是以，最終的字典是由原始調色闆和一組像素模式構成的。

gif調色闆中的某一個顔色通常會被賦予值“透明”，意思是背景色可以透過每一個被賦予該“顔色”的區域表現出來。這個選擇，與gif系統的相對簡便性相結合，使得gif成為簡單動畫應用（這動畫應用中的多重圖像必須在計算機螢幕上移動）的合理選擇。另一方面，它隻能夠對256種顔色編碼，這使得它不适合精确度要求較高的應用，如攝影領域。

另外一種流行的圖像壓縮系統是jpeg（讀作“jay-peg”）。它是由iso中的聯合圖像專家組（joint photographic experts group，标準是以得名）研制開發的标準。jpeg已經被證明是壓縮彩色照片的一種有效标準，并被廣泛用于攝影業，這一點可由大多數數位相機都将jpeg作為它們預設的壓縮技術這一事實來證明。

jpeg标準實際上包含多種圖像壓縮方法，每種都有它自己的目标。在需要絕對精确的情況下，jpeg可提供無損模式。不過，相對于jpeg的其他模式，jpeg的無損模式不能形成進階别的壓縮。而且，jpeg的其他模式已被證明很成功，這就意味着人們很少使用其無損模式。相反，稱為jpeg基線标準（也稱為jpeg的有損順序模式）的jpeg模式已經成為許多應用的選擇标準。

使用jpeg基線标準的圖像壓縮有幾個步驟，其中有一些是利用人眼的局限性設計的。尤其是，相對于顔色的變化，人眼對亮度的變化更為敏感。是以，我們首先來看一幅用亮度成分和色度成分進行編碼的圖像。第一步是在一個2×2的像素方塊中求色度的平均值。這能将色度資訊的大小減小為$\frac{1}{4}$，同時保留所有的原始亮度資訊。結果是，在沒有明顯損失圖像品質的情況下獲得了很高的壓縮率。

下一步是将圖像劃分成8×8的像素塊，然後将每一個塊作為一個單元來壓縮資訊。這是通過一種稱為離散餘弦轉換的數學技術實作的，我們現在不需要關心這個轉換的細節。更重要的是，這種轉換将原始的8×8塊變成了另外一種塊（這種塊中的條目反映了原始塊中的像素之間是如何互相聯系的），而不是實際像素值。在這個新塊裡，那些低于預定極限的數值将被0替代，反映的是這些數值所表示出的變化非常小，人眼無法覺察。例如，如果原始塊中包含一個棋盤（checkerboard）模式，那麼新塊就可能表現為平均色。（一個典型的８×８像素塊表示的是圖像中一個非常小的方塊，是以人眼根本不能夠識别棋盤的外觀。）

這時候，可以應用更傳統的行程長度編碼、相對編碼以及變長編碼技術進行進一步的壓縮。總之，jpeg基線标準一般能在沒有明顯品質損失的情況下，将彩色圖像壓縮至少10倍，有時甚至能壓縮30倍。

另外一個資料壓縮系統是tiff（tagged image file format的縮寫，即标記圖像檔案格式）。不過，tiff最普遍的應用不是資料壓縮，而是存儲照片及其相關的資訊（如日期、時間以及相機設定）的一個标準格式。在存儲照片時，圖像本身通常會被存儲為沒有壓縮的紅、綠、藍像素成分。

tiff标準集合裡的确有資料壓縮技術，其中大多數是為在傳真應用中壓縮文本文檔的圖像設計的。為了利用文本文檔包含長串的白色像素這一事實，這些标準使用了行程長度編碼的變體。tiff标準中的彩色圖像壓縮選擇是以類似于gif所使用的技術為基礎的，是以并沒有被廣泛應用于攝影業。

1.9.3　音頻和視訊壓縮

音頻及視訊的編碼和壓縮最常用的标準是由iso上司的運動圖像專家組（motion picture experts group，mpeg）研制開發的，是以這些标準稱為mpeg。

mpeg包含許多不同應用的各種标準。例如，高清晰度電視（high definition television，hdtv）廣播的要求與視訊會議的就不同，廣播信号必須找到在各種容量可能很有限的通信路徑上傳輸的方式。另外，這兩種應用又都不同于存儲視訊的應用，它的有些部分可以被重放或略過。

mpeg使用的技術已經超出了本書的範圍，但是一般說來，視訊壓縮技術是以圖檔序列建構成的視訊為基礎的，與将運動圖像錄制到膠片上的方式基本相同。為了壓縮這些序列，隻有一部分稱為i幀（i-frame）的圖檔是被整個編碼的。在兩個i幀之間的圖檔是采用相對編碼技術進行編碼的，即并沒有對整個圖檔進行編碼，而隻是記錄了與前一個圖檔的差别。i幀本身經常使用類似于jpeg的技術壓縮。

最著名的音頻壓縮系統是mp3，它是在mpeg标準中開發出來的。事實上，mp3是mpeg layer 3的縮寫。與其他壓縮技術相比，mp3利用人耳的特性，删除了人耳覺察不到的細節。其中一個特性稱為暫時模糊（temporal masking），指的是在一次巨大聲響後，短時間内人耳覺察不到本可以聽見的輕柔聲音。另一個稱為頻率模糊（frequency masking），指的是某一頻率的聲音可能掩蓋相近頻率的輕柔聲音。利用這些特性，可以通過mp3獲得顯著的音頻壓縮，而且保持接近cd的音質。

使用mpeg和mp3壓縮技術，錄影機用128 mb的存儲空間就可以錄制長達1小時的視訊，便攜音樂播放器用1 gb的存儲空間就可以存儲多達400首流行歌曲。但是，不同于其他壓縮目的，音頻和視訊的壓縮目的不一定是節省存儲空間。真正重要的是獲得編碼，使得資訊能夠通過現在的通信系統得到及時的傳輸。如果每一個視訊幀需要1 mb的存儲空間，而傳播幀的通信路徑每秒隻能傳輸1 kb，那麼根本無法實作成功的視訊會議。是以，除了被認可的複制品質，音頻和視訊壓縮系統的選擇還要看及時資料通信的傳輸速度。這些速度通常用比特每秒（bits per second，bit/s）來度量。常見的機關包括kbit/s（kilo-bps的簡寫，即千比特每秒，等于103 bit/s）、mbit/s（mega-bps的簡寫，即兆比特每秒，等于106bps）和gbit/s（giga-bps的簡寫，即吉比特每秒，等于109 bit/s）。使用mpeg技術，視訊展示可以在40 mbit/s傳輸速率的通信路徑上成功傳輸。mp3錄制需要的傳輸速率一般不超過64 kbit/s。

問題與練習

1．列出4種通用的壓縮技術。

2．如果使用lzw壓縮，并且最初字典隻包含x、y和一個空格（如文中所述），對下列資訊編碼，結果是什麼？

xyx yxxxy xyx yxxxy yxxxy

3．在對彩色卡通編碼時，為什麼gif比jpeg要好？

4．假設你是航天器設計團隊的一員，要設計能駛向其他星球并發回照片的航天器。那麼，為了減少存儲和傳輸圖像所需的資源，使用gif或jpeg的基準标準壓縮照片是否是一個好主意？

5．jpeg的基準标準利用了人眼的什麼特性？

6．mp3利用了人耳的什麼特性？

7．說出一種在把數字資訊、圖像和聲音編碼為位模式時常見的麻煩現象。