數(shù)據(jù)壓縮

目錄
·概要
·應(yīng)用
·理論
·參見
·外部鏈接





   




在計算機(jī)科學(xué)和信息論中，數(shù)據(jù)壓縮或者源編碼是按照特定的編碼機(jī)制用比未經(jīng)編碼少的數(shù)據(jù)位元（或者其它信息相關(guān)的單位）表示信息的過程。例如，如果我們將“compression”編碼為“comp”那么這篇文章可以用較少的數(shù)據(jù)位表示。一種流行的壓縮實(shí)例是許多計算機(jī)都在使用的ZIP 文件格式，它不僅僅提供了壓縮的功能，而且還作為歸檔工具（Archiver）使用，能夠?qū)⒃S多文件存儲到同一個文件中。




概要

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


應(yīng)用

一種非常簡單的壓縮方法是行程長度編碼，這種方法使用數(shù)據(jù)及數(shù)據(jù)長度這樣簡單的編碼代替同樣的連續(xù)數(shù)據(jù)，這是無損數(shù)據(jù)壓縮的一個實(shí)例。這種方法經(jīng)常用于辦公計算機(jī)以更好地利用磁盤空間、或者更好地利用計算機(jī)網(wǎng)絡(luò)中的帶寬。對于電子表格、文本、可執(zhí)行文件等這樣的符號數(shù)據(jù)來說，無損是一個非常關(guān)鍵的要求，因為除了一些有限的情況，大多數(shù)情況下即使是一個數(shù)據(jù)位的變化都是無法接受的。
對于視頻和音頻數(shù)據(jù)，只要不損失數(shù)據(jù)的重要部分一定程度的質(zhì)量下降是可以接受的。通過利用人類感知系統(tǒng)的局限，能夠大幅度得節(jié)約存儲空間并且得到的結(jié)果質(zhì)量與原始數(shù)據(jù)質(zhì)量相比并沒有明顯的差別。這些有損數(shù)據(jù)壓縮方法通常需要在壓縮速度、壓縮數(shù)據(jù)大小以及質(zhì)量損失這三者之間進(jìn)行折衷。
有損圖像壓縮用于數(shù)碼相機(jī)中，大幅度地提高了存儲能力，同時圖像質(zhì)量幾乎沒有降低。用于DVD的有損MPEG-2編解碼視頻壓縮也實(shí)現(xiàn)了類似的功能。
在有損音頻壓縮中，心理聲學(xué)的方法用來去除信號中聽不見或者很難聽見的成分。人類語音的壓縮經(jīng)常使用更加專業(yè)的技術(shù)，因此人們有時也將“語音壓縮”或者“語音編碼”作為一個獨(dú)立的研究領(lǐng)域與“音頻壓縮”區(qū)分開來。不同的音頻和語音壓縮標(biāo)準(zhǔn)都屬于音頻編解碼范疇。例如語音壓縮用于因特網(wǎng)電話，而音頻壓縮被用于CD翻錄并且使用 MP3 播放器解碼。


理論

壓縮的理論基礎(chǔ)是信息論（它與算法信息論密切相關(guān)）以及率失真理論，這個領(lǐng)域的研究工作主要是由 Claude Shannon 奠定的，他在二十世紀(jì)四十年代末期及五十年代早期發(fā)表了這方面的基礎(chǔ)性的論文。Doyle 和 Carlson 在2000年寫道數(shù)據(jù)壓縮“有所有的工程領(lǐng)域最簡單、最優(yōu)美的設(shè)計理論之一”。密碼學(xué)與編碼理論也是密切相關(guān)的學(xué)科，數(shù)據(jù)壓縮的思想與統(tǒng)計推斷也有很深的淵源。
許多無損數(shù)據(jù)壓縮系統(tǒng)都可以看作是四步模型，有損數(shù)據(jù)壓縮系統(tǒng)通常包含更多的步驟，例如它包括預(yù)測、頻率變換以及量化。
Lempel-Ziv（LZ）壓縮方法是最流行的無損存儲算法之一。DEFLATE是 LZ 的一個變體，它針對解壓速度與壓縮率進(jìn)行了優(yōu)化，雖然它的壓縮速度可能非常緩慢，PKZIP、gzip 以及 PNG 都在使用 DEFLATE。LZW （Lempel-Ziv-Welch）是 Unisys 的專利，直到2003年6月專利到期限，這種方法用于 GIF 圖像。另外值得一提的是 LZR (LZ-Renau) 方法，它是 Zip 方法的基礎(chǔ)。LZ 方法使用基于表格的壓縮模型，其中表格中的條目用重復(fù)的數(shù)據(jù)串替換。對于大多數(shù)的 LZ 方法來說，這個表格是從最初的輸入數(shù)據(jù)動態(tài)生成的。這個表格經(jīng)常采用霍夫曼編碼維護(hù)（例如，SHRI、LZX）。 目前一個性能良好基于 LZ 的編碼機(jī)制是 LZX，它用于微軟公司的 CAB 格式。
最好的壓縮工具將概率模型預(yù)測結(jié)果用于算術(shù)編碼。算術(shù)編碼由 Jorma Rissanen 發(fā)明，并且由 Witten、Neal 以及 Cleary 將它轉(zhuǎn)變成一個實(shí)用的方法。這種方法能夠?qū)崿F(xiàn)比眾人皆知的哈夫曼算法更好的壓縮，并且它本身非常適合于自適應(yīng)數(shù)據(jù)壓縮，自適應(yīng)數(shù)據(jù)壓縮的預(yù)測與上下文密切相關(guān)。算術(shù)編碼已經(jīng)用于二值圖像壓縮標(biāo)準(zhǔn) JBIG、文檔壓縮標(biāo)準(zhǔn) DejaVu。文本 輸入 系統(tǒng) Dasher 是一個逆算術(shù)編碼器。


參見


數(shù)據(jù)壓縮專題

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


壓縮算法

無損數(shù)據(jù)壓縮

行程長度編碼
字典編碼

LZ77與LZ78
LZW


局部匹配預(yù)測（也稱為 PPM）
熵編碼

哈夫曼編碼 (簡單的熵編碼，通常用于壓縮的最后一步)
自適應(yīng)哈夫曼編碼
算術(shù)編碼

range encoding (與算術(shù)編碼一樣，但是用一種少許不同的方法工作)


T-code, 哈夫曼編碼的變體
Golomb coding (用于幾何分布的無限輸入數(shù)據(jù)的簡單熵編碼)




有損數(shù)據(jù)壓縮

離散余弦變換
分形壓縮（en:fractal compression）

分形變換（en:fractal transform）


小波壓縮
向量量化（en:vector quantization）
線性預(yù)測編碼


實(shí)現(xiàn)實(shí)例

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 (廣泛使用的音頻及視頻壓縮標(biāo)準(zhǔn)族，視頻壓縮使用離散余弦變換以及運(yùn)動補(bǔ)償預(yù)測)

MP3 (MPEG-1 標(biāo)準(zhǔn)中用于聲音及音樂壓縮的部分，使用子帶、MDCT、感知模型、量化以及哈夫曼編碼)
AAC (MPEG-2 及 MPEG-4 音頻編碼規(guī)范中的一部分，使用 MDCT、感知模型、量化以及哈夫曼編碼)


Vorbis (類似于 AAC 的基于 DCT 的音頻編解碼，為了避免專利問題而設(shè)計)
JPEG 2000 (使用小波、量化、熵編碼的圖像壓縮)
TTA (使用線性預(yù)測編碼，用于無損音頻壓縮)
FLAC (用于無損音頻壓縮的線性預(yù)測編碼)



外部鏈接


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


</td>
</tr>
<tr>
<th style="white-space:nowrap;background:#ddddff;text-align:right;">音頻壓縮</th>
<td colspan="1" style="text-align:left;width:100%;font-size:95%;background:#f7f7f7;">

</td>
</tr>
<tr>
<th style="white-space:nowrap;background:#ddddff;text-align:right;">圖像壓縮</th>
<td colspan="1" style="text-align:left;width:100%;font-size:95%;">

</td>
</tr>
<tr>
<th style="white-space:nowrap;background:#ddddff;text-align:right;">視頻壓縮</th>
<td colspan="1" style="text-align:left;width:100%;font-size:95%;background:#f7f7f7;">

</td>
</tr>
</table>

• 通信詞典解釋