鵬哥

基于huffman編碼特點建立的一個huffman編/譯碼器，并做了建立簡單的可視化

效果圖

編碼結果圖

壓縮效果圖

凹凸表可視化

二叉樹可視化

問題重述

利用哈夫曼編碼進行信息通信可以較大提高信道利用率,縮短信息傳輸時間,降低傳輸成本。但是,這要求在發送端通過一個編碼系統對待傳數據預先編碼;在接收端將傳來的數據進行譯碼(復原)。對于雙工信道（即可以雙向傳輸信息的信道),每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編譯碼系統。該系統應具有以下功能

1. 初始化（Initialization)。從終端讀入字符集大小n,及n個字符和m個權值,建立哈夫曼樹,并將其保存于磁盤huffman文件中。
2. 編碼(Coding)。利用已建好的哈夫曼樹(如不在內存,則從已保存的 huffman文件中讀入),對帶發送電文(讀取自文件 tobetrans. dat)進行編碼,然后將結果保存于磁盤文件codefile 中。
3. 解碼(Decoding)。利用已建好的哈夫曼樹,對文件codefile中的代碼進行譯碼，結果存入文件textfile中。
4. 打印代碼文件(Print)。將文件codefile顯示在終端上,每行50個代碼。同時將此字符形式的編碼文件寫人文件codeprint 中。
5. 打印哈夫曼樹(Tree printing)。將已在內存中的哈夫曼樹以直觀的方式(樹或凹入表的形式顯示在終端，同時將此字符形式的哈弗曼樹寫入文件treeprint

全局變量

 	static Map<Character, String> huffmanCodes = new HashMap<>()
    static StringBuilder stringBuilder = new StringBuilder();
    static Node huffmanTree
    static String stringtree = "";

這里我們主要是定義一些全局變量方便后面使用：

1. huffmancode ：建立哈希表；
2. stringBuilder ：后面用于翻譯huffman樹；
3. huffmanTree ：huffman樹的根節點；；
4. huffmancode ：建立哈希表；；

自定義List類型

static class MyList<Node> {
        //定義Object類型的數組
        Object[] data ;
        //統計變量，用于統計數組元素的真實個數
        int size;
        public MyList() {
            this(50);
        }
        MyList(int length){
            data = new Object[length];
        }
        //長度
        public int getLength(){
            return size;
        }
        @Override
        public String toString() {
            //構建一個新的數組，長度為size
            Object[] newdata = new Object[size];
            //將data中的元素拷貝到新數組中
            System.arraycopy(data, 0, newdata, 0, size);
            //利用Arrays類，將數組轉換成字符串
            return Arrays.toString(newdata);
        }
        public void remove(Node obj){
            int index = getFirstIndex(obj);
            //System.out.println(index);
            deleteElementByIndex(index);
        }
        public int getFirstIndex(Node  obj){
            for (int i = 0; i < size; i++) {
                if(obj.equals(data[i])){
                    return i;
                }
            }
            return -1;//沒有找到
        }
        //刪除指定索引處的元素
        public void deleteElementByIndex(int index){
            if(index<0||index>size){
                throw new ArrayIndexOutOfBoundsException("數組越界了，索引范圍是：0~"+(size-1));
            }
            System.arraycopy(data, index+1, data, index, size-index-1);
            size--;
        }

        void add(Node obj){
            //如果數組滿了
            if(size>=data.length){
                //構建一個新的數組，容量默認增加10
                Object[] newdata = new Object[data.length+10];
                //將原來的數組內容拷貝到擴容后的數組中
                System.arraycopy(data, 0, newdata, 0, size);
            }
            //將新增的元素添加在數組的末尾
            data[size] = obj;
            //數組真實長度自增1
            size++;
        }
        public void sort()
        {
            Arrays.sort( data);
        }

    }

Node節點類型

這里采用了Comparable類型，因為后面我們采用了Collections的比較。

class Node implements Comparable<Node> {
    Character data; //存放數據
    int weight; //權值,表示字符出現的次數
    Node left;
    Node right;

    public Node() {
    }

    public Node(Character data, int weight) {
        this.data = data;
        this.weight = weight;
   }
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

}

導入字符集數據

 利用Java的字典結構導入數據（利用字典來統計數據也是極快的），將導入的數據變成鏈表的樣式，便于后面的樹建立。

private static ArrayList<Node> getNodes() {
        MyList<Node> rootnode1=new MyList<>();
        ArrayList<Node> node_temp = new ArrayList<>();
        //構建一個map等下存huffman編碼
        Map<Character, Integer> counts = new HashMap<>();
        File zhifuji = new File("D:/Desktop/string.txt");
        try {
            BufferedReader bufferedReader = new BufferedReader(new FileReader(zhifuji));//把讀取的數據給fr
            String line;
            while ((line = bufferedReader.readLine()) != null) {
                String[] strArray = line.split("=");
                counts.put(strArray[0].charAt(0), Integer.valueOf(strArray[1]));
            }
        } catch (FileNotFoundException e2) {
            System.out.println("找不到指定文件");
            System.exit(-1);
        } catch (IOException e1) {
            System.out.println("文件內容讀取錯誤");
            System.exit(-1);
        }
        System.out.println("字符集內容已導入");
        //將統計來的每個鍵值對轉成一個Node對象，并加入到nodes集合
        //遍歷map
        System.out.println("輸入結果展示結果：");
        System.out.println(counts + "\n");
        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            node_temp.add(new Node(entry.getKey(), entry.getValue()));
        }
        return node_temp;
    }

建立huffman樹

建立huffman樹的規則

1. 將所有左，右子樹都為空的作為根節點
2. 在森林中選出兩根節點的權值最小的樹作為一棵樹的左，右子樹，且置新樹的附加根節點的權值為其左，右子樹上根節點的權值之和，其中左子數的權值小于右子樹的權值；
3. 從森林中刪除這兩顆樹，同時把新樹加入到森林中；
4. 重復2，3步驟，直到森林中只有一棵樹為止，此樹便是赫夫曼樹
   

private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //利用collections的接口
            Collections.sort(nodes);
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        //返回根節點
        return nodes.get(0);
    }

根據建立的huffman樹構建出huffmancode

利用已經建立的huffman樹和StringBuilder結構的特點，遞歸得到葉子結點，建立huffmancode

private static void gethuffmancode(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        if (node != null) {
            //判斷當前node是葉子節點還是非葉子節點
            //因為非葉子結點的data為null
            if (node.data == null) {
                //說明是非葉子節點
                //遞歸處理向左遞歸
                //左0右1原則
                gethuffmancode(node.left, "0", stringBuilder2);
                //向右遞歸
                gethuffmancode(node.right, "1", stringBuilder2);
            } else {
                //說明是葉子節點就表示找到了某個葉子節點最后
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }

編碼

利用我們之前得到huffmancode編碼，進行編碼。

private static StringBuilder zip(char[] bytes, Map<Character, String> huffmanCodes) {
        //利用huffman編碼表將傳進來的byte數組轉成huffman編碼的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (char b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        System.out.println("利用huffman編碼得到二進制字符串：\n" + stringBuilder.toString());
        return stringBuilder;
    }

解碼

因為huffman的前綴編碼特點，進行解密

private static List<Character> decode(Map<Character, String> huffmanCodes, StringBuilder huffmanstring) {
        System.out.println("huffman解碼對應的二進制字符串:\n" + huffmanstring.toString());
        //把字符串按照指定的huffman編碼進行解
        //因為把huffman編碼表的k,v進行調換所以要反向查詢
        Map<String, Character> map = new HashMap<>();
        for (Map.Entry<Character, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        List<Character> list =  new ArrayList<>();
        for (int i = 0; i < huffmanstring.length(); ) {
            int count = 1; //小的計數器
            boolean flag = true;
            Character b = null;//前綴編碼不用擔心弄錯
            //這里采用了貪心的策略，盡可能的匹配字節
            while (flag) {
                String key = huffmanstring.substring(i, i + count);
                //System.out.println(key);
                b = map.get(key);
                if (b == null) {
                    count++;
                } else {
                    flag = false;
                }
            }
            list.add(b);
            i += count; //匹配完畢,移動i
        }
        return list;
    }

后續可視化

這里是有個問題，是無法解決的，就是下圖的問題，就是可視化到后面，我們就會發現一個重合的問題，這里這是無法解決的，因為可視化的時候左圖的右子樹會向右延伸，右圖的左子樹會向左延伸，所以說這里的重合是不可避免的，我們只能盡量調整分支的角度使得整個重合盡可能的延緩重合

二叉樹可視化

class Test extends JPanel {
        Node root = HuffmanCode.gethuffmanTree();

public Test() {
//            this.root = HuffmanCode.huffmanTree;
        UI();
        }

private void UI() {
        System.out.println(root.data);
        this.setLayout(new BorderLayout());
        TreeView treeView = new TreeView();
        add(treeView, BorderLayout.CENTER);
        }

class TreeView extends JPanel {
    private int radius = 20;
    private int vGap = 50;

    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        if (root != null) {
            display(g, root, getWidth() / 2, 30, getWidth() / 4);
        }
    }

    private void display(Graphics g, Node root, int x, int y, int hGap) {
        g.drawOval(x - radius, y - radius, 2 * radius, 2 * radius);
        //畫圓
        g.drawString(root.data + "", x - 3, y + 2);//寫值
        //畫線
        if (root.left != null) {
            connectLeftChild(g, x - hGap, y + vGap, x, y);
            display(g, root.left, x - hGap, y + vGap, (int) (hGap / Math.pow(2, 1)));
        }
        if (root.right != null) {
            connectRightChild(g, x + hGap, y + vGap, x, y);
            display(g, root.right, x + hGap, y + vGap, (int) (hGap / Math.pow(2, 1)));
        }
    }

    private void connectRightChild(Graphics g, int x1, int y1, int x2, int y2) {
        // TODO Auto-generated method stub
        double d = Math.sqrt((y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1));
        int x11 = (int) (x1 - radius * (x1 - x2) / d);
        int y11 = (int) (y1 - radius * vGap / d);
        int x21 = (int) (x2 + radius * (x1 - x2) / d);
        int y21 = (int) (y2 + radius * vGap / d);
        g.drawLine(x11, y11, x21, y21);
    }

    private void connectLeftChild(Graphics g, int x1, int y1, int x2, int y2) {
        // TODO Auto-generated method stub
        double d = Math.sqrt(vGap * vGap + (x2 - x1) * (x2 - x1));
        int x11 = (int) (x1 + radius * (x2 - x1) / d);
        int y11 = (int) (y1 - radius * vGap / d);
        int x21 = (int) (x2 - radius * (x2 - x1) / d);
        int y21 = (int) (y2 + radius * vGap / d);
        g.drawLine(x11, y11, x21, y21);
    }
}

至此我們的huffman編碼問題已經是幾乎百分百解決了，下面我們給出總的main函數

public static void main(String[] args){
     /*   第一步：判斷文件huffmantree是否存在
        第二步：根據字符集創建huffman樹
        第三步：根據huffman樹生成對應的huffman編碼，利用map的鍵對值很方便
        第四步：根據huffman編碼壓縮，生成huffman字節數組
        第四步：解碼，根基huffmancode進行解碼*/
        File huffmanfile = new File("D:/Desktop/huffman.txt");
        if (!huffmanfile.exists()) {
            List<Node> nodes = getNodes();
            huffmanTree = createHuffmanTree(nodes);
            gethuffmancode(huffmanTree, "", stringBuilder);//得到huffman編碼
            //如果huffman code 不存在就寫入
            try {
                String line = System.getProperty("line.separator");
                StringBuilder str = new StringBuilder();
                BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(huffmanfile));  //把添加的內容添加到末尾
                Set<Map.Entry<Character, String>> set = huffmanCodes.entrySet();
                for (Map.Entry<Character, String> entry : set) {
                    str.append(entry.getKey()).append(":").append(entry.getValue()).append(line);
                }
                bufferedWriter.write(str.toString());
                bufferedWriter.flush(); //清空緩存區
                bufferedWriter.close();
            } catch (FileNotFoundException e2) {
                System.out.println("找不到指定文件");
                System.exit(-1);
            } catch (IOException e1) {
                System.out.println("文件內容寫入錯誤");
                System.exit(-1);
            }
            System.out.println("huffmancode已寫入");
        } else {
            try {
                BufferedReader bufferedReader = new BufferedReader(new FileReader(huffmanfile));//把讀取的數據給fr
                String line;
                while ((line = bufferedReader.readLine()) != null) {
                    String[] strArray = line.split(":");
                    huffmanCodes.put(strArray[0].charAt(0), strArray[1]);
                }
            } catch (FileNotFoundException e2) {
                System.out.println("找不到指定文件");
                System.exit(-1);
            } catch (IOException e1) {
                System.out.println("文件內容讀取錯誤");
                System.exit(-1);
            }
            System.out.println("huffmancode已導入");
        }
        //huffman樹已建立
        System.out.println("huffman編碼表：");
        System.out.println(huffmanCodes + "\n");
//        System.out.println("請輸入想要進行編碼的字符串(目前只支持大寫英文字符和-)");
//        Scanner scanner = new Scanner(System.in);
//        String content = scanner.nextLine();
        StringBuilder content = new StringBuilder("");
        try {
            BufferedReader bufferedReader = new BufferedReader(new FileReader("D:/Desktop/tobetrans.dat"));//把讀取的數據給fr
            String line;
            while ((line = bufferedReader.readLine()) != null) {
                content.append(line);
            }
        } catch (FileNotFoundException e2) {
            System.out.println("找不到指定文件");
            System.exit(-1);
        } catch (IOException e1) {
            System.out.println("文件內容讀取錯誤");
            System.exit(-1);
        }
        System.out.println("content已導入");
        char[] contentbytes = content.toString().toCharArray();
        StringBuilder stringBuilder = zip(contentbytes, huffmanCodes);//壓縮
        try {
            BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("D:/Desktop/codefile.txt", false));  //把添加的內容添加到末尾
            bufferedWriter.write(stringBuilder.toString());//寫入編碼的結果
            bufferedWriter.flush(); //清空緩存區
            bufferedWriter.close();
        } catch (FileNotFoundException e2) {
            System.out.println("找不到指定文件");
            System.exit(-1);
        } catch (IOException e1) {
            System.out.println("文件內容寫入錯誤");
            System.exit(-1);
        }
        System.out.println();
        System.out.println("壓縮后的編碼寫入完成");

        System.out.println("壓縮后的結果: \n" + stringBuilder.toString());//解壓
        List<Character> decodecontent = decode(huffmanCodes, stringBuilder);//解壓
        try {
            BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("D:/Desktop/textfile.txt", false));  //把添加的內容添加到末尾
            bufferedWriter.write(String.valueOf(decodecontent));//寫入譯碼的結果
            bufferedWriter.flush(); //清空緩存區
            bufferedWriter.close();
        } catch (FileNotFoundException e2) {
            System.out.println("找不到指定文件");
            System.exit(-1);
        } catch (IOException e1) {
            System.out.println("文件內容寫入錯誤");
            System.exit(-1);
        }
        System.out.println();
        System.out.println("content解碼后的文件寫入完成");
        System.out.println("解碼后的字符串：");
        try {
            BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("D:/Desktop/codeprint.txt", false));  //把添加的內容添加到末尾
            int nextline = 0;
            Iterator iterator = decodecontent.iterator();
            while (iterator.hasNext()) {
                nextline++;
                Character temp = (Character) iterator.next();
                System.out.print(temp);
                bufferedWriter.write(temp);//寫入譯碼的結果
                if (nextline % 50 == 0) {
                    bufferedWriter.write("\n");
                    System.out.println();
                }
            }
            bufferedWriter.flush(); //清空緩存區
            bufferedWriter.close();
        } catch (FileNotFoundException e2) {
            System.out.println("找不到指定文件");
            System.exit(-1);
        } catch (IOException e1) {
            System.out.println("文件內容寫入錯誤");
            System.exit(-1);
        }
        System.out.println();
        System.out.println("50字符形式的文件寫入完成");
        JFrame jFrame = new JFrame("Tree GUI");
        System.out.printf(String.valueOf(huffmanTree));
        jFrame.add(new Test());
        jFrame.setSize(1980, 1280);
        jFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        jFrame.setLocationRelativeTo(null);
        jFrame.setVisible(true);
        File file = new File("D:/Desktop/huffman.txt");
        if (file.exists()) {
            file.delete();
            System.out.println("刪除成功");
        }
        Print(huffmanTree, "");
        try {
            BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("D:/Desktop/treeprint.txt", false));
            bufferedWriter.write(stringtree);
            bufferedWriter.flush(); //清空緩存區
            bufferedWriter.close();
        } catch (FileNotFoundException e2) {
            System.out.println("找不到指定文件");
            System.exit(-1);
        } catch (IOException e1) {
            System.out.println("文件內容寫入錯誤");
            System.exit(-1);
        }
    }

鏈接: 完整代碼下載鏈.