資源描述：
《自適應(yīng)ｈｕｆｆｍａｎ壓縮碼的生成論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、自適應(yīng)Ｈｕｆｆｍａｎ壓縮碼的生成論文摘要:隨著現(xiàn)代社會(huì)信息量的增加,對(duì)數(shù)據(jù)進(jìn)行壓縮越來越有它的必要性。其中，Huffman編碼作為一種高效的數(shù)據(jù)編碼方法在文本、圖象、音頻等壓縮有著廣泛的應(yīng)用。本文中，筆者根據(jù)Huffman編碼的原理，實(shí)現(xiàn)對(duì)文本進(jìn)行壓縮與解壓的功能。關(guān)鍵詞：Huffman編碼；數(shù)據(jù)壓縮；解壓；文本；自適應(yīng)編碼Huffman編碼壓縮是一種無損壓縮技術(shù)。利用Huffman編碼原理進(jìn)行壓縮的主要問題包括壓縮的算法設(shè)計(jì)及程序?qū)崿F(xiàn)、解壓算法及程序?qū)崿F(xiàn)。一、Huffman編碼介紹Huffman于1952年提出一種編碼的方法，
2、它完全依據(jù)字符出現(xiàn)概率來構(gòu)造平均長(zhǎng)度最短的編碼，有時(shí)稱之為最佳編碼，一般叫做Huffman編碼。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長(zhǎng)的代碼代替.freelan編碼原理基于靜態(tài)Huffman編碼算法對(duì)輸入的符號(hào)流進(jìn)行編碼，必須進(jìn)行兩次掃描，第一次掃描統(tǒng)計(jì)字符出現(xiàn)的概率，并創(chuàng)建Huffman樹；第二次掃描是按照Huffman樹的字符進(jìn)行編碼。并且在存儲(chǔ)和傳輸Huffman編碼時(shí)，必須先存儲(chǔ)和傳送Huffman樹。這些問題使的靜態(tài)Huffman編碼在實(shí)際應(yīng)用用的的較少。為了解決靜態(tài)Huffman編碼的缺點(diǎn)
3、，產(chǎn)生了自適應(yīng)Huffman編碼，它只需要對(duì)輸入的符號(hào)流進(jìn)行一次掃描即可。它不僅涉及到編碼樹的構(gòu)造過程，還與編碼和解碼有關(guān)。自適應(yīng)Huffman編碼過程初始化Huffman樹對(duì)每個(gè)輸入符號(hào){對(duì)符號(hào)編碼；更新Huffman樹；}初始化Huffman樹時(shí)，由于對(duì)字符流進(jìn)行一次掃描，因此，不能預(yù)先知道各字符的概率，為了對(duì)所以字符一致對(duì)待，在這里使用符號(hào)為NYT，權(quán)值為0作為初始的Huffman樹。NYT不同于任何一個(gè)將要傳送的符號(hào)，在這里作為一個(gè)逸出碼。NYT有兩種作用：一是在編碼時(shí)，當(dāng)有一個(gè)還沒在編碼樹出現(xiàn)的字符需要編碼時(shí)，系統(tǒng)就輸
4、出NYT編碼，然后跟著字符的原始表達(dá)；在解碼時(shí)，當(dāng)解碼器讀出NYT時(shí)，就知道下面的內(nèi)容暫不是Huffman編碼，而是一個(gè)從沒在編碼數(shù)據(jù)流出現(xiàn)的原始字符；二是作為新字符的插入點(diǎn)，在需要插入一個(gè)新字符時(shí)，總是構(gòu)造一個(gè)新子樹，子樹包括NYT符號(hào)和新符號(hào)兩個(gè)葉結(jié)點(diǎn)，然后將舊的NYT結(jié)點(diǎn)用新子樹代替，并使原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)，它具有如下特性：(一
5、)權(quán)值越大的結(jié)點(diǎn)，結(jié)點(diǎn)編號(hào)越大。(二)父結(jié)點(diǎn)的編號(hào)總是大于子結(jié)點(diǎn)的編號(hào)。以上兩點(diǎn)稱為兄弟屬性，在每次調(diào)整結(jié)點(diǎn)權(quán)值時(shí)，都需要調(diào)整結(jié)點(diǎn)的編號(hào)，以避免兄弟屬性破壞。在本課程設(shè)計(jì)中用數(shù)組來表示結(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壓縮編碼算法（一）判斷字符在文本中是否出現(xiàn)由
6、于自適應(yīng)Huffman編碼只對(duì)字符流掃描一次，因此，就需要判斷該字符在前面的字符流是否出現(xiàn)過。（二）判斷該字符是否是所屬塊的最大結(jié)點(diǎn)為了保證其兄弟屬性不破壞，在進(jìn)行加一操作時(shí)，必須判斷該結(jié)點(diǎn)是否是所屬快的最大結(jié)點(diǎn)，不是就必須交換當(dāng)前結(jié)點(diǎn)與最大結(jié)點(diǎn)。（三）交換當(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)過該字符，則對(duì)該字符進(jìn)行編碼，并判斷該字符是否是所屬塊的最大結(jié)點(diǎn)，否就交換當(dāng)前結(jié)點(diǎn)與最大結(jié)點(diǎn)；若以
7、前沒有出現(xiàn)該字符，則生成兩個(gè)結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)用于保存該字符，另一個(gè)用做逸出碼結(jié)點(diǎn)NYT，并這兩個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)為原逸出碼結(jié)點(diǎn)NYT，輸出逸出碼及原字符。在這里我們用了code這個(gè)結(jié)構(gòu)來保存一個(gè)字符的編碼。程序流程過程如下：1、從字符輸入流中，取出一個(gè)字符；2、判斷該字符以前是否出現(xiàn)過？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é)
8、點(diǎn)的權(quán)值加一。（五）更新Huffman樹結(jié)構(gòu)當(dāng)從輸入流中取出一個(gè)字符并對(duì)其編碼后，Huffman樹的權(quán)值發(fā)生了變化，這就要更新Huffman樹，在程序?qū)崿F(xiàn)上用了變量nean樹的過程。程序流程如下：（一）初始化Huffman樹；（二）是否遇到結(jié)束符’/0’，否，轉(zhuǎn)
