自適應(yīng)ｈｕｆｆｍａｎ壓縮碼的生成

《自適應(yīng)ｈｕｆｆｍａｎ壓縮碼的生成 》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、自適應(yīng)Ｈｕｆｆｍａｎ壓縮碼的生成　　摘要:隨著現(xiàn)代社會(huì)信息量的增加,對(duì)數(shù)據(jù)進(jìn)行壓縮越來(lái)越有它的必要性。其中，Huffman編碼作為一種高效的數(shù)據(jù)編碼方法在文本、圖象、音頻等壓縮有著廣泛的應(yīng)用。本文中，筆者根據(jù)Huffman編碼的原理，實(shí)現(xiàn)對(duì)文本進(jìn)行壓縮與解壓的功能?！　￡P(guān)鍵詞：Huffman編碼；數(shù)據(jù)壓縮；解壓；文本；自適應(yīng)編碼　　　　Huffman編碼壓縮是一種無(wú)損壓縮技術(shù)。利用Huffman編碼原理進(jìn)行壓縮的主要問(wèn)題包括壓縮的算法設(shè)計(jì)及程序?qū)崿F(xiàn)、解壓算法及程序?qū)崿F(xiàn)?！　　　∫?、Huffman編碼介紹　　　　Huffman于1952年提出一種編碼的方法，它完全依據(jù)字符出現(xiàn)

2、概率來(lái)構(gòu)造平均長(zhǎng)度最短的編碼，有時(shí)稱之為最佳編碼，一般叫做Huffman編碼。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長(zhǎng)的代碼代替，每個(gè)數(shù)據(jù)的代碼各不相同。這些代碼都是二進(jìn)制碼，且碼的長(zhǎng)度是可變的?！　　　《?、自適應(yīng)Huffman編碼原理　　　　基于靜態(tài)Huffman編碼算法對(duì)輸入的符號(hào)流進(jìn)行編碼，必須進(jìn)行兩次掃描，第一次掃描統(tǒng)計(jì)字符出現(xiàn)的概率，并創(chuàng)建Huffman樹(shù)；第二次掃描是按照Huffman樹(shù)的字符進(jìn)行編碼。并且在存儲(chǔ)和傳輸Huffman編碼時(shí)，必須先存儲(chǔ)和傳送Huffman樹(shù)。這些問(wèn)題使的靜態(tài)Huffman編碼在實(shí)際應(yīng)用用的的較少。為了解決

3、靜態(tài)Huffman編碼的缺點(diǎn)，產(chǎn)生了自適應(yīng)Huffman編碼，它只需要對(duì)輸入的符號(hào)流進(jìn)行一次掃描即可。它不僅涉及到編碼樹(shù)的構(gòu)造過(guò)程，還與編碼和解碼有關(guān)?！　∽赃m應(yīng)Huffman編碼過(guò)程　　初始化Huffman樹(shù)　　對(duì)每個(gè)輸入符號(hào)　　{對(duì)符號(hào)編碼；　　更新Huffman樹(shù)；　　}　　初始化Huffman樹(shù)時(shí)，由于對(duì)字符流進(jìn)行一次掃描，因此，不能預(yù)先知道各字符的概率，為了對(duì)所以字符一致對(duì)待，在這里使用符號(hào)為NYT，權(quán)值為0作為初始的Huffman樹(shù)。NYT不同于任何一個(gè)將要傳送的符號(hào)，在這里作為一個(gè)逸出碼。NYT有兩種作用：一是在編碼時(shí)，當(dāng)有一個(gè)還沒(méi)在編碼樹(shù)出現(xiàn)的字符需要編碼時(shí)

4、，系統(tǒng)就輸出NYT編碼，然后跟著字符的原始表達(dá)；在解碼時(shí)，當(dāng)解碼器讀出NYT時(shí)，就知道下面的內(nèi)容暫不是Huffman編碼，而是一個(gè)從沒(méi)在編碼數(shù)據(jù)流出現(xiàn)的原始字符；二是作為新字符的插入點(diǎn)，在需要插入一個(gè)新字符時(shí)，總是構(gòu)造一個(gè)新子樹(shù)，子樹(shù)包括NYT符號(hào)和新符號(hào)兩個(gè)葉結(jié)點(diǎn)，然后將舊的NYT結(jié)點(diǎn)用新子樹(shù)代替，并使原NYT和新符號(hào)結(jié)點(diǎn)的權(quán)值賦一。對(duì)符號(hào)編碼與靜態(tài)的一樣。在每次編碼完成之后，需要試圖對(duì)包含的結(jié)點(diǎn)進(jìn)行權(quán)值加一操作，為此在這里需要介紹兩個(gè)概念：結(jié)點(diǎn)編號(hào)和所屬塊。結(jié)點(diǎn)編號(hào)是一個(gè)全局唯一的的值，不同的結(jié)點(diǎn)有不同的結(jié)點(diǎn)編號(hào)，它具有如下特性：　　(一)權(quán)值越大的結(jié)點(diǎn)，結(jié)點(diǎn)編號(hào)越大。

5、　　(二)父結(jié)點(diǎn)的編號(hào)總是大于子結(jié)點(diǎn)的編號(hào)?！　∫陨蟽牲c(diǎn)稱為兄弟屬性，在每次調(diào)整結(jié)點(diǎn)權(quán)值時(shí)，都需要調(diào)整結(jié)點(diǎn)的編號(hào)，以避免兄弟屬性破壞。在本課程設(shè)計(jì)中用數(shù)組來(lái)表示結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)在數(shù)組的最大位置。所屬塊指權(quán)值相同的一組結(jié)點(diǎn)。在對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行權(quán)值加一時(shí)，首先檢查該結(jié)點(diǎn)是否是所在塊的最大結(jié)點(diǎn)，如果不是，將該結(jié)點(diǎn)與所在塊的最大結(jié)點(diǎn)交換位置，在對(duì)該結(jié)點(diǎn)的權(quán)值加一，這樣保證了結(jié)點(diǎn)的兄弟屬性，由于結(jié)點(diǎn)的權(quán)值發(fā)生變化，必須遞歸對(duì)結(jié)點(diǎn)的夫結(jié)點(diǎn)執(zhí)行加一操作。　　　　三、自適應(yīng)Huffman壓縮編碼算法　　　?。ㄒ唬┡袛嘧址谖谋局惺欠癯霈F(xiàn)　　由于自適應(yīng)Huffman編碼只對(duì)字符流掃描一次，因此

6、，就需要判斷該字符在前面的字符流是否出現(xiàn)過(guò)?！　。ǘ┡袛嘣撟址欠袷撬鶎賶K的最大結(jié)點(diǎn)　　為了保證其兄弟屬性不破壞，在進(jìn)行加一操作時(shí)，必須判斷該結(jié)點(diǎn)是否是所屬快的最大結(jié)點(diǎn)，不是就必須交換當(dāng)前結(jié)點(diǎn)與最大結(jié)點(diǎn)?！　。ㄈ┙粨Q當(dāng)前結(jié)點(diǎn)與所屬塊的最大結(jié)點(diǎn)　　當(dāng)HighInBlock函數(shù)返回的不是-1就必須交換當(dāng)前結(jié)點(diǎn)與所屬塊的最大結(jié)點(diǎn)，保證兄弟屬性?！　。ㄋ模?duì)當(dāng)前字符進(jìn)行編碼　　從輸入流中得到一個(gè)字符，若以前出現(xiàn)過(guò)該字符，則對(duì)該字符進(jìn)行編碼，并判斷該字符是否是所屬塊的最大結(jié)點(diǎn)，否就交換當(dāng)前結(jié)點(diǎn)與最大結(jié)點(diǎn)；若以前沒(méi)有出現(xiàn)該字符，則生成兩個(gè)結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)用于保存該字符，另一個(gè)用做逸出

7、碼結(jié)點(diǎn)NYT，并這兩個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)為原逸出碼結(jié)點(diǎn)NYT，輸出逸出碼及原字符。在這里我們用了code這個(gè)結(jié)構(gòu)來(lái)保存一個(gè)字符的編碼?！　〕绦蛄鞒踢^(guò)程如下：　　1、從字符輸入流中，取出一個(gè)字符；　　2、判斷該字符以前是否出現(xiàn)過(guò)？　　3、否，用新的NYT及字符結(jié)點(diǎn)代替原NYT，輸出逸出碼及原字符，并使原NYT及字符結(jié)點(diǎn)的權(quán)值賦為一，改變當(dāng)前結(jié)點(diǎn)為原NYT結(jié)點(diǎn)；　　4、是，輸出該字符的編碼，判斷該字符是否是所屬塊的最大結(jié)點(diǎn)？否，交換該字符結(jié)點(diǎn)與最大結(jié)點(diǎn)，改變當(dāng)前結(jié)點(diǎn)為最大結(jié)點(diǎn)，并是當(dāng)前結(jié)點(diǎn)的權(quán)值加一。　?。ㄎ澹└翲uffm