1、哈夫曼树又称最优树(二叉树),是一类带权路径最短的树。这种树在信息检索中很有用。
结点的带权路径长度:从该节点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度:树中所有叶子结点的带权路径长度之和。即:WPL
WPL最小的二叉树就称作最优二叉树或哈弗曼树。
2、哈夫曼树的构造
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
如:
四个数: 7 5 2 4 构建的树为
············18···········
··········/····\·········
········7········11······
···············/···\·····
··············5·····6····
···················/·\···
··················2···4···
构建规则:由最小的两个结点开始建树,左子节点权值小于右子结点权值
3、哈弗曼编码
从哈弗曼树根节点开始,对左子树分配代码“0”,右子树分配代码“1”,一直到达叶子节点为止,然后将从树根沿每条路径到达叶
子节点的代码排列起来,便得到了哈弗曼编码。
如上树中: 7 的哈弗曼编码:0
5 的哈弗曼编码为:10
2 的哈弗曼编码为: 110
4 的哈弗曼编码为:111
4、哈弗曼压缩
它是一种无损压缩方法,在压缩过程中不会丢失信息熵,而且可以证明Huffman算法在无损压缩算法中是最优的。
(1)将要压缩的文件一个一个字节的读出来即扫描要压缩的文件,并统计每个字节的权值即出现的频率。
(2)构建哈弗曼树
(3)取得每一个叶子节点的哈弗曼编码
(4)写出每一个字节对应编码的长度
(5)写出每一个字节所对应的编码
(6)将源文件中的所有byte转化为01哈弗曼编码,写入压缩文件
然后就没然后了,恭喜你已经实现了压缩!
哈弗曼树练习:
1.构建哈弗曼树
2.根据哈弗曼树生成码表并且打印出码表
3.根据字符串生成01串编码
4.再根据01串编码还原字符串
结点类:
public class Node implements java.lang.Comparable<Node>{
private int count;
private char verb;
private Node Lnode;
private Node Rnode;
//构造函数
public Node(char verb,int count) {
this.verb = verb;
this.count = count;
}
// 返回左子树
public Node getLnode() {
return Lnode;
}
// 设置左子树
public void setLnode(Node lnode) {
Lnode = lnode;
}
// 返回右子树
public Node getRnode() {
return Rnode;
}
// 设置右子树
public void setRnode(Node rnode) {
Rnode = rnode;
}
//返回字符
public char getVerb() {
return verb;
}
//设置字符
public void setVerb(char verb) {
this.verb = verb;
}
//返回个数
public int getCount() {
return count;
}
//设置数目
public void setCount(int count) {
this.count = count;
}
public int compareTo(Node no){
if(this.count<no.count){
return -1;
}
else if(this.count>no.count){
return 1;
}
else return 0;
}
}
哈夫曼树类:
import java.util.PriorityQueue;
public class Hfmtree {
/**
* @param args
*/
public static void main(String[] args) {
Hfmtree tree = new Hfmtree();
tree.creattree();
}
public void creattree(){
String s = new String("listentomeplease");
System.out.println("字符串为:"+s);
//实例化一个优先队列
PriorityQueue<Node> queue = new PriorityQueue<Node>();
char[] c = new char[s.length()];
// 声明26个小写字母
for(int i=0;i<26;i++){
node[i]=new Node((char)(97+i),0);
}
System.out.println("node数组的长度"+node.length);
// 将字符分别存入数组里
for(int i=0;i<s.length();i++){
c[i] = s.charAt(i);
}
System.out.println("字符数组的长度"+c.length);
// 计数并存入优先队列
for(int i=0;i<node.length;i++){
int count=0;
for(int j=0;j<s.length();j++){
if(node[i].getVerb()==c[j]){
count++;
node[i].setCount(count);
}
}
}
for(int i=0;i<node.length;i++){
if(node[i].getCount()!=0){
System.out.print("字符:"+node[i].getVerb()+"\t 个数:"+node[i].getCount());
System.out.println();
queue.add(node[i]);
}
}
System.out.println("队列的长度"+queue.size());
// 循环取出最小两个值 并构架二叉树
while(queue.size()>1){
Node node1 = queue.poll();//获取队列头
Node node2 = queue.poll();
Node result = new Node((char)0,node1.getCount()+node2.getCount());
result.setLnode(node1);
result.setRnode(node2);
queue.add(result);
}
// 得到根节点
root = queue.peek();
this.getMB(root, "");
}
public void getMB(Node root,String s){
if(root.getLnode()==null&&root.getRnode()==null){
System.out.println("叶子节点"+root.getVerb()+"编码"+s);
}
if(root.getLnode()!=null){//左 0 右 1
getMB(root.getLnode(),s+'0');
}
if(root.getRnode()!=null){
getMB(root.getRnode(),s+'1');
}
}
private Node root= null;
private Node[] node = new Node[26] ;
}
分享到:
相关推荐
树的应用——哈夫曼编码 二、 实验内容: 利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。 从...
构建Huffman树,详细展示Huffman的初态和终态,通过Huffman树生成Huffman编码。
数据结构课程的课程设计,实现哈夫曼树,压缩文件
重庆大学数据结构项目2——哈夫曼编码树.用MFC实现界面。界面良好,程序结构清晰
数据结构课程设计模——哈夫曼编码译码器.doc
这是哈夫曼树源代码的源代码。可以编码,解码。是用VS2005编写的。
数据结构课程设计 ——哈夫曼编/译码器,里面什么都有 啊
数据结构课程设计模——哈夫曼编码译码器.c语言程序
这是大二时的数据结构的课设,今天与大家分享。可以读写文件,编码译码,以及对输入的异常处理。
哈夫曼树 基本功能: (1) 从文件中读出一篇英文文章,包含字母和空格等字符。 (2) 统计各个字符出现的频度。 (3) 根据出现的频度,为每个出现的字符建立一个哈夫曼编码,并输出。 (4) 输入一个字符串,为其...
设计内容: 欲发一封内容为AABBCAB ……(共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码。
哈夫曼树的应用——数据结构课程设计
树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。
哈夫曼编码的演示程序 可以由用户指定每个字符的权值进行编码 也可以输入一段字符串,程序自动计算每个字符的权值。...建立哈夫曼树之后,可以对一段字符串进行相应的加密。结果输出到文本文件中。
《数据结构》实验,(人民邮电出版社)哈夫曼编码部分
哈夫曼编码,支持汉字编码
哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短...
二叉树的应用——哈夫曼树和哈夫曼编码.pdf二叉树的应用——哈夫曼树和哈夫曼编码.pdf
哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2