赞
踩
哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。 我们通过一个具体的实例来讲解哈夫曼树的构造以及编码和反编码。
比如说我们要对一字符串进行01编码,该如何做?我们要清楚为什么要使用哈夫曼编码?答案很简单,哈夫曼编码占位可以做到最少。
注:每次挑选两个权重最小的结点执行父节点
以此类推,得到最终的哈夫曼树:
我们可以得到根节点的权值为18。
从根节点开始,路径左为0,右为1(这个不做要求,左1又0也可),从而对用01编码对叶子节点进行编码:
ajsfhsdhfasdfk jhsd对应的编码就是
1000 101 01 110 111 01 00 111 110 1000 01 00 110 1001 101 111 01 00
给定01,译出字符串为多少,比如按照上面的规则对 110111001000 进行译码。
分析:
从第一个进行查找,一个一个比对,第一个数字是1,规则中没有对应的,接着往下11,也没有对应的,再往下110,对应f,接着分析后面的数字(110分离出来,分析剩下的数字),1没有对应的,11没有对应的,111对应h,分离出111,对剩下的数字比对,0没有对应的,00对应d,1没有,10没有,100没有,1000对应a。综上分析110111001000对应的编码为:fhda
到这里我们就分析完毕了,下面看代码演示:
节点类:
public class NodeClass { private int num; private String ch; private NodeClass left; private NodeClass right; public NodeClass() { } public NodeClass( String ch , int num) { this.num = num; this.ch = ch; } public int getNum() { return num; } public void setNum(int num) { this.num = num; } public String getCh() { return ch; } public void setCh(String ch) { this.ch = ch; } public NodeClass getLeft() { return left; } public void setLeft(NodeClass left) { this.left = left; } public NodeClass getRight() { return right; } public void setRight(NodeClass right) { this.right = right; } @Override public String toString() { return "NodeClass{" + "num=" + num + ", ch='" + ch + '\'' + ", left=" + left + ", right=" + right + '}'; } }
构建哈夫曼树、哈夫曼编码、译码:
import java.util.ArrayList; import java.util.HashMap; import java.util.Map; public class Hafuman { public static void main(String[] args) { String str = "ajsfhsdhfasdfkjhsd"; HashMap<String , Integer> map = new HashMap<String , Integer>(); for (int i = 0 ; i < str.length(); i++){ String ch = str.charAt(i) + ""; //统计每个字母出现的次数 if(map.get(ch) == null){ map.put(ch,1); }else { //为了防止覆盖 map.put(ch , map.get(ch) + 1); } } ArrayList<NodeClass> arr = new ArrayList<>(); //map遍历 for(Map.Entry<String , Integer> en : map.entrySet()){ System.out.println("key:" + en.getKey() + ",value:" + en.getValue() ); NodeClass no = new NodeClass(en.getKey() , en.getValue()); arr.add(no); } //构建哈夫曼树 for(;;){ if(arr.size() > 1){ NodeClass[] data = getNode(arr); NodeClass root = new NodeClass(null , data[0].getNum() + data[1].getNum()); root.setLeft(data[0]); root.setRight(data[1]); arr.add(root); }else { break; } } //TREE就是最终的哈夫曼树 NodeClass tree = arr.get(0); System.out.println(tree); //key是字符 Map<String,String> charMaps = new HashMap<>(); 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 ); //反编码 int index = 0; String charStr = ""; for(int i = 1 ; i <= hafucode.length() ; i++){ String string = hafucode.substring(index , i); if(codeMaps.get(string) != null){ charStr += codeMaps.get(string); index = i; } } System.out.println(charStr); } //取出最小的两个结点 public static NodeClass[] getNode(ArrayList<NodeClass> arr){ NodeClass[] nos = new NodeClass[2]; int index1; int index2; if(arr.get(0).getNum() <= arr.get(1).getNum()){ index1 = 0; index2 = 1; }else { index1 = 1; index2 = 0; } for(int i = 2 ; i < arr.size() ; i++){ if(arr.get(i).getNum() < arr.get(index1).getNum()){ index2 = index1; index1 = i; }else if(arr.get(i).getNum() >= arr.get(index1).getNum() && arr.get(i).getNum() < arr.get(index2).getNum()){ index2 = i; } } nos[0] = arr.get(index1); nos[1] = arr.get(index2); arr.remove(index1); if(index2 > index1){ arr.remove(index2 - 1); }else{ arr.remove(index2); } return nos; } public static void allView(NodeClass tree , String code, Map<String,String> charMaps , Map<String,String> codeMaps ){ if(tree.getLeft() == null){ //System.out.println(tree.getCh() + " : " + tree.getNum() + " code:" + code ); 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); } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。