Java利用哈夫曼编码实现字符串压缩

第Java利用哈夫曼编码实现字符串压缩赫夫曼编码基本介绍

1)赫夫曼编码也翻译为哈夫曼编码(HuffmanCoding)，又称霍夫曼编码，是一种编码方式,属于一种程序算法

2)赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。

3)赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间

4)赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码

在通信领域中几种信息处理方式的区别（以字符串ilikelikelikejavadoyoulikeajava举例）:

第一种-定长编码:

第二种-变长编码:

第三种-赫夫曼编码:

传输的字符串:

1、ilikelikelikejavadoyoulikeajava

2、d:1y:1u:1j:2v:2o:2l:4k:4e:4i:5a:5:9//各个字符对应的个数

3、按照上面字符出现的次数构建一颗赫夫曼树,次数作为权值

构成赫夫曼树的步骤：

1)从小到大进行排序,将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树

2)取出根节点权值最小的两颗二叉树

3)组成一颗新的二叉树,该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4)再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

4、根据赫夫曼树，给各个字符,规定编码(前缀编码)，向左的路径为0向右的路径为1，编码

如下:

o:1000u:10010d:100110y:100111i:101

a:110k:1110e:1111j:0000v:0001l:001:01

5、按照上面的赫夫曼编码，我们的ilikelikelikejavadoyoulikeajava字符串对应的编码为(注意这里我们使用的无损压缩)1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110通过赫夫曼编码处理长度为：133

通过以上三种信息处理方式可以对比看出赫夫曼编码的优越性。

以下给出实现哈夫曼编码需要的各个方法:

1、先创建节点对象:

//为了排序，必须实现Comprable接口

publicclassNodeimplementsComparableNode{

Bytedata;

intweight;

Nodeleft;

Noderight;

publicNode(Bytedata,intweight){

this.data=data;

this.weight=weight;

@Override

publicStringtoString(){

return"Node{"+

"data="+data+

",weight="+weight+

'}';

@Override

publicintcompareTo(Nodeo){

returnthis.weight-o.weight;

//前序遍历

publicvoidprefixOrder(){

System.out.println(this);

if(this.left!=null){

this.left.prefixOrder();

if(this.right!=null){

this.right.prefixOrder();

}

2、需要先实现统计输入的字符串中各个字符的个数:

/**

*//统计字符串中每个字符出现的次数和空格出现次数

*@paramstr字符串

*@return返回一个排好序的Node集合

publicstaticListNodetotalCharCounts(Stringstr){

for(inti=0;istr.length();i++){

charch=str.charAt(i);

Integercount=map.get(ch);

if(count==null){

count=0;

map.put(ch,count+1);

//遍历map，将map中的数据存入Node节点中

//先将map转为set集合

SetMap.EntryCharacter,IntegermapSet=map.entrySet();

//观察测试输出

//System.out.println(mapSet);

ListNodenodeList=newArrayList();

//遍历set

for(Map.EntryCharacter,Integerset:mapSet){

//将map中的数据存入Node节点中

Nodenode=newNode((byte)set.getKey().charValue(),set.getValue());

//将node存入集合中

nodeList.add(node);

//System.out.println(set.getKey()+"="+set.getValue());

//排序

Collections.sort(nodeList);

//测试

//System.out.println(nodeList);

returnnodeList;

}

3、创建赫夫曼树:

/**

*创建huffman树

*@paramnodeList排好序的集合

*@return返回huffman树的根节点

publicstaticNodecreateHuffmanTree(ListNodenodeList){

//循环创建huffman树

while(nodeList.size()1){

//1、每次取出集合中的前两个节点

Nodeleft=nodeList.get(0);

Noderight=nodeList.get(1);

//2、将他们的权值相加构成一个新的节点并作为他们的父节点

Nodeparent=newNode(null,left.weight+right.weight);

parent.left=left;

parent.right=right;

//3、删除已经处理过的节点

nodeList.remove(left);

nodeList.remove(right);

//4、将新的节点存入集合中

nodeList.add(parent);

//5、重新给集合排序,循环这5步即可，直到集合中只有一个节点，这就是huffman树的根节点

Collections.sort(nodeList);

//观察测试输出

//System.out.println(nodeList);

//返回huffman树的根节点

returnnodeList.get(0);

}

4、根据创建的赫夫曼树进行字符串编码压缩:

/**

*根据huffman树来进行数据编码压缩

*思路:

*1、只要向左子树走就代表0，向右子树走就代表1

*2、从头节点走到对于字符在的节点位置的路径对于的0和1组成的二进制编码就是压缩后该字符对于的编码

*3、需要定义一个StringBuffer来存储某个节点的路径对于的编码

*4、将赫夫曼编码表存放在MapByte,String中

*@paramnodehuffman树的根节点

*@paramstringBuffer用于拼接路径

*@paramcode路径：左子节点是0，右子节点是1

*@return

privatestaticvoidgetHuffmanCompressionCode(Nodenode,Stringcode,StringBufferstringBuffer){

StringBufferstringBuffer1=newStringBuffer(stringBuffer);

stringBuffer1.append(code);

//如果为空，不进行处理

if(node!=null){

//判断node是叶子节点还是非叶子节点

if(node.data==null){

//非叶子节点

//向左递归

getHuffmanCompressionCode(node.left,"0",stringBuffer1);

//向右递归

getHuffmanCompressionCode(node.right,"1",stringBuffer1);

}else{

//叶子节点

//说明这条路走到尾了，将路径编码存入map中

huffmanCodes.put(node.data,stringBuffer1.toString());

}

5、得到压缩后的赫夫曼编码长度(二进制位数):

/**

*@return得到压缩后的赫夫曼编码大小

publicstaticintgetStrCodeSize(){

intsize=0;

//将两个map集合都转为set集合

SetMap.EntryCharacter,IntegermapSet=map.entrySet();

SetMap.EntryByte,StringhuffmanMapSet=huffmanCodes.entrySet();

//循环两个set集合

for(Map.EntryCharacter,Integerset1:mapSet){

for(Map.EntryByte,Stringset2:huffmanMapSet){

//如果两个set的key相同就将他们的value相乘,只是需要注意存储huffman编码中的是字符串，需要乘字符串的长度

if((byte)set1.getKey().charValue()==set2.getKey()){

size=size+set1.getValue()*(set2.getValue().length());

//节约时间，之间退出内循环。因为不可能有一对多的关系。

break;

returnsize;

}

6、编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]

/**

*编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]

*@parambytes这时原始的字符串对应的byte[]

*@paramhuffmanCodes生成的赫夫曼编码map

*@return返回赫夫曼编码处理后的byte[]

*举例：Stringcontent="ilikelikelikejavadoyoulikeajava";=》byte[]contentBytes=content.getBytes();

*返回的是字符串:

*"1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000

*101111111100110001001010011011100"

*=对应的byte[]huffmanCodeBytes，即8位对应一个byte,放入到huffmanCodeBytes

*huffmanCodeBytes[0]=10101000(补码)=byte[推导10101000=10101000-1=10100111(反

*码)=11011000(源码)=-88]

publicstaticbyte[]zip(byte[]bytes,MapByte,StringhuffmanCodes){

//1、先利用赫夫曼编码表将传进来的bytes数组转为压缩后的编码

StringBufferstringBuffer1=newStringBuffer();

for(byteb:bytes){

stringBuffer1.append(huffmanCodes.get(b));

//输出字符串压缩成赫夫曼编码后对应的二进制编码

//System.out.println("输出字符串压缩成赫夫曼编码后对应的二进制编码:"+stringBuffer1+"长度为:"+stringBuffer1.length());

//获取byte数组的长度，Math.ceil()表示向上取整

intlen=(int)Math.ceil(stringBuffer1.length()*1.0/8);

//也可以用下面的方法获取长度

/*if(stringBuffer1.length()%8==0){

len=stringBuffer1.length()/8;

}else{

len=stringBuffer1.length()/8+1;

//测试

//System.out.println(stringBuffer1.length());

//System.out.println(len);

byte[]huffmanBytes=newbyte[len];

intindex=0;

for(inti=0;istringBuffer1.length();i=i+8){

StringstrByte;

if(i+8stringBuffer1.length()){

//从i取到字符串最后一个字符

strByte=stringBuffer1.substring(i);

}else{

//一次截取8个

strByte=stringBuffer1.substring(i,i+8);

//将strByte转成一个byte,放入到huffmanBytes中

//该方法是将strByte对应的01字符串传换为十进制

//第二个参数表示基数（radix）,表示转换为radix进制

huffmanBytes[index]=(byte)Integer.parseInt(strByte,2);

index++;

returnhuffmanBytes;

}

其实也可以不用写5中的方法，可以直接在6中输出stringBuffer1.length()就可以得到压缩后的二进制位数。不过也可以把5当作一种解决的算法。

以下给出完整的代码:

importjava.util.*;

*实现huffman编码

publicclassHuffmanCode{

//将赫夫曼编码表存放在MapByte,String中

publicstaticMapByte,StringhuffmanCodes=newHashMap();

//需要定义一个StringBuffer来存储某个节点的路径对于的编码

publicstaticStringBufferstringBuffer=newStringBuffer();

//创建一个map，来保存每个字符以及他对应出现的次数

publicstaticMapCharacter,Integermap=newHashMap();

publicstaticvoidmain(String[]args){

Scannerscanner=newScanner(System.in);

System.out.println("输入字符串:");

//scanner.next()方法不能输入空格，例如输入:aaabbb实际上只能接收到aaa,空格后面的字符串都接收不到

//所以需要用scanner,nextLine()方法来接收字符串

Stringstr=scanner.nextLine();

//把输入的字符串转为byte数组，在byte数组中存储的是字符对应的ASCII码值

byte[]strBytes=str.getBytes();

System.out.println(str+",压缩成赫夫曼编码前对应的byte数组:"+Arrays.toString(strBytes));

//计算压缩前的字符串有多少位二进制数

intcompressionBeforeCodeSize=str.length()*8+str.length()-1;

System.out.println(str+",压缩前的字符串大小:"+compressionBeforeCodeSize);

//统计字符串中每个字符出现的次数和空格出现次数并存入Node节点中

ListNodenodeList=totalCharCounts(str);

//创建huffman树

Noderoot=createHuffmanTree(nodeList);

//得到压缩后的编码

getHuffmanCompressionCode(root,"",stringBuffer);

//输出赫夫曼编码表

System.out.println(str+",对应的赫夫曼编码表:");

System.out.println(huffmanCodes);

//得到压缩后的字符串大小

intcompressionAfterCodeSize=getStrCodeSize();

System.out.println(str+",压缩后的字符串大小:"+compressionAfterCodeSize);

//可以算出压缩率是多少

doublecompressionRadio=(compressionBeforeCodeSize-compressionAfterCodeSize)*1.0/compressionBeforeCodeSize;

System.out.println(str+",压缩成赫夫曼编码的压缩率为:"+compressionRadio);

byte[]bytes=zip(strBytes,huffmanCodes);

System.out.println(str+",压缩成赫夫曼编码后对应的byte数组:"+Arrays.toString(bytes));

*@return得到压缩后的赫夫曼编码大小

publicstaticintgetStrCodeSize(){

intsize=0;

//将两个map集合都转为set集合

SetMap.EntryCharacter,IntegermapSet=map.entrySet();

SetMap.EntryByte,StringhuffmanMapSet=huffmanCodes.entrySet();

//循环两个set集合

for(Map.EntryCharacter,Integerset1:mapSet){

for(Map.EntryByte,Stringset2:huffmanMapSet){

//如果两个set的key相同就将他们的value相乘,只是需要注意存储huffman编码中的是字符串，需要乘字符串的长度

if((byte)set1.getKey().charValue()==set2.getKey()){

size=size+set1.getValue()*(set2.getValue().length());

//节约时间，之间退出内循环。因为不可能有一对多的关系。

break;

returnsize;

*根据huffman树来进行数据编码压缩

*思路:

*1、只要向左子树走就代表0，向右子树走就代表1

*2、从头节点走到对于字符在的节点位置的路径对于的0和1组成的二进制编码就是压缩后该字符对于的编码

*3、需要定义一个StringBuffer来存储某个节点的路径对于的编码

*4、将赫夫曼编码表存放在MapByte,String中

*@paramnodehuffman树的根节点

*@paramstringBuffer用于拼接路径

*@paramcode路径：左子节点是0，右子节点是1

*@return

privatestaticvoidgetHuffmanCompressionCode(Nodenode,Stringcode,StringBufferstringBuffer){

StringBufferstringBuffer1=newStringBuffer(stringBuffer);

stringBuffer1.append(code);

//如果为空，不进行处理

if(node!=null){

//判断node是叶子节点还是非叶子节点

if(node.data==null){

//非叶子节点

//向左递归

getHuffmanCompressionCode(node.left,"0",stringBuffer1);

//向右递归

getHuffmanCompressionCode(node.right,"1",stringBuffer1);

}else{

//叶子节点

//说明这条路走到尾了，将路径编码存入map中

huffmanCodes.put(node.data,stringBuffer1.toString());

*//统计字符串中每个字符出现的次数和空格出现次数

*@paramstr字符串

*@return返回一个排好序的Node集合

publicstaticListNodetotalCharCounts(Stringstr){

for(inti=0;istr.length();i++){

charch=str.charAt(i);

Integercount=map.get(ch);

if(count==null){

count=0;

map.put(ch,count+1);

//遍历map，将map中的数据存入Node节点中

//先将map转为set集合

SetMap.EntryCharacter,IntegermapSet=map.entrySet();

//观察测试输出

//System.out.println(mapSet);

ListNodenodeList=newArrayList();

//遍历set

for(Map.EntryCharacter,Integerset:mapSet){

//将map中的数据存入Node节点中

Nodenode=newNode((byte)set.getKey().charValue(),set.getValue());

//将node存入集合中

nodeList.add(node);

//System.out.println(set.getKey()+"="+set.getValue());

//排序

Collections.sort(nodeList);

//测试

//System.out.println(nodeList);

returnnodeList;

*创建huffman树

*@paramnodeList排好序的集合

*@return返回huffman树的根节点

publicstaticNodecreateHuffmanTree(ListNodenodeList){

//循环创建huffman树

while(nodeList.size()1){

//1、每次取出集合中的前两个节点

Nodeleft=nodeList.get(0);

Noderight=nodeList.get(1);

//2、将他们的权值相加构成一个新的节点并作为他们的父节点

Nodeparent=newNode(null,left.weight+right.weight);

parent.left=left;

parent.right=right;

//3、删除已经处理过的节点

nodeList.remove(left);

nodeList.remove(right);

//4、将新的节点存入集合中

nodeList.add(parent);

//5、重新给集合排序,循环这5步即可，直到集合中只有一个节点，这就是huffman树的根节点

Collections.sort(nodeList);

//观察测试输出

//System.out.println(nodeList);

//返回huffman树的根节点

returnnodeList.get(0);

*编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]

*@parambytes这时原始的字符串对应的byte[]

*@paramhuffmanCodes生成的赫夫曼编码map

*@return返回赫夫曼编码处理后的byte[]

*举例：Stringcontent="ilikelikelikejavadoyoulikeajava";=》byte[]contentBytes=content.getBytes();

*返回的是字符串:

*"1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000

*101111111100110001001010011011100"

*=对应的byte[]huffmanCodeBytes，即8位对应一个byte,放入到huffmanCodeBytes

*huffmanCodeBytes[0]=10101000(补码)=byte[推导10101000=10101000-1=1