最佳实践-数据压缩(生成赫夫曼编码和赫夫曼编码后的数据)

朴灿烈づ我的快乐病毒、 2024-03-27 15:16 69阅读 0赞

我们已经生成了 赫夫曼树, 下面我们继续完成任务

1.  生成赫夫曼树对应的赫夫曼编码 , 如下表: =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
2.  使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码，将"i like like like java do you like a java" 字符串生成对应的编码数据, 形式如下. 10101000101111111100100010111111110010001011111111001001010011011100011100000110111010001111001010  
    00101111111100110001001010011011100
3.  思路：前面已经分析过了，而且我们讲过了生成赫夫曼编码的具体实现。
4.  代码实现：

//生成赫夫曼树对应的赫夫曼编码
    	//思路
    	//1.将赫夫曼编码表存放在Map<Byte,String>形式
    	// 32->01 97->100 100->1100等等形式
    	static Map<Byte,String> huffmanCodes = new HashMap<Byte,String>();
    	//2.在生成赫夫曼编码表示，需要去拼接路径，定义一个StringBuilder 存储某个叶子节点的路径
    	static StringBuilder stringBuilder = new StringBuilder();
    	
    	//为了方便，重载getCodes
    	private 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== null不处理
    			//判断当前node是叶子节点还是非叶子结点
    			if(node.data == null) {
        //非叶子节点
    				//递归处理
    				//向左递归
    				getCodes(node.left,"0",stringBuilder2);
    				//向右递归
    				getCodes(node.right, "1", stringBuilder2);
    			}else {
        //说明是一个叶子节点
    				//就表示找到某个叶子节点的最后
    				huffmanCodes.put(node.data, stringBuilder2.toString());
    			}
    		}
    	}