[数据结构与算法]Java数据结构与算法

目录

赫夫曼编码字节数组

代码实现

?完整代码

?运行效果

测试Test?

?运行效果

?赫夫曼字节数组封装

实现代码

字节转二进制字符串

代码实现

赫夫曼编码字节数组

代码实现

	//编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，
//返回一个赫夫曼编码压缩后的byte[]
	/*
	 * bytes 这时原始的字符串对应的byte[]
	 * huffmanCodes 生成的赫夫曼编码map
	 * 返回赫夫曼编码处理后的byte[]
	 * 举例:String content="I like like like java do you like a java";
=>byte[] contentBytes=content.getBytes();
	 * 返回的是字符串
	 * =>对应的byte[] huffmanCodeBytes,即8位对应一个byte，放入到huffmanCodeBytes
	 * huffmanCodeBytes[0]=10101000(补码)=>byte
	 * */
	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;
		if (stringBuilder.length()%8==0) {
			len=stringBuilder.length()/8;
		}else {
			len=stringBuilder.length()/8+1;
		}
		//创建存储压缩后的byte数组
		byte[] huffmanCodeBytes=new byte[len];
		int index=0;
		for (int i = 0; i < stringBuilder.length(); i+=8) {
			String strByte;
			if (i+8>stringBuilder.length()) {//不够8位
				strByte=stringBuilder.substring(i);
			}else {
				strByte=stringBuilder.substring(i,i+8);
			}
			
			//将strByte转成一个byte,放入到huffmanCodeBytes
			huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2);
			index++;
		}
		return huffmanCodeBytes;
	}

		//测试
		byte[] huffmanCodeBytes=zip(contentBytes, huffmanCodes);
		System.out.println("huffmanCodeBytes="+huffmanCodeBytes);
		
		//发送huffmanCodeBytes数组

?完整代码

package huffmancode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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(contentBytes.length);//40
		
		List<Node> nodes=getNodes(contentBytes);
		System.out.println("nodes"+nodes);
		
		//测试一把，创建的二叉树
		System.out.println("赫夫曼树");
		Node huffmanTreeRoot=createHuffmanTree(nodes);
		System.out.println("前序遍历");
		huffmanTreeRoot.preOrder();
		
		//测试一把是否生成了对应的赫夫编码
		Map<Byte, String> huffmanCodes=getCodes(huffmanTreeRoot);
		System.out.println("生成的赫夫曼编码表"+huffmanCodes);
		
		//测试
		byte[] huffmanCodeBytes=zip(contentBytes, huffmanCodes);
		System.out.println("huffmanCodeBytes="+huffmanCodeBytes);
		
		//发送huffmanCodeBytes数组
	}
	//编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
	/*
	 * bytes 这时原始的字符串对应的byte[]
	 * huffmanCodes 生成的赫夫曼编码map
	 * 返回赫夫曼编码处理后的byte[]
	 * 举例:String content="I like like like java do you like a java";=>byte[] contentBytes=content.getBytes();
	 * 返回的是字符串
	 * =>对应的byte[] huffmanCodeBytes,即8位对应一个byte，放入到huffmanCodeBytes
	 * huffmanCodeBytes[0]=10101000(补码)=>byte
	 * */
	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;
		if (stringBuilder.length()%8==0) {
			len=stringBuilder.length()/8;
		}else {
			len=stringBuilder.length()/8+1;
		}
		//创建存储压缩后的byte数组
		byte[] huffmanCodeBytes=new byte[len];
		int index=0;
		for (int i = 0; i < stringBuilder.length(); i+=8) {
			String strByte;
			if (i+8>stringBuilder.length()) {//不够8位
				strByte=stringBuilder.substring(i);
			}else {
				strByte=stringBuilder.substring(i,i+8);
			}
			
			//将strByte转成一个byte,放入到huffmanCodeBytes
			huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2);
			index++;
		}
		return huffmanCodeBytes;
	}
	//生成赫夫曼树对应的赫夫曼编码
	//思路:
	//1.将赫夫曼编码存放在Map<Byte,String>形式
	//32->01 97->100 100->11000等等[形式]
	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集合
	 * node 传入结点
	 * code 路径:左子节点是0，右子节点1
	 * 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());
			}
			
		}
	}
	//前序遍历的方法
	private static void preOrder(Node root) {
		if(root!=null) {
			root.preOrder();
		}else {
			System.out.println("赫夫曼树为空");
		}
	}
	private static List<Node>getNodes(byte[] bytes){
		//创建一个ArrayList
		ArrayList<Node> nodes=new ArrayList<Node>();
		
		//遍历bytes,统计每一个byte出现的次数->map[key,value]
		Map<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集合
		//遍历map
		for (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);
			//将新的二叉树，加入到nodes
			nodes.add(parent);
		}
		//nodes最后的结点，就是赫夫曼树的根结点
		return nodes.get(0);
	}
}
//创建Node,待数据和权值
class Node implements Comparable<Node>{
	Byte data;//存放数据(字符)本身，比如'a'=>97 ''=>32
	int weight;//权值，表示字符出现的次数
	Node left;
	Node right;
	public Node(Byte data,int weight) {
		this.data=data;
		this.weight=weight;
	}
	@Override
	public int compareTo(Node o) {
		//从小到大排序
		return this.weight-o.weight;
	}
	public String toString() {
		return "Node[data="+data+"weight="+weight+"]";
	}
	//前序遍历
	public void preOrder() {
		System.out.println(this);
		if(this.left!=null) {
			this.left.preOrder();
		}
		if(this.right!=null) {
			this.right.preOrder();
		}
	}
}

?运行效果

测试Test?

package tree;

public class Test {

	@SuppressWarnings("unused")
	public static void main(String[] args) {
		String strByte="10101000";
		System.out.println((byte)Integer.parseInt(strByte,2));//-88
	}
}

?运行效果

?赫夫曼字节数组封装

实现代码

		//分布过程
		List<Node> nodes=getNodes(contentBytes);
		System.out.println("nodes"+nodes);
		
		//测试一把，创建的二叉树
		System.out.println("赫夫曼树");
		Node huffmanTreeRoot=createHuffmanTree(nodes);
		System.out.println("前序遍历");
		huffmanTreeRoot.preOrder();
		
		//测试一把是否生成了对应的赫夫编码
		Map<Byte, String> huffmanCodes=getCodes(huffmanTreeRoot);
		System.out.println("生成的赫夫曼编码表"+huffmanCodes);
		
		//测试
		byte[] huffmanCodeBytes=zip(contentBytes, huffmanCodes);
		System.out.println("huffmanCodeBytes="+huffmanCodeBytes);
		
		//发送huffmanCodeBytes数组

	//使用一个方法，将前面的方法封装起来，便于我们的调用
	/*
	 * bytes原始的字符串对应的字节数组
	 * 是经过赫夫曼编码处理后的字节数组(压缩后的数组)
	 * */
	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;
	}

字节转二进制字符串

数据解压(使用赫夫曼编码解码)

使用赫夫曼编码来解码数据，具体要求是

1)前面我们得到了赫夫曼编码和对应的编码byte[]

2)现在要求使用赫夫曼编码，进行解码，又重新得到原来的字符串"

I like like like java do you like a java"

思路:解码过程，就是编码的一个逆向操作

代码实现

package huffmancode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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(contentBytes.length);//40
		
		byte[] huffmanCodesBytes=huffmanZip(contentBytes);
		System.out.println("压缩后的结果是:"+Arrays.toString(huffmanCodesBytes)+"长度="+huffmanCodesBytes.length);
		
		//测试一把byteToBitString方法
		//System.out.println("压缩后的结果是:"+Arrays.toString(huffmanCodesBytes)+"长度="+huffmanCodesBytes.length);
		byte[] sourceBytes=decode(huffmanCodes, huffmanCodesBytes);
		System.out.println("原来的字符串="+new String(sourceBytes));
		//如何将数据进行解压(解码)
		
		//分布过程
		/*List<Node> nodes=getNodes(contentBytes);
		System.out.println("nodes"+nodes);
		
		//测试一把，创建的二叉树
		System.out.println("赫夫曼树");
		Node huffmanTreeRoot=createHuffmanTree(nodes);
		System.out.println("前序遍历");
		huffmanTreeRoot.preOrder();
		
		//测试一把是否生成了对应的赫夫编码
		Map<Byte, String> huffmanCodes=getCodes(huffmanTreeRoot);
		System.out.println("生成的赫夫曼编码表"+huffmanCodes);
		
		//测试
		byte[] huffmanCodeBytes=zip(contentBytes, huffmanCodes);
		System.out.println("huffmanCodeBytes="+huffmanCodeBytes);
		
		//发送huffmanCodeBytes数组*/
	}
	
	//完成数据的解压
	//思路
	//1.将huffmanCodeBytes[]
	//重写先转成赫夫曼编码对应的二进制的字符串
	//2.赫夫曼编码对应的二进制的字符串=>对照赫夫曼编码=>I like like like java do you like a java
	
	//编写一个方法，完成对压缩数据的解码
	/*
	 * huffmanCodes 赫夫曼编码表map
	 * huffmanBytes 赫夫曼编码得到的字节数组
	 * 就是原来的字符串对应的数组
	 * */
	private static byte[] decode(Map<Byte, String>huffmanCodes,byte[] huffmanBytes) {
		
		//1.先得到huffmanBytes对应的二进制的字符串，形式
		StringBuilder stringBuilder=new StringBuilder();
		//将byte数组转成二进制的字符串
		for (int i = 0; i < huffmanBytes.length; i++) {
			byte b=huffmanBytes[i];
			//判断是不是最后一个字节
			boolean flag=(i==huffmanBytes.length-1);
			stringBuilder.append(byteToBitString(!flag, b));
		}
	//	System.out.println("赫夫曼字节数组对应的二进制字符串="+stringBuilder.toString());
	//	return null;
		//把字符串安装指定的赫夫曼编码进行解码
		//把赫夫曼编码表进行调换，因为反向查询a->100 100->a
		Map<String, Byte> map=new HashMap<String, Byte>();
		for (Map.Entry<Byte, String>entry:huffmanCodes.entrySet()) {
			map.put(entry.getValue(),entry.getKey());
		}
		
		//创建要给集合，存放byte
		List<Byte> list=new ArrayList<Byte>();
		//i可以理解成就是索引，扫描stringBuilder
		for (int i = 0; i < huffmanBytes.length; i++) {
			int count=1;
			boolean flag=true;
			Byte b=null;
			
			while (flag) {
				//取出一个'1''0'
				String key=stringBuilder.substring(i,i+count);//i不动，让count移动，指定匹配到一个字符
				b=map.get(key);
				if (b==null) {//说明没有匹配到
					count++;
				}else {
					//匹配到
					flag=false;
				}
			}
			list.add(b);
			i+=count;//i直接移动到count
		}
		//当for循环结束后，我们list中存放了所有的字符
		//把list中的数据放入到byte[]并返回
		byte b[]=new byte[list.size()];
		for (int i = 0; i < b.length; i++) {
			b[i]=list.get(i);
		}
		return b;
	}
	private static String byteToBitString(boolean flag,byte b) {
		//使用变量保存b
		int temp=b;//将b转成int
		//如果是正数我们还存在补高位
		
		temp|=256;//temp 1=>000
		String str=Integer.toBinaryString(temp);//返回的是temp对应的二进制的补码
		if (flag) {
			return str.substring(str.length()-8);
		}else {
			return str;
		}		
	}
	//使用一个方法，将前面的方法封装起来，便于我们的调用
	/*
	 * bytes原始的字符串对应的字节数组
	 * 是经过赫夫曼编码处理后的字节数组(压缩后的数组)
	 * */
	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[]
	/*
	 * bytes 这时原始的字符串对应的byte[]
	 * huffmanCodes 生成的赫夫曼编码map
	 * 返回赫夫曼编码处理后的byte[]
	 * 举例:String content="I like like like java do you like a java";=>byte[] contentBytes=content.getBytes();
	 * 返回的是字符串
	 * =>对应的byte[] huffmanCodeBytes,即8位对应一个byte，放入到huffmanCodeBytes
	 * huffmanCodeBytes[0]=10101000(补码)=>byte
	 * */
	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;
		if (stringBuilder.length()%8==0) {
			len=stringBuilder.length()/8;
		}else {
			len=stringBuilder.length()/8+1;
		}
		//创建存储压缩后的byte数组
		byte[] huffmanCodeBytes=new byte[len];
		int index=0;
		for (int i = 0; i < stringBuilder.length(); i+=8) {
			String strByte;
			if (i+8>stringBuilder.length()) {//不够8位
				strByte=stringBuilder.substring(i);
			}else {
				strByte=stringBuilder.substring(i,i+8);
			}
			
			//将strByte转成一个byte,放入到huffmanCodeBytes
			huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2);
			index++;
		}
		return huffmanCodeBytes;
	}
	//生成赫夫曼树对应的赫夫曼编码
	//思路:
	//1.将赫夫曼编码存放在Map<Byte,String>形式
	//32->01 97->100 100->11000等等[形式]
	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集合
	 * node 传入结点
	 * code 路径:左子节点是0，右子节点1
	 * 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());
			}
			
		}
	}
	//前序遍历的方法
	private static void preOrder(Node root) {
		if(root!=null) {
			root.preOrder();
		}else {
			System.out.println("赫夫曼树为空");
		}
	}
	private static List<Node>getNodes(byte[] bytes){
		//创建一个ArrayList
		ArrayList<Node> nodes=new ArrayList<Node>();
		
		//遍历bytes,统计每一个byte出现的次数->map[key,value]
		Map<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集合
		//遍历map
		for (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);
			//将新的二叉树，加入到nodes
			nodes.add(parent);
		}
		//nodes最后的结点，就是赫夫曼树的根结点
		return nodes.get(0);
	}
}
//创建Node,待数据和权值
class Node implements Comparable<Node>{
	Byte data;//存放数据(字符)本身，比如'a'=>97 ''=>32
	int weight;//权值，表示字符出现的次数
	Node left;
	Node right;
	public Node(Byte data,int weight) {
		this.data=data;
		this.weight=weight;
	}
	@Override
	public int compareTo(Node o) {
		//从小到大排序
		return this.weight-o.weight;
	}
	public String toString() {
		return "Node[data="+data+"weight="+weight+"]";
	}
	//前序遍历
	public void preOrder() {
		System.out.println(this);
		if(this.left!=null) {
			this.left.preOrder();
		}
		if(this.right!=null) {
			this.right.preOrder();
		}
	}
}