求真百科歡迎當事人提供第一手真實資料,洗刷冤屈,終結網路霸凌。

资料压缩檢視原始碼討論檢視歷史

事實揭露 揭密真相
前往: 導覽搜尋

計算機科學信息論中,數據壓縮或者源編碼是按照特定的編碼機制用比未經編碼少的數據位元(或者其它信息相關的單位)表示信息的過程。例如,如果我們將「compression」編碼為「comp」那麼這篇文章可以用較少的數據位表示。常見的例子是ZIP文件格式,此格式不僅僅提供壓縮功能,還可作為歸檔工具(Archiver),能夠將許多文件存儲到同一個文件中。

概要

對於任何形式的通信來說,只有當信息發送方和接受方都能夠理解編碼機制的時候壓縮數據通信才能夠工作。例如,只有當接受方知道這篇文章需要用漢語字符解釋的時候這篇文章才有意義。同樣,只有當接受方知道編碼方法的時候他才能夠理解壓縮數據。

數據壓縮能夠實現是因為多數現實世界的數據都有統計冗餘。例如,字母「e」在英語中比字母「z」更加常用,字母「q」後面是「z」的可能性非常小。非破壞性資料壓縮通常利用了統計冗餘,這樣就能更加簡練地、但仍然是完整地表示發送方的數據。

如果允許一定程度的保真度損失,那麼還可以實現進一步的壓縮。例如,人們看圖畫或者電視畫面的時候可能並不會注意到一些細節並不完善。同樣,兩個音頻錄音採樣序列可能聽起來一樣,但實際上並不完全一樣。破壞性資料壓縮在帶來微小差別的情況下使用較少的位數表示圖像、視頻或者音頻。

然而,經常有一些文件不能被破壞性資料壓縮壓縮,實際上對於不含可以辨別樣式的數據任何壓縮算法都不能壓縮。另外,試圖壓縮已經經過壓縮的數據通常得到的結果實際上是增加數據。

實際上,破壞性資料壓縮也會最終達到不能工作的地步。例如一個極端的例子:壓縮算法每次去掉文件最後一個字節,那麼經過這個算法不斷的壓縮直至文件變空,壓縮算法將不能繼續工作。

由於可以幫助減少如硬盤空間與連接帶寬這樣的昂貴資源的消耗,所以壓縮非常重要,然而壓縮需要消耗信息處理資源,這也可能是費用昂貴的。所以數據壓縮機制的設計需要在壓縮能力、失真度、所需計算資源以及其它需要考慮的不同因素之間進行折衷。

應用

一種非常簡單的壓縮方法是行程長度編碼,這種方法使用數據及數據長度這樣簡單的編碼代替同樣的連續數據,這是無損數據壓縮的一個實例。這種方法經常用於辦公計算機以更好地利用磁盤空間、或者更好地利用計算機網絡中的帶寬。對於電子表格、文本、可執行文件等這樣的符號數據來說,無損是一個非常關鍵的要求,因為除了一些有限的情況,大多數情況下即使是一個數據位的變化都是無法接受的。

對於視頻和音頻數據,只要不損失數據的重要部分一定程度的質量下降是可以接受的。通過利用人類感知系統的局限,能夠大幅度的節約存儲空間並且得到的結果質量與原始數據質量相比並沒有明顯的差別。這些有損數據壓縮方法通常需要在壓縮速度、壓縮數據大小以及質量損失這三者之間進行折衷。

有損圖像壓縮用於數碼相機中,大幅度地提高了存儲能力,同時圖像質量幾乎沒有降低。用於DVD的有損MPEG-2編解碼視頻壓縮也實現了類似的功能。

在有損音頻壓縮中,心理聲學的方法用來去除信號中聽不見或者很難聽見的成分。人類語音的壓縮經常使用更加專業的技術,因此人們有時也將「語音壓縮」或者「語音編碼」作為一個獨立的研究領域與「音頻壓縮」區分開來。不同的音頻和語音壓縮標淮都屬於音頻編解碼範疇。例如語音壓縮用於因特網電話,而音頻壓縮被用於CD翻錄並且使用MP3播放器解碼。

理論

壓縮的理論(它與算法信息論密切相關)以及率失真理論,這個領域的研究工作主要是由美國學者克勞德·香農(Claude Elwood Shannon)奠定的,他在二十世紀四十年代末期及五十年代早期發表了這方面的基礎性的論文。Doyle和Carlson在2000年寫到數據壓縮「是所有的工程領域最簡單、最優美的設計理論之一」。密碼學編碼理論也是密切相關的學科,數據壓縮的思想與統計推斷也有很深的淵源。

許多無損數據壓縮系統都可以看作是四步模型,有損數據壓縮系統通常包含更多的步驟,例如它包括預測、頻率變換以及量化。

Lempel-Ziv(LZ)壓縮方法是最流行的無損存儲算法之一。DEFLATE是LZ的一個變體,它針對解壓速度與壓縮率進行了優化,雖然它的壓縮速度可能非常緩慢,PKZIPgzip以及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是一個逆算術編碼器。

參見

數據壓縮專題

壓縮算法

無損數據壓縮

有損數據壓縮

實現實例

  • DEFLATE(LZ77與哈夫曼編碼的組合)——爲ZIP、gzip、zlib與PN文件所使用
  • LZMA7-ZipStuffiXStuffitX使用
  • LZO(非常快速的LZ變體,針對速度要求)
  • Unix compress工具(.Z文件格式)、以及GIF使用LZW
  • bzip2(Burrows-Wheeler變換與哈夫曼編碼的組合)
  • PAQPAQ(一種基於上下文混合context mixing的超高壓縮率的算法,但是極度緩慢,是最高壓縮比競爭中的佼佼者。)
  • JPEG(使用離散餘弦變換、量化、哈夫曼編碼的圖像壓縮
  • MPEG(廣泛使用的音頻及視頻壓縮標淮族,視頻壓縮使用離散餘弦變換以及運動補償預測)
  • MP3MPEG-1標淮中用於聲音及音樂壓縮的部分,使用子帶、MDCT、感知模型、量化以及哈夫曼編碼)
  • WMAWMV音頻編碼規範中的一部分,使用MDCT、感知模型、低位元率量化、量化以及哈夫曼編碼)
  • Vorbis(類似於AAC的基於DCT的音頻編解碼,為了避免專利問題而設計)
  • JPEG 2000(使用小波、量化、熵編碼的圖像壓縮)
  • TTA(使用線性預測編碼,用於無損音頻壓縮)
  • FLAC(用於無損音頻壓縮的線性預測編碼

外部鏈接