資料壓縮

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

可利用資料的一致性（可用信息熵，entropy來表示），規則性，與可預測性去實現資料壓縮。人類最先發展的壓縮技術實為自然語言，一般來說，若可以用比較精簡的自然語言來描述一樣事物，那麼也就越能夠對這樣事物做壓縮。資料越一致，亦代表其統計特性越集中。以影像壓縮為例，其集中代表有傅立葉變換的時域及頻域，直方圖，特徵值。

概要

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

非破壞性資料壓縮的壓縮率不足以處理龐大體積的音視頻數據，但如果允許一定程度的保真度損失，那麼還可以實現進一步的壓縮。例如，人們看圖畫或者電視畫面的時候可能並不會注意到一些細節並不完善。同樣，兩個音頻錄音採樣序列可能聽起來一樣，但實際上並不完全一樣。破壞性資料壓縮在可以接受或無法察覺的情況下使用較少的位數表示圖像、視頻或者音頻。

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

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

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

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

應用

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

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

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

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

理論

壓縮的理論（它與算法信息論密切相關）以及率失真理論，這個領域的研究工作主要是由美國學者克勞德·香農（Claude Elwood 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）
• 熵編碼
  • 哈夫曼編碼：簡單的熵編碼，通常用於壓縮的最後一步
  • 自適應哈夫曼編碼
  • 算術編碼
    • 區間編碼：與算術編碼一樣，但是用一種少許不同的方法工作
  • T-code：哈夫曼編碼的變體
  • 格倫布編碼：用於幾何分布的無限輸入數據的簡單熵編碼
• Slepian-Wolf編碼：無損的分布式信源編碼

有損數據壓縮

• 離散餘弦變換
• 分形壓縮（fractal compression）
  • 分形變換（fractal transform）
• 小波壓縮
• 向量量化（vector quantization）
• 線性預測編碼
• Wyner-Ziv編碼（有損的分布式信源編碼）

實現實例

• DEFLATE（LZ77與哈夫曼編碼的組合）——爲ZIP、gzip、zlib與PN文件所使用
• LZMA：7-Zip與StuffiX使用
• LZO（非常快速的LZ變體，針對速度要求）
• Unix compress工具（.Z文件格式）、以及GIF使用LZW
• bzip2（Burrows-Wheeler變換與哈夫曼編碼的組合）
• PAQ（一種基於上下文混合的超高壓縮率的算法，但是極度緩慢，是最高壓縮比競爭中的佼佼者。）

• JPEG（使用離散餘弦變換、量化、哈夫曼編碼的圖像壓縮）
• MPEG（廣泛使用的音頻及視頻壓縮標準族，視頻壓縮使用離散餘弦變換以及運動補償預測）
• MP3（MPEG-1標準中用於聲音及音樂壓縮的部分，使用子帶、MDCT、感知模型、量化以及哈夫曼編碼）
• WMA（WMV音頻編碼規範中的一部分，使用MDCT、感知模型、低位元率量化、量化以及哈夫曼編碼）
• Vorbis（類似於AAC的基於DCT的音頻編解碼，為了避免專利問題而設計）
• JPEG 2000（使用小波、量化、熵編碼的圖像壓縮）
• TTA（使用線性預測編碼，用於無損音頻壓縮）
• FLAC（用於無損音頻壓縮的線性預測編碼）
• ATRAC（Adaptive Transform Acoustic Coding，自適應聽覺轉換編碼）為SONY公司於1992年所開發之音訊有損數據壓縮技術，也是相關技術名詞之總稱。

外部連結

• Data Compression - Systematisation by T.Strutz （頁面存檔備份，存於網際網路檔案館）
• How Compression Works （頁面存檔備份，存於網際網路檔案館）
• Practical Compressor Test （頁面存檔備份，存於網際網路檔案館）（Compares speed and efficiency for commonly used compression programs）