java实现哈夫曼文件解压缩

java实现哈夫曼文件解压缩

本文实例为大家分享了java实现哈夫曼文件解压缩的具体代码，供大家参考，具体内容如下

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 map=(Map)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 map,byte [] array)

{

StringBuilder stringBuilder = new StringBuilder();

for(int i=0;i

{

boolean flag=(i==array.length-1);

stringBuilder.append(byteToBitString(!flag, array[i]));

}

Map map2=new HashMap();//反向编码表

Set keySet = map.keySet();

for(Byte b:keySet)

{

String value=map.get(b);

map2.put(value, b);

}

List list=new ArrayList();

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[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 nodes = getNodes(array);

Node createHuffManTree = createHuffManTree(nodes);

Map m=getCodes(createHuffManTree);

byte[] zip = zip(array, m);

return zip;

}

//

private static byte[] zip(byte [] array,Map 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

{

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 getCodes(Node root)

{

if(root==null)

{

return null;

}

getCodes(root.leftNode,"0",sBuilder);

getCodes(root.rightNode,"1",sBuilder);

return map;

}

//获取哈夫曼编码

static Map 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 getNodes(byte [] array)

{

List list=new ArrayList();

Map map=new HashMap();

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 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 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

{

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 + "]";

}

http://

//前序遍历

public void preOrder()

{

System.out.println(this);

if(this.leftNode!=null)

{

this.leftNode.preOrder();

}

if(this.rightNode!=null)

{

this.rightNode.preOrder();

}

}

}

{

boolean flag=(i==array.length-1);

stringBuilder.append(byteToBitString(!flag, array[i]));

}

Map map2=new HashMap();//反向编码表

Set keySet = map.keySet();

for(Byte b:keySet)

{

String value=map.get(b);

map2.put(value, b);

}

List list=new ArrayList();

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[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 nodes = getNodes(array);

Node createHuffManTree = createHuffManTree(nodes);

Map m=getCodes(createHuffManTree);

byte[] zip = zip(array, m);

return zip;

}

//

private static byte[] zip(byte [] array,Map 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

{

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 getCodes(Node root)

{

if(root==null)

{

return null;

}

getCodes(root.leftNode,"0",sBuilder);

getCodes(root.rightNode,"1",sBuilder);

return map;

}

//获取哈夫曼编码

static Map 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 getNodes(byte [] array)

{

List list=new ArrayList();

Map map=new HashMap();

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 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 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

{

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 + "]";

}

http://

//前序遍历

public void preOrder()

{

System.out.println(this);

if(this.leftNode!=null)

{

this.leftNode.preOrder();

}

if(this.rightNode!=null)

{

this.rightNode.preOrder();

}

}

}

{

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 nodes = getNodes(array);

Node createHuffManTree = createHuffManTree(nodes);

Map m=getCodes(createHuffManTree);

byte[] zip = zip(array, m);

return zip;

}

//

private static byte[] zip(byte [] array,Map 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

{

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 getCodes(Node root)

{

if(root==null)

{

return null;

}

getCodes(root.leftNode,"0",sBuilder);

getCodes(root.rightNode,"1",sBuilder);

return map;

}

//获取哈夫曼编码

static Map 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 getNodes(byte [] array)

{

List list=new ArrayList();

Map map=new HashMap();

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 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 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

{

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 + "]";

}

http://

//前序遍历

public void preOrder()

{

System.out.println(this);

if(this.leftNode!=null)

{

this.leftNode.preOrder();

}

if(this.rightNode!=null)

{

this.rightNode.preOrder();

}

}

}

{

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 getCodes(Node root)

{

if(root==null)

{

return null;

}

getCodes(root.leftNode,"0",sBuilder);

getCodes(root.rightNode,"1",sBuilder);

return map;

}

//获取哈夫曼编码

static Map 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 getNodes(byte [] array)

{

List list=new ArrayList();

Map map=new HashMap();

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 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 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

{

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 + "]";

}

http://

//前序遍历

public void preOrder()

{

System.out.println(this);

if(this.leftNode!=null)

{

this.leftNode.preOrder();

}

if(this.rightNode!=null)

{

this.rightNode.preOrder();

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。