資料壓縮

資料壓縮也稱為數據壓縮。在計算機科學和資訊論中,資料壓縮或者源編碼是按照特定的編碼機制用比未經編碼少的資料位元(或者其資訊相關的單位)表示資訊的過程。

概要

對於任何形式的通信來說,只有當資訊的傳送方和接受方都能夠理解編碼機制的時候壓縮資料通信才能夠工作。例如,只有當接受方知道這篇文章需要用英語字元解釋的時候這篇文章才有意義。同樣,只有當接受方知道編碼方法的時候他才能夠理解壓縮資料。一些壓縮算法利用了這個特性,在壓縮過程中對資料進行加密,例如利用密碼加密,以保證只有得到授權的一方才能正確地得到資料。
資料壓縮能夠實現是因為多數現實世界的資料都有統計冗餘。例如,字母「e」在英語中比字母「z」更加常用,字母「q」後面是「z」的可能性非常小。非破壞性壓縮算法通常利用利用了統計冗餘,這樣就能更加簡練地、但仍然是完整地表示傳送方的資料。
如果允許一定程度的保真度損失,那麼還可以實現進一步的壓縮。例如,人們看圖畫或者電視畫面的時候可能並不會注意到一些細節並不完善。同樣,兩個音頻錄音採樣序列可能聽起來一樣,但實際上並不完全一樣。破壞性壓縮算法在帶來微小差別的情況下使用較少的位數表示圖像、視頻或者音頻。
由於可以幫助減少如硬碟空間與連線頻寬這樣的昂貴資源的消耗,所以壓縮非常重要,然而壓縮需要消耗資訊處理資源,這也可能是費用昂貴的。所以資料壓縮機制的設計需要在壓縮能力、失真度、所需計算資源以及其它需要考慮的不同因素之間進行折衷。
一些機制是可逆的,這樣就可以恢復原始的資料,這種機制稱為非破壞性資料壓縮;另外一些機制為了實現更高的壓縮率允許一定程度的資料損失,這種機制稱為破壞性資料壓縮。
然而,經常有一些檔案不能被非破壞性資料壓縮算法壓縮,實際上對於不含可以辨別樣式的資料任何壓縮算法都不能壓縮。試圖壓縮已經經過壓縮的資料通常得到的結果實際上是擴展資料,試圖壓縮經過加密的資料通常也會得到這種結果。
實際上,破壞性資料壓縮也會最終達到不能工作的地步。我們來舉一個極端的例子,壓縮算法每次去掉檔案最後一個位元組,那麼經過這個算法不斷的壓縮直至檔案變空,壓縮算法將不能繼續工作。

套用

一種非常簡單的壓縮方法是行程長度編碼,這種方法使用資料及資料長度這樣簡單的編碼代替同樣的連續資料,這是非破壞性資料壓縮的一個實例。這種方法經常用於辦公計算機以更好地利用磁碟空間、或者更好地利用計算機網路中的頻寬。對於電子表格、文本、執行檔等這樣的符號資料來說,非破壞性是一個非常關鍵的要求,因為除了一些有限的情況,大多數情況下即使是一個資料位的變化都是無法接受的。
對於視頻和音頻資料,只要不損失資料的重要部分一定程度的品質下降是可以接受的。通過利用人類感知系統的局限,能夠大幅度得節約存儲空間並且得到的結果品質與原始資料品質相比並沒有明顯的差別。這些破壞性資料壓縮方法通常需要在壓縮速度、壓縮資料大小以及品質損失這三者之間進行折衷。
破壞性圖像壓縮用於數位相機中,大幅度地提高了存儲能力,同時圖像品質幾乎沒有降低。用於DVD的破壞性MPEG-2編解碼視頻壓縮也實現了類似的功能。
在破壞性音頻壓縮中,心理聲學的方法用來去除信號中聽不見或者很難聽見的成分。人類語音的壓縮經常使用更加專業的技術,因此人們有時也「語音壓縮」或者「語音編碼」作為一個獨立的研究領域與「音頻壓縮」區分開來。不同的音頻和語音壓縮標準都屬於音頻編解碼範疇。例如語音壓縮用於網際網路電話,而音頻壓縮被用於CD翻錄並且使用 MP3 播放器解碼。

理論

壓縮的理論基礎是資訊論(它與算法資訊論密切相關)以及率失真理論,這個領域的研究工作主要是由 Claude Shannon 奠定的,他在二十世紀四十年代末期及五十年代早期發表了這方面的基礎性的論文。Doyle 和 Carlson 在2000年寫道資料壓縮「有所有的工程領域最簡單、最優美的設計理論之一」。密碼學與編碼理論也是密切相關的學科,資料壓縮的思想與統計推斷也有很深的淵源。
許多非破壞性資料壓縮系統都可以看作是四步模型,破壞性資料壓縮系統通常包含更多的步驟,例如它包括預測、頻率變換以及量化。
Lempel-Ziv(LZ)壓縮方法是最流行的非破壞性存儲算法之一。deflate是 LZ 的一個變體,它針對解壓速度與壓縮率進行了最佳化,雖然它的壓縮速度可能非常緩慢,pkzip、gzip 以及 PNG 都在使用 DEFLATE。LZW (Lempel-Ziv-Welch)是 Unisys 的專利,直到2003年6月專利到期限,這種方法用於 GIF 圖像。另外值得一提的是 LZR (LZ-Renau) 方法,它是 Zip 方法的基礎。LZ 方法使用基於表格的壓縮模型,其中表格中的條目用重複的資料串替換。對於大多數的 LZ 方法來說,這個表格是從最初的輸入資料動態生成的。這個表格經常採用霍夫曼編碼維護(例如,SHRI、LZX)。 目前一個性能良好基於 LZ 的編碼機制是 LZX,它用於微軟公司的 CAB 格式。
最好的壓縮工具將機率模型預測結果用於算術編碼。算術編碼由 Jorma Rissanen 發明,並且由 Witten、Neal 以及 Cleary 將它轉變成一個實用的方法。這種方法能夠實現比眾人皆知的哈夫曼算法更好的壓縮,並且它本身非常適合於自適應資料壓縮,自適應資料壓縮的預測與上下文密切相關。算術編碼已經用於二值圖像壓縮標準 JBIG、文檔壓縮標準 DejaVu。文本 輸入 系統 Dasher 是一個逆算術編碼器。

相關詞條

相關搜尋

熱門詞條

聯絡我們