嘉兴网站建设福州市建设工程工料机信息网站

嘉兴网站建设,福州市建设工程工料机信息网站,谢岗仿做网站,深圳集团网站开发给定n个权值作为n个节点#xff0c;构造一棵二叉树#xff0c;若该树的带权路径长度(wpl)达到最小#xff0c;这样的二叉树便成为最优二叉树#xff0c;也被称为赫夫曼树。节点的权#xff1a;将树中节点付给某一个具有某种含义的数值#xff0c;这个值便被称为节点的权。…给定n个权值作为n个节点构造一棵二叉树若该树的带权路径长度(wpl)达到最小这样的二叉树便成为最优二叉树也被称为赫夫曼树。节点的权将树中节点付给某一个具有某种含义的数值这个值便被称为节点的权。节点的带权路径长度便为从根节点到该节点之间的路径长度与节点的权的乘积。赫夫曼二叉树的构建从小到大对所有数据进行排序取出权值最小的两颗二叉树并组成一颗新二叉树新的二叉树的权值为这两颗二叉树的和对新二叉树以根节点的权值大小重新进行排序。重复上述步骤直到所有节点都经过处理。public class HuffmanTree { public static void main(String[] args) { int[] arr {13, 7, 8, 3, 29, 6, 1}; Node root createHuffmanTree(arr); root.preOrder(); } public static Node createHuffmanTree(int[] arr){ ListNode nodes new ArrayList(); for (int value : arr) { nodes.add(new Node(value)); } while (nodes.size() 1) { //对二叉树进行排序 Collections.sort(nodes); //取出两个最小的节点一个节点也可以看为最小的二叉树 Node left nodes.get(0); Node right nodes.get(1); //构建新二叉树 Node parent new Node(left.value right.value); parent.left left; parent.right right; nodes.remove(left); nodes.remove(right); //将最新构建的二叉树加入其中 nodes.add(parent); } return nodes.get(0); } } /** * 实现Comparable接口是为了方便节点的排序 */ class Node implements ComparableNode{ public Node left; public Node right; public int value; public Node(int value){ this.value value; } Override public String toString() { return Node{ value value }; } Override public int compareTo(Node o) { //当前节点小于 return this.value - o.value; } public void preOrder(){ System.out.println(this); if (this.left ! null){ System.out.print(左子树:); this.left.preOrder(); } if (this.right ! null){ System.out.print(右子树:); this.right.preOrder(); } } }赫夫曼编码赫夫曼编码被广泛用于数据文件的压缩压缩率一般在20%-90%之间。赫夫曼编码是可变长编码VLC的一种。并且赫夫曼编码是一种无损压缩编码。若赫夫曼树的排序方法不同对应的赫夫曼编码也不同但是wpl相同都是最小的。赫夫曼压缩代码public class Huffman { public static void main(String[] args) { String str i like like like java do you like a java; byte[] bytes str.getBytes(); ListNode codes getCodes(bytes); Node huffmanTree createHuffmanTree(codes); // huffmanTree.preOrder(); System.out.println(赫夫曼编码表); getHuffmanCodes(huffmanTree, , stringBuilder); System.out.println(huffmanCodes); byte[] zip zip(bytes, huffmanCodes); System.out.println(压缩结果 Arrays.toString(zip)); } //将赫夫曼编码表存入map中 private static MapByte,String huffmanCodes new HashMap(); //使用StringBuilder是为了方便获取这个字符的详细编码 private static StringBuilder stringBuilder new StringBuilder(); /** * 获取赫夫曼编码表 * 向左值为0向右值为1 * param node * param code * param stringBuilder */ public static void getHuffmanCodes(Node node,String code,StringBuilder stringBuilder){ //在原基础上获取 StringBuilder st new StringBuilder(stringBuilder); st.append(code); if (node.data null){ if (node.left ! null){ getHuffmanCodes(node.left, 0, st); } if (node.right ! null) getHuffmanCodes(node.right, 1, st); }else { huffmanCodes.put(node.data, st.toString()); } } //对内容进行压缩 public static byte[] zip(byte[] bytes, MapByte,String huffmanCodes){ StringBuilder builder new StringBuilder(); for (byte b : bytes) { builder.append(huffmanCodes.get(b)); } int len builder.length() % 8 0 ? builder.length()/8 : builder.length()/8 1; int index 0;//index用于记录byte的下标 byte[] fileZip new byte[len]; for (int i 0;i builder.length();i 8){ int end Math.min((i 8), builder.length()); //将builder.substring(i, end)转换为byte二进制转换为十进制 fileZip[index] (byte) Integer.parseInt(builder.substring(i, end), 2); } return fileZip; } //将文本内容转换为节点 public static ListNode getCodes(byte[] bytes) { ListNode nodes new ArrayList(); //查询并保存每个字节出现的次数 MapByte, Integer huffmanCodes new HashMap(); for (byte b : bytes) { Integer i huffmanCodes.get(b); if(i null){ huffmanCodes.put(b, 1); }else{ huffmanCodes.put(b, i1); } } //转换为Node集合 for (Map.EntryByte, Integer entry : huffmanCodes.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } //通过转换的节点集合转换为赫夫曼树 public static Node createHuffmanTree(ListNode nodes) { while(nodes.size() 1){ //进行排序 Collections.sort(nodes); //取出最小的两颗树 Node left nodes.get(0); Node right nodes.get(1); //进行构建最新的树 Node parent new Node(null, left.weight right.weight); parent.left left; parent.right right; //删掉原最小的两棵树 nodes.remove(left); nodes.remove(right); //将最新的树添加进去 nodes.add(parent); } return nodes.get(0); } } class Node implements ComparableNode{ public Byte data; public int weight; public Node left; public Node right; public Node(Byte data, int weight) { this.data data; this.weight weight; } public void preOrder(){ System.out.println(this); if (this.left ! null){ System.out.println(左); this.left.preOrder(); } if (this.right ! null) { System.out.println(右); this.right.preOrder(); } } Override public int compareTo(Node o) { return this.weight - o.weight; } Override public String toString() { return Node{ data data , weight weight }; } }赫夫曼编码压缩上述实例字符串后结果如下图赫夫曼编码解压赫夫曼编码解压操作是压缩操作的逆向操作即将上述压缩后结果进行还原为i like like like java do you like a java字符串。解压步骤将byte十进制数组还原为原二进制所对应的字符串根据二进制字符串通过创建的赫夫曼编码表进行还原。//这里的byte值为压缩过的值 public static byte[] decode(byte[] bytes, MapByte,String huffmanCodes){ // 添加空值检查 if (bytes null || huffmanCodes null || huffmanCodes.isEmpty()) { return new byte[0]; } // 构建二进制字符串 StringBuilder binaryStr new StringBuilder(); for (int i 0; i bytes.length; i) { boolean isLast (i bytes.length - 1); binaryStr.append(BinToString(!isLast, bytes[i])); } // 反转编码表 MapString, Byte reverseMap new HashMap(); for (Map.EntryByte, String entry : huffmanCodes.entrySet()) { reverseMap.put(entry.getValue(), entry.getKey()); } // 解码 ListByte result new ArrayList(); StringBuilder currentCode new StringBuilder(); for (int i 0; i binaryStr.length(); i) { currentCode.append(binaryStr.charAt(i)); Byte decodedByte reverseMap.get(currentCode.toString()); if (decodedByte ! null) { result.add(decodedByte); currentCode.setLength(0); } } // 转换为字节数组 byte[] source new byte[result.size()]; for (int i 0; i result.size(); i) { source[i] result.get(i); } return source; } //将压缩的byte转换为原字符串的byte //flag的作用是首先执行 bytes | 256将第9位设为1256的二进制是100000000 public static String BinToString(boolean flag,int bytes){ if(flag){ bytes | 256; } String binaryString Integer.toBinaryString(bytes); if(flag){ return binaryString.substring(binaryString.length() - 8); }else { return binaryString; } }