[开源]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 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
int ch = inString.charAt(i);
int j=1;
for( ;huffmanTree.get(j).charTag!=ch&&j1;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
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
if(huffmanTree.get(j).parent==0){
if(huffmanTree.get(j).weight
huffmanTree.get(j).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
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(charset.size()+1);
huffmanCode.add(0,null);
char [] tempChars = new char[charset.size()+1];
for(int i=1;i1;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();
Iterator 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 charTable;
private Set charset;
//store the huffman tree with the ArrayList
private ArrayList huffmanTree ;
//store the huffman code with the ArrayList
private ArrayList 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 hasmap = new LinkedHashMap();
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));
}
}
