|
|
|
如何进行哈夫曼编码：
这里随便写了个用java实现的哈夫曼编码的算法（二叉树表示）。
/**
* @(#) 岑村高科
*/
package cn.javayy.struct;
/**
* 定义了一种接口，要进行编码的最小单元类必需实现些接口
* @author boss
*
* create on : 下午10:56:59 2009-5-19
*/
public interface Combinable<T> extends Comparable<T> {
T combinate(T a,T b);
}
=====================================================
/**
* @(#) 岑村高科
*/
package cn.javayy.struct;
/**
* the huffman tree Class
* <p> 哈夫曼树，包括当前节点数据信息，左节点，右节点信息。
* @author boss
*
* create on : 下午10:16:23 2009-5-19
*/
public class HuffmanTree<T extends Combinable<T>> implements Comparable<HuffmanTree<T>>{
/**the root of huffman tree*/
private T root;
/**the left node of huffman tree*/
private HuffmanTree<T> left;
/**the right node of huffman tree*/
private HuffmanTree<T> right;
/**哈夫曼编码字符串，如:0000110*/
private String huffmanCodeString = "";
/**是否对最终生成的哈夫曼进行过编码操作*/
private static boolean isSettedHuffmanCoderString = false;
public T getRoot() {
return root;
}
public void setRoot(T root) {
this.root = root;
}
public HuffmanTree<T> getLeft() {
return left;
}
public void setLeft(HuffmanTree<T> left) {
this.left = left;
}
public HuffmanTree<T> getRight() {
return right;
}
public void setRight(HuffmanTree<T> right) {
this.right = right;
}
/**
* 重写此方法用于递归合并节点后进行排序操作
*/
@Override
public int compareTo(HuffmanTree<T> o) {
// TODO Auto-generated method stub
return o.getRoot().compareTo(this.getRoot());
}
@Override
public String toString(){
return "the root:" + this.getRoot()
+ "\r\nthe left:" + this.getLeft()
+ "\r\nthe right:" + this.getRight();
}
/**
* 对最终生成的树进行哈夫曼编码，使每个叶子节点生成01的路径编码
*/
private void setHuffmanCoderString(){
HuffmanTree<T> left = this.getLeft();
//如果有左节点则在路径中追加"0"
if(left != null){
left.huffmanCodeString = this.huffmanCodeString + "0";
left.setHuffmanCoderString();//递归编码
}
HuffmanTree<T> right = this.getRight();
//如果有右节点则在路径中追加"1"
if(right != null){
right.huffmanCodeString = this.huffmanCodeString + "1";
right.setHuffmanCoderString();//递归编码
}
}
public void printHuffmanCoderString(){
//打印最终生成树的哈夫曼编码前要进行编码操作，
//且此操作只执行一次，所以用全局标识变量判断
if(!HuffmanTree.isSettedHuffmanCoderString){
this.setHuffmanCoderString();
HuffmanTree.isSettedHuffmanCoderString = true;//标识已执行过编码
}
//如果是叶子节点（即要编码的单元），则打印出编码信息，如果是非叶子结点（中间临时生成的节点），则不打印
if(this.left == null && this.right == null)
System.out.println("the " + this.getRoot() + " huffmanCoder:" +
this.huffmanCodeString);
if(this.left != null)
this.left.printHuffmanCoderString();//递归打印
if(this.right != null)
this.right.printHuffmanCoderString();//递归打印
}
}
==================================================
/**
* @(#) 岑村高科
*/
package cn.javayy.struct;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/**
* 用类用于生成一个哈夫曼树
* @author boss
*
* create on : 下午10:51:39 2009-5-19
*/
public class HuffmanTreeFactory<T extends Combinable<T>> {
/**初始时一个list列表当作要编码的单元类的容器*/
private List<HuffmanTree<T>> HuffmanTreeCollection;
// public HuffmanTreeFactory(){}
/**
* @param unitClasses 待编码的单元类集合
*/
public HuffmanTreeFactory(List<T> unitClasses){
if(unitClasses == null || unitClasses.size() == 0)
throw new IllegalArgumentException(
"the unit classes collection can't be empty");
HuffmanTreeCollection = new LinkedList<HuffmanTree<T>>();
//初始化哈夫曼集合容器
for(T unitClass : unitClasses){
HuffmanTree<T> huffmanTree = new HuffmanTree<T>();
huffmanTree.setRoot(unitClass);
huffmanTree.setLeft(null);
huffmanTree.setLeft(null);
HuffmanTreeCollection.add(huffmanTree);
}
Collections.sort(HuffmanTreeCollection);
}
/**
* 将待编码的哈夫曼集合处理成只含有一个元素的集合，则这最后一个元素
* 即为最终生成的哈夫曼树
*/
private void generateHuffmanTree(){
while(true){
if(HuffmanTreeCollection == null || HuffmanTreeCollection.size() <= 1)
break ;
//处理之前一定要重新排序，这是哈夫曼编码的关键原理
Collections.sort(HuffmanTreeCollection);
HuffmanTree<T> huffmanTreeOne = HuffmanTreeCollection.remove(0);
HuffmanTree<T> huffmanTreeTwo = HuffmanTreeCollection.remove(0);
HuffmanTree<T> huffmanTreeNew = new HuffmanTree<T>();
//将集合中前面两个元素合并成一个元素插到集合中去
//并将第一个元素和第二个元素分别作为新元素的左，右节点
huffmanTreeNew.setRoot(huffmanTreeOne.getRoot().
combinate(huffmanTreeOne.getRoot(), huffmanTreeTwo.getRoot()));
huffmanTreeNew.setLeft(huffmanTreeOne);
huffmanTreeNew.setRight(huffmanTreeTwo);
HuffmanTreeCollection.add(huffmanTreeNew);
}
}
/**
*
* @return 生成最终的哈夫曼树
*/
public HuffmanTree<T> getHuffmanTree(){
generateHuffmanTree();
return this.HuffmanTreeCollection.get(0);
}
}
================================================
/**
* @(#) 岑村高科
*/
package cn.javayy.struct;
import java.io.Serializable;
/**
* 自定义一个用于测试的单元类
* @author boss
*
* create on : 下午09:53:07 2009-5-19
*/
public class UnitClass implements Serializable,Combinable<UnitClass>{
/**
* serialVersionUID
*/
private static final long serialVersionUID = -4109190579335512743L;
/**出现概率数据*/
private int rate;
public UnitClass(int rate){
this.rate = rate;
}
public int getRate() {
return rate;
}
public void setRate(int rate) {
this.rate = rate;
}
/**
* implements thid compartTo() in order to sort the
* collection stored from unitclass
*/
@Override
public int compareTo(UnitClass o) {
return o.getRate() > this.rate ? 1: o.getRate() < this.rate ? -1 : 0;
}
@Override
public String toString(){
return "the rate is:" + rate;
}
/**
* 重写此方法用于哈夫曼编码时可以合并两个分支点信息
*/
@Override
public UnitClass combinate(UnitClass a, UnitClass b) {
if(a == null || b == null)
return null;
return new UnitClass(a.getRate() + b.getRate());
}
}
========================================
/**
* @(#) 岑村高科
*/
package cn.javayy.struct;
import java.util.ArrayList;
import java.util.List;
/**
* @author boss
*
* create on : 下午10:03:12 2009-5-19
*/
public class Main {
public static void main(String[] args){
List<UnitClass> l = new ArrayList<UnitClass>();
l.add(new UnitClass(2));
l.add(new UnitClass(4));
l.add(new UnitClass(10));
l.add(new UnitClass(7));
l.add(new UnitClass(20));
HuffmanTreeFactory<UnitClass> factory = new HuffmanTreeFactory<UnitClass>(l);
// System.out.println(factory.getHuffmanTree());
factory.getHuffmanTree().printHuffmanCoderString();
}
}
=========================================
打印结果：
the the rate is:20 huffmanCoder:0
the the rate is:10 huffmanCoder:10
the the rate is:2 huffmanCoder:1100
the the rate is:4 huffmanCoder:1101
the the rate is:7 huffmanCoder:111 |
|
|手机版|Java学习者论坛
( 声明：本站资料整理自互联网，用于Java学习者交流学习使用，对资料版权不负任何法律责任，若有侵权请及时联系客服屏蔽删除 )
发表于 2011-9-19 16:02:10