數(shù)據(jù)壓縮算法計算步驟及過程

一種非常簡單的壓縮方法是行程長度編碼，這種方法使用數(shù)據(jù)及數(shù)據(jù)長度這樣簡單的編碼代替同樣的連續(xù)數(shù)據(jù)，這是無損數(shù)據(jù)壓縮的一個實例。這種方法經(jīng)常用于辦公計算機以更好地利用磁盤空間、或者更好地利用計算機網(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ì)量損失這三者之間進行折衷。

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

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

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

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

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

壓縮管道

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

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

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

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

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

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

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

例如，“日本的一次地震”的出現(xiàn)比“月球的一次地震”提供的信息號少，因為月球上的地震很不常見。我們可以預(yù)期，大多數(shù)壓縮算法在壓縮一個符號時，能夠仔細地考慮它出現(xiàn)的頻率或幾率。

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

概率模型

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

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

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

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

最小編碼率

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

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

ASCII

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

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

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

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

例如，如果一個符號出現(xiàn)的概率是50%，那么它絕對最少需要一個字節(jié)來存儲。

熵和冗余

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

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

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

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

編碼模型

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

常見算法

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

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

霍夫曼編碼

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

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

字典方法

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

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

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

哥倫布指數(shù)編碼

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

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

算數(shù)編碼

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

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

行程長度編碼

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

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

行程長度編碼器預(yù)測數(shù)據(jù)串中連續(xù)重復(fù)符號的長度，并使用這個符號和重復(fù)次數(shù)來替代它們。