哈夫曼编码详解（Java实现，详细代码及解析）

本是古典何须时尚 2023-03-13 15:21 12阅读 0赞

哈夫曼编码过程以及实例：  
由上篇文章[哈夫曼树与哈夫曼编码原理分析][Link 1]，设置一个字符串“aasdf ghjkd hsgaf sfdga ahsjh g”  
统计一下各字符出现的频率k,1 f,2 j,2 d,3 h,4 a,5 s,4 g,4

1.为以上每一个字符创建一个二叉树，并将其出现的频次存储在节点中，节点的数据结构定义为Node:

public class Node { 
    	//只存储两个值 0，1
        private String ch;
        //存储字符出现的频率次数
        private int num;
        //左节点
        private Node left;
        //右节点
        private Node right;
        public Node(String c, int n){ 
            ch = c;
            num = n;
        }
        public Node(){ 
        }
        public String getCh() { 
            return ch;
        }
        public void setCh(String ch) { 
            this.ch = ch;
        }
        public int getNum() { 
            return num;
        }
        public void setNum(int num) { 
            this.num = num;
        }
        public Node getLeft() { 
            return left;
        }
        public void setLeft(Node left) { 
            this.left = left;
        }
        public Node getRight() { 
            return right;
        }
        public void setRight(Node right) { 
            this.right = right;
        }
        @Override
        public String toString() { 
            return "Node{" +
                    "ch='" + ch + '\'' +
                    ", num=" + num +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

2.代码中有详细解释，末尾有运行效果图

public class Hafuman { 
        public static void main(String[] args) { 
        	//定义一个字符串
            String str = "ajsfhsdhfasdfkjhsdfhsalkdjsfhdsfhjsklasjfjksfdghkslkdahjfjhsdgasjfhsdjfjshhfg";
            //创建一个HashMap，用来存储字符和出现的频率
            HashMap<String,Integer> map = new HashMap<>();
            for (int i = 0; i < str.length(); i++) { 
                String ch = str.charAt(i) + "";
                //如果是第一次出现的字符，添加进map里，value为1
                if(map.get(ch) == null)
                    map.put(ch,1);
                else{ 
                	//否则value加1
                    map.put(ch,map.get(ch)+1);
                }
            }
            //创建数组，用来存放map中的数据建立的节点
            ArrayList<Node> arr = new ArrayList<>();
            for (Map.Entry<String, Integer> stringIntegerEntry : map.entrySet()) { 
                //System.out.println("key : " + stringIntegerEntry.getKey() + " value : " + stringIntegerEntry.getValue());
                //遍历map，将每一个key和value存储到数组里
                Node no = new Node(stringIntegerEntry.getKey(),stringIntegerEntry.getValue());
                arr.add(no);
            }
    		//可以输出验证一下
            System.out.println(arr);
            //将数组中的点建立哈夫曼树
            for (;;){ 
                if (arr.size() > 1){ 
                    //取数组中权重最小的两个点
                    Node[] data= getNode(arr);
                    //新建一个节点，将其的左右孩子指向这两个节点，该节点的权重是两个节点的权重之和
                    Node root = new Node(null, data[0].getNum()+data[1].getNum());
                    root.setLeft(data[0]);
                    root.setRight(data[1]);
                    //把新建的节点添加进数组
                    arr.add(root);
                }else{ 
                    break;
                }
            }
            //定义一个新节点，指向数组的第一个节点
            Node tree = arr.get(0);
            //对哈夫曼树进行编码并输出对应的编码
            //定义一个编码使用的map
            Map<String,String> charMaps = new HashMap<>();
            //定义一个解码使用的map
            Map<String, String> codeMaps = new HashMap<>();
            allView(tree,"",charMaps,codeMaps);
            String hafucode = "";
            for (int i = 0; i < str.length(); i++) { 
                String ch = str.charAt(i) + "";
                hafucode += charMaps.get(ch);
            }
            System.out.println(hafucode.length() + "----" + str.length());
            System.out.println(hafucode);
        }
        public static void allView(Node tree, String code, Map<String,String> charMaps,Map<String,String> codeMaps){ 
            //哈夫曼树是一个完全二叉树，左子树存在，右子树一定存在，所以只需判断一个
            if (tree.getLeft() == null){ 
            	//如果没有孩子，输出权重，字符以及编码
                System.out.println(tree.getNum() + "||" + tree.getCh() + "--code:" + code);
                //把字符和编码放入map中
                charMaps.put(tree.getCh(),code);
                codeMaps.put(code,tree.getCh());
            }else{ 
            	//否则不是叶子节点，递归调用
                allView(tree.getLeft(),code + "0",charMaps,codeMaps);
                allView(tree.getRight(), code + "1", charMaps, codeMaps);
            }
        }
        //找出权重最小的两个节点
        public static Node[] getNode(ArrayList<Node> arr) { 
        	//建立一个数组，用于存放最小的两个点的下标
            Node[] nos = new Node[2];
            int min1;
            int min2;
            if (arr.get(0).getNum() <= arr.get(1).getNum()) { 
                min1 = 0;
                min2 = 1;
            } else { 
                min1 = 1;
                min2 = 0;
            }
            for (int i = 2; i < arr.size(); i++) { 
                if (arr.get(i).getNum() < arr.get(min1).getNum()) { 
                    min2 = min1;
                    min1 = i;
                } else if (arr.get(i).getNum() >= arr.get(min1).getNum() && arr.get(i).getNum() < arr.get(min2).getNum()) { 
                    min2 = i;
                }
            }
            	//拿到两个节点
                nos[0] = arr.get(min1);
                nos[1] = arr.get(min2);
                //将两节点在数组中删除
                arr.remove(min1);
                if (min2 > min1) { 
                    arr.remove(min2 - 1);
                } else { 
                    arr.remove(min2);
                }
                //返回这两个节点
                return nos;
            }
    }

运行截图（部分）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]

[Link 1]: https://blog.csdn.net/sinat_41920065/article/details/106065295
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]: /images/20230312/6466b55196d04f4b866ae4bcb5407e58.png