数据结构与算法之编码、解码、文件压缩、文件解压

ゞ浴缸里的玫瑰 2021-09-01 09:37 223阅读 0赞

### 数据结构与算法之编码、解码、文件压缩、文件解压 ###

*   *  实体映射
     *  代码实现

## 实体映射 ##

public class Node implements Comparable<Node>{
    	Byte data; // 构造的节点树
    	int weight; // 权值
    	Node left; // 左节点
    	Node right; // 右节点
    
    	public Node(Byte data, int weight) {
    		this.data = data;
    		this.weight = weight;
    	}
    	@Override
    	public String toString() {
    		return "Node [data=" + data + ", weight=" + weight + "]";
    	}
    	
    	public int compareTo(Node o) {
    		// 倒序
    		return o.weight - this.weight;
    	}
    }

## 代码实现 ##

public class TestHuffmanCode {
    
    
    	public static void main(String[] args) {
    		String msg="can you can a can as a can canner can a can";
    		//String msg = "accompany is the longest love confession";
    		//对字符串的byte数组进行编码，因为所有的数据最终都可以转换为一个byte数组
    		byte[] bytes = msg.getBytes();
    		//进行赫夫曼编码
    		byte[] b = huffmanzip(bytes);
    		//System.out.println(bytes.length);
    		//System.out.println(b.length);
    		//使用赫夫曼编码进行解码
    		byte[] newBytes = decode(huffCodes , b);
    		//验证前后两个是否一样
    		//System.out.println(Arrays.toString(bytes));
    		//System.out.println(Arrays.toString(newBytes));
    		//无损压缩
    		System.out.println(new String(newBytes));
    		//需要压缩的文件，在项目下
    		String src="D://test.bmp";
    		//文件压缩的地方
    		String dst="2.zip";
    		try {
    			zipFile(src , dst);
    		} catch (IOException e) {
    			e.printStackTrace();
    		}
    		//文件解压
    		try {
    			unZip("2.zip", "3.bmp");
    		} catch (Exception e) {
    			e.printStackTrace();
    		}
    		/**
    		 * 赫夫曼编码：简单图形:相同的数据处理的更少，压缩效率更高；复杂图形则数据处理的更多，根节点会跑到最后面去，压缩效率会降低
    		 */
    		/*//验证补全方法
    		byte b = 1;
    		String byteToBitStr = byteToBitStr(b);
    		System.out.println(byteToBitStr);*/
    	}
    	/**
    	 * 文件解压
    	 * @param src
    	 * @param dst
    	 * @throws Exception
    	 */
    	public static void unZip(String src , String dst) throws Exception{
    		//创建一个输入流
    		InputStream is = new FileInputStream(src);
    		ObjectInputStream ois = new ObjectInputStream(is);
    		//读取
    		byte[] b = (byte[]) ois.readObject();
    		//读取赫夫曼编码表
    		Map<Byte , String> codes = (Map<Byte, String>) ois.readObject();
    		ois.close();
    		is.close();
    		//解码
    		byte[] bytes = decode(codes, b);
    		//创建一个输入流
    		OutputStream os = new FileOutputStream(dst);
    		//写出数据
    		os.write(bytes);
    		os.close();
    	}
    	/**
    	 * 文件压缩
    	 * @param src
    	 * @param dst
    	 * @throws IOException
    	 */
    	public static void zipFile(String src , String dst) throws IOException{
    		//创建一个输入流
    		InputStream is = new FileInputStream(src);
    		//创建一个和输入流指向的文件大小一样的byte数组
    		byte[] b = new byte[is.available()];
    		//读取文件内容
    		is.read(b);
    		is.close();
    		//使用赫夫曼编码进行编码
    		byte[] byteZip = huffmanzip(b);
    		System.out.println(b.length);
    		System.out.println(byteZip.length);
    		//输入流
    		OutputStream os = new FileOutputStream(dst);
    		ObjectOutputStream oos = new ObjectOutputStream(os);
    		//把压缩后的byte数组写入文件
    		oos.writeObject(byteZip);
    		//把赫夫曼编码表写入文件
    		oos.writeObject(huffCodes);
    		oos.close();
    		os.close();
    	}
    	/**
    	 * 使用指定的赫夫曼编码进行解码
    	 * @param huffCodes2
    	 * @param b
    	 * @return
    	 */
    	private static byte[] decode(Map<Byte, String> huffCodes2, byte[] bytes) {
    		StringBuilder sb = new StringBuilder();
    		//把byte数组转为一个二进制的字符串
    		for(int i=0;i<bytes.length;i++){
    			byte b = bytes[i];
    			//是否是最后一个
    			boolean flag = (i == bytes.length-1);
    			sb.append(byteToBitStr(!flag , b));
    		}
    		//System.out.println(sb.toString());
    		//把字符串按照指定的赫夫曼编码进行解码
    		//把赫夫曼编码的键值对进行调换
    		Map<String , Byte> map = new HashMap<String , Byte>();
    		for(Map.Entry<Byte, String> entry : huffCodes.entrySet()){
    			map.put(entry.getValue(), entry.getKey());
    		}
    		//创建一个集合用于存放byte
    		List<Byte> list = new ArrayList<Byte>();
    		//处理字符串
    		for(int i=0;i<sb.length();){
    			int count = 1;
    			boolean flag = true;
    			Byte b = null;
    			//截取出一个key
    			while(flag){
    				String key = sb.substring(i , i+count);
    				b = map.get(key);
    				if(b==null){
    					count++;
    				}else{
    					flag = false;
    				}
    			}
    			//查看获取到的字母ASCII码
    			System.out.println(b);
    			list.add(b);
    			i+=count;
    		}
    		//把集合转为数组
    		byte[] b = new byte[list.size()];
    		for(int i =0; i<b.length ; i++){
    			b[i] = list.get(i);
    		}
    		return b;
    	}
    	/**
    	 * 赫夫曼编码 每八位放在一起 最后不够8位的按位补齐，赫夫曼编码正数用0补齐，负数用1补齐
    	 * @param b
    	 * @return
    	 */
    	private static String byteToBitStr(boolean flag , byte b){
    		int temp = b;
    		if(flag){
    			temp |= 256;
    		}
    		String str = Integer.toBinaryString(temp);
    		if(flag){
    			return str.substring(str.length()-8);
    		}else{
    			return str;
    		}
    	}
    	/**
    	 * 进行赫夫曼编码压缩方法
    	 * @param bytes
    	 * @return
    	 */
    	private static byte[] huffmanzip(byte[] bytes) {
    		//先统计每一个byte出现的次数，并放入一个集合中
    		List<Node> nodes = getNodes(bytes);
    		//创建一个赫夫曼数
    		Node tree = createHaffmanTree(nodes);
    		//测试创建出来的赫夫曼数
    		//System.out.println(tree);
    		//System.out.println(tree.left);
    		//System.out.println(tree.right);
    		//创建一个赫夫曼编码表
    		Map<Byte , String> huffCodes = getCodes(tree);
    		//System.out.println(huffCodes);
    		//编码
    		byte[] b= zip(bytes , huffCodes);
    		return b;
    	}
    	/**
    	 * 进行赫夫曼编码
    	 * @param bytes
    	 * @param huffCodes2
    	 * @return
    	 */
    	private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
    		StringBuilder sb = new StringBuilder();
    		//把需要压缩的数组处理成一个二进制的字符串
    		for(byte b : bytes){
    			sb.append(huffCodes.get(b));
    		}
    		//定义长度
    		int len;
    		if(sb.length()%8==0){
    			len = sb.length()/8;
    		}else{
    			len = sb.length()/8+1;
    		}
    		//System.out.println(sb.toString());
    		//用于存储压缩后的byte
    		byte[] by = new byte[len];
    		//记录新byte的位置
    		int index=0;
    		for(int i=0;i<sb.length();i+=8){
    			String strByte;
    			if(i+8>sb.length()){
    				strByte = sb.substring(i);
    			}else{
    				strByte = sb.substring(i , i+8);
    			}
    			byte byt = (byte) Integer.parseInt(strByte,2);
    			//System.out.println(strByte+":"+byt);
    			by[index] = byt;
    			index++;
    		}
    		return by;
    	}
    	//用于临时存储路径
    	static StringBuilder sb = new StringBuilder();
    	//用于存储赫夫曼编码
    	static Map<Byte,String> huffCodes =  new HashMap<Byte, String>();
    	/**
    	 * 根据赫夫曼树获取赫夫曼编码
    	 * @param tree
    	 * @return
    	 */
    	private static Map<Byte, String> getCodes(Node tree) {
    		if(tree == null){
    			return null;
    		}
    		getCodes(tree.left,"0",sb);
    		getCodes(tree.right,"1",sb);
    		
    		return huffCodes;
    	}
    			
    	private static void getCodes(Node node, String code, StringBuilder sb) {
    		StringBuilder sb2 = new StringBuilder(sb);
    		sb2.append(code);
    		if(node.data==null){
    			getCodes(node.left,"0",sb2);
    			getCodes(node.right,"1",sb2);
    		}else{
    			huffCodes.put(node.data, sb2.toString());
    		}
    	}
    	/**
    	 * 创建赫夫曼树
    	 * @param nodes
    	 * @return
    	 */
    	private static Node createHaffmanTree(List<Node> nodes) {
    		//排序即验证
    		//Collections.sort(nodes);
    		//System.out.println(nodes);
    		while(nodes.size()>1){
    			//排序
    			Collections.sort(nodes);
    			//取出两个权值最低的二叉树
    			Node left = nodes.get(nodes.size() - 1);
    			Node right = nodes.get(nodes.size() - 2);
    			//创建一个新的二叉树
    			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);
    	}
    	/**
    	 * 把byte数组转为node集合
    	 * @param bytes
    	 * @return
    	 */
    	private static List<Node> getNodes(byte[] bytes) {
    		List<Node> nodes = new ArrayList<Node>();
    		//存储没一个byte出现了多少次
    		Map<Byte , Integer> counts = new HashMap<Byte , Integer>();
    		//统计每一个byte出现的次数
    		for(byte b : bytes){
    			Integer count = counts.get(b);
    			if(count == null){
    				counts.put(b, 1);
    			}else{
    				counts.put(b, count+1);
    			}
    		}
    		//统计次数打印
    		//System.out.println(counts);
    		//把每一个键值对转化为一个node对象
    		for(Map.Entry<Byte, Integer> entry : counts.entrySet()){
    			nodes.add(new Node(entry.getKey() , entry.getValue()));
    		}
    		return nodes;
    	}
    }