浙江龙网

  1. 首页 > 生活百科 > >

数据结构与算法【Java】08---树结构的实际应用( 六 )

生活百科

3.5、数据压缩小结将3.3与3.4中编写的所有方法封装成一个方法
//使用一个方法，将前面的方法封装起来，便于我们的调用/** * @param bytes 原始的字符串对应的字节数组 * @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组) */private static byte[] huffmanZip(byte[] bytes){List<Node> nodes = getNodes(bytes);//根据nodes创建的赫夫曼树Node huffmanTreeRoot = createHuffmanTree(nodes);//生成对应的赫夫曼编码（根据赫夫曼树）Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);//根据生成的赫夫曼编码来对原始的字节数组进行压缩byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);return huffmanCodeBytes;}

数据压缩的所有代码
import java.util.*;public class HuffmanCode {public static void main(String[] args) {String content = "i like like like java do you like a java";byte[] contentBytes = content.getBytes();System.out.println("原始的content字符串长度为："+contentBytes.length);//40byte[] huffmanCodesBytes = huffmanZip(contentBytes);System.out.println("对content字符串压缩后的结果是："+Arrays.toString(huffmanCodesBytes));System.out.println("长度为："+huffmanCodesBytes.length);//17}//使用一个方法 ， 将前面的方法封装起来，便于我们的调用/*** @param bytes 原始的字符串对应的字节数组* @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)*/private static byte[] huffmanZip(byte[] bytes){List<Node> nodes = getNodes(bytes);//根据nodes创建的赫夫曼树Node huffmanTreeRoot = createHuffmanTree(nodes);//生成对应的赫夫曼编码（根据赫夫曼树）Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);//根据生成的赫夫曼编码来对原始的字节数组进行压缩byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);return huffmanCodeBytes;}//编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]/**** @param bytes 这是原始的字符串对应的 byte[]* @param huffmanCodes 生成的赫夫曼编码map* @return 返回赫夫曼编码处理后的 byte[]* 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();* 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"* => 对应的 byte[] huffmanCodeBytes ， 即 8位对应一个 byte,放入到 huffmanCodeBytes* huffmanCodeBytes[0] =10101000(补码) => byte[推导10101000=> 10101000 - 1 => 10100111(反码)=> 11011000（原码）= -88 ]* huffmanCodeBytes[1] = -88*/private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {//1.利用 huffmanCodes 将bytes 转成赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();//遍历bytes 数组for(byte b: bytes) {stringBuilder.append(huffmanCodes.get(b));}//System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());//将 "1010100010111111110..." 转成 byte[]//统计返回byte[] huffmanCodeBytes 长度//一句话 int len = (stringBuilder.length() + 7) / 8;int len;if(stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}//创建 存储压缩后的 byte数组byte[] huffmanCodeBytes = new byte[len];int index = 0;//记录是第几个bytefor (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8String strByte;if(i+8 > stringBuilder.length()) {//不够8位strByte = stringBuilder.substring(i);}else{strByte = stringBuilder.substring(i, i + 8);}//将strByte 转成一个byte,放入到 huffmanCodeByteshuffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}//生成赫夫曼树对应的赫夫曼编码//思路://1. 将赫夫曼编码表存放在 Map<Byte,String> 形式//生成的赫夫曼编码表{32（空格）=01, 97（a）=100, 100(...)=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();//2. 在生成赫夫曼编码表示，需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();//为了调用方便 ， 我们重载 getCodesprivate static Map<Byte, String> getCodes(Node root) {if(root == null) {return null;}//处理root的左子树getCodes(root.left, "0", stringBuilder);//处理root的右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合* @param node传入结点* @param code路径： 左子结点是 0, 右子结点 1* @param stringBuilder 用于拼接路径*/private static void getCodes(Node node,String code,StringBuilder stringBuilder){StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);//将code加入到 stringBuilder2 （拼接路径）stringBuilder2.append(code);if (node != null){//如果node等于空，不处理//判断当前node是叶子节点还是非叶子结点if (node.data =https://www.huyubaike.com/biancheng/= null){//非叶子节点//递归处理//向左递归getCodes(node.left,"0", stringBuilder2);//向右递归getCodes(node.right, "1", stringBuilder2);}else {//进入到这里说明是叶子节点 ， 找到了最后huffmanCodes.put(node.data,stringBuilder2.toString());}}}//前序遍历的方法public static void preOrder(Node root){if (root != null){root.preOrder();}else {System.out.println("赫夫曼树为空");}}/**** @param bytes 接收字节数组* @return 返回的就是 List 形式[Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],*/private static List<Node> getNodes(byte[] bytes){//1.创建一个ArrayListArrayList<Node> nodes = new ArrayList<>();//遍历bytes,存储每一个byte出现的次数=》map[key,value]HashMap<Byte,Integer> counts = new HashMap<>();for (byte b: bytes) {Integer count = counts.get(b);if (count == null){//Map还没有这个数据counts.put(b,1);}else {counts.put(b,count+1);}}//把每个键值对转成一个Node对象,并加入到nodes集合//遍历mapfor (Map.Entry<Byte,Integer> entry : counts.entrySet()){nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}//通过list创建应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes){while (nodes.size() > 1){//排序,从小到大Collections.sort(nodes);//取出第一棵最小的二叉树左节点Node leftNode = nodes.get(0);//取出第二棵最小的二叉树右节点Node rightNode = nodes.get(1);//创建一棵新的二叉树，它的根节点没有data，只有权值Node parent = new Node(null, leftNode.weight+ rightNode.weight);parent.left = leftNode;parent.right = rightNode;//将已经处理的两棵二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);//将新的二叉树加入到nodesnodes.add(parent);}//nodes 最后的节点就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值class Node implements Comparable<Node>{Byte data;//存放数据本身a===>97 ascii码int weight;//权值，表示字符出现的次数Node left;Node right;public Node(Byte data, int weight) {this.data = https://www.huyubaike.com/biancheng/data;this.weight = weight;}@Overridepublic int compareTo(Node o) {//从小到大排序return this.weight-o.weight;}public String toString() {return"Node [data = "https://www.huyubaike.com/biancheng/+ data +" weight=" + weight + "]";}//前序遍历public void preOrder() {System.out.println(this);if(this.left != null) {this.left.preOrder();}if(this.right != null) {this.right.preOrder();}}}

推荐阅读


上一篇：frp服务利用云主机实现Windows远程连接

下一篇：「Tubian」Tubian0.41!支持Windows QQ微信！