文章目录前言
所有博客文件目录索引:博客目录索引(持续更新)
源代码:Gitee—.java、Github—.java
一、哈夫曼树原理
对于哈夫曼树的构造以及权值计算原理知识点推荐看这个视频:哈夫曼树和哈夫曼编码—
哈夫曼编码有两个特点:
带权路径长度WPL最短且唯一;【核心减少编码的操作】编码互不为前缀(一个编码不是另一个编码的开头)【可进行还原用途】。
应用场景:压缩文件。
公式:路径长度:WPL = l1× w1+l2× w2 +…+ ln × wn,w表示权值,n表示叶子节点个数。
哈夫曼编码是如何进行应用的呢,有什么具体的示例呢?
哈夫曼树是一颗二叉树哈夫曼树 编码,其是根据元素的权重来进行构成的一棵树,在树上的每个节点val都使用0或1来进行表示。
就像下面一样,可以说每个元素值所对应的路径都是唯一的:
3:00000 5:00001 11:0001 前者是值,后者即为路径,就是从上到下的路径合并。
问题来了为什么要构成构造成一个哈夫曼树?尤其是为什么要根据权重来进行排列分布呢?
首先解决后面一个问题:若是在一组数据中,有10个不同的字符,字符a出现了1000次,其他字符出现的数量很少,我们是否可以根据出现的次数来对这些字符来进行编码,a用1表示,b字符用01…d字符使用0003表示,那么1000次a仅仅只需要1000个字符即可哈夫曼树 编码,是不是大大减少了存储空间?这也就是我们为什么要根据权重进行排列分布。
此时可以来说明前面一个问题:因为哈夫曼树是带权路径长度最短的树,权值较大的节点离根节点较近。而带权路径长度是指:树中所有的叶子节点的权值乘上其到根节点的路径长度,这与最终的哈夫曼编码总长度成正比关系的。
核心操作:一旦哈夫曼树构建出来之后,我们可以得到每个字符与其路径,那么我们根据这个hash表即可进行字符串编码,而由于每个路径都是唯一的,我们同样也可依靠hash表来进行解码!
二、哈夫曼编码(Java题解)
编码思路过程:
encode编码:构造哈夫曼树 -> 获取字符及路径map -> 根据map去构建指定编码 1、构造哈夫曼树: 准备条件:自定义树节点(字符、val、权重,其中val为之后路径组成的值) 过程:①准备一个map来统计所有字符出现次数即权重。②根据权重进行排序。③遍历map来构建树节点,接着根据权重排序,存储到一个链表节点中。④遍历链表节点每次取出两个构成一个虚拟节点,之后再找前缀最小的进行重复合并,视角是从底之上进行合并构建。 2、获取字符及路径map:递归过程,核心路径重点就是叶子节点,在哈夫曼树里有效字符节点都是叶子节点。 3、根据map中的字符与对应匹配的路径来进行对所有源字符遍历编码。 decode解码:根据map来进行前缀匹配(由于每个字符的路径唯一),即可进行还原字符
Java题解:
/*
* 提示:该行代码过长,系统自动注释不进行高亮。一键复制会移除系统注释
* package com.changlu.tree; import java.util.Collections; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; / @Description: 哈夫曼树 @Author: changlu @Date: 8:09 PM / //哈夫曼树节点 class TreeNode { public Character ch; public int val; public int freq; public TreeNode left; public TreeNode right; public TreeNode(){} public TreeNode(Character ch, int val, int freq, TreeNode left, TreeNode right) { this.ch = ch; this.val = val; this.freq = freq; this.left = left; this.right = right; } } public class Huffman { / 解码 @param encodeStr 已编码字符串 @param encodeMap 编码map集合 @return / public static String decode (String encodeStr, Map encodeMap) { StringBuilder decodeStr = new StringBuilder(); while (encodeStr.length() > 0) { //遍历所有编码map对应的value(也就是编码路径) for (Map.Entry entry : encodeMap.entrySet()) { String charEncode = entry.getValue(); //匹配路径前缀 if (encodeStr.startsWith(charEncode)) { decodeStr.append(entry.getKey()); //删除该前缀 encodeStr = encodeStr.substring(charEncode.length()); break; } } } return decodeStr.toString(); } //编码 //0:编码后的字符串 //1:对应哈弗曼树中字符的路径表示 public static Object[] encode(String s) { Object[] res = new Object[2]; //编码字符串 //1、构建哈夫曼树 TreeNode rootNode = constructTree(s); //2、根据哈夫曼树找到所有的路径并存储到map中 Map encodeMap = new HashMap(); findPath(rootNode, encodeMap, new StringBuilder());//存储所有字符、编码路径到map中 //此时 字符:路径编码 已经再encodeMap中存储了,我们即可来进行编码 StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { sb.append(encodeMap.get(s.charAt(i))); } res[0] = sb.toString(); res[1] = encodeMap; return res; } / 寻找到哈夫曼树中所有字符的路径,并存储到map中 @param root 哈夫曼树的根节点 @param encodeMap 编码map @param path 存储路径 / private static void findPath(TreeNode root, Map encodeMap, StringBuilder path) { //每个元素的终点就是n0节点 if (root.left == null || root.right == null) { path.append(root.val); //为什么要从第1位开始呢?因为完全可以再少一位0,这样也能减少不少字符 encodeMap.put(root.ch, path.substring(1)); path.deleteCharAt(path.length() - 1); return; } path.append(root.val); //递归左右 if (root.left != null) findPath(root.left, encodeMap, path); if (root.right != null) findPath(root.right, encodeMap, path); //删除所有最后一个字符 path.deleteCharAt(path.length() - 1); } / 构造哈夫曼树 @param s @return / private static TreeNode constructTree(String s) { //1、统计每个字符出现的权重 Map cntMap = new HashMap(); for (int i = 0; i < s.length(); i++) { cntMap.put(s.charAt(i), cntMap.getOrDefault(s.charAt(i), 1)); } //2、将所有的字符构建成TreeNode节点存储到LinkedList中 LinkedList nodelist = new LinkedList(); for (Map.Entry entry : cntMap.entrySet()) { Character ch = entry.getKey();//字符 Integer freq = entry.getValue();//频率 int val = 0;//节点值 nodelist.add(new TreeNode(ch, val, freq, null, null)); } //3、根据频率来进行排序 Collections.sort(nodelist, (node1, node2)->node1.freq - node2.freq); //4、构建哈夫曼树 //处理只有一个节点的情况 if (nodelist.size() == 1) { //1个节点也要有父节点 TreeNode treeNode = nodelist.get(0); return new TreeNode(null, 0, treeNode.freq, treeNode, null); } //开始构建哈夫曼树 TreeNode root = null; while (nodelist.size() > 0) { //取出头部两个节点 TreeNode t1 = nodelist.removeFirst(); TreeNode t2 = nodelist.removeFirst(); //左右子树节点来进行分别赋值0,1 t1.val = 0; t2.val = 1; //若是当前节点中没有节点了 if (nodelist.size() == 0) { root = new TreeNode(null, 0, t1.freq + t2.freq, t1, t2); }else { //首先构建成一个虚拟节点 TreeNode combineNode = new TreeNode(null, 0, t1.freq + t2.freq, t1, t2); //将虚拟节点插入到链表中,同样需要维护其有序性 //暴力法【实际这里可用二分来进行】 if (combineNode.freq > nodelist.getLast().freq) { nodelist.addLast(combineNode); }else { //遍历找到权重>该合并节点的权重 for (int i = 0; i < nodelist.size(); i++) { if (nodelist.get(i).freq >= combineNode.freq) { nodelist.add(i, combineNode); break; } } } } } return root; } }
*/
测试代码:
public class Huffman { public static void main(String[] args) { String s = "abbbbeeerrryuiolll"; System.out.println("编码前:" + s); //编码API Object[] encodeRes = encode(s); String encodeStr = (String) encodeRes[0]; Map encodeMap = (Map) encodeRes[1]; System.out.println("编码表:"); for (Map.Entry e : encodeMap.entrySet()) { System.out.println(e.getKey() + ":" + e.getValue()); } System.out.println("编码后:" + encodeStr); //解码API String decodeStr = decode(encodeStr, encodeMap); System.out.println("解码后:" + decodeStr); } }
参考资料
1 哈夫曼编码( Coding)原理详解
2. 哈夫曼编码细解& Java 实现
3. 视频:哈夫曼树和哈夫曼编码
4. 【JAVA】KMP算法保姆级教程
本文共 1346 个字数,平均阅读时长 ≈ 4分钟