Qz学算法-数据结构篇(哈夫曼树&哈夫曼编码)

哈夫曼树1.基本介绍

• 给定n个权值作为叶结点，构建二叉树，如果树的带权路径长度(wpl)达到最小，称这样的二叉树为最佳二叉树，也称哈夫曼树Huffman Tree,还有一些书被翻译成霍夫曼树。
• 赫夫曼树是带权路径长度最短的树，权值较大的结点靠近根部。

• 路径和路径长度：在一棵树上，儿童或孙子从一个结点向下可以到达的路径称为路径。路径中分支的数量称为路径长度。如果根点的层数为1，则从根点到第L层结点的路径长度为L-1
• 结点的权利和权利路径长度：如果将树中的结点赋予具有一定意义的值，则该值称为结点的权利。结点的权利路径长度为：从根点到结点之间的路径长度和结点的权利乘积
• 树的带权路径长度：树的带权路径长度规定为所有叶结点的带权路径长度之和，记为WPL(weighted path length),权值越大，离根点越近的二叉树是最好的二叉树。
• 最小的WPL是赫夫曼树

构成赫夫曼树的步骤：

1)从小到大排序，每个数据，每个数据都是一个节点，每个节点都可以看作是最简单的二叉树

2)取出根节点权值最小的两棵二叉树

3)形成新的二叉树，新的二叉树根节点的权重是前两个二叉树根节点的权重和

4)然后将新的二叉树按根节点的权重排序，重复1-2-3-4的步骤，直到数列中处理所有数据，获得赫夫曼树

package huffmantree;import java.util.ArrayList;import java.util.Collections;import java.util.List;/** * @author LeeZhi * @version 1.0 */public class HuffmanTree {    public static void main(String[] args) {        int arr[] = {13,7,8,3,29,6,1};        Node node = createHuffmanTree(arr);        ///测试一个        preOrder(node);    }    ////编写前序遍历的方法    public static void preOrder(Node root){        if (root!=null){            root.preOrder();        }else{            System.out.println()是空树，不能遍历~");        }    }    ////创建赫夫曼树的方法    /**     *     * @param arr 需要创建成哈夫曼树的数组     * @return 赫夫曼树的root节点创建后     */    public static Node createHuffmanTree(int []arr){        //第一步，操作方便        /1.遍历arrr数组        //2.将arr的每个元素构成Node        //3.将Node放入ArrayList中        List<Node>nodes = new ArrayList<Node>();        for(int value:arr){            nodes.add(new Node(value));        }        ///我们处理的过程是一个循环过程        while(nodes.size()>1){            //从小到大排序            Collections.sort(nodes);            System.out.println("nodes="+nodes);            ///取出根节点权值最小的两棵二叉树            //(1)取出权值最小的节点(二叉树)            Node leftNode = nodes.get(0);            //(2)取出权值第二小的节点(二叉树)            Node rightNode = nodes.get(1);            //(3)构建一颗心的二叉树            Node parent = new Node(leftNode.value+rightNode.value);            parent.left = leftNode;            parent.right = rightNode;            //(4)从ArrayList删除处理过的二叉树            nodes.remove(leftNode);            nodes.remove(rightNode);            //(5)将parent添加到nodes中            nodes.add(parent);        }        ///回到哈夫曼树的root节点        return nodes.get(0);    }}//创建结点类// 对象继续排序Collection集合排序//让Node实现Comparable接口classs Node implements Comparable<Node>{    int value;///节点权值    Node left;//指向左节点    Node right;//指向右子节点    //写一个前序遍历    public void preOrder(){        System.out.println(this);        if (this.left!=null){            this.left.preOrder();        }        if (this.right!=null){            this.right.preOrder();        }    }    public Node(int value) {        this.value = value;    }    @Override    public String toString() {        return "Node{" +                "value=" + value +                '}';    }    @Override    public int compareTo(Node o) {        //表示从小到大排序        return this.value-o.value;    }}

1)赫夫曼编码也被翻译成哈夫曼编码(Huffman Coding),霍夫曼编码，又称霍夫曼编码，是一种编码方法，属于程序算法2)赫夫曼编码是赫哈夫曼树在电信通信中的经典应用之一。3)赫夫曼编码广泛应用于数据文件压缩。赫夫曼代码的压缩率通常在20%~90%之间(LC)的一种。1952年，Huffman提出了一种编码方法，称为最佳编码

信息在通信领域的处理方法1-定长编码

• i like like like java do you like a java∥共40个字符(包括空格)
• 105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 9732 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 /对应Ascii码
• 01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 0110010100100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 ///对应的二进制
• 按二进制传递信息，总长度为359(包括空格)
• 在线转码工具：hhtps://www.mokuge.com/tool/ascito16/

信息在通信领域的处理方法2-变长编码

• i like like like java do you like a java//40个字符(包括空格)
• d:1 y:1 u:1 j:2 v:2 o:2 I:4 k:4 e:4 i:5 a:5 :9 ////每个字符对应的个数
• 0=,1=a,10=i,11=e,100=k,101=l,110=0,111=V,1000=j,1001=u,1010=y,1011=d描述:根据每个字符出现的次数进行编码。原则是出现的次数越多，编码就越小。例如，空间出现9次，编码为0，其他类似.
• 按照上述字符规定的编码，我们正在传输“i like like like java do you like a java“数据时，编码是10010110100.
• 字符编码不能是其他字符编码的前缀。符合这一要求的编码称为前缀编码，即不能与重复编码相匹配

信息在通信领域的处理方法3-赫夫曼编码

///根据赫夫曼树，每个字符//规定编码，左路径0///右路径1，编码如下：o:1000 u:10010 d:100110 y:100111 i:101 a:110 k:1110 e:1111 j:0000 v:0001 I:001 :01根据上述赫夫曼编码，我们的"i like like like javado you like a java字符串对应的编码为(注意这里我们使用的无损压缩)101010110110110110110110110110110110110011000110001100110011001100011001100110011001100110011011001010101010101010010010100101001001010010010010010010010010010010100101010101010101010100101010010101001001010010010101010101010101010101010101010101010101010101010101010110101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010

长度为：133

说明：

1)原长度为359，压缩(359-133)/359=62.9%

2)本编码满足前斑编码，即字符编码不能是其他字符编码的前缀。不会导致匹配的多义性

思路

(1)Node{data存储数据，weight{权值}，left和right}

(2)得到"i likelikelike java do you like a java“相应的byte[]数组

(3)写一个方法，把准备建造赫夫曼树的Node节点放在List上，形式[Node[date='7!weight=5],Node[]date=32,weight =9]...d:1 y:1 u:1 j:2 v:2 o:2 1:4 k:4 e:4 i:5 a:5 :9

(4)相应的赫夫曼树可以通过List创建

package huffmantree;import java.nio.charset.StandardCharsets;import java.util.*;/** * @author LeeZhi * @version 1.0 */public class HuffmanCode {    public static void main(String[] args) {        String str = "i like like like java do you like a java";        byte[] contentBytes = str.getBytes(StandardCharsets.UTF_8);        System.out.println(contentBytes.length);//40        List<Node> nodes = getNodes(contentBytes);        System.out.println("nodes:"+nodes);        ///测试一个，二叉树        System.out.println(赫夫曼树);        Node huffmanTreeRoot = createHuffmanTree(nodes);        System.out.println(“前序遍历”);        huffmanTreeRoot.preOrder();        ///测试生成        getCodes(huffmanTreeRoot,"",stringBuilder);        System.out.println(生成的huffmam编码表”+huffmanCodes);    }    ///生成哈夫曼树对应的哈发满编码    //思路    //1.将哈夫曼编码表存储在Map中<Byte,String> 形式    // 32-> =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=11111 l=0000 o=0011    static Map<Byte,String> huffmanCodes = new HashMap<>();    //2.生成哈夫曼编码表时，需要拼接路径，Stringbuilder定义 存储叶子节点的路径    static StringBuilder stringBuilder = new StringBuilder();    ///为了方便调用，我们重载getcodes    private static Map<Byte,String> getCodes(Node root){        if (root == null){            return null;        }        ///处理root左子树        getCodes(root.left,"0",stringBuilder);        ///处理rot右子树        getCodes(root.right,"1",stringBuilder);        return huffmanCodes;    }    /**     * 功能：将传入node节点的所有叶子节点的哈夫曼编码，将蛋糕放入huffmancodes集合     * @param node 传入节点     * @param code 路径: 左子结点是0 右子结点1     * @param stringBuilder 用于拼接路径     */    private static void getCodes(Node node,String code,StringBuilder stringBuilder){        StringBuilder stringbuilder2 = new StringBuilder(stringBuilder);        ///code 加入到stringbuilder2        stringbuilder2.append(code);        if (node!=null){ /如果node=nulll不处理            ///目前单端node是叶结点还是非叶结点？            if (node.data == null){//非叶结点                ///递归处理                //向左                getCodes(node.left,“0”，stringbuilder2);                ///向右递归                getCodes(node.right,"1",stringbuilder2);            }else{                //说明是叶子的结点                ///意味着找到某个叶结点的最后                huffmanCodes.put(node.data,stringbuilder2.toString());            }        }    }    ///前序遍历    private static void preOrder(Node root){        if(root!=null){            root.preOrder();        }else{            System.out.println(“赫夫曼树为空”;        }    }    private static List<Node> getNodes(byte[] bytes){        //1.创建ArrayList        ArrayList<Node> nodes = new ArrayList<>();        //遍历bytes 统计每个byte出现的次数 ->map[key,value]        Map<Byte,Integer> counts = new HashMap<>();        for (byte b:bytes) {            Integer count = counts.get(b);            if (count==null){//Map还没有这个字符数据，第一次                counts.put(b,1);            }else{                counts.put(b,count+1);            }        }        ///将每个键对转换成一个Node对象，加入道nodes集合        for (Map.Entry<Byte,Integer> entry:counts.entrySet()){            nodes.add(new Node(entry.getKey(), entry.getValue()));        }        return nodes;    }    //通过List 与哈夫曼树相对应    private static Node createHuffmanTree(List<Node> nodes){        while(nodes.size()>1){            //排序,从小到大            Collections.sort(nodes);            ///取出第一棵最小的二叉树            Node leftNode = nodes.get(0);            ///取出第二课醉倒的二叉树            Node rightNode = nodes.get(1);            //创造新的二叉树，他的根节点，没有data，只有权值            Node parent = new Node(null, leftNode.weight+rightNode.weight);            parent.left=leftNode;            parent.right=rightNode;            ///从nodes删除已处理的两棵二叉树            nodes.remove(leftNode);            nodes.remove(rightNode);            ///你将是新的二叉树，加入nodes            nodes.add(parent);        }        //nodes 最后一个节点是哈夫曼树的根节点        return nodes.get(0);    }}///创建Node，带数据和权值class Node implements Comparable<Node>{    Byte data;//存储数据本身，比如'a'=>97 ' '=>32    int weight;//权值    Node left;    Node right;    public Node(Byte data, int weight) {        this.data = data;        this.weight = weight;    }    @Override    public int compareTo(Node o) {        //从小到大排序        return this.weight-o.weight;    }    @Override    public String toString() {        return "Node{" +                "data=" + data +                ", weight=" + weight +                ", left=" + left +                ", right=" + right +                '}';    }    ///前序遍历    public void preOrder(){        System.out.println(this);        if (this.left!=null){            this.left.preOrder();        }        if (this.right!=null){            this.left.preOrder();        }        if (this.right!=null){            this.right.preOrder();        }    }}