資料壓縮

在電腦科學和資訊論中，資料壓縮或者原始碼是按照特定的編碼機制用比未經編碼少的數據位元（或者其它資訊相關的單位）表示資訊的過程。例如，若將「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）