赫夫曼算法类 Huffman.java
/**
- @Author: ltx
- @Description: 赫夫曼编码
*/
public class Huffman {
Map<Character, String> codeMap = new HashMap<>();/** * 中序遍历(前序或后序也行) * 失去huffman编码 * * @param node 节点 * @param sb StringBuilder */public void getCodeByMidOrder(Node node, StringBuilder sb) { if (node.left != null) { //往左走+'0' sb.append("0"); getCodeByMidOrder(node.left, sb); } //叶子节点 if (node.left == null && node.right == null) {// System.out.print(node + ":" + sb + ", ");
codeMap.put(node.value, sb.toString()); } if (node.right != null) { //往右走+'1' sb.append("1"); getCodeByMidOrder(node.right, sb); } //回溯向上走缩小一个字符 if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); }}public Node getHuffmanTree(List<Node> nodes) { Collections.sort(nodes);// System.out.println(nodes);
while (nodes.size() > 1) { //左叶子-数组最小值 Node leafLeft = nodes.remove(0); //右叶子-数组次小值 Node leafRight = nodes.remove(0); //父节点=数组最小值+数组次小值 Node parentNode = new Node(null, leafLeft.weight + leafRight.weight); parentNode.left = leafLeft; parentNode.right = leafRight; //新的节点增加到list外面 nodes.add(parentNode); Collections.sort(nodes); } return nodes.get(0);} /** * 获取各个字符权重(字符个数) * * @param str * @return */public List<Node> getCharWight(String str) { Map<Character, Integer> charNumMap = new HashMap<>(); char[] chs = str.toCharArray(); for (char c : chs) { //数量 Integer count = charNumMap.get(c); if (count == null) { charNumMap.put(c, 1); } else { charNumMap.put(c, count + 1); } }// System.out.println(charNumMap);
List<Node> nodes = new ArrayList<>(); //创立节点List for (char c : charNumMap.keySet()) { nodes.add(new Node(c, charNumMap.get(c))); } return nodes;} /** * 编码 * 依据赫夫曼编码表，对原始数据做转换 * * @param str 原始字符串 * @return */public String encoding(String str) { StringBuilder sb = new StringBuilder(); char[] chs = str.toCharArray(); for (char c : chs) { sb.append(codeMap.get(c)); } return sb.toString();} /** * 解码 * * @return */public String decode(String encodStr) { //翻转codeMap Map<String, Character> encodeMap = new HashMap<>(); for (char c : codeMap.keySet()) { encodeMap.put(codeMap.get(c), c); } char[] chs = encodStr.toCharArray(); int j = 0; StringBuilder res = new StringBuilder(); while (j < encodStr.length() - 1) { StringBuilder sb = new StringBuilder(); Character cr; //匹配出字符串 while ((cr = encodeMap.get(sb.toString())) == null) { sb.append(chs[j]); j++; } res.append(cr); } return res.toString();}public static void main(String[] args) { Huffman huffman = new Huffman(); System.out.println("原始数据:"); //须要压缩的串 String str = "i like like like java do you like a java"; System.out.println(str); //1.取得字符权重List List<Node> nodes = huffman.getCharWight(str); //[ :9, a:5, d:1, e:4, u:1, v:2, i:5, y:1, j:2, k:4, l:4, o:2] System.out.println("节点权重列表:"); System.out.println(nodes); //2.[PerfectMoney下载](https://www.gendan5.com/wallet/PerfectMoney.html)结构赫夫曼树 Node root = huffman.getHuffmanTree(nodes); //3.取得赫夫曼编码表 huffman.getCodeByMidOrder(root, new StringBuilder("")); System.out.println("赫夫曼编码表:"); //失去赫夫曼编码表 //{ =01, a=100, d=11000, u=11001, e=1110, v=11011, i=101, y=11010, j=0010, k=1111, l=000, o=0011} System.out.println(huffman.codeMap); //4.压缩编码 String encodStr = huffman.encoding(str); System.out.println("压缩后数据:");//1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
System.out.println(encodStr); //5.解压 String res = huffman.decode(encodStr); System.out.println("解压后数据:"); //打印最终后果 //i like like like java do you like a java System.out.println(res);}}