目录
代码实现
完整代码
运行效果
测试Test
运行效果
赫夫曼字节数组封装
实现代码
字节转二进制字符串
代码实现
赫夫曼编码字节数组 代码实现
//编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表, //返回一个赫夫曼编码压缩后的byte[] private static byte[] zip(byte[] bytes,MaphuffmanCodes) { //1.利用huffmanCodes将bytes转成赫夫曼编码对应的字符串 StringBuilder stringBuilder=new StringBuilder(); //遍历bytes数组 for (byte b:bytes) { stringBuilder.append(huffmanCodes.get(b)); } //System.out.println("测试stringBuilder="+stringBuilder.toString()); //将"1010100010111111110..."转成byte[] //统计返回byte[] huffmanCodeBytes长度 int len; if (stringBuilder.length()%8==0) { len=stringBuilder.length()/8; }else { len=stringBuilder.length()/8+1; } //创建存储压缩后的byte数组 byte[] huffmanCodeBytes=new byte[len]; int index=0; for (int i = 0; i < stringBuilder.length(); i+=8) { String strByte; if (i+8>stringBuilder.length()) {//不够8位 strByte=stringBuilder.substring(i); }else { strByte=stringBuilder.substring(i,i+8); } //将strByte转成一个byte,放入到huffmanCodeBytes huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2); index++; } return huffmanCodeBytes; }
//测试 byte[] huffmanCodeBytes=zip(contentBytes, huffmanCodes); System.out.println("huffmanCodeBytes="+huffmanCodeBytes); //发送huffmanCodeBytes数组完整代码
package huffmancode; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; public class HuffmanCode { public static void main(String[] args) { String content="I like like like java do you like a java"; byte[] contentBytes=content.getBytes(); System.out.println(contentBytes.length);//40 List运行效果 测试Testnodes=getNodes(contentBytes); System.out.println("nodes"+nodes); //测试一把,创建的二叉树 System.out.println("赫夫曼树"); Node huffmanTreeRoot=createHuffmanTree(nodes); System.out.println("前序遍历"); huffmanTreeRoot.preOrder(); //测试一把是否生成了对应的赫夫编码 Map huffmanCodes=getCodes(huffmanTreeRoot); System.out.println("生成的赫夫曼编码表"+huffmanCodes); //测试 byte[] huffmanCodeBytes=zip(contentBytes, huffmanCodes); System.out.println("huffmanCodeBytes="+huffmanCodeBytes); //发送huffmanCodeBytes数组 } //编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码压缩后的byte[] private static byte[] zip(byte[] bytes,Map huffmanCodes) { //1.利用huffmanCodes将bytes转成赫夫曼编码对应的字符串 StringBuilder stringBuilder=new StringBuilder(); //遍历bytes数组 for (byte b:bytes) { stringBuilder.append(huffmanCodes.get(b)); } //System.out.println("测试stringBuilder="+stringBuilder.toString()); //将"1010100010111111110..."转成byte[] //统计返回byte[] huffmanCodeBytes长度 int len; if (stringBuilder.length()%8==0) { len=stringBuilder.length()/8; }else { len=stringBuilder.length()/8+1; } //创建存储压缩后的byte数组 byte[] huffmanCodeBytes=new byte[len]; int index=0; for (int i = 0; i < stringBuilder.length(); i+=8) { String strByte; if (i+8>stringBuilder.length()) {//不够8位 strByte=stringBuilder.substring(i); }else { strByte=stringBuilder.substring(i,i+8); } //将strByte转成一个byte,放入到huffmanCodeBytes huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2); index++; } return huffmanCodeBytes; } //生成赫夫曼树对应的赫夫曼编码 //思路: //1.将赫夫曼编码存放在Map 形式 //32->01 97->100 100->11000等等[形式] static Map huffmanCodes=new HashMap (); //2.在生成赫夫曼编码表示中,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径 static StringBuilder stringBuilder=new StringBuilder(); //为了调用方便,我们重载getCodes private static Map getCodes(Node root){ if (root==null) { return null; } //处理root的左子树 getCodes(root.left,"0",stringBuilder); //处理root的右子树 getCodes(root.right,"1",stringBuilder); return huffmanCodes; } private static void getCodes(Node node,String code,StringBuilder stringBuilder) { StringBuilder stringBuilder2=new StringBuilder(stringBuilder); //将code加入到stringBuilder2 stringBuilder2.append(code); if (node!=null) {//如果node==null不处理 //判断当前node是叶子节点还是非叶子结点 if (node.data==null) {//非叶子结点 //递归处理 //向右递归 getCodes(node.left,"0", stringBuilder2); //向右递归 getCodes(node.right, "1", stringBuilder2); }else {//说明是一个叶子节点 //就表示找到某个叶子结点的最后 huffmanCodes.put(node.data,stringBuilder2.toString()); } } } //前序遍历的方法 private static void preOrder(Node root) { if(root!=null) { root.preOrder(); }else { System.out.println("赫夫曼树为空"); } } private static List getNodes(byte[] bytes){ //创建一个ArrayList ArrayList nodes=new ArrayList (); //遍历bytes,统计每一个byte出现的次数->map[key,value] Map counts=new HashMap<>(); for (byte b:bytes) { Integer count=counts.get(b); if (count==null) {//Map还没有这个字符数据,第一次 counts.put(b,1); }else { counts.put(b,count+1); } } //把每一个键值对转成一个Node对象,并加入到nodes集合 //遍历map for (Map.Entry entry:counts.entrySet()) { nodes.add(new Node(entry.getKey(),entry.getValue())); } return nodes; } //可以通过List创建对应的赫夫曼树 private static Node createHuffmanTree(List nodes) { while (nodes.size()>1) { //排序,从小到大 Collections.sort(nodes); //取出第一颗最小的二叉树 Node leftNode=nodes.get(0); //取出第二颗最小的二叉树 Node rightNode=nodes.get(1); //创建一颗新的二叉树,它的根结点没有data,只有权值 Node parent=new Node(null,leftNode.weight+rightNode.weight); parent.left=leftNode; parent.right=rightNode; //将已经处理的两棵二叉树从nodes删除 nodes.remove(leftNode); nodes.remove(rightNode); //将新的二叉树,加入到nodes nodes.add(parent); } //nodes最后的结点,就是赫夫曼树的根结点 return nodes.get(0); } } //创建Node,待数据和权值 class Node implements Comparable { Byte data;//存放数据(字符)本身,比如'a'=>97 ''=>32 int weight;//权值,表示字符出现的次数 Node left; Node right; public Node(Byte data,int weight) { this.data=data; this.weight=weight; } @Override public int compareTo(Node o) { //从小到大排序 return this.weight-o.weight; } 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 tree; public class Test { @SuppressWarnings("unused") public static void main(String[] args) { String strByte="10101000"; System.out.println((byte)Integer.parseInt(strByte,2));//-88 } }运行效果 赫夫曼字节数组封装 实现代码
//分布过程 Listnodes=getNodes(contentBytes); System.out.println("nodes"+nodes); //测试一把,创建的二叉树 System.out.println("赫夫曼树"); Node huffmanTreeRoot=createHuffmanTree(nodes); System.out.println("前序遍历"); huffmanTreeRoot.preOrder(); //测试一把是否生成了对应的赫夫编码 Map huffmanCodes=getCodes(huffmanTreeRoot); System.out.println("生成的赫夫曼编码表"+huffmanCodes); //测试 byte[] huffmanCodeBytes=zip(contentBytes, huffmanCodes); System.out.println("huffmanCodeBytes="+huffmanCodeBytes); //发送huffmanCodeBytes数组
//使用一个方法,将前面的方法封装起来,便于我们的调用 private static byte[] huffmanZip(byte[] bytes) { List字节转二进制字符串nodes=getNodes(bytes); //根据nodes创建的赫夫曼树 Node huffmanTreeRoot=createHuffmanTree(nodes); //对应的赫夫曼编码(根据赫夫曼树) Map huffmanCodes=getCodes(huffmanTreeRoot); //根据生成的赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组 byte[] huffmanCodeBytes=zip(bytes, huffmanCodes); return huffmanCodeBytes; }
数据解压(使用赫夫曼编码解码)
使用赫夫曼编码来解码数据,具体要求是
1)前面我们得到了赫夫曼编码和对应的编码byte[]
2)现在要求使用赫夫曼编码,进行解码,又重新得到原来的字符串"
I like like like java do you like a java"
思路:解码过程,就是编码的一个逆向 *** 作
代码实现package huffmancode; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; public class HuffmanCode { public static void main(String[] args) { String content="i like like like java do you like a java"; byte[] contentBytes=content.getBytes(); System.out.println(contentBytes.length);//40 byte[] huffmanCodesBytes=huffmanZip(contentBytes); System.out.println("压缩后的结果是:"+Arrays.toString(huffmanCodesBytes)+"长度="+huffmanCodesBytes.length); //测试一把byteToBitString方法 //System.out.println("压缩后的结果是:"+Arrays.toString(huffmanCodesBytes)+"长度="+huffmanCodesBytes.length); byte[] sourceBytes=decode(huffmanCodes, huffmanCodesBytes); System.out.println("原来的字符串="+new String(sourceBytes)); //如何将数据进行解压(解码) //分布过程 } //完成数据的解压 //思路 //1.将huffmanCodeBytes[] //重写先转成赫夫曼编码对应的二进制的字符串 //2.赫夫曼编码对应的二进制的字符串=>对照赫夫曼编码=>I like like like java do you like a java //编写一个方法,完成对压缩数据的解码 private static byte[] decode(MaphuffmanCodes,byte[] huffmanBytes) { //1.先得到huffmanBytes对应的二进制的字符串,形式 StringBuilder stringBuilder=new StringBuilder(); //将byte数组转成二进制的字符串 for (int i = 0; i < huffmanBytes.length; i++) { byte b=huffmanBytes[i]; //判断是不是最后一个字节 boolean flag=(i==huffmanBytes.length-1); stringBuilder.append(byteToBitString(!flag, b)); } // System.out.println("赫夫曼字节数组对应的二进制字符串="+stringBuilder.toString()); // return null; //把字符串安装指定的赫夫曼编码进行解码 //把赫夫曼编码表进行调换,因为反向查询a->100 100->a Map map=new HashMap (); for (Map.Entry entry:huffmanCodes.entrySet()) { map.put(entry.getValue(),entry.getKey()); } //创建要给集合,存放byte List list=new ArrayList (); //i可以理解成就是索引,扫描stringBuilder for (int i = 0; i < huffmanBytes.length; i++) { int count=1; boolean flag=true; Byte b=null; while (flag) { //取出一个'1''0' String key=stringBuilder.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中存放了所有的字符 //把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 String byteToBitString(boolean flag,byte b) { //使用变量保存b int temp=b;//将b转成int //如果是正数我们还存在补高位 temp|=256;//temp 1=>000 String str=Integer.toBinaryString(temp);//返回的是temp对应的二进制的补码 if (flag) { return str.substring(str.length()-8); }else { return str; } } //使用一个方法,将前面的方法封装起来,便于我们的调用 private static byte[] huffmanZip(byte[] bytes) { List nodes=getNodes(bytes); //根据nodes创建的赫夫曼树 Node huffmanTreeRoot=createHuffmanTree(nodes); //对应的赫夫曼编码(根据赫夫曼树) Map huffmanCodes=getCodes(huffmanTreeRoot); //根据生成的赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组 byte[] huffmanCodeBytes=zip(bytes, huffmanCodes); return huffmanCodeBytes; } //编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码压缩后的byte[] private static byte[] zip(byte[] bytes,Map huffmanCodes) { //1.利用huffmanCodes将bytes转成赫夫曼编码对应的字符串 StringBuilder stringBuilder=new StringBuilder(); //遍历bytes数组 for (byte b:bytes) { stringBuilder.append(huffmanCodes.get(b)); } //System.out.println("测试stringBuilder="+stringBuilder.toString()); //将"1010100010111111110..."转成byte[] //统计返回byte[] huffmanCodeBytes长度 int len; if (stringBuilder.length()%8==0) { len=stringBuilder.length()/8; }else { len=stringBuilder.length()/8+1; } //创建存储压缩后的byte数组 byte[] huffmanCodeBytes=new byte[len]; int index=0; for (int i = 0; i < stringBuilder.length(); i+=8) { String strByte; if (i+8>stringBuilder.length()) {//不够8位 strByte=stringBuilder.substring(i); }else { strByte=stringBuilder.substring(i,i+8); } //将strByte转成一个byte,放入到huffmanCodeBytes huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2); index++; } return huffmanCodeBytes; } //生成赫夫曼树对应的赫夫曼编码 //思路: //1.将赫夫曼编码存放在Map 形式 //32->01 97->100 100->11000等等[形式] static Map huffmanCodes=new HashMap (); //2.在生成赫夫曼编码表示中,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径 static StringBuilder stringBuilder=new StringBuilder(); //为了调用方便,我们重载getCodes private static Map getCodes(Node root){ if (root==null) { return null; } //处理root的左子树 getCodes(root.left,"0",stringBuilder); //处理root的右子树 getCodes(root.right,"1",stringBuilder); return huffmanCodes; } private static void getCodes(Node node,String code,StringBuilder stringBuilder) { StringBuilder stringBuilder2=new StringBuilder(stringBuilder); //将code加入到stringBuilder2 stringBuilder2.append(code); if (node!=null) {//如果node==null不处理 //判断当前node是叶子节点还是非叶子结点 if (node.data==null) {//非叶子结点 //递归处理 //向右递归 getCodes(node.left,"0", stringBuilder2); //向右递归 getCodes(node.right, "1", stringBuilder2); }else {//说明是一个叶子节点 //就表示找到某个叶子结点的最后 huffmanCodes.put(node.data,stringBuilder2.toString()); } } } //前序遍历的方法 private static void preOrder(Node root) { if(root!=null) { root.preOrder(); }else { System.out.println("赫夫曼树为空"); } } private static List getNodes(byte[] bytes){ //创建一个ArrayList ArrayList nodes=new ArrayList (); //遍历bytes,统计每一个byte出现的次数->map[key,value] Map counts=new HashMap<>(); for (byte b:bytes) { Integer count=counts.get(b); if (count==null) {//Map还没有这个字符数据,第一次 counts.put(b,1); }else { counts.put(b,count+1); } } //把每一个键值对转成一个Node对象,并加入到nodes集合 //遍历map for (Map.Entry entry:counts.entrySet()) { nodes.add(new Node(entry.getKey(),entry.getValue())); } return nodes; } //可以通过List创建对应的赫夫曼树 private static Node createHuffmanTree(List nodes) { while (nodes.size()>1) { //排序,从小到大 Collections.sort(nodes); //取出第一颗最小的二叉树 Node leftNode=nodes.get(0); //取出第二颗最小的二叉树 Node rightNode=nodes.get(1); //创建一颗新的二叉树,它的根结点没有data,只有权值 Node parent=new Node(null,leftNode.weight+rightNode.weight); parent.left=leftNode; parent.right=rightNode; //将已经处理的两棵二叉树从nodes删除 nodes.remove(leftNode); nodes.remove(rightNode); //将新的二叉树,加入到nodes nodes.add(parent); } //nodes最后的结点,就是赫夫曼树的根结点 return nodes.get(0); } } //创建Node,待数据和权值 class Node implements Comparable { Byte data;//存放数据(字符)本身,比如'a'=>97 ''=>32 int weight;//权值,表示字符出现的次数 Node left; Node right; public Node(Byte data,int weight) { this.data=data; this.weight=weight; } @Override public int compareTo(Node o) { //从小到大排序 return this.weight-o.weight; } 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(); } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)