一、实验目的：
掌握哈夫曼树的构造和应用，利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统。
二、实验内容：
1、用静态链表存储哈夫曼树，根据结点字符及其权值构造哈夫曼树，并输出哈夫曼树中所有结点数据值和各字符的哈夫曼编码
- 哈夫曼节点类
- 哈夫曼树类
- 测试
- 应用
package HuffmanTree;
public class HuffmanNode {
public int weight;
public int flag;
public HuffmanNode parent,lchild,rchild;
public HuffmanNode(){
this(0);
}
public HuffmanNode(int weight){
this.weight = weight;
flag = 0;
parent = lchild = rchild = null;
}
}
哈夫曼树类
包括哈夫曼树的构造函数、生成某一个字符的哈夫曼编码函数、输出一颗Huffman的结点数组和所有字符的哈夫曼编码
package HuffmanTree;
import java.util.HashMap;
public class HuffmanTree {
//求哈夫曼编码
public int[][] huffmanCoding(int[] W){
int num = W.length;
int m = 2 * num - 1; //哈夫曼节点数是2 * 叶节点数 - 1
HuffmanNode[] HN = new HuffmanNode[m];
int i;
//构造n个有权值的根结点
for (i = 0; i < num; i++) {
HN[i] = new HuffmanNode(W[i]);
}
//构造哈夫曼树
for (i = num;i < m; i++){
HuffmanNode min1 = selectMin(HN,i - 1);
min1.flag = 1;
HuffmanNode min2 = selectMin(HN,i - 1);
min2.flag = 1;
HN[i] = new HuffmanNode();
min1.parent = HN[i];
min2.parent = HN[i];
HN[i].lchild = min1;
HN[i].rchild = min2;
HN[i].weight = min1.weight + min2.weight;
}
//从叶子结点到根结点逆向求每个字符的哈夫曼编码
int[][] HuffCode = new int[num][num];
for (int j = 0; j < num; j++) {
int start = num - 1;
for (HuffmanNode c = HN[j],p = c.parent;p != null;c = p,p = p.parent){
//左子树编码为0
if (p.lchild.equals(c)){
HuffCode[j][start--] = 0;
}else {
HuffCode[j][start--] = 1;
}
}
//以-1作为编码开始的标识
HuffCode[j][start] = -1;
}
return HuffCode;
}
private HuffmanNode selectMin(HuffmanNode[] HN,int end){
HuffmanNode min = HN[end];
for (int i = 0;i <= end; i++){
HuffmanNode h = HN[i];
if (min.weight > h.weight && h.flag == 0)
min = h;
}
return min;
}
}
测试
package HuffmanTree;
public class Test {
public static void main(String[] args) {
//int[] W = {6,30,8,9,15,24,4,12};
int[] W = {5,29,7,8,14,23,3,11};
HuffmanTree T = new HuffmanTree();
int[][] huffmanCoding = T.huffmanCoding(W);
System.out.println("哈夫曼编码为：");
for (int i = 0;i
应用
2、[问题描述]（设计性实验）
哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。
请自行设计实现一个将文本压缩为Huffman编码序列、再将压缩的Huffman编码序列解压缩成原文本功能的哈夫曼码的编码/译码系统。并实现以下文本的压缩和解压缩：“this program is my favorite”。
[测试数据]
某文本的字符集为26个英文字母及空格字符，其出现频度如下表所示：
对节点类进行改进
package TextZip;
import HuffmanTree.HuffmanNode;
public class HuffmanNode_Zip extends HuffmanNode {
public Object name;
public String huffmanCode;
public HuffmanNode_Zip(){
}
public HuffmanNode_Zip(Object name,int weight){
this.name = name;
this.weight = weight;
flag = 0;
parent = lchild = rchild = null;
}
}
注：此代码仅为demo，不建议拷贝，运行尚不能满足所有测试
对应应用的哈夫曼树及哈夫曼编码
算法思路：
- 先将输入文本的不同字符记录，根据不同字符的数目来创建对应数目的节点，之后构造哈夫曼树及哈夫曼编码。同时因为哈夫曼编码的唯一性，所以通过Hashmap来存储不同字符对应的编码（用于压缩），以及不同编码对应的字符（用于解压缩）
特殊函数展示：
//判断target元素是否在arr数组里面
Arrays.asList(arr).contains(target);
package TextZip;
import HuffmanTree.HuffmanTree;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class HuffmanTree_Zip extends HuffmanTree {
private String zip_Coding = "";
private String unzip_Coding = "";
private HashMap unzip_CodingMap;
private HashMap zip_CodingMap;
public int[][] huffmanCoding(String str){
String[] chars = getChars(str);
int num = chars.length;
int m = 2 * num - 1;
HuffmanNode_Zip[] HN = new HuffmanNode_Zip[m];
int i;
//构造n个有名字、有权值的根结点
for ( i = 0; i < num; i++) {
switch(chars[i]){
case " ":
HN[i] = new HuffmanNode_Zip(chars[i],186);
break;
case "a":
HN[i] = new HuffmanNode_Zip(chars[i],64);
break;
case "b":
HN[i] = new HuffmanNode_Zip(chars[i],13);
break;
case "c":
HN[i] = new HuffmanNode_Zip(chars[i],22);
break;
case "d":
HN[i] = new HuffmanNode_Zip(chars[i],32);
break;
case "e":
HN[i] = new HuffmanNode_Zip(chars[i],103);
break;
case "f":
HN[i] = new HuffmanNode_Zip(chars[i],21);
break;
case "g":
HN[i] = new HuffmanNode_Zip(chars[i],15);
break;
case "h":
HN[i] = new HuffmanNode_Zip(chars[i],47);
break;
case "i":
HN[i] = new HuffmanNode_Zip(chars[i],57);
break;
case "j":
HN[i] = new HuffmanNode_Zip(chars[i],1);
break;
case "k":
HN[i] = new HuffmanNode_Zip(chars[i],5);
break;
case "l":
HN[i] = new HuffmanNode_Zip(chars[i],32);
break;
case "m":
HN[i] = new HuffmanNode_Zip(chars[i],20);
break;
case "n":
HN[i] = new HuffmanNode_Zip(chars[i],57);
break;
case "o":
HN[i] = new HuffmanNode_Zip(chars[i],63);
break;
case "p":
HN[i] = new HuffmanNode_Zip(chars[i],15);
break;
case "q":
HN[i] = new HuffmanNode_Zip(chars[i],1);
break;
case "r":
HN[i] = new HuffmanNode_Zip(chars[i],48);
break;
case "s":
HN[i] = new HuffmanNode_Zip(chars[i],51);
break;
case "t":
HN[i] = new HuffmanNode_Zip(chars[i],80);
break;
case "u":
HN[i] = new HuffmanNode_Zip(chars[i],23);
break;
case "v":
HN[i] = new HuffmanNode_Zip(chars[i],8);
break;
case "w":
HN[i] = new HuffmanNode_Zip(chars[i],18);
break;
case "x":
HN[i] = new HuffmanNode_Zip(chars[i],1);
break;
case "y":
HN[i] = new HuffmanNode_Zip(chars[i],16);
break;
case "z":
HN[i] = new HuffmanNode_Zip(chars[i],1);
break;
}
}
//构造哈夫曼树
for (i = num;i h.weight && h.flag == 0)
min = h;
}
return min;
}
public boolean useList(char[] arr,char target){
return Arrays.asList(arr).contains(target);
}
//用集合的元素唯一性，来将所有不重复的字符记录下来
private String[] getChars(String str){
int index = 0;
String[] chars = new String[str.length()];
for (int i=0;i hashMap = new HashMap();
for (int i=0;i hashMap = new HashMap();
for (int i=0;i keys = hashMap_zip.keySet();
for (int i=0;i keys = hashMap.keySet();
for (String key : keys){
System.out.println(key+"="+hashMap.get(key));
}
System.out.println("原文本为："+str);
String zip_coding = huffmanTree_zip.zip_Coding(str);
String unzip_coding = huffmanTree_zip.unzip_Coding(zip_coding);
System.out.println("加密为：");
System.out.print(zip_coding);
System.out.println();
System.out.println("解密为：");
System.out.print(unzip_coding);
}
}
