幾種壓縮算法原理介紹

《幾種壓縮算法原理介紹》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、幾種壓縮算法原理介紹1.??RLERLE又叫RunLengthEncoding，是一個(gè)針對(duì)無損壓縮的非常簡(jiǎn)單的算法。它用重復(fù)字節(jié)和重復(fù)的次數(shù)來簡(jiǎn)單描述來代替重復(fù)的字節(jié)。盡管簡(jiǎn)單并且對(duì)于通常的壓縮非常低效，但它有的時(shí)候卻非常有用（例如，JPEG就使用它）。1.1.原理圖2.1顯示了一個(gè)如何使用RLE算法來對(duì)一個(gè)數(shù)據(jù)流編碼的例子，其中出現(xiàn)六次的符號(hào)‘93’已經(jīng)用3個(gè)字節(jié)來代替：一個(gè)標(biāo)記字節(jié)（‘0’在本例中）重復(fù)的次數(shù)（‘6’）和符號(hào)本身（‘93’）。RLE解碼器遇到符號(hào)‘0’的時(shí)候，它表明后面的兩個(gè)字節(jié)決定了

2、需要輸出哪個(gè)符號(hào)以及輸出多少次。1.2.實(shí)現(xiàn)RLE可以使用很多不同的方法?；緣嚎s庫中詳細(xì)實(shí)現(xiàn)的方式是非常有效的一個(gè)。一個(gè)特殊的標(biāo)記字節(jié)用來指示重復(fù)節(jié)的開始，而不是對(duì)于重復(fù)非重復(fù)節(jié)都codingrun。因此非重復(fù)節(jié)可以有任意長度而不被控制字節(jié)打斷，除非指定的標(biāo)記字節(jié)出現(xiàn)在非重復(fù)節(jié)（頂多以兩個(gè)字節(jié)來編碼）的稀有情況下。為了最優(yōu)化效率，標(biāo)記字節(jié)應(yīng)該是輸入流中最少出現(xiàn)的符號(hào)（或許就不存在）。重復(fù)runs能夠在32768字節(jié)的時(shí)候運(yùn)轉(zhuǎn)。少于129字節(jié)的要求3個(gè)字節(jié)編碼（標(biāo)記+次數(shù)+符號(hào)），而大雨128字節(jié)要求四個(gè)

3、字節(jié)（標(biāo)記+次數(shù)的高4位

4、0x80+次數(shù)的低4位）。這是通常所有采用的壓縮的做法，并且也是相比較三個(gè)字節(jié)固定編碼（允許使用3個(gè)字節(jié)來編碼256個(gè)字節(jié)）而言非常少見的有損壓縮率的方法。在這種模式下，最壞的壓縮結(jié)果是：輸出大小=257/256*輸入大小+12.??哈夫曼哈夫曼編碼是無損壓縮當(dāng)中最好的方法。它使用預(yù)先二進(jìn)制描述來替換每個(gè)符號(hào)，長度由特殊符號(hào)出現(xiàn)的頻率決定。常見的符號(hào)需要很少的位來表示，而不常見的符號(hào)需要很多為來表示。哈夫曼算法在改變?nèi)魏畏?hào)二進(jìn)制編碼引起少量密集表現(xiàn)方面是最佳的。然而，它并不處理

5、符號(hào)的順序和重復(fù)或序號(hào)的序列。2.1.原理我不打算探究哈夫曼編碼的所有實(shí)際的細(xì)節(jié)，但基本的原理是為每個(gè)符號(hào)找到新的二進(jìn)制表示，從而通常符號(hào)使用很少的位，不常見的符號(hào)使用較多的位。簡(jiǎn)短的說，這個(gè)問題的解決方案是為了查找每個(gè)符號(hào)的通用程度，我們建立一個(gè)未壓縮數(shù)據(jù)的柱狀圖；通過遞歸拆分這個(gè)柱狀圖為兩部分來創(chuàng)建一個(gè)二叉樹，每個(gè)遞歸的一半應(yīng)該和另一半具有同樣的權(quán)（權(quán)是∑NK=1符號(hào)數(shù)k,N是分之中符號(hào)的數(shù)量，符號(hào)數(shù)k是符號(hào)k出現(xiàn)的次數(shù)）這棵樹有兩個(gè)目的：1．?編碼器使用這棵樹來找到每個(gè)符號(hào)最優(yōu)的表示方法2．?解碼器

6、使用這棵樹唯一的標(biāo)識(shí)在壓縮流中每個(gè)編碼的開始和結(jié)束，其通過在讀壓縮數(shù)據(jù)位的時(shí)候自頂向底的遍歷樹，選擇基于數(shù)據(jù)流中的每個(gè)獨(dú)立位的分支，一旦一個(gè)到達(dá)葉子節(jié)點(diǎn)，解碼器知道一個(gè)完整的編碼已經(jīng)讀出來了。我們來看一個(gè)例子會(huì)讓我們更清楚。圖2.2顯示了一個(gè)10個(gè)字節(jié)的未壓縮的數(shù)據(jù)。根據(jù)符號(hào)頻率，哈夫曼編碼器生成哈夫曼樹（圖2.4）和相應(yīng)的編碼表示（圖2.3）。?你可以看到，常見的符號(hào)接近根，因此只要少數(shù)位來表示。于是最終的壓縮數(shù)據(jù)流如圖2.5所示。壓縮后的數(shù)據(jù)流是24位（三個(gè)字節(jié)），原來是80位（10個(gè)字節(jié)）。當(dāng)然，我

7、應(yīng)該存儲(chǔ)哈夫曼樹，這樣解碼器就能夠解碼出對(duì)應(yīng)的壓縮流了，這就使得該例子中的真正數(shù)據(jù)流比輸入的流數(shù)據(jù)量大。這是相對(duì)較短的數(shù)據(jù)上的副作用。對(duì)于大數(shù)據(jù)量來說，上面的哈夫曼樹就不占太多比例了。解碼的時(shí)候，從上到下遍歷樹，為壓縮的流選擇從左/右分支，每次碰到一個(gè)葉子節(jié)點(diǎn)的時(shí)候，就可以將對(duì)應(yīng)的字節(jié)寫到解壓輸出流中，然后再從根開始遍歷。2.2.實(shí)現(xiàn)哈夫曼編碼器可以在基本壓縮庫中找到，其是非常直接的實(shí)現(xiàn)。這個(gè)實(shí)現(xiàn)的基本缺陷是：1．?慢位流實(shí)現(xiàn)2．?相當(dāng)慢的解碼（比編碼慢）3．?最大的樹深度是32（編碼器在任何超過32位大

8、小的時(shí)候退出）。如果我不是搞錯(cuò)的話，這是不可能的，除非輸出的數(shù)據(jù)大于232字節(jié)。另一方面，這個(gè)實(shí)現(xiàn)有幾個(gè)優(yōu)點(diǎn)：1．?哈夫曼樹以一個(gè)緊密的形式每個(gè)符號(hào)要求12位（對(duì)于8位的符號(hào)）的方式存儲(chǔ)，這意味著最大的頭為384。2．?編碼相當(dāng)容易理解哈夫曼編碼在數(shù)據(jù)有噪音的情況（不是有規(guī)律的，例如RLE）下非常好，這中情況下大多數(shù)基于字典方式的編碼器都有問題。3.??Rice對(duì)于由大word（例如：16或32位）組成的數(shù)據(jù)和教低的數(shù)據(jù)值，Rice編碼能夠獲得較好的壓縮比。音頻和高動(dòng)態(tài)變化的圖像都是這種類型的數(shù)據(jù)，它們被

9、某種預(yù)言預(yù)處理過（例如delta相鄰的采樣）。盡管哈夫曼編碼處理這種數(shù)據(jù)是最優(yōu)的，卻由于幾個(gè)原因而不適合處理這種數(shù)據(jù)（例如：32位大小要求16GB的柱狀圖緩沖區(qū)來進(jìn)行哈夫曼樹編碼）。因此一個(gè)比較動(dòng)態(tài)的方式更適合由大word組成的數(shù)據(jù)。3.1.原理Rice編碼背后的基本思想是盡可能的用較少的位來存儲(chǔ)多個(gè)字（正像使用哈夫曼編碼一樣）。實(shí)際上，有人可能想到Rice是靜態(tài)的哈夫曼編碼（例如，編碼不是由實(shí)際數(shù)據(jù)內(nèi)容的統(tǒng)計(jì)信息決定，而是由