壓縮算法

壓縮算法（compaction algorithm）是指數據壓縮的算法，在電子與通信領域也常被稱為信號編碼，包括壓縮和還原（或解碼和編碼）兩個步驟。

由於多媒體信號的數據量巨大，所以需要壓縮；同時，由於在多媒體數據中，存在着各種冗餘，所以可以壓縮。

用於多媒體數據的壓縮方法眾多，可按主要特點將它們分成不同的類型。

（1）無損與有損

1、無損壓縮：能夠無失真地從壓縮後的數據重構，準確地還原原始數據。可用於對數據的準確性要求嚴格的場合，如可執行文件和普通文件的壓縮、磁盤的壓縮，也可用於多媒體數據的壓縮。該方法的壓縮比較小。如差分編碼、RLE、Huffman編碼、LZW編碼、算術編碼。

2、有損壓縮：有失真，不能完全準確地恢復原始數據，重構的數據只是原始數據的一個近似。可用於對數據的準確性要求不高的場合，如多媒體數據的壓縮。該方法的壓縮比較大。例如預測編碼、音感編碼、分形壓縮、小波壓縮、JPEG/MPEG。

（2）對稱性

若編解碼算法的複雜性和所需時間差不多，則為對稱的編碼方法，多數壓縮算法都是對稱的。但也有不對稱的，一般是編碼難而解碼容易，如Huffman編碼和分形編碼。但用於密碼學的編碼方法則相反，是編碼容易，而解碼則非常難。

（3）幀間與幀內

在視頻編碼中會同時用到幀內與幀間的編碼方法，幀內編碼是指在一幀圖像內獨立完成的編碼方法，同靜態圖像的編碼，如JPEG；而幀間編碼則需要參照前後幀才能進行編解碼，並在編碼過程中考慮對幀之間的時間冗餘的壓縮，如MPEG。

（4）實時性

在有些多媒體的應用場合，需要實時處理或傳輸數據（如現場的數字錄音和錄影、播放MP3/RM/VCD/DVD、視頻/音頻點播、網絡現場直播、可視電話、視頻會議），編解碼一般要求延時≤50ms。這就需要簡單/快速/高效的算法和高速/複雜的CPU/DSP芯片。

（5）分級處理

有些壓縮算法可以同時處理不同分辨率、不同傳輸速率、不同質量水平的多媒體數據，如JPEG2000、MPEG-2/4。

熵編碼（Entropy Encoding）是一類利用數據額統計信息進行壓縮的無語義數據流的無損編碼。信息熵為信源的平均信息量（不確定性的度量）。常見的熵編碼有行程碼（RLE）、LZW編碼、香農（Shannon）編碼、哈夫曼（Huffman）編碼和算術編碼（Arithmetic coding）。

混合編碼即熵編碼和（信）源編碼的組合。大多數壓縮標準都採用混合編碼的方法進行數據壓縮，一般是先利用信源編碼進行有損壓縮，再利用熵編碼做進一步的無損壓縮。

（信）源編碼（Source Coding）是一類利用信號原數據在時間域和頻率域中的相關性和冗餘進行壓縮的有損編碼。種類繁多，可進一步分為如下幾種。

1、預測編碼：利用先前和限制的數據對在時間或空間上相鄰的下面或後來的數據進行預測，從而達到壓縮的目的。如增量調製（DM）、差分和自適應編碼（ADPCM）；

2、變換編碼：採用各種數學變換方法，將原時間域或空間域的數據變換到頻率域或其他域，利用數據在變換域中的冗餘或人類感覺的特徵來進行壓縮。常見的變換編碼有FFT（快速傅里葉變換）、DCT（離散餘弦變換）、DWT（離散小波變換）和IFS（迭代函數系統）；

3、分層編碼：將原數據在時空域或頻率域上分成若干子區域，利用人類感覺的特徵進行壓縮編碼，然後再合併，如二值位、子採樣、子帶編碼； ^[1]