數據壓縮

數據壓縮

數據壓縮是指在不丟失有用信息的前提下,縮減數據量以減少存儲空間,提高其傳輸、存儲和處理效率,或按照一定的算法對數據進行重新組織,減少數據的冗餘和存儲的空間的一種技術方法。數據壓縮檔括有損壓縮無損壓縮

計算機科學資訊理論中,數據壓縮或者源編碼是按照特定的編碼機制用比未經編碼少的數據位元(或者其它信息相關的單位)表示信息的過程。例如,如果我們將“compression”編碼為“comp”那么這篇文章可以用較少的數據位表示。一種流行的壓縮實例是許多計算機都在使用的ZIP 檔案格式,它不僅僅提供了壓縮的功能,而且還作為歸檔工具(Archiver)使用,能夠將許多檔案存儲到同一個檔案中。

基本介紹

概要,分類,原理,套用,理論,流行算法,算法編碼,類型,

概要

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

分類

數據壓縮的方式非常多,不同特點的數據有不同的數據壓縮方式(也就是編碼方式),下面從幾個方面對其進行分類。
(1)即時壓縮和非即時壓縮
比如打IP電話,就是將語音信號轉化為數位訊號,同時進行壓縮,然後通過Internet傳送出去,這個數據壓縮的過程是即時進行的。即時壓縮一般套用在影像、聲音數據的傳送中。即時壓縮常用到專門的硬體設備,如壓縮卡等。
非即時壓縮是計算機用戶經常用到的,這種壓縮在需要的情況下才進行,沒有即時性。例如壓縮一張圖片、一篇文章、一段音樂等。非即時壓縮一般不需要專門的設備,直接在計算機中安裝並使用相應的壓縮軟體就可以了。
(2)數據壓縮和檔案壓縮
其實數據壓縮檔含了檔案壓縮,數據本來是泛指任何數位化的信息,包括計算機中用到的各種檔案,但有時,數據是專指一些具有時間性的數據,這些數據常常是即時採集、即時處理或傳輸的。而檔案壓縮就是專指對將要保存在磁碟等物理介質的數據進行壓縮,如一篇文章數據、一段音樂數據、一段程式編碼數據等的壓縮。
(3)無損壓縮與有損壓縮
無損壓縮利用數據的統計冗餘進行壓縮。數據統計冗餘度的理論限制為2:1到5:1,所以無損壓縮的壓縮比一般比較低。這類方法廣泛套用於文本數據、程式和特殊套用場合的圖像數據等需要精確存儲數據的壓縮。有損壓縮方法利用了人類視覺、聽覺對圖像、聲音中的某些頻率成分不敏感的特性,允許壓縮的過程中損失一定的信息。雖然不能完全恢復原始數據,但是所損失的部分對理解原始圖像的影響較小,卻換來了比較大的壓縮比。有損壓縮廣泛套用於語音、圖像和視頻數據的壓縮。

原理

事實上,多媒體信息存在許多數據冗餘。例如,一幅圖像中的靜止建築背景、藍天和綠地,其中許多像素是相同的如果逐點存儲,就會浪費許多空間,這稱為空間冗餘。又如,在電視和動畫的相鄰序列中,只有運動物體有少許變化,僅存儲差異部分即可,這稱為時間冗餘。此外還有結構冗餘、視覺冗餘等,這就為數據壓縮提供了條件。
總之,壓縮的理論基礎是資訊理論。從信息的角度來看,壓縮就是去除掉信息中的冗餘,即去除掉確定的或可推知的信息,而保留不確定的信息,也就是用一種更接近信息本質的描述來代替原有的冗餘的描述,這個本質的東西就是信息量。

套用

一種非常簡單的壓縮方法是行程長度編碼,這種方法使用數據及數據長度這樣簡單的編碼代替同樣的連續數據,這是無損數據壓縮的一個實例。這種方法經常用於辦公計算機以更好地利用磁碟空間、或者更好地利用計算機網路中的頻寬。對於電子表格文本執行檔等這樣的符號數據來說,無損是一個非常關鍵的要求,因為除了一些有限的情況,大多數情況下即使是一個數據位的變化都是無法接受的。
對於視頻和音頻數據,只要不損失數據的重要部分一定程度的質量下降是可以接受的。通過利用人類感知系統的局限,能夠大幅度得節約存儲空間並且得到的結果質量與原始數據質量相比並沒有明顯的差別。這些有損數據壓縮方法通常需要在壓縮速度、壓縮數據大小以及質量損失這三者之間進行折衷。
有損圖像壓縮用於數位相機中,大幅度地提高了存儲能力,同時圖像質量幾乎沒有降低。用於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 是一個逆算術編碼器。

類型

數據壓縮可分成兩種類型,一種叫做無損壓縮,另一種叫做有損壓縮
無損壓縮是指使用壓縮後的數據進行重構(或者叫做還原,解壓縮),重構後的數據與原來的數據完全相同;無損壓縮用於要求重構的信號與原始信號完全一致的場合。一個很常見的例子是磁碟檔案的壓縮。無損壓縮算法一般可以把普通檔案的數據壓縮到原來的1/2~1/4。一些常用的無損壓縮算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)壓縮算法。
有損壓縮是指使用壓縮後的數據進行重構,重構後的數據與原來的數據有所不同,但不影響人對原始資料表達的信息造成誤解。有損壓縮適用於重構信號不一定非要和原始信號完全相同的場合。例如,圖像和聲音的壓縮就可以採用有損壓縮,因為其中包含的數據往往多於我們的視覺系統和聽覺系統所能接收的信息,丟掉一些數據而不至於對聲音或者圖像所表達的意思產生誤解,但可大大提高壓縮比

相關詞條

熱門詞條

聯絡我們