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编码。
哈夫曼树(Huffman Tree),也称为最优二叉树,是一种特殊的二叉树结构,广泛应用于数据压缩领域。在信息编码中,哈夫曼编码是一种可变长度的前缀编码,它根据字符出现的频率分配不同的二进制编码,频率高的字符编码...
在数据结构的学习中,哈夫曼树(Huffman Tree)是一种非常重要的数据结构,它在数据压缩、编码优化等领域有着广泛的应用。哈夫曼树,也称为最优二叉树,是一种带权路径长度最短的二叉树。在这个数据结构课程设计中,...
在这个课设中,我们关注的是哈夫曼树(Huffman Tree),一种在数据压缩领域广泛应用的数据结构。哈夫曼树,也称为最优二叉树,是通过哈夫曼编码实现数据压缩的关键工具。下面将详细阐述哈夫曼树的概念、构建过程、...
它的核心思想是通过构建一个特殊的二叉树——哈夫曼树(Huffman Tree),来为数据的各个符号分配最短的编码,使得频率高的符号编码较短,频率低的符号编码较长,从而实现数据的平均码长最小化,达到压缩数据的目的。...
在这个“数据结构课程设计——哈夫曼编/译码器”项目中,我们将深入学习哈夫曼编码的原理和实现。哈夫曼编码的过程主要包括以下几个步骤: 1. **统计字符频率**:首先,我们需要统计输入文本中每个字符出现的次数,...
哈夫曼树 基本功能: (1) 从文件中读出一篇英文文章,包含字母和空格等字符。 (2) 统计各个字符出现的频度。 (3) 根据出现的频度,为每个出现的字符建立一个哈夫曼编码,并输出。 (4) 输入一个字符串,为其...
设计内容: 欲发一封内容为AABBCAB ……(共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码。
哈夫曼编码是一种高效的数据压缩方法,源自于数据结构中的树形数据结构,主要用于无损数据压缩。在《数据结构》这本教材中,哈夫曼编码是重要的章节之一,通常由人民邮电出版社出版的教材会详细讲解这一概念。在进行...
哈夫曼树,也称为最优二叉树或最小带权路径长度树,是一棵特殊的二叉树,其中每个叶子节点代表一个需要编码的字符,而内部节点(非叶子节点)则表示合并两个频率较低的字符节点形成的新的频率节点。构建哈夫曼树的...
树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。
3. 构建哈弗曼树:每次从队列中取出两个频率最小的节点,合并成一个新的节点,新节点的频率是两个子节点的频率之和,然后将新节点入队。 4. 生成哈弗曼编码:从根节点到每个叶子节点的路径构成该叶子节点的哈弗曼...
哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短...
"数据结构哈夫曼树PPT学习教案.pptx" 哈夫曼树是一种特殊的二叉树,它的带权路径长度最小。哈夫曼树的构造是数据结构中的一种重要算法,广泛应用于数据压缩、编码和决策树等领域。 一、基本术语 在哈夫曼树中,...
用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树