一種非常簡(jiǎn)單的壓縮方法是行程長(zhǎng)度編碼，這種方法使用數(shù)據(jù)及數(shù)據(jù)長(zhǎng)度這樣簡(jiǎn)單的編碼代替同樣的連續(xù)數(shù)據(jù)，這是無(wú)損數(shù)據(jù)壓縮的一個(gè)實(shí)例。這種方法經(jīng)常用于辦公計(jì)算機(jī)以更好地利用磁盤(pán)空間、或者更好地利用計(jì)算機(jī)網(wǎng)絡(luò)中的帶寬。對(duì)于電子表格、文本、可執(zhí)行文件等這樣的符號(hào)數(shù)據(jù)來(lái)說(shuō)，無(wú)損是一個(gè)非常關(guān)鍵的要求，因?yàn)槌艘恍┯邢薜那闆r，大多數(shù)情況下即使是一個(gè)數(shù)據(jù)位的變化都是無(wú)法接受的。

對(duì)于視頻和音頻數(shù)據(jù)，只要不損失數(shù)據(jù)的重要部分一定程度的質(zhì)量下降是可以接受的。通過(guò)利用人類感知系統(tǒng)的局限，能夠大幅度得節(jié)約存儲(chǔ)空間并且得到的結(jié)果質(zhì)量與原始數(shù)據(jù)質(zhì)量相比并沒(méi)有明顯的差別。這些有損數(shù)據(jù)壓縮方法通常需要在壓縮速度、壓縮數(shù)據(jù)大小以及質(zhì)量損失這三者之間進(jìn)行折衷。

有損圖像壓縮用于數(shù)碼相機(jī)中，大幅度地提高了存儲(chǔ)能力，同時(shí)圖像質(zhì)量幾乎沒(méi)有降低。用于DVD的有損MPEG-2編解碼視頻壓縮也實(shí)現(xiàn)了類似的功能。

在有損音頻壓縮中，心理聲學(xué)的方法用來(lái)去除信號(hào)中聽(tīng)不見(jiàn)或者很難聽(tīng)見(jiàn)的成分。人類語(yǔ)音的壓縮經(jīng)常使用更加專業(yè)的技術(shù)，因此人們有時(shí)也將“語(yǔ)音壓縮”或者“語(yǔ)音編碼”作為一個(gè)獨(dú)立的研究領(lǐng)域與“音頻壓縮”區(qū)分開(kāi)來(lái)。不同的音頻和語(yǔ)音壓縮標(biāo)準(zhǔn)都屬于音頻編解碼范疇。例如語(yǔ)音壓縮用于因特網(wǎng)電話，而音頻壓縮被用于CD翻錄并且使用 MP3 播放器解碼。

壓縮，是為了減少存儲(chǔ)空間而把數(shù)據(jù)轉(zhuǎn)換成比原始格式更緊湊形式的過(guò)程。數(shù)據(jù)壓縮的概念相當(dāng)古老，可以追溯到發(fā)明了摩爾斯碼的19世紀(jì)中期。

摩爾斯碼的發(fā)明，是為了使電報(bào)員能夠通過(guò)電報(bào)系統(tǒng)，利用一系列可聽(tīng)到的脈沖信號(hào)傳遞字母信息，從而實(shí)現(xiàn)文字消息的傳輸。摩爾斯碼的發(fā)明者意識(shí)到，某些字母比其他字母使用地更頻繁（例如E比X更常見(jiàn)），因此決定使用短的脈沖信號(hào)來(lái)表示常用字母，而使用較長(zhǎng)的脈沖信號(hào)表示非常用字母。這個(gè)基本的壓縮方案有效地改善了系統(tǒng)的整體效率，因?yàn)樗闺妶?bào)員在更短的時(shí)間內(nèi)傳輸了更多的信息。

雖然現(xiàn)代的壓縮流程比摩爾斯碼要復(fù)雜地多，但是它們?nèi)匀皇褂弥嗤幕驹恚簿褪俏覀冞@篇文章中將要講述的內(nèi)容。這些概念對(duì)我們?nèi)缃竦挠?jì)算機(jī)世界高效運(yùn)行至關(guān)重要——互聯(lián)網(wǎng)上從本地與云端存儲(chǔ)到數(shù)據(jù)流的一切東西都嚴(yán)重依賴壓縮算法，離開(kāi)了它很可能會(huì)變得非常低效。

壓縮管道

下圖展示了壓縮方案的通用流程。原始的輸入數(shù)據(jù)包含我們需要壓縮或減小尺寸的符號(hào)序列。這些符號(hào)被壓縮器編碼，輸出結(jié)果是編碼過(guò)的數(shù)據(jù)。需要注意的是，雖然通常編碼后的數(shù)據(jù)要比原始輸入數(shù)據(jù)小，但是也有例外情況（我們后面會(huì)講到）。

通常在之后的某個(gè)時(shí)間，編碼后的數(shù)據(jù)會(huì)被輸入到一個(gè)解壓縮器，在這里數(shù)據(jù)被解碼、重建，并以符號(hào)序列的形式輸出原始數(shù)據(jù)。注意，本文我們會(huì)交替地使用“序列”和“串”來(lái)指一個(gè)符號(hào)序列集。

如果輸出數(shù)據(jù)和輸入數(shù)據(jù)始終完全相同，那么這個(gè)壓縮方案被稱為無(wú)損的，也稱無(wú)損編碼器。否則，它就是一個(gè)有損的壓縮方案。

無(wú)損壓縮方案通常被用來(lái)壓縮文本，可執(zhí)行程序，或者其他任何需要完全重建數(shù)據(jù)的地方。

有損壓縮方案在圖像，音頻，視頻，或者其他為了提高壓縮效率而可以接受某些程度信息丟失的場(chǎng)合很有用處。

數(shù)據(jù)模型

信息的定義是度量一個(gè)數(shù)據(jù)片段復(fù)雜度的量。一個(gè)數(shù)據(jù)集擁有越多的信息，它就越難被壓縮。稀有的概念和信息的概念是相關(guān)的，因?yàn)橄∮蟹?hào)的出現(xiàn)比常見(jiàn)符號(hào)的出現(xiàn)提供了更多的信息。

例如，“日本的一次地震”的出現(xiàn)比“月球的一次地震”提供的信息號(hào)少，因?yàn)樵虑蛏系牡卣鸷懿怀Ｒ?jiàn)。我們可以預(yù)期，大多數(shù)壓縮算法在壓縮一個(gè)符號(hào)時(shí)，能夠仔細(xì)地考慮它出現(xiàn)的頻率或幾率。

我們把壓縮算法降低信息負(fù)載的有效性，稱為它的效率。一個(gè)效率更高的壓縮算法相比效率低的壓縮算法，能夠更多地降低特定數(shù)據(jù)集的大小。

概率模型

設(shè)計(jì)一個(gè)壓縮方案的最重要一步，是為數(shù)據(jù)創(chuàng)建一個(gè)概率模型。這個(gè)模型允許我們測(cè)量數(shù)據(jù)的特征，達(dá)到有效的適應(yīng)壓縮算法的目的。為了使它更加清晰一些，讓我們?yōu)g覽一下建模過(guò)程的部分環(huán)節(jié)。

假設(shè)我們有一個(gè)字母表G，它由數(shù)據(jù)集中所有可能出現(xiàn)的字符組成。在我們的例子中，G包含4個(gè)字符：從A到D。

我們還有一個(gè)概率統(tǒng)計(jì)函數(shù)P，它定義了在輸入數(shù)據(jù)串中，G中每個(gè)字符出現(xiàn)的概率。在輸入數(shù)據(jù)串中，概率高的符號(hào)比概率低的符號(hào)更有可能出現(xiàn)。

在這個(gè)例子中，我們假定符號(hào)是獨(dú)立同分布的。在源數(shù)據(jù)串中，一個(gè)符號(hào)的出現(xiàn)與其他任何符號(hào)沒(méi)有相關(guān)性。

最小編碼率

B是最常見(jiàn)的符號(hào)，出現(xiàn)的概率是40%；而C是最不常見(jiàn)的符號(hào)，它的出現(xiàn)概率只有10%。我們的目標(biāo)是設(shè)計(jì)一個(gè)壓縮方案，它對(duì)于常見(jiàn)符號(hào)使所需存儲(chǔ)空間最小化，同時(shí)它支持使用更多的必要空間來(lái)存儲(chǔ)不常見(jiàn)符號(hào)。這個(gè)折衷是壓縮的基本原理，并且已經(jīng)存在于幾乎所有的壓縮算法中。

有了字母表，我們可以小試身手，來(lái)定義一個(gè)基本的壓縮方案。如果我們簡(jiǎn)單地把一個(gè)符號(hào)編碼為8比特的ASCII值，那么我們的壓縮效率，即編碼率，將是8比特/符號(hào)。假定我們對(duì)只包含4個(gè)符號(hào)的字母表改進(jìn)這個(gè)方案。如果我們?yōu)槊總€(gè)符號(hào)分配2個(gè)比特，我們?nèi)匀荒軌蛲耆亟ň幋a過(guò)的數(shù)據(jù)串，而只需要1/4的空間。

ASCII

在計(jì)算機(jī)中，所有的數(shù)據(jù)在存儲(chǔ)和運(yùn)算時(shí)都要使用二進(jìn)制數(shù)表示（因?yàn)橛?jì)算機(jī)用高電平和低電平分別表示1和0），例如，像a、b、c、d這樣的52個(gè)字母（包括大寫(xiě)）、以及0、1等數(shù)字還有一些常用的符號(hào)（例如*、#、@等）在計(jì)算機(jī)中存儲(chǔ)時(shí)也要使用二進(jìn)制數(shù)來(lái)表示，而具體用哪些二進(jìn)制數(shù)字表示哪個(gè)符號(hào)，當(dāng)然每個(gè)人都可以約定自己的一套（這就叫編碼），而大家如果要想互相通信而不造成混亂，那么大家就必須使用相同的編碼規(guī)則，于是美國(guó)有關(guān)的標(biāo)準(zhǔn)化組織就出臺(tái)了ASCII編碼，統(tǒng)一規(guī)定了上述常用符號(hào)用哪些二進(jìn)制數(shù)來(lái)表示。

它是現(xiàn)今最通用的單字節(jié)編碼系統(tǒng)。

這時(shí)候，我們已經(jīng)顯著地提升了編碼率（從8到2比特/符號(hào)），但是完全忽視了我們的概率模型。正如前面提到的，我們可以結(jié)合模型發(fā)明一個(gè)策略，通過(guò)對(duì)常見(jiàn)符號(hào)（B和D）使用更少的比特，對(duì)不常見(jiàn)符號(hào)（A和C）使用更多的比特，以提高編碼效率。

這提出了一個(gè)在香農(nóng)開(kāi)創(chuàng)性論文中描述的重要觀點(diǎn)——我們可以簡(jiǎn)單地基于符號(hào)（或事件）的概率，定義它的理論最小存儲(chǔ)空間。我們?nèi)缦露x一個(gè)符號(hào)的最小編碼率：

例如，如果一個(gè)符號(hào)出現(xiàn)的概率是50%，那么它絕對(duì)最少需要一個(gè)字節(jié)來(lái)存儲(chǔ)。

熵和冗余

更進(jìn)一步，如果我們?yōu)樽帜副碇械淖址?jì)算最小編碼率的加權(quán)平均值，我們得到一個(gè)被稱作香農(nóng)熵的值，簡(jiǎn)單地稱作模型的熵。熵被定義為給定模型的最小編碼率。它建立在字母表和它的概率模型之上，如下描述。

正如你預(yù)料的一樣，擁有更多罕見(jiàn)符號(hào)的模型，比擁有較少并且常見(jiàn)符號(hào)的模型的熵要高。更進(jìn)一步，熵值更高的模型比熵值低的模型更難壓縮。

在我們當(dāng)前的例子中，我們模型的熵值是1.85比特/符號(hào)。編碼率（2）和熵值（1.85）的差值被稱作壓縮方案的冗余。

在眾多諸如加密和人工智能等不同的子領(lǐng)域，熵都是一個(gè)非常有用的話題。

編碼模型

到目前為止，我們采取了一點(diǎn)點(diǎn)自由措施：自動(dòng)地給出了我們符號(hào)的概率。在現(xiàn)實(shí)中，模型通常并不是容易得到的，我們可能通過(guò)分析源數(shù)據(jù)串（如在樣例數(shù)據(jù)匯總統(tǒng)計(jì)符號(hào)概率），或者在壓縮過(guò)程中自適應(yīng)地學(xué)習(xí)，以得到這些概率值。不管是哪種情形，真實(shí)數(shù)據(jù)串的概率值不會(huì)完美地與模型匹配，而且我們會(huì)與這個(gè)差別正比例地?fù)p失壓縮效率?；谶@個(gè)原因，推導(dǎo)出（或恒定地保持）一個(gè)盡可能精確的模型是至關(guān)重要的。

常見(jiàn)算法

當(dāng)我們?yōu)閿?shù)據(jù)集定義了概率模型之后，我們就能夠適當(dāng)?shù)乩眠@個(gè)模型設(shè)計(jì)出一個(gè)壓縮方案。雖然開(kāi)發(fā)一個(gè)新壓縮算法的過(guò)程超出了本文的范圍，但是我們可以利用已經(jīng)存在的算法。下面我們回顧一些最流行的算法。

下面的每一個(gè)算法都是一個(gè)順序處理器，這就是說(shuō)如果要重建已編碼序列的第n個(gè)符號(hào)，必須先對(duì)第0.。（n-1）個(gè)符號(hào)進(jìn)行解碼。由于編碼后數(shù)據(jù)的不定長(zhǎng)特性，尋找操作是不可能的——解碼器在不解碼前面的符號(hào)的情況下，無(wú)法直接跳轉(zhuǎn)到符號(hào)n的正確偏移位置。另外，一些編碼方案依賴于順序處理每個(gè)符號(hào)時(shí)保持的內(nèi)部歷史狀態(tài)。

霍夫曼編碼

這是一個(gè)最為廣泛知曉的壓縮方案。它能夠追溯到19世紀(jì)50年代，David Huffman在他的論文“一種構(gòu)建極小多余編碼的方法”中第一次描述了這種方法?；舴蚵幋a通過(guò)得到給定字母表的最優(yōu)前綴碼工作。

一個(gè)前綴碼代表一個(gè)數(shù)值，并使字母表中的每個(gè)符號(hào)的前綴碼不會(huì)成為另一個(gè)符號(hào)前綴碼的前綴。例如，如果0是我們第一個(gè)符號(hào)A的前綴碼，那么字母表中的其他符號(hào)都不能以0開(kāi)始。由于前綴碼使比特流解碼變得清晰明確，因此很有用。

字典方法

這種類型的編碼器使用一個(gè)字典來(lái)保存最近發(fā)現(xiàn)的符號(hào)。當(dāng)遇到一個(gè)符號(hào)時(shí)，首先會(huì)在字典中查找它，檢查是否已經(jīng)存儲(chǔ)過(guò)了。如果是，那么輸出將只包含字典入口的引用（通常是一個(gè)偏移量），而不是整個(gè)符號(hào)。

使用字典方法的壓縮方案包括LZ77 and LZ78，它們是很多不同的無(wú)損壓縮方案的基礎(chǔ)。

在一些情況下，會(huì)使用一個(gè)滑動(dòng)窗口來(lái)自適應(yīng)地追蹤最近發(fā)現(xiàn)的符號(hào)。這種情況下，一個(gè)符號(hào)只在相對(duì)較近發(fā)現(xiàn)時(shí)才會(huì)保存在字典中。否則，符號(hào)被剔除（之后再出現(xiàn)可能會(huì)重新加入字典）。這個(gè)過(guò)程防止符號(hào)字典變得過(guò)大，并利用了一個(gè)事實(shí)，即序列中的符號(hào)會(huì)在相對(duì)短的窗口內(nèi)重復(fù)出現(xiàn)。

哥倫布指數(shù)編碼

假設(shè)你有一個(gè)由0到255范圍內(nèi)的整數(shù)組成的字母表，并且一個(gè)符號(hào)的出現(xiàn)概率與它到0的距離有關(guān)。這樣，比較小的值是最常見(jiàn)的，而值越大出現(xiàn)的概率越小。

和大多數(shù)壓縮方案一樣，哥倫布編碼的效率非常依賴于輸入序列中的特定符號(hào)。包含很多大值的序列與包含較少大值的序列相比，壓縮效果更差一些；在某些情況下，經(jīng)過(guò)哥倫布編碼后的序列甚至可能比原始輸入串的尺寸更大。

算數(shù)編碼

算數(shù)編碼是一個(gè)比較新的壓縮算法，在最近（過(guò)去的15年里）得到了極大的普及，特別是媒體壓縮方面。算數(shù)編碼器是一種高效率，計(jì)算密集型，具有時(shí)序性的編碼器。

一個(gè)常見(jiàn)的算數(shù)編碼變種，二進(jìn)制算數(shù)編碼，使用只包含兩個(gè)符號(hào)（0和1）的字母表。這個(gè)變種特別有用處，因?yàn)樗?jiǎn)化了編碼器的設(shè)計(jì)，降低了運(yùn)行時(shí)的計(jì)算代價(jià)，并且在編碼器和解碼器處理一個(gè)字母表和模型時(shí)，不需要任何顯式的通訊。

行程長(zhǎng)度編碼

到現(xiàn)在為止，我們已經(jīng)假設(shè)源符號(hào)是獨(dú)立同分布的。我們的概率模型和編碼率與熵的計(jì)算方法都依賴于這個(gè)事實(shí)。但是，如果我們的符號(hào)序列不滿足這個(gè)要求呢？

假設(shè)我們序列中符號(hào)的重復(fù)度很高，并且一個(gè)特定符號(hào)的出現(xiàn)有力地表明，它的重復(fù)實(shí)例即將跟隨出現(xiàn)。這種情況下，我們可以選擇使用另一個(gè)稱作行程長(zhǎng)度編碼的編碼方案。這種技術(shù)在符號(hào)重復(fù)度很高時(shí)表現(xiàn)良好，而在重復(fù)度低時(shí)表現(xiàn)較差。

行程長(zhǎng)度編碼器預(yù)測(cè)數(shù)據(jù)串中連續(xù)重復(fù)符號(hào)的長(zhǎng)度，并使用這個(gè)符號(hào)和重復(fù)次數(shù)來(lái)替代它們。