多媒體數(shù)據(jù)處理中幾種無損壓縮算法的比較概要

1、119摘要:為了使大容量的多媒體數(shù)據(jù)在網(wǎng)絡(luò)上有效的傳輸，必須對(duì)多媒體數(shù)據(jù)進(jìn)行壓 縮。對(duì)多媒體數(shù)據(jù)壓縮中的幾種無損壓縮方 法進(jìn)行了比較，并對(duì)每種方法用一個(gè)例子說 明。關(guān)鍵詞:數(shù)據(jù)壓縮;霍夫曼樹；LZW;二叉樹引言隨著網(wǎng)絡(luò)發(fā)展的速度越來越快,視頻，音頻的廣泛應(yīng)用使得大數(shù)據(jù)量的傳輸顯得尤 為重要，如何更快、更多、更好地傳輸與存 儲(chǔ)數(shù)據(jù)成為數(shù)據(jù)信息處理的首要問題。在壓縮算法中分為無損壓縮和有損壓 縮。相對(duì)于有損壓縮來說，無損壓縮的占用 空間大，壓縮比不高，但是它100%的保存了 原始信息，沒有任何信號(hào)丟失并且音質(zhì)高,不受信號(hào)源的影響,這點(diǎn)是有損壓縮不可比擬的。而且隨著時(shí)間的推移,限制無損格式 的種種因

2、素將逐漸被消除,比如說硬盤容量 的急劇增長(zhǎng)以及低廉的價(jià)格使得無損壓縮格 式的前景無比光明。1、無損壓縮的原理以及幾種常見算法 本質(zhì)上壓縮數(shù)據(jù)是因?yàn)閿?shù)據(jù)自身具有冗 余性。數(shù)據(jù)壓縮是利用各種算法將數(shù)據(jù)冗余 壓縮到最小,并盡可能地減少失真,從而提 高傳輸效率和節(jié)約存儲(chǔ)空間。常見的無損壓縮算法有,游長(zhǎng)編碼;香濃-凡諾算法;霍夫曼算法;LZW算法;下面詳細(xì)介紹這些算法或編碼步驟,并比較其優(yōu)缺點(diǎn)。2、游長(zhǎng)編碼也叫行程編碼,它是數(shù)據(jù)壓縮中最簡(jiǎn)單 的一種方法。它的思想是:將圖像一行中顏 色值相同的相鄰象素用一個(gè)計(jì)數(shù)值和該顏色值來代替。例如:aabbbccccdddddeeeeee 對(duì)其進(jìn)行游長(zhǎng)編碼可得2a3b

3、4c5d6e，可見其效率很高。但它有兩個(gè)致命缺點(diǎn)。一:如果圖象中每?jī)蓚€(gè)相鄰點(diǎn)的顏色都不同，用這種算法不但不能壓縮，反而數(shù)據(jù)量會(huì)增加，例如對(duì) abcdeabcde 進(jìn)行編碼得Ia2b3c4d5ela2b3c4d5e，可見數(shù)據(jù)量反而增加了1倍。二:容錯(cuò)性差。還是以 aabbbccccdddddeeeeee為例,如果在第二位a出錯(cuò)，例如丟失了 a,那么編碼后結(jié)果為1a3b4c5d6e，雖然只有一位發(fā)生了錯(cuò)誤，但是在恢復(fù)數(shù)據(jù)時(shí)，將和原始數(shù)據(jù)完全不同。所以說游長(zhǎng)編碼在要壓縮信息源中的符號(hào)形成連續(xù)出現(xiàn)片段時(shí)才有效，并且它不是一種自適應(yīng)的編碼方式。 3、香濃- 凡諾算法香濃-凡諾算法由貝爾實(shí)驗(yàn)室的Shann

4、on和MIT的Robert Fano開發(fā)的。 它的編碼步驟如下:一:根據(jù)符號(hào)出現(xiàn)的頻率對(duì)符號(hào)進(jìn)行排序 二:遞歸的把符號(hào)分成 兩部分，每一部 分中的符號(hào)具有相似的頻率，直到所有的部 分只有一個(gè)符號(hào)為止。 這樣，就得到一顆二叉樹，我們把樹中 的左支賦為 0，把樹中的右支賦為 1。 那么從根 節(jié)點(diǎn)到節(jié)點(diǎn)的路徑即為它的編碼。例如:對(duì)字符串a(chǎn)bcccd編碼。進(jìn)行排序后為 cabd。遞歸過程圖1-圖3。應(yīng)當(dāng)指出香濃-凡諾算法的編碼結(jié)果并不是唯一的，例如 在圖1的時(shí)候可以交換左右子樹的位置，在圖3的時(shí)候也可以交換b,d的位置。香 濃-凡諾算法是一種自頂向下的，非自適應(yīng)的編碼算法。4、霍夫曼編碼霍夫曼編碼 主

5、要是一個(gè)構(gòu)造霍夫曼樹的過程，算法見參考文獻(xiàn)，它是一種自下向上的,非自適 應(yīng)的編碼算法，其編碼過程主要有讀取字符串，統(tǒng)計(jì)各字符出現(xiàn)次數(shù)并排序,構(gòu)造霍 夫曼樹以及賦值這3個(gè)步驟。例如對(duì)字符串a(chǎn)abccbb進(jìn)行編碼，先進(jìn)行統(tǒng)計(jì)字符出 現(xiàn)次數(shù)并排序得,a2，c2，b3構(gòu)造霍夫曼樹過程見圖5和圖6,賦值見圖7。通過霍夫 曼樹的構(gòu)造可見,編碼的結(jié)果多媒體數(shù)據(jù)處理中幾種無損壓縮算法的比較文畢永成（蘇州科技學(xué)院網(wǎng)絡(luò)與教育技術(shù)中心江蘇蘇州也不是唯一的。另外因?yàn)榉?hào)的出現(xiàn)頻率不能預(yù)知,需要統(tǒng)計(jì)和編碼兩次處理, 所以速度較慢，無法實(shí)用。繼而推出了自適應(yīng)霍夫曼編碼算法。5、自適應(yīng)霍夫曼 編碼在自適應(yīng)霍夫曼編碼算法中,

6、統(tǒng)計(jì)字符是隨著數(shù)據(jù)流的到達(dá)而動(dòng)態(tài)收集和更新 的，字符出現(xiàn)的次數(shù)是基于到目前為止實(shí)際收到的字符數(shù)。在這種方式下，隨著數(shù)據(jù) 流的不斷變化，符號(hào)的編碼也會(huì)不停的改變,直到完全接收完為止，我們把這種方式 叫做自適應(yīng)。其編碼過程主要經(jīng)過初始化，讀取字符和構(gòu)造自適應(yīng)霍夫曼樹三個(gè)部 分。初始化主要是分配一些開始時(shí)候的編解碼雙方達(dá)成的共同的碼字,比如所 ACSII碼。在構(gòu)造自適應(yīng)霍夫曼樹的時(shí)候,最采用的是自頂向下的方式。構(gòu)造自適 應(yīng)霍夫曼樹主要是將字符出現(xiàn)的次數(shù)+1,然后更新樹。更新樹要保持一原則,即“兄 弟特性”。它指的是:樹所有節(jié)點(diǎn)都要按照以字符出現(xiàn)次數(shù)的多少，從左到右,從下到 上的順序排列。如果違反了“

7、兄弟特性”就要進(jìn)行交換。交換的原則是:具有計(jì)數(shù)N 的最遠(yuǎn)的節(jié)點(diǎn)將會(huì)和計(jì)數(shù)剛剛增加到N+1的節(jié)點(diǎn)交換。如果N不是節(jié)點(diǎn)，是根節(jié)點(diǎn) 的話,那么將整個(gè)子樹進(jìn)行交換。我們還是以上述字符串a(chǎn)abccbb為例按照自頂向 下的構(gòu)樹方式，進(jìn)行自適應(yīng)霍夫曼樹的構(gòu)建，圖7給出了在構(gòu)樹過程中需要交換的過 程。6、LZW編碼信息產(chǎn)業(yè)120LZW的是一種基于字典的編碼方法。它是自適應(yīng)的，壓縮率高，花費(fèi)時(shí)間少LZW編碼過程如下:一:初始化編譯表并定義前綴current prefix為c，初始時(shí)為null,定義當(dāng) 前字符串current string為ck,k為當(dāng)前讀取字符二:讀第一個(gè)字符 p ,則 c u r r e n

8、t string=cp，因?yàn)閏=null,所以 current string=p三:在編譯表中查找有沒有c u r r e n t sting值，因?yàn)閜為根字符，所以可以 找到四:把p設(shè)為current prefix的值，繼續(xù)讀取下一字符，設(shè)為q,current string為cq,此時(shí)current sting=pq,查看編譯表中有沒有，當(dāng)然沒有，這時(shí)候要把current string(pq加到編譯表的末項(xiàng)，并把current prefix也就是p在編譯表中的索引值輸出。 并修改current prefix為當(dāng)前讀取字符，即q,繼續(xù)五:如果在編譯表中可以查到current string的值（

9、ck,則把current string的值 （ck賦予current prefix,如果找不到,則添加current string的值（ck到編譯表，把 current prefix的值（c在編譯表中對(duì)應(yīng)的索引值輸出，同時(shí)修改current prefix為k,繼 續(xù),不斷的重復(fù),直到接收完 字符為止。用一個(gè)例子說明LZW的編碼過程。例如:一個(gè)字符流有四種類型的數(shù)據(jù)a,b,c,d, 現(xiàn)字符流為abacaba，對(duì)其進(jìn)行LZW編碼如下：初始化編譯表為:0a,lb,2c,3d讀第一個(gè)字符a,則cp=a，可以在編譯表中找到讀第二個(gè)字符b,則cb=ab,在編譯表中找不到，則加ab到表中，此時(shí)編譯表為0a,

10、1b,2c,3d,4ab,并且輸出a的索引值0,修改c=b讀第三個(gè)字符a,則ca=ba,在編譯表中找不到，則加ba到表中，此時(shí)編譯表為0a,1b,2c,3d,4ab,5ba，并且輸出b的索引值1,修改c=a讀第四個(gè)字符c,則cc=ac,在編譯表中找不到，則加ac到表中，此時(shí)編譯表為0a,1b,2c,3d,4ab,5ba,6ac,并且輸出a的索引值0,修改c=c讀第五個(gè)字符a,則ca=ca，在編譯表中找不到，則加ca到表中，此時(shí)編譯表為0a,1b,2c,3d,4ab,5ba,6ac, 7ca，并且輸出c的索引值2,修改c=a讀第六個(gè)字符b,則cb=ab,在編譯表中找到，此時(shí)c=ab讀第七個(gè)字符a

11、,則ca=aba，在編譯1這時(shí)羸(2艸，交換X1朋以將整個(gè)子樹艾挽iimbw裁定因?yàn)槭歉?jié)點(diǎn).1這時(shí)羸(2艸，交換X1朋以將整個(gè)子樹艾挽iimbw裁定因?yàn)槭歉?jié)點(diǎn).因-*bo)灌)S射侯要和穩(wěn)定最遠(yuǎn)弧女換表中找不到，則加aba到表中，此時(shí)編譯表為0a,lb,2c,3d,4ab,5ba,6ac,7ca, 8aba，并 且輸出ab的索引值4,修改c=a接收結(jié)束。編碼結(jié)果為,0,1,0,2,4通過列子可見 LZW算法與其他算法相比具有自適應(yīng)的特點(diǎn),即可以根據(jù)壓縮內(nèi)容不同來建立不 同字典，以減少冗余度，提高壓縮比。并且解壓時(shí)這個(gè)字典無需與壓縮代碼同時(shí)傳送, 而是在解壓過程中逐步建立與壓縮時(shí)完全相同的字

12、典，從而完整、準(zhǔn)確地恢復(fù)被壓 縮內(nèi)容。因此,LZW算法是一種解碼速度與壓縮性能較好的壓縮算法。但是LZW 應(yīng)用的時(shí)候應(yīng)注意字典越大，代替的子串越多。但應(yīng)用中字典容量則受一定限制，要 權(quán)衡利弊選擇合適的字典。當(dāng)字典滿時(shí)，字典的維護(hù)和更新對(duì)壓縮率也是至關(guān)重 要。7、結(jié)束語需要注意的是，每種算法都有各自的優(yōu)缺點(diǎn)，都有自己的適用范圍。 在當(dāng)今高要求的壓縮條件下，通常的需要集成兩種或者兩種以上壓縮算法。例如，在 winrar就應(yīng)用了 LZW和霍夫曼混合編碼的方法進(jìn)行數(shù)據(jù)壓縮。因此，根據(jù)需要，選 擇合適的壓縮算法至關(guān)重要。研究在保持高壓縮比，提高壓縮及解壓縮速度的同時(shí) 保持原始數(shù)據(jù)的完整性還是一個(gè)重要的研究課題。參考文獻(xiàn)許霞，馬光思,魚濤. LZW無損壓縮算法的研究與改進(jìn)J.計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(4:127-1272 Nelson M.數(shù)據(jù)壓縮技術(shù)原理與范例M.賈啟東譯北京:希望出版社