您的位置:新文秘網(wǎng)>>畢業(yè)論文/文教論文/>>正文

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

發(fā)表時(shí)間:2013/8/17 20:30:13


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

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

1、本課題的的研究目的和意義:
在當(dāng)今信息爆炸時(shí)代,如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視。哈夫曼編碼(Huffman Coding)是一種信源編碼方式,該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造平均長(zhǎng)度最短的碼字。 哈夫曼壓縮是個(gè)無損的壓縮算法,一般用來壓縮文本和程序文件。因此,在文件中出現(xiàn)頻率高的符號(hào),使用短的位序列,而那些很少出現(xiàn)的符號(hào),則用較長(zhǎng)的位序列。通過本題目,訓(xùn)練了我們對(duì)于信源編碼技術(shù)的理解及相應(yīng)編程解決問題的能力
2、 文獻(xiàn)綜述(國內(nèi)外研究情況及其發(fā)展)
……(新文秘網(wǎng)http://m.120pk.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),然后用這棵子樹代替原來的空葉結(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)行無損壓縮的算法 ,其中哈夫曼算法依據(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語言為基礎(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)用》
文章搜索
相關(guān)文章