java实现哈夫曼文件解压缩

刺骨的言语ヽ痛彻心扉 2023-07-07 08:20 38阅读 0赞

1.  哈夫曼压缩对已经经过压缩处理的文件压缩率比较低，比如ppt和视频。
2.  这个程序主要涉及到集合、树、IO相关知识。  
    字符的统计可以用map集合进行统计。  
    哈夫曼树的构建过程也并不复杂：  
    ①先对树的集合按照根节点大小进行排序  
    ②拿出根节点数值最小的两棵树，用它两构建成一颗新的树；  
    ③从集合中删除之前那两颗根节点最小的数；  
    ④把新生成的树加入到集合中  
    一直循环重复上面的过程，直到集合的大小变成1为止；  
    写出、读取文件时注意使用对象流Object流。
3.  这个程序可以对字符进行压缩，也可以对文件进行压缩。代码中的主函数中只是调用了对文件解压缩的方法，若想对字符进行解压缩，可以调用对应的方法。
4.  代码如下：

package huffmancode;
    
    import java.io.FileInputStream;
    import java.io.FileOutputStream;
    import java.io.InputStream;
    import java.io.ObjectInputStream;
    import java.io.ObjectOutputStream;
    import java.io.OutputStream;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    
    public class HuffManCode 
    {
        
    
    	public static void main(String[] args) 
    	{
        
    		String srcFile="d://mydata.txt";//要压缩的文件
    		String dstFile="d://mydata.zip";//压缩后的文件
    		zipFile(srcFile, dstFile);//压缩文件
    		System.out.println("压缩成功！");
    		
    		unZipFile(dstFile,"d://unzip.txt");//对刚才的文件进行解压，解压后的文件名称叫做unzip.txt
    		System.out.println("解压文件成功！");		
    	}
    	
    	public static void unZipFile(String zipFile,String dstFile)
    	{
        
    		InputStream inputStream=null;
    		ObjectInputStream objectInputStream=null;
    		OutputStream outputStream=null;
    		try 
    		{
        
    			inputStream=new FileInputStream(zipFile);
    			objectInputStream=new ObjectInputStream(inputStream);
    			byte [] array= (byte [])objectInputStream.readObject();
    			Map<Byte,String> map=(Map<Byte,String>)objectInputStream.readObject();
    			byte[] decode = decode(map, array);
    			outputStream=new FileOutputStream(dstFile);
    			outputStream.write(decode);
    		} catch (Exception e) 
    		{
        
    			System.out.println(e);
    		}finally
    		{
        
    			try {
        
    				outputStream.close();
    				objectInputStream.close();
    				inputStream.close();
    				
    			} catch (Exception e2) {
        
    				System.out.println(e2);
    			}
    			
    		}
    		
    		
    	}
    	
    	public static void zipFile(String srcFile,String dstFile)
    	{
        
    		FileInputStream inputStream=null;
    		OutputStream outputStream=null;
    		ObjectOutputStream objectOutputStream=null;
    		
    		try 
    		{
        
    			inputStream=new FileInputStream(srcFile);
    			byte [] b=new byte[inputStream.available()];
    			inputStream.read(b);
    			byte[] huffmanZip = huffmanZip(b);
    			outputStream=new FileOutputStream(dstFile);
    			objectOutputStream=new ObjectOutputStream(outputStream);
    			objectOutputStream.writeObject(huffmanZip);
    			objectOutputStream.writeObject(map);
    		} catch (Exception e)
    		{
        
    			System.out.println(e);
    		}
    		finally 
    		{
        
    			if(inputStream!=null)
    			{
        
    				try 
    				{
        
    					objectOutputStream.close();
    					outputStream.close();
    					inputStream.close();//释放资源
    				
    				} catch (Exception e2) 
    				{
        
    					System.out.println(e2);
    				}
    				
    			}		
    		}
    	}
    	
    	private static byte[] decode(Map<Byte, String> map,byte [] array)
    	{
        
    		StringBuilder stringBuilder = new StringBuilder();
    		for(int i=0;i<array.length;i++)
    		{
        
    			boolean flag=(i==array.length-1);
    			stringBuilder.append(byteToBitString(!flag, array[i]));
    		}
    		
    		Map<String, Byte> map2=new HashMap<String, Byte>();//反向编码表
    		Set<Byte> keySet = map.keySet();
    		for(Byte b:keySet)
    		{
        
    			String value=map.get(b);
    			map2.put(value, b);
    		}
    		List<Byte> list=new ArrayList<Byte>();
    		for (int i = 0; i < stringBuilder.length();) 
    		{
        
    			int count=1;
    			boolean flag=true;
    			Byte byte1=null;
    			while (flag) 
    			{
        
    				String substring = stringBuilder.substring(i, i+count);
    				byte1 = map2.get(substring);
    				if(byte1==null)
    				{
        
    					count++;
    				}
    				else 
    				{
        
    					flag=false;
    				}
    				
    			}
    			list.add(byte1);
    			i+=count;		
    		}
    		
    		byte [] by=new byte[list.size()];
    		for(int i=0;i<by.length;i++)
    		{
        
    			by[i]=list.get(i);
    		}
    		return by;
    	}
    	
    	private static String byteToBitString(boolean flag, byte b)
    	{
        
    		int temp=b;
    		if(flag)
    		{
        
    			temp|=256;
    		}
    		
    		String binaryString = Integer.toBinaryString(temp);
    		if(flag)
    		{
        
    			return binaryString.substring(binaryString.length()-8);
    		}
    		else
    		{
        
    			return binaryString;
    		}
    		
    	}
    	
    	private static byte[] huffmanZip(byte [] array)
    	{
        
    		List<Node> nodes = getNodes(array);
    		Node createHuffManTree = createHuffManTree(nodes);
    		Map<Byte, String> m=getCodes(createHuffManTree);
    		byte[] zip = zip(array, m);
    		return zip;	
    	}
    	
    	//
    	private static byte[] zip(byte [] array,Map<Byte,String> map)
    	{
        
    		StringBuilder sBuilder=new StringBuilder();
    		for(byte item:array)
    		{
        
    			String value=map.get(item);
    			sBuilder.append(value);
    		}
    		//System.out.println(sBuilder);
    		int len;
    		if(sBuilder.toString().length()%8==0)//如果可以整除
    		{
        
    			len=sBuilder.toString().length()/8;
    		}
    		else //如果不能整除
    		{
        
    			len=sBuilder.toString().length()/8+1;
    		}
    		
    		byte [] by=new byte[len];
    		int index=0;
    		for(int i=0;i<sBuilder.length();i+=8)
    		{
        
    			String string;
    			if((i+8)>sBuilder.length())
    			{
        
    				string=sBuilder.substring(i);
    			}
    			else 
    			{
        
    				string=sBuilder.substring(i, i+8);
    			}
    						
    			by[index]=(byte)Integer.parseInt(string,2);
    			index++;
    		}
    		
    		return by;
    			
    	}
    	
    	
    	//重载
    	private static Map<Byte, String> getCodes(Node root)
    	{
        
    		if(root==null)
    		{
        
    			return null;
    		}
    		getCodes(root.leftNode,"0",sBuilder);
    		getCodes(root.rightNode,"1",sBuilder);
    		return map;
    	}
    	
    	
    	
    	//获取哈夫曼编码
    		static Map<Byte, String> map=new HashMap<>();
    		static StringBuilder sBuilder=new StringBuilder();
    		public static void getCodes(Node node,String code,StringBuilder stringBuilder)
    		{
        
    			StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
    			stringBuilder2.append(code);
    			if(node!=null)
    			{
        
    				if(node.data==null)//非叶子结点
    				{
        
    					//向左递归
    					getCodes(node.leftNode,"0",stringBuilder2);
    					//向右递归
    					getCodes(node.rightNode,"1",stringBuilder2);
    				}
    				else //如果是叶子结点
    				{
        
    					map.put(node.data,stringBuilder2.toString());
    				}
    			}
    		}
    	
    	
    	
    	public static List<Node> getNodes(byte [] array)
    	{
        
    		List<Node> list=new ArrayList<Node>();
    		Map<Byte, Integer> map=new HashMap<Byte, Integer>();
    		for(Byte data:array)
    		{
        
    			Integer count=map.get(data);//通过键获取值
    			if(count==null)//说明此时map集合中还没有改字符
    			{
        
    				map.put(data, 1);
    			}
    			else 
    			{
        
    				map.put(data,count+1);
    			}
    		}
    		//遍历map集合
    		Set<Byte> set=map.keySet();
    		for(Byte key:set)
    		{
        
    			int value=map.get(key);
    			Node node=new Node(key, value);
    			list.add(node);
    		}
    		return list;
    	}
    	
    	private static Node createHuffManTree(List<Node> list)
    	{
        
    		while(list.size()>1)
    		{
        
    			Collections.sort(list);//先对集合进行排序
    			Node leftNode=list.get(0);
    			Node rightNode=list.get(1);
    			
    			Node parentNode=new Node(null, leftNode.weight+rightNode.weight);
    			parentNode.leftNode=leftNode;
    			parentNode.rightNode=rightNode;
    			
    			list.remove(leftNode);
    			list.remove(rightNode);
    			
    			list.add(parentNode);
    		}
    		return list.get(0);
    		
    	}
    
    }
    
    class Node implements Comparable<Node>
    {
        
    	Byte data;//字符
    	int weight;//字符出现的次数
    	Node leftNode;
    	Node rightNode;
    	
    	public Node(Byte data,int weight)//构造器
    	{
        
    		this.data=data;
    		this.weight=weight;
    	}
    
    	@Override
    	public int compareTo(Node o) 
    	{
        
    		return this.weight-o.weight;
    	}
    
    	@Override
    	public String toString() 
    	{
        
    		return "Node [data=" + data + ", weight=" + weight + "]";
    	}
    	
    	//前序遍历
    	public void preOrder()
    	{
        
    		System.out.println(this);
    		if(this.leftNode!=null)
    		{
        
    			this.leftNode.preOrder();
    		}
    		if(this.rightNode!=null)
    		{
        
    			this.rightNode.preOrder();
    		}
    	}
    	
    	
    }