數(shù)據(jù)壓縮的歷史、原理及常用算法

《數(shù)據(jù)壓縮的歷史、原理及常用算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。

1、壓縮，是為了減少存儲空間而把數(shù)據(jù)轉(zhuǎn)換成比原始格式更緊湊形式的過程。數(shù)據(jù)壓縮的概念相當古老，可以追溯到發(fā)明了摩爾斯碼的19世紀中期。摩爾斯碼的發(fā)明，是為了使電報員能夠通過電報系統(tǒng)，利用一系列可聽到的脈沖信號傳遞字母信息，從而實現(xiàn)文字消息的傳輸。摩爾斯碼的發(fā)明者意識到，某些字母比其他字母使用地更頻繁（例如E比X更常見），因此決定使用短的脈沖信號來表示常用字母，而使用較長的脈沖信號表示非常用字母。這個基本的壓縮方案有效地改善了系統(tǒng)的整體效率，因為它使電報員在更短的時間內(nèi)傳輸了更多的信息。雖然現(xiàn)代的壓縮流程比摩爾斯碼要復雜地多，但是它們?nèi)匀?/p>

2、使用著相同的基本原理，也就是我們這篇文章中將要講述的內(nèi)容。這些概念對我們?nèi)缃竦挠嬎銠C世界高效運行至關重要——互聯(lián)網(wǎng)上從本地與云端存儲到數(shù)據(jù)流的一切東西都嚴重依賴壓縮算法，離開了它很可能會變得非常低效。壓縮管道下圖展示了壓縮方案的通用流程。原始的輸入數(shù)據(jù)包含我們需要壓縮或減小尺寸的符號序列。這些符號被壓縮器編碼，輸出結(jié)果是編碼過的數(shù)據(jù)。需要注意的是，雖然通常編碼后的數(shù)據(jù)要比原始輸入數(shù)據(jù)小，但是也有例外情況（我們后面會講到）。通常在之后的某個時間，編碼后的數(shù)據(jù)會被輸入到一個解壓縮器，在這里數(shù)據(jù)被解碼、重建，并以符號序列的形式輸出原始數(shù)據(jù)

3、。注意，本文我們會交替地使用“序列”和“串”來指一個符號序列集。如果輸出數(shù)據(jù)和輸入數(shù)據(jù)始終完全相同，那么這個壓縮方案被稱為無損的，也稱無損編碼器。否則，它就是一個有損的壓縮方案。無損壓縮方案通常被用來壓縮文本，可執(zhí)行程序，或者其他任何需要完全重建數(shù)據(jù)的地方。有損壓縮方案在圖像，音頻，視頻，或者其他為了提高壓縮效率而可以接受某些程度信息丟失的場合很有用處。數(shù)據(jù)模型信息的定義是度量一個數(shù)據(jù)片段復雜度的量。一個數(shù)據(jù)集擁有越多的信息，它就越難被壓縮。稀有的概念和信息的概念是相關的，因為稀有符號的出現(xiàn)比常見符號的出現(xiàn)提供了更多的信息。例如，“

4、日本的一次地震”的出現(xiàn)比“月球的一次地震”提供的信息號少，因為月球上的地震很不常見。我們可以預期，大多數(shù)壓縮算法在壓縮一個符號時，能夠仔細地考慮它出現(xiàn)的頻率或幾率。我們把壓縮算法降低信息負載的有效性，稱為它的效率。一個效率更高的壓縮算法相比效率低的壓縮算法，能夠更多地降低特定數(shù)據(jù)集的大小。概率模型設計一個壓縮方案的最重要一步，是為數(shù)據(jù)創(chuàng)建一個概率模型。這個模型允許我們測量數(shù)據(jù)的特征，達到有效的適應壓縮算法的目的。為了使它更加清晰一些，讓我們?yōu)g覽一下建模過程的部分環(huán)節(jié)。假設我們有一個字母表G，它由數(shù)據(jù)集中所有可能出現(xiàn)的字符組成。在我們

5、的例子中，G包含4個字符：從A到D。我們還有一個概率統(tǒng)計函數(shù)P，它定義了在輸入數(shù)據(jù)串中，G中每個字符出現(xiàn)的概率。在輸入數(shù)據(jù)串中，概率高的符號比概率低的符號更有可能出現(xiàn)。在這個例子中，我們假定符號是獨立同分布的。在源數(shù)據(jù)串中，一個符號的出現(xiàn)與其他任何符號沒有相關性。最小編碼率B是最常見的符號，出現(xiàn)的概率是40%；而C是最不常見的符號，它的出現(xiàn)概率只有10%。我們的目標是設計一個壓縮方案，它對于常見符號使所需存儲空間最小化，同時它支持使用更多的必要空間來存儲不常見符號。這個折衷是壓縮的基本原理，并且已經(jīng)存在于幾乎所有的壓縮算法中。有了字

6、母表，我們可以小試身手，來定義一個基本的壓縮方案。如果我們簡單地把一個符號編碼為8比特的ASCII值，那么我們的壓縮效率，即編碼率，將是8比特/符號。假定我們對只包含4個符號的字母表改進這個方案。如果我們?yōu)槊總€符號分配2個比特，我們?nèi)匀荒軌蛲耆亟ň幋a過的數(shù)據(jù)串，而只需要1/4的空間。這時候，我們已經(jīng)顯著地提升了編碼率（從8到2比特/符號），但是完全忽視了我們的概率模型。正如前面提到的，我們可以結(jié)合模型發(fā)明一個策略，通過對常見符號（B和D）使用更少的比特，對不常見符號（A和C）使用更多的比特，以提高編碼效率。這提出了一個在香農(nóng)開創(chuàng)性

7、論文中描述的重要觀點——我們可以簡單地基于符號（或事件）的概率，定義它的理論最小存儲空間。我們?nèi)缦露x一個符號的最小編碼率：例如，如果一個符號出現(xiàn)的概率是50%，那么它絕對最少需要一個字節(jié)來存儲。熵和冗余更進一步，如果我們?yōu)樽帜副碇械淖址嬎阕钚【幋a率的加權(quán)平均值，我們得到一個被稱作香農(nóng)熵的值，簡單地稱作模型的熵。熵被定義為給定模型的最小編碼率。它建立在字母表和它的概率模型之上，如下描述。正如你預料的一樣，擁有更多罕見符號的模型，比擁有較少并且常見符號的模型的熵要高。更進一步，熵值更高的模型比熵值低的模型更難壓縮。在我們當前的例子中

8、，我們模型的熵值是1.85比特/符號。編碼率（2）和熵值（1.85）的差值被稱作壓縮方案的冗余。在眾多諸如加密和人工智能等不同的子領域，熵都是一個非常有用的話題。完整地討論熵不在本文的范圍內(nèi)，但是有興趣的讀者可以在這里獲得更多的信息。