hufman编码 java版本

Question

我们这学期学的数据结构C语言版本。课程设计要做一个huffman编码原理做的压缩和解压的小程序。
我想用JAVA做。可以没学JAVA版本的。
请各位朋友给我说一下原理思路。还要一个完整的程序。
多谢大家啊！

Answer 1

c语言和java语法没很大区别，自己实习看看
不行的话搞本java版本的数据结构看看，我正在研究呢

Answer 2

我想要做的事情应该有以下几点：
1. 统计各个数据出现频率。
2. 根据频率生成huffman编码
3. 根据编码生成压缩文件。同时保存huffman编码跟数据的映射

Answer 3

java要注意其中的字符串和字节的转换的问题。。

Answer 4

仅供参考
/*
 * Huff.java
 *
 */package datacompress;
import java.io.*;
import java.util.*;public class Huff {
    
    /** Creates a new instance of Huff */
    private int num;
    private int numNode;
    public    int value[][]=new int[2][num];
    public    int valueNode[][]=new int[2][num];
        
        public void Huff()throws IOException {
        System.out.print("程序正huff运行！");
        String s;
        int n,i;
        InputStreamReader ir;
        BufferedReader in;
        ir=new InputStreamReader(System.in);
        in=new BufferedReader(ir);
        System.out.print("input the numbers of data:");
        s=in.readLine();
        n=Integer.parseInt(s);
        System.out.print("input"+s+"numbers");        for(i=0;i<n-1;i++){
            s=in.readLine();
            value[0][i]=i;
            value[1][i]=Integer.parseInt(s);
            valueNode[0][i]=i;
            valueNode[1][i]=Integer.parseInt(s);
            }
         }
    void class1(){
    int i,j,k,m,n;
    n=num;
    for(i=0;i<n-2;i++){
        k=i;
        for(j=i+1;j<n-1;j++)
            if(valueNode[1][k]>valueNode[1][j])
                k=j;
                if(i!=k){
                  m=valueNode[1][i];
                    valueNode[1][j]=valueNode[1][k];
                    valueNode[1][k]=m;
                    m=valueNode[0][i];
                    valueNode[0][i]=valueNode[0][k];
                    valueNode[0][k]=m;
             
                }
        
        }
    }
    void class2(int m,int n){
    int i,j,sum;
    int arr[][]=new int[2][num];            //?
    sum=arr[1][0]+arr[1][1];
    int number=n-1;
    boolean ff=true;
    for(i=2;i<number;i++){
        if(valueNode[1][i]<sum){
            valueNode[1][i-2]=valueNode[1][i];
            valueNode[0][i-2]=valueNode[0][i];
            }
        else{
                if(ff){
                    valueNode[1][i-2]=sum;
                    valueNode[0][i-2]=number-1;
                    valueNode[1][i-1]=valueNode[1][i];
                    valueNode[0][i-1]=valueNode[0][i];
                    ff=false;
                    }
                else{
                    valueNode[1][i-1]=valueNode[1][i];
                    valueNode[0][i-1]=valueNode[0][1];
                    }
            }
        if(ff){
            valueNode[1][num-1]=sum;
            valueNode[0][num-1]=number-1;
            }
        }
    }
    void huffbm(){
    int huffVal[][]=new int[numNode][4];
    int i,j,k,m,num1,num2,val,par;
    int mm=num;
    Huff huff=new Huff();
        for(i=0;i<numNode;i++){
        if(i<num)
        {huffVal[i][0]=value[1][i];}
        else
        huffVal[i][0]=0;
        huffVal[i][1]=0;
        huffVal[i][2]=0;
        huffVal[i][3]=0;
        }
        for(i=mm+1;i<=num;i++){         //?
        num1=valueNode[0][0];
        num2=valueNode[0][1];
        val=valueNode[1][0]+valueNode[1][1];
        huff.class2(i,mm--);
        par=i;
        huffVal[num1][3]=par;
        huffVal[num2][3]=par;
        huffVal[par][0]=val;
        huffVal[par][3]=0;
        huffVal[par][1]=num1;
        huffVal[par][2]=num2;
        }
    StringBuffer bm;
        for(i=0;i<num;i++){
        j=1;
        bm=new StringBuffer(" ");
            par=huffVal[j][4];
            while(par!=0){
            if(huffVal[par][2]==j)
            bm.insert(0,'0');
            else
            bm.insert(0,'1');
            j=par;
            par=huffVal[par][4];
            }
        System.out.println(bm.toString());
        }
    }
    public static void main(String args[])throws IOException{
    Huff huff=new Huff();
    System.out.print("程序正运行！");
    huff.class1();
    System.out.print("程序正运行！");
    huff.huffbm();
    System.out.print("程序正运行！");
    } 
}

Answer 5

看我的：刚把树建立起来。很快就会做一个完整的漂亮的程序出来。
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Set;
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;
parent = p;
lchild = l;
rchild = r;

}

public String toString() {

String result;
result = "char:" + charTag + "," + "weight:" + weight + ",parent:" + parent
 + ",lchild:" + lchild + ",rchild:" + rchild;
return result;
}

}public class HuffmanCoding {

//store character and its frquency
private LinkedHashMap charTable;

//store huffman tree node
private ArrayList huffmanTree;

private ArrayList huffmanCode;

//store the charaset
private Set charset;

public HuffmanCoding(LinkedHashMap m) {

charTable = m;
charset = m.keySet();

}

public void initTree() {
//init the tree with the init node

huffmanTree = new ArrayList();
Iterator charIter = charset.iterator();
int i = 1;

//first position don't use
huffmanTree.add(0,new Node((char)0,0,0,0,0));
while(charIter.hasNext()) {
Character ch = (Character)charIter.next();
huffmanTree.add(i,new Node(ch,((Integer)(charTable.get(ch))).intValue(),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));

// for(int k = 1; k < huffmanTree.size(); k++) {
// System.out.println(huffmanTree.get(k));
// }

}

public void huffmanTree() {

int minIndex1 = 0,minIndex2 = 0;
int temp = 0;
initTree();
System.out.println("charset size():" + charset.size());
for(int i = charset.size() + 1; i < 2 * charset.size(); i++) {

int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;

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


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

if(((Node)huffmanTree.get(j)).weight < min1) {

min2 = min1;
minIndex2 = minIndex1;
min1 = ((Node)huffmanTree.get(j)).weight;
minIndex1 = j;

} else if(((Node)huffmanTree.get(j)).weight < min2) {

min2 = ((Node)huffmanTree.get(j)).weight;
minIndex2 = j;
}

}

}
temp++;
((Node)huffmanTree.get(i)).lchild = minIndex1;
((Node)huffmanTree.get(i)).rchild = minIndex2;
((Node)huffmanTree.get(i)).weight = ((Node)huffmanTree.get(minIndex1)).weight +
((Node)huffmanTree.get(minIndex2)).weight;
((Node)huffmanTree.get(minIndex1)).parent = i;
((Node)huffmanTree.get(minIndex2)).parent = i;


}
for(int k = 1; k < huffmanTree.size(); k++) {
System.out.println(huffmanTree.get(k));
}

}

public void huffmanCode() {

huffmanCode = new ArrayList(charset.size() + 1);
char[] temp = new char[charset.size() + 1];


huffmanCode.add(0,null);

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

int startIndex = charset.size();

int parent = ((Node)huffmanTree.get(i)).parent;
int ch = i;

while(parent != 0 ) {

if(((Node)huffmanTree.get(parent)).lchild == ch) {

temp[startIndex] = '0';

} else { temp[startIndex] = '1';

}
ch = parent;
parent = ((Node)huffmanTree.get(parent)).parent;

startIndex--;


}

huffmanCode.add(i,String.valueOf(temp, startIndex + 1, charset.size() - startIndex));
System.out.print(((Node)huffmanTree.get(i)).charTag + ":");
System.out.println(String.valueOf(temp,startIndex+1,charset.size() - startIndex));

}

}

public static void main(String []args) {

LinkedHashMap m = new LinkedHashMap();
m.put('a', 5);
m.put('b', 44);
m.put('c', 23);
m.put('d', 33);
m.put('e', 12);
//m.put('f', 53);

HuffmanCoding h = new HuffmanCoding(m);
h.huffmanTree();
h.huffmanCode();
}


}

Answer 6

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Set;
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;
parent = p;
lchild = l;
rchild = r;

}

public String toString() {

String result;
result = "char:" + charTag + "," + "weight:" + weight + ",parent:" + parent
 + ",lchild:" + lchild + ",rchild:" + rchild;
return result;
}

}public class HuffmanCoding {

//store character and its frquency
private LinkedHashMap charTable;

//store huffman tree node
private ArrayList huffmanTree;

private ArrayList huffmanCode;

//store the charaset
private Set charset;

public HuffmanCoding(LinkedHashMap m) {

charTable = m;
charset = m.keySet();

}

public void initTree() {
//init the tree with the init node

huffmanTree = new ArrayList();
Iterator charIter = charset.iterator();
int i = 1;

//first position don't use
huffmanTree.add(0,new Node((char)0,0,0,0,0));
while(charIter.hasNext()) {
Character ch = (Character)charIter.next();
huffmanTree.add(i,new Node(ch,((Integer)(charTable.get(ch))).intValue(),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));

// for(int k = 1; k < huffmanTree.size(); k++) {
// System.out.println(huffmanTree.get(k));
// }

}

public void huffmanTree() {

int minIndex1 = 0,minIndex2 = 0;
int temp = 0;
initTree();
System.out.println("charset size():" + charset.size());
for(int i = charset.size() + 1; i < 2 * charset.size(); i++) {

int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;

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


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

if(((Node)huffmanTree.get(j)).weight < min1) {

min2 = min1;
minIndex2 = minIndex1;
min1 = ((Node)huffmanTree.get(j)).weight;
minIndex1 = j;

} else if(((Node)huffmanTree.get(j)).weight < min2) {

min2 = ((Node)huffmanTree.get(j)).weight;
minIndex2 = j;
}

}

}
temp++;
((Node)huffmanTree.get(i)).lchild = minIndex1;
((Node)huffmanTree.get(i)).rchild = minIndex2;
((Node)huffmanTree.get(i)).weight = ((Node)huffmanTree.get(minIndex1)).weight +
((Node)huffmanTree.get(minIndex2)).weight;
((Node)huffmanTree.get(minIndex1)).parent = i;
((Node)huffmanTree.get(minIndex2)).parent = i;


}
for(int k = 1; k < huffmanTree.size(); k++) {
System.out.println(huffmanTree.get(k));
}

}

public void huffmanCode() {

huffmanCode = new ArrayList(charset.size() + 1);
char[] temp = new char[charset.size() + 1];


huffmanCode.add(0,null);

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

int startIndex = charset.size();

int parent = ((Node)huffmanTree.get(i)).parent;
int ch = i;

while(parent != 0 ) {

if(((Node)huffmanTree.get(parent)).lchild == ch) {

temp[startIndex] = '0';

} else { temp[startIndex] = '1';

}
ch = parent;
parent = ((Node)huffmanTree.get(parent)).parent;

startIndex--;


}

huffmanCode.add(i,String.valueOf(temp, startIndex + 1, charset.size() - startIndex));
System.out.print(((Node)huffmanTree.get(i)).charTag + ":");
System.out.println(String.valueOf(temp,startIndex+1,charset.size() - startIndex));

}

}

public static void main(String []args) {

LinkedHashMap m = new LinkedHashMap();
m.put('a', 5);
m.put('b', 44);
m.put('c', 23);
m.put('d', 33);
m.put('e', 12);
//m.put('f', 53);

HuffmanCoding h = new HuffmanCoding(m);
h.huffmanTree();
h.huffmanCode();
}


}

Answer 7

转一个过来 
 //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));   
      
      
  }   
     
 }   

Answer 8

/* 
  *   Huff.java 
  * 
  */ package   datacompress; 
import   java.io.*; 
import   java.util.*; public   class   Huff   { 
        
        /**   Creates   a   new   instance   of   Huff   */ 
        private   int   num; 
        private   int   numNode; 
        public         int   value[][]=new   int[2][num]; 
        public         int   valueNode[][]=new   int[2][num]; 
                
                public   void   Huff()throws   IOException   { 
                System.out.print("程序正huff运行！"); 
                String   s; 
                int   n,i; 
                InputStreamReader   ir; 
                BufferedReader   in; 
                ir=new   InputStreamReader(System.in); 
                in=new   BufferedReader(ir); 
                System.out.print("input   the   numbers   of   data:"); 
                s=in.readLine(); 
                n=Integer.parseInt(s); 
                System.out.print("input"+s+"numbers");                 for(i=0;i <n-1;i++){ 
                        s=in.readLine(); 
                        value[0][i]=i; 
                        value[1][i]=Integer.parseInt(s); 
                        valueNode[0][i]=i; 
                        valueNode[1][i]=Integer.parseInt(s); 
                        } 
                  } 
        void   class1(){ 
        int   i,j,k,m,n; 
        n=num; 
        for(i=0;i <n-2;i++){ 
                k=i; 
                for(j=i+1;j <n-1;j++) 
                        if(valueNode[1][k]> valueNode[1][j]) 
                                k=j; 
                                if(i!=k){ 
                                    m=valueNode[1][i]; 
                                        valueNode[1][j]=valueNode[1][k]; 
                                        valueNode[1][k]=m; 
                                        m=valueNode[0][i]; 
                                        valueNode[0][i]=valueNode[0][k]; 
                                        valueNode[0][k]=m; 
                          
                                } 
                
                } 
        } 
        void   class2(int   m,int   n){ 
        int   i,j,sum; 
        int   arr[][]=new   int[2][num];                         //? 
        sum=arr[1][0]+arr[1][1]; 
        int   number=n-1; 
        boolean   ff=true; 
        for(i=2;i <number;i++){ 
                if(valueNode[1][i] <sum){ 
                        valueNode[1][i-2]=valueNode[1][i]; 
                        valueNode[0][i-2]=valueNode[0][i]; 
                        } 
                else{ 
                                if(ff){ 
                                        valueNode[1][i-2]=sum; 
                                        valueNode[0][i-2]=number-1; 
                                        valueNode[1][i-1]=valueNode[1][i]; 
                                        valueNode[0][i-1]=valueNode[0][i]; 
                                        ff=false; 
                                        } 
                                else{ 
                                        valueNode[1][i-1]=valueNode[1][i]; 
                                        valueNode[0][i-1]=valueNode[0][1]; 
                                        } 
                        } 
                if(ff){ 
                        valueNode[1][num-1]=sum; 
                        valueNode[0][num-1]=number-1; 
                        } 
                } 
        } 
        void   huffbm(){ 
        int   huffVal[][]=new   int[numNode][4]; 
        int   i,j,k,m,num1,num2,val,par; 
        int   mm=num; 
        Huff   huff=new   Huff(); 
                for(i=0;i <numNode;i++){ 
                if(i <num) 
                {huffVal[i][0]=value[1][i];} 
                else 
                huffVal[i][0]=0; 
                huffVal[i][1]=0; 
                huffVal[i][2]=0; 
                huffVal[i][3]=0; 
                } 
                for(i=mm+1;i <=num;i++){                   //? 
                num1=valueNode[0][0]; 
                num2=valueNode[0][1]; 
                val=valueNode[1][0]+valueNode[1][1]; 
                huff.class2(i,mm--); 
                par=i; 
                huffVal[num1][3]=par; 
                huffVal[num2][3]=par; 
                huffVal[par][0]=val; 
                huffVal[par][3]=0; 
                huffVal[par][1]=num1; 
                huffVal[par][2]=num2; 
                } 
        StringBuffer   bm; 
                for(i=0;i <num;i++){ 
                j=1; 
                bm=new   StringBuffer("   "); 
                        par=huffVal[j][4]; 
                        while(par!=0){ 
                        if(huffVal[par][2]==j) 
                        bm.insert(0,'0'); 
                        else 
                        bm.insert(0,'1'); 
                        j=par; 
                        par=huffVal[par][4]; 
                        } 
                System.out.println(bm.toString()); 
                } 
        } 
        public   static   void   main(String   args[])throws   IOException{ 
        Huff   huff=new   Huff(); 
        System.out.print("程序正运行！"); 
        huff.class1(); 
        System.out.print("程序正运行！"); 
        huff.huffbm(); 
        System.out.print("程序正运行！"); 
        }   
}