数据结构与算法---哈夫曼编码
2021/4/29 1:25:20
本文主要是介绍数据结构与算法---哈夫曼编码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.哈夫曼编码可用与字符压缩加压,密码学等领域
2.java实现:
2.1.HfmNode.java
package com.hfm.util; public class HfmNode implements Comparable<HfmNode>{ String chr; int weight; HfmNode left; HfmNode right; HfmNode parent; @Override public int compareTo(HfmNode o) { return this.weight - o.weight; } }
2.2.HfmTree.java
package com.hfm.util; import java.nio.charset.StandardCharsets; import java.util.*; import java.util.stream.Collectors; public class HfmTree { HfmNode root; List<HfmNode> leafList; Map<String,Integer> direct; Map<String,String> dic = new HashMap<>(); public HfmTree(Map<String, Integer> direct) { this.direct = direct; this.leafList = new ArrayList<>(direct.size()); create(); } public void encode(){ leafList.stream().forEach(node -> { HfmNode current = node; String curStr = ""; while(current.parent != null) { if(current == current.parent.left) { curStr = "0" + curStr; }else { curStr = "1" + curStr; } current = current.parent; } dic.put(curStr,node.chr); System.out.println(node.chr+" after encode:"+curStr); }); } public void decode(String oxStr){ String res = ""; String curStr = ""; HfmNode current = root,pre = null; for (char c : oxStr.toCharArray()) { curStr += c; if(dic.containsKey(curStr)){ res += dic.get(curStr); curStr = ""; } } System.out.println(oxStr+" after decode:"+res); } private void create(){ PriorityQueue<HfmNode> priorityQueue = new PriorityQueue<>(); String tags [] = direct.keySet().toArray(new String[0]); for (String item : tags) { HfmNode tmp = new HfmNode(); tmp.weight = direct.get(item); tmp.chr = item; priorityQueue.add(tmp); leafList.add(tmp); } for (int i = 1; i < leafList.size(); i++) { HfmNode left = priorityQueue.poll(); HfmNode right = priorityQueue.poll(); HfmNode parent = new HfmNode(); parent.chr = left.chr.concat(right.chr); parent.weight = left.weight + right.weight; left.parent = parent; right.parent = parent; parent.left = left; parent.right = right; priorityQueue.add(parent); } this.root = priorityQueue.poll(); } public static void main(String[] args) { Map<String,Integer> integerMap = new HashMap<>(); integerMap.put("a",3); integerMap.put("b",24); integerMap.put("c",6); integerMap.put("d",20); integerMap.put("e",34); integerMap.put("f",4); integerMap.put("g",12); HfmTree tree = new HfmTree(integerMap); tree.encode(); //gecbaf String oxStr = "100111010011011010111"; tree.decode(oxStr); } }
说明:解码尚存在问题,日后修改
这篇关于数据结构与算法---哈夫曼编码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?