《哈夫曼編碼的JAVA實(shí)現(xiàn)課程設(shè)計(jì)》由會員分享，可在線閱讀，更多相關(guān)《哈夫曼編碼的JAVA實(shí)現(xiàn)課程設(shè)計(jì)（8頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、哈夫曼編碼的JAVA實(shí)現(xiàn)課程設(shè)計(jì)
目 錄
摘 要 2
一、問題綜述 2
二、求解方法介紹 3
三、實(shí)驗(yàn)步驟及結(jié)果分析 4
四、程序設(shè)計(jì)源代碼 5
參考文獻(xiàn) 8
摘要
利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本，試用java語言設(shè)計(jì)一個(gè)哈夫曼編碼系統(tǒng)。通過本課程設(shè)計(jì)，應(yīng)使學(xué)生掌握哈夫曼編碼的特點(diǎn)、儲存方法和基本原理，培養(yǎng)學(xué)生利用java語言正確編寫程序及調(diào)試程序的能力，運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識解決實(shí)際問題的能力。
關(guān)鍵字：哈夫曼編碼 JAVA語言 類 方法
2、
一、問題綜述
1 哈夫曼編碼的算法思想
哈夫曼編碼也稱前綴編碼，它是根據(jù)每個(gè)字符出現(xiàn)的頻率而進(jìn)行編碼的，要求任一字符的編碼都不是其它任意字符編碼的前綴且字符編碼的總長度為最短。它主要應(yīng)用于通信及數(shù)據(jù)的傳送以及對信息的壓縮處理等方面。哈夫曼編碼的基礎(chǔ)是依據(jù)字符出現(xiàn)的頻率值而構(gòu)造一棵哈夫曼樹，從而實(shí)現(xiàn)最短的編碼表示最常用的數(shù)據(jù)塊或出現(xiàn)頻率最高的數(shù)據(jù)，具體的方法是：
1.1 建立哈夫曼樹
把N 個(gè)字符出現(xiàn)的頻率值作為字符的權(quán)值,然后依據(jù)下列步驟建立哈夫曼樹。
1.1.1 由N 個(gè)權(quán)值分別作N 棵樹的根結(jié)點(diǎn)而形成一個(gè)森林。
1.1.2 從中選擇兩棵根值最小的樹T1 和T
3、2 組成一棵以結(jié)點(diǎn)T 為根結(jié)點(diǎn)的增長樹，根結(jié)點(diǎn)T = T1 + T2 ,即新樹的根值為原來兩棵樹的根值之和，而T1 和T2 分別為增長樹的左右子樹。
1.1.3 把這棵新樹T 加入到森林中，把原來的兩棵樹T1 和T2 從森林中刪除。
1.1.4 重復(fù)1.1.2～1.1.3 步，直到合并成一棵樹為止。
1.2 生成各字符的哈夫曼編碼
在上面形成的哈夫曼樹中，各個(gè)字符的權(quán)值結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，從葉子結(jié)點(diǎn)開始向根搜索，如果是雙親的左分支，則用“0”標(biāo)記，右分支用“1”標(biāo)記，從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)所經(jīng)過的分支編碼“0”、“1”的組合序列就是各字符的哈夫曼編碼。
2 構(gòu)造哈夫曼樹的算法
1）對給定
4、的n個(gè)權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右子樹均為空。
2）在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。
3）從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。
4）重復(fù)2）和3），直到集合F中只有一棵二叉樹為止。
例如，對于4個(gè)權(quán)值為1、3、5、7的節(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，其構(gòu)造過程如下圖所示：
圖1 構(gòu)造哈夫曼樹的過程示例
二、求解方
5、法介紹
以往的哈夫曼編碼程序?qū)崿F(xiàn)都是利用PASCAL 或C 語言描述的，而這兩門語言都有相應(yīng)的指針類型來解決，實(shí)現(xiàn)起來較為容易，但是，JAVA語言是面向?qū)ο蟮木幊陶Z言，沒有提供指針類型，所以在實(shí)現(xiàn)上應(yīng)該結(jié)合JAVA 的應(yīng)用環(huán)境，采用靜態(tài)的方法解決。同時(shí)，JAVA 語言是具有平臺無關(guān)性的網(wǎng)絡(luò)編程語言，用JAVA 語言實(shí)現(xiàn)哈夫曼編碼不論在教學(xué)中或是在實(shí)際應(yīng)用中都有一定的意義。
本程序是用哈夫曼樹來實(shí)現(xiàn)哈夫曼編碼的功能，根據(jù)輸入的報(bào)文進(jìn)行分析，建立哈夫曼樹。統(tǒng)計(jì)輸入字符串的長度，并對每個(gè)字符的頻度進(jìn)行計(jì)算。對每個(gè)字符及相應(yīng)的頻度作為葉結(jié)點(diǎn)建立哈夫曼樹。哈夫曼樹的建立過程采用把結(jié)點(diǎn)看作樹每次選最小
6、的兩個(gè)建立樹，并把他們的頻度相加，再繼續(xù)選取最小的兩個(gè)數(shù)建立，直到所有的結(jié)點(diǎn)建立完，才形成完整的哈夫曼樹。接下來是對沒個(gè)結(jié)點(diǎn)進(jìn)行編碼，從第一個(gè)結(jié)點(diǎn)開始看它的雙親，若它雙親做左孩子則記0，若是右孩子則記1，依次往上推，直到哈夫曼的根結(jié)點(diǎn)為止。記錄編碼打印出來。
為了體現(xiàn)程序中各個(gè)功能的獨(dú)立性，結(jié)合JAVA 語言的編程要求，對程序中所用到的類和方法進(jìn)行說明：
1 公共類Tree：組成哈夫曼樹的最小單元。其成員變量有：
1.1 lchild：最小單元的左孩子。
1.2 rchild：最小單元的右孩子。
1.3 parents：最小單元的雙親。
2 公共類Huffman：描述哈夫曼編碼
7、的整個(gè)過程,其成員變量有：
2.1 numsMo：儲存要進(jìn)行編碼的一組數(shù)。
2.2 nums：臨時(shí)儲存要進(jìn)行編碼的這組數(shù)，會隨著后面的調(diào)用而變化。
2.3 trees：儲存哈夫曼樹，由若干最小單元構(gòu)成。
2.4 temp：中間變量，是字符串類型。
3 核心方法及流程
3.1 main 方法：用于程序的執(zhí)行入口。其中定義了一個(gè)Huff 類實(shí)體，調(diào)用方法start() 完成數(shù)組初始排序，實(shí)現(xiàn)哈夫曼編碼等一系列的操作。
3.2 addNum 方法：用于方法初始化給定的要進(jìn)行編碼的數(shù)組，數(shù)組通過控制臺鍵盤錄入。
3.3 minTo 方法：在一組數(shù)中選擇最小的兩個(gè)
8、，按遞增順序返回。
3.4 compareNum 方法：是公共類Huffman的核心算法之一，該方法是將一組樹形成哈夫曼樹，左孩子為較小值。
3.5 print 方法：是公共類Huffman的核心算法之一，該方法利用遞歸打印出編碼。其流程圖如下：
三、實(shí)驗(yàn)步驟及結(jié)果分析
測試數(shù)據(jù)：
0.01 0.03 0.07 0.13 0.19 0.26 0.31
程序運(yùn)行：
請輸入一組數(shù)，中間用空格分隔：
0.01 0.03 0.07 0.13 0.19 0.26 0.31
輸出結(jié)果為：
0.01 : 01000 碼長：5
0.03 : 01001 碼長：5
0.07
9、: 0101 碼長：4
0.13 : 011 碼長：3
0.19 : 00 碼長：2
0.26 : 10 碼長：2
0.31 : 11 碼長：2
心得體會：
在本次的課程設(shè)計(jì)中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難。我的調(diào)試及其中的錯(cuò)誤和我最終找出錯(cuò)誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了：在遞歸調(diào)用方法時(shí)最好不要有返回值，否則會使程序變得邏輯混亂，復(fù)雜難懂；當(dāng)從葉結(jié)點(diǎn)向上編碼時(shí)，根據(jù)本程序的特點(diǎn)會有可能重復(fù)的tree，所以要分成同tree和不同tree進(jìn)行不同的邏輯編程。
通過本次的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒懂的知
10、識，并對求哈夫曼樹及哈夫曼編碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會了一種算法。當(dāng)求解一個(gè)算法時(shí)，不是拿到問題就不加思索地做，而是首先要先對它有個(gè)大概的了解，接著再詳細(xì)地分析每一不怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。
四、程序設(shè)計(jì)源代碼
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Huffman {
private List nu
11、ms;
private List numsMo;
private List trees;
private String temp;
public Huffman() {
nums = new ArrayList();
numsMo = new ArrayList();
trees = new ArrayList();
temp="";
}
public void addNums() {// 給定一組數(shù)
System.out.println("請輸入一組數(shù)，中間用
12、空格分隔：");
Scanner sca = new Scanner(System.in);
String str = sca.nextLine();
String[] strs = str.split(" ");
for (int i = 0; i < strs.length; i++) {
nums.add(Double.parseDouble(strs[i]));
numsMo.add(Double.parseDouble(strs[i]));
}
}
public void compareNum(List num
13、s,List trees) {// 遞歸算法
double[] min = new double[2];
if(nums.size()>1){
min = minTwo(nums);
Tree t = new Tree(min[0],min[1],min[0]+min[1]);
nums.remove(Double.valueOf(min[0]));
nums.remove(Double.valueOf(min[1]));
nums.add(min[0]+min[1]);
trees.add(t);
compare
14、Num(nums,trees);
}
}
public void print(double num) {// 遞歸打印編碼
for(Tree t : trees){
if(num == t.getRchild()){
temp = 1+temp;
print(t.getParents());
break;
}else if(num == t.getLchild()){
temp = 0+temp;
print(t.getParents());
break;
}
}
}
15、 public void write(double d){
temp = "";
System.out.print(d+" : ");
print(d);
System.out.print(temp);
System.out.println(" 碼長："+temp.length());
}
public double[] minTwo(List nums) {// 在一組數(shù)中選則最小的兩個(gè)，按遞增排序返回
Double temp = 0.0;
for (int j = 0; j < 2; j++) {
for (in
16、t i = 1; i < nums.size(); i++) {
if (nums.get(i - 1) < nums.get(i)) {
temp = nums.get(i);
nums.set(i, nums.get(i - 1));
nums.set(i - 1, temp);
}
}
}
double[] n = {nums.get(nums.size()-1),nums.get(nums.size()-2)};
return n;
}
public void start(){
add
17、Nums();
compareNum(nums,trees);
while(numsMo.size()>1){
double[] mins = minTwo(numsMo);
if(mins[0]!=mins[1]){
numsMo.remove(Double.valueOf(mins[0]));
write(mins[0]);
}
}
if(!numsMo.isEmpty()){
write(numsMo.get(0));
}
}
public static void main(String[] args){
new Huffman().start();
}
}
參考文獻(xiàn)
1(美)Stuart Reges，(美)Marty Stepp著 陳志等譯，java程序設(shè)計(jì)教程，機(jī)械工業(yè)出版社,2008
2（英）David J.C.Mackay著 肖明波，席斌，許芳，王建新譯，信息論、推理與學(xué)習(xí)算法，高等教育出版社，2006
8
哈夫曼編碼的JAVA實(shí)現(xiàn)課程設(shè)計(jì)
