@

目录

• 效果图
  • 编码结果图
  • 压缩效果图
  • 凹凸表可视化
  • 二叉树可视化
• 问题重述
• 全局变量
• 自定义List类型
• Node节点类型
• 导入字符集数据
• 建立huffman树
• 根据建立的huffman树构建出huffmancode
• 编码
• 解码
• 后续可视化
  • 二叉树可视化

基于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);
        }
    }

链接: 完整代码下载链接.