Implementation of Huffman File Decompression by java
- 2021-09-16 07:12:49
- OfStack
This article example for everyone to share java Huffman file decompression code, for your reference, the specific content is as follows
1. Huffman compression has a low compression ratio for compressed files, such as ppt and video.
2. This program mainly involves the knowledge of collection, tree and IO.
Character statistics can be made using the map set.
The construction process of Huffman tree is not complicated:
Firstly, the set of trees is sorted according to the size of root nodes
2. Take out two trees with the smallest root node value and build them into a new tree;
Remove the minimum number of the previous two root nodes from the set;
Add the newly generated tree to the set
1 Repeat the above process in a straight loop until the size of the set becomes 1;
Pay attention to using object stream Object stream when writing and reading files.
3, program can compress the character, also can compress the file. The main function in the code only calls the method of decompressing files. If you want to decompress characters, you can call the corresponding method.
4. The code is as follows:
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";// File to be compressed
String dstFile="d://mydata.zip";// A compressed file
zipFile(srcFile, dstFile);// Zip file
System.out.println(" Compression succeeded! ");
unZipFile(dstFile,"d://unzip.txt");// Extract the file just now, and the name of the extracted file is called unzip.txt
System.out.println(" Unzip the file successfully! ");
}
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();// Release resources
} 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>();// Reverse coding table
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)// If you can divisive exactly
{
len=sBuilder.toString().length()/8;
}
else // If you can't divisive exactly
{
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;
}
// Heavy load
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;
}
// Get Huffman code
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)// Non-leaf node
{
// Left recursion
getCodes(node.leftNode,"0",stringBuilder2);
// Rightward recursion
getCodes(node.rightNode,"1",stringBuilder2);
}
else // If it is a leaf node,
{
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);// Get a value by key
if(count==null)// Explain that at this time map Characters have not been changed in the collection
{
map.put(data, 1);
}
else
{
map.put(data,count+1);
}
}
// Traversal map Set
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);// Sort the collection first
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;// Character
int weight;// Number of occurrences of characters
Node leftNode;
Node rightNode;
public Node(Byte data,int weight)// Constructor
{
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 + "]";
}
// Preorder traversal
public void preOrder()
{
System.out.println(this);
if(this.leftNode!=null)
{
this.leftNode.preOrder();
}
if(this.rightNode!=null)
{
this.rightNode.preOrder();
}
}
}