數據壓縮

數據壓縮 （简体）

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

概要

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

資料壓縮能夠實現是因為多數現實世界的資料都有統計冗余。例如，字母「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 是一個逆算術編碼器。

參見

資料壓縮專題

• 演算法複雜性理論
• 資訊熵
• 自解壓）
• 圖像壓縮
• 語音壓縮
• 視頻壓縮
• 多媒體壓縮
• 最小描述長度
• 最小消息長度 (two-part lossless compression designed for inference)

壓縮演算法

非破壞性資料壓縮

• 行程長度編碼
• 字典編碼
  • LZ77與LZ78
  • LZW
• 局部匹配預測（也稱為 PPM）
• 熵編碼
  • 哈夫曼編碼 (簡單的熵編碼，通常用於壓縮的最後一步)
  • 自適應哈夫曼編碼
  • 算術編碼
    • range encoding (與算術編碼一樣，但是用一種少許不同的方法工作)
  • T-code, 哈夫曼編碼的變體
  • Golomb coding (用於幾何分佈的無限輸入資料的簡單熵編碼)

破壞性資料壓縮

• 離散餘弦變換
• 分形壓縮（en:fractal compression）
  • 分形變換（en:fractal transform）
• 小波壓縮
• 向量量化（en:vector quantization）
• 線性預測編碼

實現實例

• DEFLATE ( LZ77 與哈夫曼編碼的組合) – ZIP、gzip、zlib 與 PNG 檔案在使用
• LZMA，7-Zip 與 StuffitX 使用
• LZO (非常快速的 LZ 變體，針對速度要求)
• Unix compress 工具 ( .Z 檔案格式)、以及 GIF 使用 LZW
• bzip2 ( Burrows-Wheeler 變換與哈夫曼編碼的組合)
• PAQ (一種基於 context mixing 的超高壓縮率的演算法，但是極度緩慢，是最高壓縮比競爭中的佼佼者。)

• JPEG (使用離散餘弦變換、量化、哈夫曼編碼的圖像壓縮）
• MPEG (廣泛使用的音頻及視頻壓縮標準族，視頻壓縮使用離散餘弦變換以及運動補償預測)
• MP3 (MPEG-1 標準中用於聲音及音樂壓縮的部分，使用子帶、MDCT、感知模型、量化以及哈夫曼編碼)
• WMA (WMV音頻編碼規範中的一部分，使用 MDCT、感知模型、低位元率量化、量化以及哈夫曼編碼)
• Vorbis (類似於 AAC 的基於 DCT 的音頻編解碼，為了避免專利問題而設計)
• JPEG 2000 (使用小波、量化、熵編碼的圖像壓縮)
• TTA (使用線性預測編碼，用於非破壞性音頻壓縮)
• FLAC (用於非破壞性音頻壓縮的線性預測編碼)

外部連結

• Data Compression Benchmarks and Tests
• Data Compression - Systematisation by T.Strutz
• Public domain article on data compression
• How Compression Works
• Ultimate Command Line Compressors
• Compression Resources catalog (currently the biggest)
• The Data Compression News Blog
• Practical Compressor Test (Compares speed and efficiency for commonly used compression programs)
• The Monthly Data Compression Newsletter
• Compressed File Types and File Extensions

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History