package com.qyx; import java.lang.reflect.Array; import java.util.*; /** * 赫夫曼编码 */ public class HuffmanCode { public static void main(java.lang.String[] args) { java.lang.String str="i like java forever"; byte[] bytes=str.getBytes(); byte[] bys=huffmanZip(bytes); System.out.println(Arrays.toString(bys)); byte[] bytes1=decode(huffmanCodes,bys); System.out.println(new String(bytes1)); } private static List<Node> getNodes(byte[] bytes) { //1 创建ArrayList ArrayList<Node> list=new ArrayList<Node>(); //遍历bytes,统计存储每个byte出现的次数->map Map<Byte,Integer> counts=new HashMap<Byte, Integer>(); for(byte b:bytes) { Integer count=counts.get(b); if (count==null) { counts.put(b,1); }else { counts.put(b, ++count); } } //把每个键值对转化成一个Node对象，并放入到nodes集合中 for (Map.Entry<Byte,Integer> entry:counts.entrySet()) { list.add(new Node(entry.getKey(),entry.getValue())); } return list; } //通过List创建对应的哈夫曼树 private static Node createHuffManTree(List<Node> list) { while (list.size()>1) { //排序,从小到大，根据我们实现的compareTo方法来决定的 Collections.sort(list); Node leftNode=list.get(0); Node rightNode=list.get(1); //新的根节点没有data，只有权值 Node parent=new Node(null,leftNode.weight+rightNode.weight); parent.left=leftNode; parent.right=rightNode; //将已经处理的两颗二叉树从list移除 list.remove(leftNode); list.remove(rightNode); list.add(parent); } return list.get(0); } //生成哈夫曼树对应的哈夫曼编码表 /** * 思路: * 1 将赫夫曼编码表存放在Map<Byte,String>中 * 2 在生成赫夫曼编码表示，需要去拼接路径，定义一个StringBuilder * 存储某个叶子节点的路径 * @param */ private static Map<Byte,String> huffmanCodes=new HashMap<Byte, String>(); private static StringBuilder builder=new StringBuilder(); /** * 功能:将传入的node结点的所有叶子节点的赫夫曼编码得到，并放入到huffmanCode的集合中 * @param node 传入节点 * @param code 路径：左子节点是0，右子节点是1 * @param builder 用于拼接路径 */ private static void getCodes(Node node,String code,StringBuilder builder) { StringBuilder builder1=new StringBuilder(builder); //将code加入到builder1 builder1.append(code); if (node!=null) { //判断当前node是叶子节点还是非叶子节点 if(node.data==null) { //非叶子节点,则需要递归 //向左递归 getCodes(node.left,"0",builder1); //向右递归 getCodes(node.right,"1",builder1); }else{ //说明是一个叶子节点 huffmanCodes.put(node.data,builder1.toString()); } } } //为了调用方便，重载getCodes private static Map<Byte,String> getCodes(Node root) { if (root==null) { return null; } //处理root的左子树 getCodes(root.left,"0",builder); //处理root的右子树 getCodes(root.right,"1",builder); return huffmanCodes; } //编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[] /** * * @param bytes 这是原始的字符串生成byte数组 * @param huffmanCodes 这是字符对应的赫夫曼编码的map * @return 返回赫夫曼编码处理后的字符数组 */ private static byte[] zip(byte[] bytes,Map<Byte,String>huffmanCodes) { //1 利用huffmanCodes将bytes转成转成赫夫曼编码对应的字符串 StringBuilder stringBuilder=new StringBuilder(); //遍历bytes数组 for(byte b:bytes) { stringBuilder.append(huffmanCodes.get(b)); } //System.out.println("测试stringBuilder="+stringBuilder.toString()); //将赫夫曼字符串转成byte[] int len; if (stringBuilder.length()%8==0) { len=stringBuilder.length()/8; }else { len=stringBuilder.length()/8+1; } //创建 存储压缩后的byte数组 byte[] by=new byte[len]; int index=0;//记录是第几个byte for (int i=0;i<stringBuilder.length();i+=8) { //因为是每8位对应一个byte，所有步长+8 String strByte; if (i+8>stringBuilder.length()) { //不够8位 strByte=stringBuilder.substring(i,stringBuilder.length()); }else { strByte = stringBuilder.substring(i, i + 8); } //将strByte转成byte数组，放入到by by[index]= (byte) Integer.parseInt(strByte,2); index++; } return by; } //使用一个方法，将前面的方法封装起来，便于调用 /** * * @param bytes 原始的字符串对应的字节数组 * @return 经历赫夫曼编码处理的字节数组 */ private static byte[] huffmanZip(byte[] bytes) { List<Node> nodes=getNodes(bytes); //创建赫夫曼树 Node root=createHuffManTree(nodes); //生成对应的赫夫曼编码(根据赫夫曼树) Map<Byte,String> huffmanCodes=getCodes(root); //根据赫夫曼编码对原始的数组进行压缩 byte[] huffmanCodeBytes=zip(bytes,huffmanCodes); return huffmanCodeBytes; } /** * @param flag 是否需要补位 * @param b 需要转换的byte * @return 二进制后的补码 */ private static String byteToBitString(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 huffmanCodes 赫夫曼编码表 map * @param bytes 赫夫曼编码得到的字节数组 * @return 返回的就是原来字符串对应的数组 */ private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] bytes) { //1 先得到赫夫曼编码对应的二进制的字符串,刑如1010100010111... StringBuilder builder=new StringBuilder(); //将Byte数组转成二进制的字符串 for (int i=0;i<bytes.length;i++) { //首先需要判断是否是最后一个字节 boolean flag=(i==bytes.length); byte b=bytes[i]; builder.append(byteToBitString(!flag,b)); } //把字符串按照指定的赫夫曼编码进行解码 //把赫夫曼编码表进行交换，因为反向查询 Map<String,Byte> map=new HashMap<String,Byte>(); for (Map.Entry<Byte,String> entry:huffmanCodes.entrySet()) { map.put(entry.getValue(),entry.getKey()); } //创建一个集合，存放Byte List<Byte> list=new ArrayList<Byte>(); System.out.println(builder.length()); //i 可以理解成就是索引，扫描stringbuilder for (int i=0;i<builder.length();) { int count=1; boolean flag=true; Byte b=null; while (flag) { String key=builder.substring(i,i+count);//i不动，让count移动，指定匹配一个字符 b=map.get(key); if (b==null) { //说明没有匹配到 count++; }else{ //匹配到 flag=false; } } list.add(b); i+=count;//让i 直接移动到count的位置 } //当for循环结束后，我们list中就存放了所有的字符"i like java,forever" //把list中的数据放入byte[]数组并返回 byte[] b=new byte[list.size()]; for (int i=0;i<b.length;i++) { b[i]=list.get(i); } return b; } //前序遍历 private static void preOrder(Node root) { if (root!=null) { root.preOrder(); }else{ System.out.println("哈夫曼树为空"); } } } class Node implements Comparable<Node>{ Byte data;//存放数据 a=97 int weight;//权值，字符出现次数 Node left; Node right; public Node(Byte data, int weight) { this.data = data; this.weight = weight; } @Override public int compareTo(Node node) { return this.weight-node.weight; } //重新toString @Override public String toString() { return "Node{" + "data=" + data + ", weight=" + weight + '}'; } //前序遍历 public void preOrder(){ System.out.println(this); if(this.left!=null) { this.left.preOrder();; } if(this.right!=null) { this.right.preOrder(); } } }
赫夫曼树及赫夫曼编码原理请见我的另一篇文章
package com.qyx;
import java.lang.reflect.Array;
import java.util.*;
/**
* 赫夫曼编码
*/
public class HuffmanCode {
public static void main(java.lang.String[] args)
{
java.lang.String str="i like java forever";
byte[] bytes=str.getBytes();
byte[] bys=huffmanZip(bytes);
System.out.println(Arrays.toString(bys));
byte[] bytes1=decode(huffmanCodes,bys);
System.out.println(new String(bytes1));
}
private static List<Node> getNodes(byte[] bytes)
{
//1 创建ArrayList
ArrayList<Node> list=new ArrayList<Node>();
//遍历bytes,统计存储每个byte出现的次数->map
Map<Byte,Integer> counts=new HashMap<Byte, Integer>();
for(byte b:bytes)
{
Integer count=counts.get(b);
if (count==null)
{
counts.put(b,1);
}else {
counts.put(b, count + 1);
}
}
//把每个键值对转化成一个Node对象，并放入到nodes集合中
for (Map.Entry<Byte,Integer> entry:counts.entrySet())
{
list.add(new Node(entry.getKey(),entry.getValue()));
}
return list;
}
//通过List创建对应的哈夫曼树
private static Node createHuffManTree(List<Node> list)
{
while (list.size()>1)
{
//排序,从小到大，根据我们实现的compareTo方法来决定的
Collections.sort(list);
Node leftNode=list.get(0);
Node rightNode=list.get(1);
//新的根节点没有data，只有权值
Node parent=new Node(null,leftNode.weight+rightNode.weight);
parent.left=leftNode;
parent.right=rightNode;
//将已经处理的两颗二叉树从list移除
list.remove(leftNode);
list.remove(rightNode);
list.add(parent);
}
return list.get(0);
}
//生成哈夫曼树对应的哈夫曼编码表
/**
* 思路:
* 1 将赫夫曼编码表存放在Map<Byte,String>中
* 2 在生成赫夫曼编码表示，需要去拼接路径，定义一个StringBuilder
* 存储某个叶子节点的路径
* @param
*/
private static Map<Byte,String> huffmanCodes=new HashMap<Byte, String>();
private static StringBuilder builder=new StringBuilder();
/**
* 功能:将传入的node结点的所有叶子节点的赫夫曼编码得到，并放入到huffmanCode的集合中
* @param node 传入节点
* @param code 路径：左子节点是0，右子节点是1
* @param builder 用于拼接路径
*/
private static void getCodes(Node node,String code,StringBuilder builder)
{
StringBuilder builder1=new StringBuilder(builder);
//将code加入到builder1
builder1.append(code);
if (node!=null)
{
//判断当前node是叶子节点还是非叶子节点
if(node.data==null)
{
//非叶子节点,则需要递归
//向左递归
getCodes(node.left,"0",builder1);
//向右递归
getCodes(node.right,"1",builder1);
}else{
//说明是一个叶子节点
huffmanCodes.put(node.data,builder1.toString());
}
}
}
//为了调用方便，重载getCodes
private static Map<Byte,String> getCodes(Node root)
{
if (root==null)
{
return null;
}
//处理root的左子树
getCodes(root.left,"0",builder);
//处理root的右子树
getCodes(root.right,"1",builder);
return huffmanCodes;
}
//编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
/**
*
* @param bytes 这是原始的字符串生成byte数组
* @param huffmanCodes 这是字符对应的赫夫曼编码的map
* @return 返回赫夫曼编码处理后的字符数组
*/
private static byte[] zip(byte[] bytes,Map<Byte,String>huffmanCodes)
{
//1 利用huffmanCodes将bytes转成转成赫夫曼编码对应的字符串
StringBuilder stringBuilder=new StringBuilder();
//遍历bytes数组
for(byte b:bytes)
{
stringBuilder.append(huffmanCodes.get(b));
}
//System.out.println("测试stringBuilder="+stringBuilder.toString());
//将赫夫曼字符串转成byte[]
int len;
if (stringBuilder.length()%8==0)
{
len=stringBuilder.length()/8;
}else {
len=stringBuilder.length()/8+1;
}
//创建 存储压缩后的byte数组
byte[] by=new byte[len];
int index=0;//记录是第几个byte
for (int i=0;i<stringBuilder.length();i+=8)
{
//因为是每8位对应一个byte，所有步长+8
String strByte;
if (i+8>stringBuilder.length())
{
//不够8位
strByte=stringBuilder.substring(i);
}else {
strByte = stringBuilder.substring(i, i + 8);
}
//将strByte转成byte数组，放入到by
by[index]= (byte) Integer.parseInt(strByte,2);
index++;
}
return by;
}
//使用一个方法，将前面的方法封装起来，便于调用
/**
*
* @param bytes 原始的字符串对应的字节数组
* @return 经历赫夫曼编码处理的字节数组
*/
private static byte[] huffmanZip(byte[] bytes)
{
List<Node> nodes=getNodes(bytes);
//创建赫夫曼树
Node root=createHuffManTree(nodes);
//生成对应的赫夫曼编码(根据赫夫曼树)
Map<Byte,String> huffmanCodes=getCodes(root);
//根据赫夫曼编码对原始的数组进行压缩
byte[] huffmanCodeBytes=zip(bytes,huffmanCodes);
return huffmanCodeBytes;
}
/**
* @param flag 是否需要补位
* @param b 需要转换的byte
* @return 二进制后的补码
*/
private static String byteToBitString(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 huffmanCodes 赫夫曼编码表 map
* @param bytes 赫夫曼编码得到的字节数组
* @return 返回的就是原来字符串对应的数组
*/
private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] bytes)
{
//1 先得到赫夫曼编码对应的二进制的字符串,刑如1010100010111...
StringBuilder builder=new StringBuilder();
//将Byte数组转成二进制的字符串
for (int i=0;i<bytes.length;i++)
{
//首先需要判断是否是最后一个字节
boolean flag=(i==bytes.length);
byte b=bytes[i];
builder.append(byteToBitString(!flag,b));
}
//把字符串按照指定的赫夫曼编码进行解码
//把赫夫曼编码表进行交换，因为反向查询
Map<String,Byte> map=new HashMap<String,Byte>();
for (Map.Entry<Byte,String> entry:huffmanCodes.entrySet())
{
map.put(entry.getValue(),entry.getKey());
}
//创建一个集合，存放Byte
List<Byte> list=new ArrayList<Byte>();
System.out.println(builder.length());
//i 可以理解成就是索引，扫描stringbuilder
for (int i=0;i<builder.length();)
{
int count=1;
boolean flag=true;
Byte b=null;
while (flag) {
String key=builder.substring(i,i+count);//i不动，让count移动，指定匹配一个字符
b=map.get(key);
if (b==null)
{
//说明没有匹配到
count++;
}else{
//匹配到
flag=false;
}
}
list.add(b);
i+=count;//让i 直接移动到count的位置
}
//当for循环结束后，我们list中就存放了所有的字符"i like java,forever"
//把list中的数据放入byte[]数组并返回
byte[] b=new byte[list.size()];
for (int i=0;i<b.length;i++)
{
b[i]=list.get(i);
}
return b;
}
//前序遍历
private static void preOrder(Node root)
{
if (root!=null)
{
root.preOrder();
}else{
System.out.println("哈夫曼树为空");
}
}
}
class Node implements Comparable<Node>{
Byte data;//存放数据 a=97
int weight;//权值，字符出现次数
Node left;
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node node) {
return this.weight-node.weight;
}
//重新toString
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
//前序遍历
public void preOrder(){
System.out.println(this);
if(this.left!=null)
{
this.left.preOrder();;
}
if(this.right!=null)
{
this.right.preOrder();
}
}
}