哈夫曼树压缩和解压缩

阳光穿透心脏的1/2处 2022-04-22 23:22 198阅读 0赞

今天的主题是哈夫曼树的编码，译码和压缩，解压缩，以及用java里的压缩包等

基础的哈夫曼树分为一下几个部分
    第一步：建立哈夫曼树
    利用哈夫曼树思想，每次取两个最小值加到树上，以此循环直至结束
    
    第二步：对哈夫曼树进行编码
    编码是根据自底向上原则，从叶子节点开始往上找直至找到数根节点，并用路径进行编码（0或者1）最终形成的激素哈夫曼编码
    第三步：对哈夫曼编码进行译码
    译码则与编码是相反的，译码采用的是自顶向下原则，从树根依据唯一的编码路径对树查找它的叶子节点而实现译码
    第四不：压缩和解压缩，利用计算机底层原理，将0和1转为最合适（占空间）最小的单位存取进而实现压缩，解压缩则和压缩相对。

实现书节点的建立，这个很简单就不多说了
    public class Node<T> implements Comparable<Node<T>> {
        private T data;
        private int weight;
        private Node<T> left;
        private Node<T> right;
        private Node<T> parent;
        public Node(T data, int weight) {
            this.data = data;
            this.weight = weight;
        }
        @Override
        public String toString() {
            return "data:" + this.data + ",weight:" + this.weight + ";   ";
        }
        @Override
        public int compareTo(Node<T> o) {
            if (o.weight > this.weight) {
                return 1;
            } else if (o.weight < this.weight) {
                return -1;
            }
            return 0;
        }
        public T getData() {
            return data;
        }
        public void setData(T data) {
            this.data = data;
        }
        public int getWeight() {
            return weight;
        }
        public void setWeight(int weight) {
            this.weight = weight;
        }
        public Node<T> getLeft() {
            return left;
        }
        public void setLeft(Node<T> left) {
            this.left = left;
        }
        public Node<T> getRight() {
            return right;
        }
        public void setRight(Node<T> right) {
            this.right = right;
        }
        public void setParent(Node<T> parent) {
            this.parent = parent;
        }
        public Node getParent() {
            return parent;
        }
    }

这段代码实现的是树的建立，用的是Collection的sort方法排序，当然你也可以自己写更好的排序算法，然后也是些最基本的东西
    public static <T> Node<T> createTree(List<Node<T>> nodes) {
            while (nodes.size() > 1) {
                Collections.sort(nodes);
                Node<T> left = nodes.get(nodes.size() - 1);
                Node<T> right = nodes.get(nodes.size() - 2);
                Node<T> parent = new Node<>(null, left.getWeight() + right.getWeight());
                left.setParent(parent);//存储父子关系
                right.setParent(parent);
                parent.setLeft(left);
                parent.setRight(right);
                nodes.remove(left);
                nodes.remove(right);
                nodes.add(parent);
            }
            nodes.get(0).setParent(null);
            return nodes.get(0);
        }

这段是对树进行编码的代码，我将每一个节点编码存到字符串数组里取，编码中最核心的部分也就是最重要的部分就是将编码好的字符串逆转，我就犯过这个毛病哈哈
     public static <T> String[] HuffmanCode(List<Node<T>> nodes) {
            String[] code = new String[nodes.size()];//用来存取每一个节点的哈夫曼编码
            Node<T>[] nodes1 = (Node<T>[]) nodes.toArray(new Node[nodes.size() - 1]);
            for (int j = 0; j < nodes1.length; j++) {
                code[j] = "";
                Node parent = nodes1[j].getParent();
                while (parent != null) {
                    if (parent.getLeft() == nodes1[j]) {
                        code[j] = code[j] + "0";
                    }
                    if (parent.getRight() == nodes1[j]) {
                        code[j] = code[j] + "1";
                    }
                    nodes1[j] = parent;
                    parent = nodes1[j].getParent();
                }
            }
            return code;
        }

这段是实现译码的方法，根据0和1来判断要走的路径，碰到节点就存起来或者拼接起来，自顶向下的依次访问
     public static String Decoding(String code, Node root) {
            StringBuffer stringBuffer = new StringBuffer();
            char[] codes = code.toCharArray();
            Node e = root;
            System.out.print("文件译码为：");
            for (int i = 0; i < codes.length; i++) {
                if (codes[i] == '0') {
                    root = root.getLeft();
                    if (root.getRight() == null && root.getLeft() == null) {
                        stringBuffer.append(root.getData());
                        System.out.print(root.getData());
                        root = e;
                    }
                } else {
                    root = root.getRight();
                    if (root.getRight() == null && root.getLeft() == null) {
                        System.out.print(root.getData());
                        stringBuffer.append(root.getData());
                        root = e;
                    }
                }
            }
            System.out.println("\n");
            return stringBuffer.toString();
        }

有些同学可能会有有些疑问，为什么自己压缩了之后浪费的空间反而更多了呢？
    为什么哈夫曼编码要编为0和1的编码呢？
    大家有没有仔细的想过这个问题呢，压缩不可能会越压越大吧，下面我就说一说这其中的奥秘
    在计算机中不管是在Java中的一些数据类型都基本思以字节为单位计数的，因此如果用几个或者一个字节来存取哈夫曼编码的0和1是不是有些浪费呢？
    答案是肯定的，在计算机中比字节更小的单位是什么呢，是比特，转为0和1的好处就是可以进一步的把它压缩让它占用更少的空间，我们可以把8位0或1（比特）压缩到一个字节里去，那这样是不是就节省了很多的空间呢。
    因此我下边的编写压缩原理是根据上述理论，但是我当时没有想到这一点，因此我的压缩效率不如这个方法，但是原理都是一样的。
    我采用的是将四个字节压缩为一个字节，也就是所进制的转换（2to16）
    public static String Turn2T016(String CodeFile) throws Exception {
    
            /**
             * @param StringBuffer 可以用栈来替换实现功能
             *@param Tlenth 从文件读出来的字节长度
             * @param leave 给长度取余留下的值
             * @Tstring 编码的实际内容
             * @s  编码内容加上编码头
             *              增加文件头记录文件
             * 以*作为分割点，*前面记录它压缩前的二进制个数
             *  之后要加上他的前缀标志Ox
             * */
    //    List<String> stack = new Stack<>();
            String text = ReadFile.Getfileout(CodeFile);
            System.out.println("text:" + text);
            Integer Tlenth = text.length();
            String Tstring = "";
            int leave;//保存取余数后的值
            leave = text.length() % 4;
            System.out.println("leave:" + leave);
            if (leave == 0) {
                for (int i = text.length(); i - 4 >= 0; i = i - 4) {
                    String s = text.substring(i - 4, i);
                    int tem = Integer.parseInt(s, 2);
                    Tstring = Integer.toHexString(tem).toUpperCase() + Tstring;
    //                stack.add(s);
                }
                StringBuffer buffer = new StringBuffer();
    
            } else {
                for (int i = text.length(); i - 4 >= 0; i = i - 4) {
                    String s = text.substring(i - 4, i);
    //                stack.add(s);
                    int tem = Integer.parseInt(s);
    //                int tem = Integer.parseInt(String.valueOf(s), 2);
                    Tstring = Integer.toHexString(tem).toUpperCase() + Tstring;
                }
    
                StringBuffer stringBuffer = new StringBuffer();
                for (int i = 0; i < 4 - leave; i++) {
                    stringBuffer = stringBuffer.append("0");
    
                }
                String s = stringBuffer.append(text.substring(0, leave)).toString();
                int tem = Integer.parseInt(String.valueOf(s), 2);
                Tstring = Integer.toHexString(tem).toUpperCase() + Tstring;
    //        stack.add(s);
            }
    
            StringBuffer stringBuffer = new StringBuffer();
            stringBuffer.append(Tlenth + "*");
            String s = stringBuffer.append(Tstring).toString();
            return s;
    
        }
    
    
    
    
    
    解压缩的实现
     public static String Turn16To2(String s) {
    
            StringBuffer stringBuffer1 = new StringBuffer();
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                String tem = Integer.toBinaryString(Integer.parseInt(s.substring(i, i + 1), 16));
                // System.out.println("tem:" + tem);
                int leave = 4 - tem.length();//计算需要补0的个数
                StringBuffer stringBuffer = new StringBuffer();
                for (int j = 0; j < leave; j++) {
                    stringBuffer.append('0');
                }
                String Tcode = stringBuffer.append(tem).toString();
                // System.out.println("Tcode:" + Tcode);
                stringBuffer1.append(Tcode);
                // System.out.println("sb in:" + stringBuffer1.toString());
            }
                // String s1 = stringBuffer1.toString();
                //System.out.println("sb1" + s);
            return stringBuffer1.toString();
    
        }