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

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

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

3、ee對 其進(jìn)行游長編碼可得2a3b4c5d6e,可見其效 率很高。但它有兩個致命缺點。 一:如果圖象中每兩個相鄰點的顏色 都不同,用這種算法不但不能壓縮,反而數(shù) 據(jù)量會增加,例如對abcdeabcde進(jìn)行編碼得 1a2b3c4d5e1a2b3c4d5e,可見數(shù)據(jù)量反而增 加了1倍。 二:容錯性差。還是以aabbbccccddddde eeeee為例,如果在第二位a出錯,例如丟失 了a,那么編碼后結(jié)果為1a3b4c5d6e,雖然只 有一位發(fā)生了錯誤,但是在恢復(fù)數(shù)據(jù)時,將 和原始數(shù)據(jù)完全不同。 所以說游長編碼在要壓縮信息源中的符 號形成連續(xù)出現(xiàn)片段時才有效,并且它不是 一種自適應(yīng)的編碼方式。 3、

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

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

6、實用。繼而推出了自適應(yīng)霍夫 曼編碼算法。 5、自適應(yīng)霍夫曼編碼 在自適應(yīng)霍夫曼編碼算法中,統(tǒng)計字符 是隨著數(shù)據(jù)流的到達(dá)而動態(tài)收集和更新的, 字符出現(xiàn)的次數(shù)是基于到目前為止實際收到 的字符數(shù)。在這種方式下,隨著數(shù)據(jù)流的不 斷變化,符號的編碼也會不停的改變,直到 完全接收完為止,我們把這種方式叫做自適 應(yīng)。其編碼過程主要經(jīng)過初始化,讀取字符 和構(gòu)造自適應(yīng)霍夫曼樹三個部分。 初始化主要是分配一些開始時候的編解 碼雙方達(dá)成的共同的碼字,比如所ACSII碼。 在構(gòu)造自適應(yīng)霍夫曼樹的時候,最采用 的是自頂向下的方式。構(gòu)造自適 應(yīng)霍夫曼樹 主要是將字符出現(xiàn)的次數(shù)+1,然后更新樹。更 新樹要保持一原則,即“兄

7、弟特性”。它指 的是:樹所有節(jié)點都要按照以字符出現(xiàn)次數(shù) 的多少,從左到右,從下到上的順序排列。 如果違反了“兄弟特性”就要進(jìn)行交換。 交換的原則是:具有計數(shù)N的最遠(yuǎn)的節(jié)點 將會和計數(shù)剛剛增加到N+1的節(jié)點交換。如果 N不是節(jié)點,是根節(jié)點的話,那么將整個子樹 進(jìn)行交換。 我們還是以上述字符串a(chǎn)abccbb為例按照 自頂向下的構(gòu)樹方式,進(jìn)行自適應(yīng)霍夫曼樹 的構(gòu)建,圖7給出了在構(gòu)樹過程中需要交換的 過程。 6、LZW編碼 120 LZW的是一種基于字典的編碼方法。它是 自適應(yīng)的,壓縮率高,花費時間少。LZW編碼 過程如下:一:初始化編譯表并定義前綴current prefix為c,初始時為null,

8、定義當(dāng)前字符 串current string為ck,k為當(dāng)前讀取字符 二 :讀 第 一 個 字 符 p , 則 c u r r e n t string=cp,因為c=null,所以current string=p 三 :在 編 譯 表 中 查 找 有 沒 有 c u r r e n t sting值,因為p為根字符,所以可以找到 四:把p設(shè)為current prefix的值,繼 續(xù)讀取下一字符,設(shè)為q,current string為 cq,此時current sting=pq,查看編譯表 中有沒有,當(dāng)然沒有,這時候要把current string(pq加到編譯表的末項,并把current p

9、refix也就是p在編譯表中的索引值輸出。并 修改current prefix為當(dāng)前讀取字符,即q, 繼續(xù) 五:如果在編譯表中可以查到current string的值(ck,則把current string的 值(ck賦予current prefix,如果找不 到,則添加current string的值(ck到編 譯表,把current prefix的值(c在編譯 表中對應(yīng)的索引值輸出,同時修改current prefix為k,繼續(xù),不斷的重復(fù),直到接收完 字符為止。 用一個例子說明LZW的編碼過程。例如:一個字符流有四種類型的數(shù)據(jù)a,b,c,d, 現(xiàn)字符流為abacaba,對其進(jìn)行LZW編碼

10、如 下: 初始化編譯表為:0a,1b,2c,3d 讀第一個字符a,則cp=a,可以在編譯 表中找到 讀第二個字符b,則cb=ab,在編譯表 中找不到,則加ab到表中,此時編譯 表為0a,1b,2c,3d,4ab,并且輸出a 的索引值0,修改c=b 讀第三個字符a,則ca=ba,在編譯表 中找不到,則加ba到表中,此時編譯 表為0a,1b,2c,3d,4ab,5ba,并且 輸出b的索引值1,修改c=a 讀第四個字符c,則cc=ac,在編譯表 中找不到,則加ac到表中,此時編譯 表為0a,1b,2c,3d,4ab,5ba,6ac, 并且輸出a的索引值0,修改c=c 讀第五個字符a,則ca=ca,在

11、編譯表 中找不到,則加ca到表中,此時編譯 表為0a,1b,2c,3d,4ab,5ba,6ac, 7ca,并且輸出c的索引值2,修改c=a 讀第六個字符b,則cb=ab,在編譯表 中找到,此時c=ab 讀第七個字符a,則ca=aba,在編譯 表中找不到,則加aba到表中,此時編譯表 為0a,1b,2c,3d,4ab,5ba,6ac,7ca, 8aba,并且輸出ab的索引值4,修改c=a接收結(jié)束。編碼結(jié)果為,0,1,0,2,4通過列子可見LZW 算法與其他算法相比 具有自適應(yīng)的特點,即可以根據(jù)壓縮內(nèi)容不 同來建立不同字典,以減少冗余度,提高壓 縮比。并且解壓時這個字典無需與壓縮代碼 同時傳送,而

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