ハフマン符号化による書き込みデータ圧縮解凍ソフトウェア(java実装)

20602 ワード

何人かの他のクラスの学生がjavaの課程の設計を書いているのを見て、書いたのはすべて各種の小さいゲームで、私も書きたいと思っていますが、私は小さいゲームを書きたくなくて、長い間考えてやっとこのデータの圧縮を書くことを考えました.それから資料を調べて書いたが、私のクラスにはカリキュラム設計がないことに気づいたので、インタフェースを追加しなかった.書き終わった後も収穫があり、データ圧縮方法に対する印象を完全に更新しました.以前はデータ圧縮が0000000111100111で6041031と表現されていると思っていたが、メモリに格納されているのは符号化であることが分かった.私が書くときに使うのは、圧縮できるファイルの体積を制限する整数表現のファイル長です.BigIntegerに置き換えると、より大きなファイルを圧縮できます.参考資料:http://www.cnblogs.com/keke2014/p/3857335.html
ソースのダウンロード:http://download.csdn.net/detail/gyhguoge01234/9696065
HuffmanCompress.java:
import java.util.*;
import java.io.*;

public class HuffmanCompress {

    private PriorityQueue queue = null;

    //    
    public void compress(File inputFile, File outputFile){

        Compare cmp = new Compare();
        queue = new PriorityQueue(12,cmp);

        //              
        HashMap map = new HashMap();
        //            
        int i,char_kinds = 0;
        int char_temp,file_len = 0;
        FileInputStream fis = null;
        FileOutputStream fos = null;
        ObjectOutputStream oos = null;
        //        
        int node_num;
        HufTree[] huf_tree = null;
        String code_buf = null;

        //           
        TmpNode[] tmp_nodes = new TmpNode[256];

        for(i = 0; i < 256; ++i){
            tmp_nodes[i] = new TmpNode();
            tmp_nodes[i].weight = 0;
            tmp_nodes[i].uch = (byte)i;
        }

        try {
            fis = new FileInputStream(inputFile);
            fos = new FileOutputStream(outputFile);
            oos = new ObjectOutputStream(fos);
            //      ,      
            while((char_temp = fis.read()) != -1){
                ++tmp_nodes[char_temp].weight;
                ++file_len;
            }
            fis.close();
            Arrays.sort(tmp_nodes);
            //         0         ,       0   
            //          
            for(i = 0; i < 256; ++i){
                if(tmp_nodes[i].weight == 0)
                    break;
            }
            char_kinds = i;

            //         
            if(char_kinds == 1){
                oos.writeInt(char_kinds);
                oos.writeByte(tmp_nodes[0].uch);
                oos.writeInt(tmp_nodes[0].weight);
            //         
            }else{
                node_num = 2*char_kinds-1;//            
                huf_tree = new HufTree[node_num];
                for(i = 0; i < char_kinds; ++i){
                    huf_tree[i] = new HufTree();
                    huf_tree[i].uch = tmp_nodes[i].uch;
                    huf_tree[i].weight = tmp_nodes[i].weight;
                    huf_tree[i].parent = 0;

                    huf_tree[i].index = i;
                    queue.add(huf_tree[i]);
                }
                tmp_nodes = null;

                for(; i < node_num; ++i){
                    huf_tree[i] = new HufTree();
                    huf_tree[i].parent = 0;
                }
                //      
                createTree(huf_tree, char_kinds, node_num,queue);
                //       
                hufCode(huf_tree, char_kinds);
                //      
                oos.writeInt(char_kinds);
                for(i = 0; i < char_kinds; ++i){
                    oos.writeByte(huf_tree[i].uch);
                    oos.writeInt(huf_tree[i].weight);

                    map.put(huf_tree[i].uch, huf_tree[i].code);
                }
                oos.writeInt(file_len);
                fis = new FileInputStream(inputFile);
                code_buf = "";
                //                        
                while((char_temp = fis.read()) != -1){

                    code_buf += map.get((byte)char_temp);

                    while(code_buf.length() >= 8){
                        char_temp = 0;
                        for(i = 0; i < 8; ++i){
                            char_temp <<= 1;
                            if(code_buf.charAt(i) == '1')
                                char_temp |= 1;
                        }
                        oos.writeByte((byte)char_temp);
                        code_buf = code_buf.substring(8);
                    }
                }
                //        8    , 0  
                if(code_buf.length() > 0){
                    char_temp = 0;
                    for(i = 0; i < code_buf.length(); ++i){
                        char_temp <<= 1;
                        if(code_buf.charAt(i) == '1')
                            char_temp |= 1;
                    }
                    char_temp <<= (8-code_buf.length());
                    oos.writeByte((byte)char_temp);
                }
            }
            oos.close();
            fis.close();
        } catch (Exception e) { 
            e.printStackTrace();
        }

    }

    //    
    public void extract(File inputFile, File outputFile){
        Compare cmp = new Compare();
        queue = new PriorityQueue(12,cmp);

        int i;
        int file_len = 0;
        int writen_len = 0;
        FileInputStream fis = null;
        FileOutputStream fos = null;
        ObjectInputStream ois = null;

        int char_kinds = 0;
        int node_num;
        HufTree[] huf_tree = null;
        byte code_temp;
        int root;
        try{
            fis = new FileInputStream(inputFile);
            ois = new ObjectInputStream(fis);
            fos = new FileOutputStream(outputFile);

            char_kinds = ois.readInt();

            //         
            if(char_kinds == 1){
                code_temp = ois.readByte();
                file_len = ois.readInt();
                while((file_len--) != 0){
                    fos.write(code_temp);
                }
            //         
            }else{
                node_num = 2 * char_kinds - 1; //            
                huf_tree = new HufTree[node_num];
                for(i = 0; i < char_kinds; ++i){
                    huf_tree[i] = new HufTree();
                    huf_tree[i].uch = ois.readByte();
                    huf_tree[i].weight = ois.readInt();
                    huf_tree[i].parent = 0;

                    huf_tree[i].index = i;
                    queue.add(huf_tree[i]);
                }
                for(;i < node_num; ++i){
                    huf_tree[i] = new HufTree();
                    huf_tree[i].parent = 0;
                }
                createTree(huf_tree, char_kinds, node_num,queue);

                file_len = ois.readInt();
                root = node_num-1;
                while(true){
                    code_temp = ois.readByte();
                    for(i = 0; i < 8; ++i){
                        if((code_temp & 128) == 128){
                            root = huf_tree[root].rchild;
                        }else{
                            root = huf_tree[root].lchild;
                        }

                        if(root < char_kinds){
                            fos.write(huf_tree[root].uch);
                            ++writen_len;
                            if(writen_len == file_len) break;
                            root = node_num - 1; //         ,       
                        }
                        code_temp <<= 1;
                    }
                    //                         0
                    //      ,   0                        
                    //         0       ,                          
                    //         0   
                    if(writen_len == file_len) break;
                }
            }
            fis.close();
            fos.close();
        }catch(Exception e){
            e.printStackTrace();
        }

    }

    //      
    public void createTree(HufTree[] huf_tree, int char_kinds, int node_num,PriorityQueue queue){
        int i;
        int[] arr = new int[2];
        for(i = char_kinds; i < node_num; ++i){
            arr[0] = queue.poll().index;
            arr[1] = queue.poll().index;
            huf_tree[arr[0]].parent = huf_tree[arr[1]].parent = i;
            huf_tree[i].lchild = arr[0];
            huf_tree[i].rchild = arr[1];
            huf_tree[i].weight = huf_tree[arr[0]].weight + huf_tree[arr[1]].weight;

            huf_tree[i].index = i;
            queue.add(huf_tree[i]);
        }
    }

    //       
    public void hufCode(HufTree[] huf_tree, int char_kinds){
        int i;
        int cur,next;

        for(i = 0; i < char_kinds; ++i){
            String code_tmp = "";
            for(cur = i,next = huf_tree[i].parent; next != 0; cur = next,next = huf_tree[next].parent){
                if(huf_tree[next].lchild == cur)
                    code_tmp += "0";
                else
                    code_tmp += "1";
            }
            huf_tree[i].code = (new StringBuilder(code_tmp)).reverse().toString();
        }
    }
}

HufTree.java:

//      
public class HufTree{
    public byte uch; // 8       
    public int weight;//            
    public String code; //        
    //            
    //      index             
    //                       
    public int index; 
    public int parent,lchild,rchild;

    /**        **/
    public String toString(){
        return "uch:" + uch + ",weight:" + weight + ",code:" + code + ",parent:" + parent + ",lchild:" + lchild + ",rchild:" + rchild;
    }
}

//           
class TmpNode implements Comparable{
    public byte uch;
    public int weight;

    @Override
    public int compareTo(TmpNode arg0) {
        if(this.weight < arg0.weight)
            return 1;
        else if(this.weight > arg0.weight)
            return -1;
        return 0;
    }
}

Compare.java:
import java.util.*;

//      
public class Compare implements Comparator<HufTree>{

    @Override
    public int compare(HufTree o1, HufTree o2) {
        if(o1.weight < o2.weight)
            return -1;
        else if(o1.weight > o2.weight)
            return 1;
        return 0;
    }

}

テスト:
import java.io.*;

//  
public class Test {

    public static void main(String[] args){
        HuffmanCompress sample = new HuffmanCompress();
        File inputFile = new File("gyh.txt");
        File outputFile = new File("gyh.rar");
        sample.compress(inputFile, outputFile);
//      File inputFile = new File("gyh.rar");
//      File outputFile = new File("hyq.txt");
//      sample.extract(inputFile, outputFile);
    }
}