自適應ｈｕｆｆｍａｎ壓縮碼的生成

《自適應ｈｕｆｆｍａｎ壓縮碼的生成》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

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

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

3、使的靜態(tài)Huffman編碼在實際應用用的的較少。為了解決靜態(tài)Huffman編碼的缺點，產(chǎn)生了自適應Huffman編碼，它只需要對輸入的符號流進行一次掃描即可。它不僅涉及到編碼樹的構(gòu)造過程，還與編碼和解碼有關(guān)。　　自適應Huffman編碼過程　　初始化Huffman樹　　對每個輸入符號　　{對符號編碼；　　更新Huffman樹；　　}　　初始化Huffman樹時，由于對字符流進行一次掃描，因此，不能預先知道各字符的概率，為了對所以字符一致對待，在這里使用符號為NYT，權(quán)值為0作為初始的Huffman樹。NYT不同于任何一個將要傳送的符號，在這里作為

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

5、點編號是一個全局唯一的的值，不同的結(jié)點有不同的結(jié)點編號，它具有如下特性：　　(一)權(quán)值越大的結(jié)點，結(jié)點編號越大?！　?二)父結(jié)點的編號總是大于子結(jié)點的編號?！　∫陨蟽牲c稱為兄弟屬性，在每次調(diào)整結(jié)點權(quán)值時，都需要調(diào)整結(jié)點的編號，以避免兄弟屬性破壞。在本課程設計中用數(shù)組來表示結(jié)點編號，根結(jié)點在數(shù)組的最大位置。所屬塊指權(quán)值相同的一組結(jié)點。在對每個結(jié)點進行權(quán)值加一時，首先檢查該結(jié)點是否是所在塊的最大結(jié)點，如果不是，將該結(jié)點與所在塊的最大結(jié)點交換位置，在對該結(jié)點的權(quán)值加一，這樣保證了結(jié)點的兄弟屬性，由于結(jié)點的權(quán)值發(fā)生變化，必須遞歸對結(jié)點的夫結(jié)點執(zhí)行加一操作

6、。　　　　三、自適應Huffman壓縮編碼算法　　　?。ㄒ唬┡袛嘧址谖谋局惺欠癯霈F(xiàn)　　由于自適應Huffman編碼只對字符流掃描一次，因此，就需要判斷該字符在前面的字符流是否出現(xiàn)過?！　。ǘ┡袛嘣撟址欠袷撬鶎賶K的最大結(jié)點　　為了保證其兄弟屬性不破壞，在進行加一操作時，必須判斷該結(jié)點是否是所屬快的最大結(jié)點，不是就必須交換當前結(jié)點與最大結(jié)點?！　。ㄈ┙粨Q當前結(jié)點與所屬塊的最大結(jié)點　　當HighInBlock函數(shù)返回的不是-1就必須交換當前結(jié)點與所屬塊的最大結(jié)點，保證兄弟屬性?！　。ㄋ模Ξ斍白址M行編碼　　從輸入流中得到一個字符，若以前出現(xiàn)過

7、該字符，則對該字符進行編碼，并判斷該字符是否是所屬塊的最大結(jié)點，否就交換當前結(jié)點與最大結(jié)點；若以前沒有出現(xiàn)該字符，則生成兩個結(jié)點，一個結(jié)點用于保存該字符，另一個用做逸出碼結(jié)點NYT，并這兩個結(jié)點的父結(jié)點為原逸出碼結(jié)點NYT，輸出逸出碼及原字符。在這里我們用了code這個結(jié)構(gòu)來保存一個字符的編碼?！　〕绦蛄鞒踢^程如下：　　1、從字符輸入流中，取出一個字符；　　2、判斷該字符以前是否出現(xiàn)過？　　3、否，用新的NYT及字符結(jié)點代替原NYT，輸出逸出碼及原字符，并使原NYT及字符結(jié)點的權(quán)值賦為一，改變當前結(jié)點為原NYT結(jié)點；　　4、是，輸出該字符的編碼，

8、判斷該字符是否是所屬塊的最大結(jié)點？否，交換該字符結(jié)點與最大結(jié)點，改變當前結(jié)點為最大結(jié)點，并是當前結(jié)點的權(quán)值加一?！　。ㄎ澹└翲uffm