霍夫曼树的定义
在数据结构与算法中,人们把最小带权路径长度的二叉树称为霍夫曼树或者最优二叉树。
通俗的说就是各叶子节点的值和节点的路径长度相乘的值的和。最小的那种类型的二叉树就是霍夫曼树。
霍夫曼树的构造思想是,先将权值集合看作只有一个节点的树的集合,每次选最小的两个权值的树构造一颗新树,新树根节点的权值是左右子树的权值和,在权值集合中删除这两颗权值最小的树,将新生成的树放入权值集合中。如此重复下去,直到权值集合中只有一个元素,这就是最后整棵树的根节点了。
左子树路径看做0,右子树路径看做1的话,一个叶子节点的路径就可以通过01表示。这就是霍夫曼编码,每个节点的霍夫曼编码是不会相同的。
package com.tree;
import java.util.*;
/**
* yuyong 2012-11-2
*/
public class HuffmanTree {
Node treeRoot=null;
HuffCode huff=new HuffCode();
public HuffmanTree(SortedList<Node> values){
while(true){
Node first=values.get(0);
values.remove(0);
Node root=first;
if(values.size()<=0){
treeRoot=root;
break;
}
Node two=values.get(0);
if(two!=null){
values.remove(0);
root=new Node(null,first.weight+two.weight);
root.left=first;
root.right=two;
values.insertItem(root);
}
}
}
public static void main(String args[]) throws Exception{
long start=new Date().getTime();
SortedList<Node> list=new SortedList<Node>(SortedList.ASC);
for(int i=0;i<5;i++){
int value=(int)(Math.random()*100);
list.insertItem(new Node(value, value));
}
long end=new Date().getTime();
System.out.println("共耗时:"+(end-start));
System.out.println(list);
HuffmanTree ht=new HuffmanTree(list);
System.out.println("霍夫曼编码");
ht.show(ht.treeRoot,0);
}
void show(Node node,int c){
if(node.left!=null){
huff.put(c,0);
show(node.left, c + 1);
}
if(node.value!=null)
System.out.println("权重:"+node.weight+" 霍夫曼编码值:"+huff.toString().substring(0,c));
if(node.right!=null){
huff.put(c,1);
show(node.right, c + 1);
}
}
}
class Node{
Object value;
int weight;
Node left;
Node right;
public Node(Object value,int weight){
this.value=value;
this.weight=weight;
}
public boolean equals(Object obj){
Node node=(Node) obj;
if(node.weight==this.weight&&node.value==this.value)
return true;
return false;
}
}
class SortedList<T extends Node> extends LinkedList<T> {
public static String DESC="desc";
public static String ASC="asc";
public String sort;
public SortedList(String sort) throws Exception{
if(sort.equals(DESC))
this.sort=DESC;
else if(sort.equals(ASC))
this.sort=ASC;
else
throw new Exception("no support sort");
}
public void insertItem(T value){
int index=0;
if(this.size()>0){
int start=0;
int end=this.size()-1;
int step=0;
if(start!=end)
while((end-start)!=1){
step=(end-start)/2;
if(this.get(start+step).weight>value.weight){
end=end-step;
}else if(this.get(start+step).weight<value.weight){
start=start+step;
}else{
this.add(start+step,value);
return;
}
}
if(value.weight>=this.get(end).weight){
index=end+1;
}else if(value.weight<=this.get(start).weight){
index=start;
}else
index=end;
}
this.add(index,value);
}
public String toString(){
String str="[";
for(int j=0;j<this.size();j++){
str+=this.get(j).weight+",";
}
str=str.substring(0, str.length()-1);
str+="]";
return str;
}
}
class HuffCode extends HashMap{
public String toString(){
String str="";
for(int i=0;i<this.size();i++){
str+=this.get(i);
}
return str;
}
}
共耗时:0
[25,40,45,55,67]
霍夫曼编码
权重:45 霍夫曼编码值:00
权重:55 霍夫曼编码值:01
权重:25 霍夫曼编码值:100
权重:40 霍夫曼编码值:101
权重:67 霍夫曼编码值:11
分享到:
相关推荐
基于java实现的霍夫曼编码 随意输入数字 实现编码 并可以计算码长
利用已建好的哈夫曼树(如不在内存,则从文件 hfmtree 中读入),对文件 tobetrans 中的正文进行编码,然后将结果存入文件 codefile 中。 (3)D:解码(Decoding)。利用已建好的哈夫曼树将文件 codefile 中的代码进行...
huffman的java实现 码表生成程序 可对任意“.txt”文件进行概率统计,显示字符及其概率对照表; 依概率编制Huffman码表,显示字符、对应概率及码字对照表。 编码程序 使用码表,对任意“.txt”进行Huffman编码; ...
用c++实现霍夫曼编码——多媒体实验内容
1.哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率,求各个字符的哈夫曼编码方案。
利用霍夫曼算法实现文本文件的压缩,并输出压缩后的编码,并且可以解压
对二值图像进行游程编码并构造哈夫曼树进行哈夫曼编码
课程设计 霍夫曼编码译码 完整代码 可打印哈夫曼树
信息论课程设计基于Java Swing霍夫曼香农费诺...霍夫曼编码 实现Q符号的N重序列的R进制编码 费诺编码 实现Q符号的编码 香农编码 实现Q符号的编码 设计Windows下的可视化操作界面,不同的编码类型用不同的菜单加以分割
用java写的对操作码进行霍夫曼编码,并且计算它的最短编码长度
资源内容:基于霍夫曼编码、费诺编码、霍夫曼压缩、LZ77压缩C仿真(完整代码+说明文档+数据).rar 代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 适用对象:工科生、数学专业、算法等方向...
java实现信息论与编码,包含香农码、费诺码、霍夫曼码,有算法有界面
用面向对象的程序设计思想自己动手写压缩软件,采用了优先队列这一很好的数据结构实现的贪心算法构造Huffman树,能打印Huffman树,显示编码表,压缩文件和解压缩文件,采用UTF-8字符集,支持中文文件
首先对于赫夫曼编码有个大概的理解:赫夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度...
自适应霍夫曼使用Vitter算法在Java中实现自适应霍夫曼编码。如何运行编码器使用javac进行编译$ java adaptiveHuffman.encoder.Encoder InputFile OutputFile`其中InputFile是要压缩的一些文本或其他文件,而Output...
霍夫曼编码实现压缩文本文件,见文件huffman.rar. 对文件数据读写等功能已经实现,程序在Q2Resources.zip中。Q2Resources.zip中的文件禁止修改。请将TextZip.java文件所有未实现的函数按照要求给以实现
霍夫曼编码霍夫曼编码的另一种 Java 实现
java实现huffman算法 ~可以在控制台输入字符串编码~
基于Java实现的JPEG有损图像压缩编码器源码+项目说明(课程大作业).zip 一个基本由自己实现的JPEG有损图像压缩编码器,基于JFIF(JPEG文件交换格式)标准: 色彩空间转换(RGB to YUV) 色度抽样(采样因子4:2:0) ...
霍夫曼编码 Java 中的 Huffman 编码/解码算法