論文開題：Huffman編碼算法及其應(yīng)用

大學(xué)本科畢業(yè)論文(設(shè)計(jì))開題報(bào)告
學(xué)院：信息科學(xué)與工程學(xué)院 專業(yè)班級(jí)：09通信工程A班

課題名稱 Huffman編碼算法及其應(yīng)用

1、本課題的的研究目的和意義：
在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來(lái)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來(lái)越引起人們的重視。哈夫曼編碼(Huffman Coding)是一種信源編碼方式，該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造平均長(zhǎng)度最短的碼字。 哈夫曼壓縮是個(gè)無(wú)損的壓縮算法，一般用來(lái)壓縮文本和程序文件。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。通過本題目，訓(xùn)練了我們對(duì)于信源編碼技術(shù)的理解及相應(yīng)編程解決問題的能力
2、 文獻(xiàn)綜述（國(guó)內(nèi)外研究情況及其發(fā)展）
……（新文秘網(wǎng)http://jey722.cn省略575字，正式會(huì)員可完整閱讀）……　
立 Huffman樹。
(3)將 Huffman樹的信息寫入輸出文件(壓縮后文件),以備解壓縮時(shí)使用。
(4)進(jìn)行第二 遍掃描, 將 原文件所有 字符轉(zhuǎn)化為Huffman編碼,并以 ASCII字符形式保存到輸出文件。
(5)在輸出文件上做標(biāo)記以標(biāo)識(shí)壓縮文件, 完成對(duì)原文件的壓縮。
2、動(dòng)態(tài)哈夫曼編碼的算法思想：
（1）初始化編碼樹，即建立一棵只有一個(gè)空葉結(jié)點(diǎn)的哈夫曼樹，該結(jié)點(diǎn)的符號(hào)為NYT（尚未傳送），權(quán)值始終為0；
（2）每讀進(jìn)一個(gè)字符，首先檢查該字符是否已經(jīng)在編碼樹中，如果是，就以靜態(tài)哈夫曼編碼中相同的方式對(duì)其進(jìn)行編碼，然更新編碼樹；如果不是，先對(duì)空葉結(jié)點(diǎn)進(jìn)行編碼，再生成一棵子樹，其右分支結(jié)點(diǎn)為剛讀入的字符，其左分支結(jié)點(diǎn)為一個(gè)新的空葉結(jié)點(diǎn)，然后用這棵子樹代替原來(lái)的空葉結(jié)點(diǎn)；
（3）將前i 個(gè)字符的哈夫曼樹調(diào)整成一棵i+1 個(gè)字符的哈夫曼樹，首先，以葉結(jié)點(diǎn)ai 為初始的當(dāng)前結(jié)點(diǎn)，重復(fù)地將當(dāng)前結(jié)點(diǎn)與具有同樣權(quán)值的編號(hào)最大的結(jié)點(diǎn)進(jìn)行交換，并使得后者的父結(jié)點(diǎn)成為新的當(dāng)前結(jié)點(diǎn)，直到遇到根結(jié)點(diǎn)為止；其次，將根到葉結(jié)點(diǎn)ai 路徑上的所有結(jié)點(diǎn)的權(quán)值加1，該樹就變成了前i+1 個(gè)字符的哈夫曼樹，并且該二叉樹仍是最優(yōu)二叉樹。
靜態(tài) Huffman 編碼的缺點(diǎn)在于在壓縮時(shí), 將會(huì)降低壓縮速度同時(shí), 為保存Huffman 樹以供解壓時(shí)用, 也將浪費(fèi)一部分存儲(chǔ)空間經(jīng)驗(yàn)證明, 由于靜態(tài)建樹, 其壓縮率也有所下降。而動(dòng)態(tài) Huffman 編碼不必為解壓而保存 Huffman 樹的有關(guān)信息, 從而提高了數(shù)據(jù)壓縮率。但是, 由于解壓時(shí)采用與壓縮時(shí)相同方法建樹, 增加了解壓時(shí)間,從而降低了還原速度。而靜態(tài) Huffman編碼由于對(duì)Huffman樹進(jìn)行保存, 還原時(shí)不必重新建樹,節(jié)省了還原時(shí)間。
huffman編碼通過堆排序算法可以達(dá)到一定的改善作用，堆排序算法（HEAPSORT）由1991 年計(jì)算機(jī)先驅(qū)獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特•弗洛伊德(Robert W．Floyd)和威廉姆(J．Williams)在1964年共同發(fā)明。堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)，從而縮短了壓縮時(shí)間。Huffman編碼在現(xiàn)實(shí)生活中經(jīng)常得到應(yīng)用，例如文本的壓縮，現(xiàn)有多種對(duì)文本文件進(jìn)行無(wú)損壓縮的算法 ,其中哈夫曼算法依據(jù)字符出現(xiàn)的頻率,將頻率高的字符用短編碼,頻率低的用較長(zhǎng)編碼,不統(tǒng)計(jì)重復(fù)字符或重復(fù)子串編碼 ,現(xiàn)考慮對(duì)文本文件先用哈夫曼編碼算法壓縮,然后再利用統(tǒng)計(jì)重復(fù)字符或重復(fù)子串編碼的算法進(jìn)行第二次壓縮 ,以達(dá)到最佳的壓縮效率 。
3、本課題的主要研究?jī)?nèi)容（提綱）和成果形式：
使用huffman對(duì)t*t文本進(jìn)行加密，采用自適應(yīng)性編碼的原理，其中以C語(yǔ)言為基礎(chǔ)實(shí)現(xiàn)代碼，代碼全部在Visual C++環(huán)境下調(diào)試通過。
4、擬解決的關(guān)鍵問題：
1）、理解huffman編碼的相關(guān)工作原理。
2）、掌握huffman兩種主要的編碼方法：靜態(tài)hu ……（未完，全文共3197字，當(dāng)前僅顯示1615字，請(qǐng)閱讀下面提示信息。收藏《論文開題：Huffman編碼算法及其應(yīng)用》）