| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1008 人关注过本帖, 1 人收藏
标题:[开源]Huffman算法JAVA语言版
只看楼主 加入收藏
狂放不羁
Rank: 4
等 级:贵宾
威 望:12
帖 子:925
专家分:0
注 册:2007-1-24
收藏(1)
 问题点数:0 回复次数:3 
[开源]Huffman算法JAVA语言版

本来想用Huffman做个小的压缩软件,写到后面不想写了,就把如何创建,编码,和解码的代码发上来让大家提提建议。。

//Huffman.java
package huffman.xmu;
import java.util.LinkedHashMap;
import java.util.ArrayList;
import java.util.Set;
import java.util.Iterator;
public class Huffman {

public Huffman(LinkedHashMap<Character,Integer> map){

charTable = map;
charset = map.keySet();
creatHuffmanTree();
creatHuffmanCode();


}


//encode the input string
public String enCodeString(String inString){

StringBuffer temp = new StringBuffer();
for(int i=0;i<inString.length();i++){

int ch = inString.charAt(i);
int j=1;
for( ;huffmanTree.get(j).charTag!=ch&&j<charset.size()+1;j++){

}
if(j<=charset.size()){

temp.append(huffmanCode.get(j));
} else {

temp.append(ch);
}

}

return temp.toString();


}

//decode the string
public String deCodeString(String inString){

StringBuffer temp = new StringBuffer();
int root = charset.size()*2-1;
for(int i=0;i<inString.length();i++){
char ch=inString.charAt(i);

if(ch=='0'){

root=huffmanTree.get(root).lChild;
}else if(ch=='1'){

root=huffmanTree.get(root).rChild;
}else {

temp.append(ch);
}

if(root<=charset.size()){

temp.append(huffmanTree.get(root).charTag);
root=charset.size()*2-1;
}

}
return temp.toString();

}


//creat the huffman tree
private void creatHuffmanTree(){

initTree();
int min_child1;
int min_child2;


for(int i=charset.size()+1;i<2*charset.size();i++){

min_child1=0;
min_child2=0;

for(int j=1;j<i;j++){


if(huffmanTree.get(j).parent==0){

if(huffmanTree.get(j).weight<huffmanTree.get(min_child1).weight||
huffmanTree.get(j).weight<huffmanTree.get(min_child2).weight ) {

if (huffmanTree.get(min_child1).weight < huffmanTree.get(min_child2).weight) {
min_child2 = j;
} else {
min_child1= j;
}
}
}
}


huffmanTree.get(min_child1).parent=i;
huffmanTree.get(min_child2).parent=i;

if(min_child1<min_child2){
huffmanTree.get(i).lChild=min_child1;
huffmanTree.get(i).rChild=min_child2;
} else{
huffmanTree.get(i).rChild=min_child1;
huffmanTree.get(i).lChild=min_child2;
}

huffmanTree.get(i).weight=huffmanTree.get(i).weight+huffmanTree.get(i).weight;


}

}

private void creatHuffmanCode(){

huffmanCode = new ArrayList<String>(charset.size()+1);
huffmanCode.add(0,null);
char [] tempChars = new char[charset.size()+1];

for(int i=1;i<charset.size()+1;i++){

int startIndex=charset.size();
int parent = huffmanTree.get(i).parent;
int ch=i;
while(parent!=0){

if(huffmanTree.get(parent).lChild== ch){

tempChars[startIndex]='0';


}else {

tempChars[startIndex]='1';

}

startIndex--;
ch=parent;
parent=huffmanTree.get(parent).parent;


}

System.out.println(String.valueOf(tempChars,startIndex+1,charset.size()-startIndex));
huffmanCode.add(i, String.valueOf(tempChars,startIndex+1,charset.size()-startIndex));


}//end for



}//end method


private void initTree(){

huffmanTree = new ArrayList<Node>();

Iterator<Character> charIter = charset.iterator();

int i=1;


huffmanTree.add(0,new Node((char) 0, Integer.MAX_VALUE, 0, 0, 0));
while(charIter.hasNext()){

Character ch=charIter.next();
huffmanTree.add(i,new Node(ch,charTable.get(ch),0,0,0));


i++;

}


for(int j=charset.size()+1;j<2*charset.size();j++){

huffmanTree.add(j,new Node((char)0,0,0,0,0));
}


}

//character table with the frequency of each character
private LinkedHashMap<Character,Integer> charTable;

private Set<Character > charset;

//store the huffman tree with the ArrayList
private ArrayList<Node> huffmanTree ;

//store the huffman code with the ArrayList
private ArrayList<String> huffmanCode;


class Node{

char charTag;
int weight;
int parent;
int lChild;
int rChild;

public Node(char c,int w, int p,int l, int r){

charTag = c;
weight = w;
lChild = l;
rChild = r;
}

}//end Node



public static void main(String [] args){

LinkedHashMap<Character,Integer> hasmap = new LinkedHashMap<Character,Integer>();
hasmap.put('a',4);
hasmap.put('b',5);
hasmap.put('c',8);
hasmap.put('d',10);

Huffman huffman = new Huffman(hasmap);
String temp = huffman.enCodeString("abcd");
System.out.println(temp);
System.out.println(huffman.deCodeString(temp));


}

}

搜索更多相关主题的帖子: JAVA Huffman util 算法 java 
2007-07-21 18:30
witchery
Rank: 1
来 自:西安
等 级:新手上路
帖 子:205
专家分:0
注 册:2005-8-6
收藏
得分:0 
收了,有空看看...
多谢分享
2007-07-21 20:30
zhoujj303030
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2008-7-19
收藏
得分:0 
很好,多多学习!
2008-07-27 00:10
sunkaidong
Rank: 4
来 自:南京师范大学
等 级:贵宾
威 望:12
帖 子:4496
专家分:141
注 册:2006-12-28
收藏
得分:0 
我用c写过。。。呵呵,不错

学习需要安静。。海盗要重新来过。。
2008-07-27 20:34
快速回复:[开源]Huffman算法JAVA语言版
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021758 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved